Connecting Tech Pros Worldwide Help | Site Map
bytes > topic > c > answers

Binary Search Tree Set

Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#1: Sep 25 '07
OK, first of all, thanks to everyone who helped me out with my Isomorphism problem - it finally works. Now, the other part of my homework I'm having trouble with is this:

Quote:

Originally Posted by My Homework

Write an implementation of the set class, with associated iterators using a binary search tree. Add to each node a link to the parent node.

I don't want to post the whole code here - it's about 140 lines, and it would violate our homework policy.

Basically, it looks like my remove method is faulty; I'll include the struct definition, the class definition, and my two remove method definitions:
Expand|Select|Wrap|Line Numbers
  1. template <typename T>
  2. struct TreeNode {
  3.     T data;
  4.     TreeNode *left, *right, *parent;
  5.     ~TreeNode() {
  6.         delete left;
  7.         delete right;
  8.         parent = 0;
  9.     }
  10. };
  11.  
  12. template <typename T>
  13. class BSTreeSet {
  14.     /*friend ostream& operator<<(ostream& out, const BSTreeSet<T> BST) {
  15.         BST.inorderPrint(out);
  16.         return out;
  17.     }*/
  18.  
  19.     public:
  20.         BSTreeSet();
  21.         BSTreeSet(T initRoot);
  22.         ~BSTreeSet() { delete root; }
  23.         bool insert(T obj);
  24.         void remove(T obj);
  25.         bool contains(T obj);
  26.         bool isEmpty() const { return root == NULL; };
  27.         void inorderPrint(ostream& out);
  28.  
  29.     private:
  30.         bool insertHelper(TreeNode<T> *node, T obj);
  31.         void removeHelper(TreeNode<T> *node, T obj);
  32.         bool containsHelper(TreeNode<T> *node, T obj);
  33.         void IOPrint(TreeNode<T> *node, ostream& out);
  34.         TreeNode<T> *root;
  35. };
  36.  
  37. template <typename T>
  38. void BSTreeSet<T>::remove(T obj) {
  39.     return removeHelper(root, obj);
  40. }
  41.  
  42. template <typename T>
  43. void BSTreeSet<T>::removeHelper(TreeNode<T> *node, T obj) {
  44.     if (node == NULL) return;
  45.     if (node->data < obj) removeHelper(node->right, obj);
  46.     else if (node->data > obj) removeHelper(node->left, obj);
  47.     else if (node->left != NULL && node->right != NULL) {
  48.         TreeNode<T> *temp = node->right;
  49.         while (temp->left != NULL) temp = temp->left;
  50.         node->data = temp->data;
  51.         removeHelper(temp, temp->data);
  52.     } else {
  53.         TreeNode<T> *old = node;
  54.         node = (node->left != NULL) ? node->left : node->right;
  55.         delete old;
  56.     }
  57. }
My test program generates a tree at random and displays its contents (all of which seems to be properly functioning). I then intentionally insert the value 20, to test my contains() method and my remove() method. It looks like contains() works, but I get:

Quote:

Originally Posted by My Cygwin Shell

Aborted (core dumped)

at that point in the program. Any ideas?
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#2: Sep 25 '07

re: Binary Search Tree Set

Sure enough, when I stop using the .remove method in my driver program, everything works just fine.

I also have not yet bothered adding the iterators - that'll be tomorrows fun project.
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#3: Sep 25 '07

re: Binary Search Tree Set

UPDATE:

So I missed the & several places in the book's code. After adding these in the appropriate places to insert, contains, and remove, every thing's working as expected. :\

I'd still like to keep this thread alive, as I'll probably need a hand implementing the iterator.
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#4: Sep 26 '07

re: Binary Search Tree Set

OK, I've thought of the algorithm for ++ and -- on my iterator (which was the main problem in this assignment), but I'm having trouble actually inserting the iterator (and const_iterator) into my BSTreeSet class. Here's the class definitions:

Expand|Select|Wrap|Line Numbers
  1. class const_iterator {
  2.    public:
  3.       const_iterator() : current(NULL) { }
  4.       const T & operator*() const { return retrieve(); }
  5.  
  6.       const_iterator& operator++() {
  7.          // Code removed to follow Guidelines
  8.       }
  9.  
  10.       const_iterator operator++(int) {
  11.          const_iterator old = *this;
  12.          ++(*this);
  13.          return old;
  14.       }
  15.  
  16.       const_iterator& operator--() {
  17.          // Code removed to follow Guidelines
  18.       }
  19.  
  20.       const_iterator operator--(int) {
  21.          const_iterator old = *this;
  22.          --(*this);
  23.          return old;
  24.       }
  25.  
  26.       bool operator==(const const_iterator & rhs) const {
  27.          return current = rhs.current;
  28.       }
  29.  
  30.       bool operator!=(const const_iterator & rhs) const {
  31.          return !(*this == rhs);
  32.       }
  33.  
  34.    protected:
  35.       TreeNode<T> *current;
  36.       T & retrieve() const {
  37.          return current->data;
  38.       }
  39.       const_iterator(TreeNode<T> *t) : current(t) { }
  40.       friend class BSTreeSet<T>;
  41. };
  42.  
  43. class iterator : public const_iterator {
  44.    public:
  45.       iterator() { }
  46.  
  47.       T& operator*() { return retrieve(); }
  48.       const T& operator*() const { return const_iterator::operator*(); }
  49.  
  50.       iterator& operator++() {
  51.          // Code removed to follow Guidelines
  52.       }
  53.  
  54.       iterator operator++(int) {
  55.          iterator old = *this;
  56.          ++(*this);
  57.          return old;
  58.       }
  59.  
  60.       iterator& operator--() {
  61.          // Code removed to follow Guidelines
  62.       }
  63.  
  64.       iterator operator--(int) {
  65.          iterator old = *this;
  66.          --(*this);
  67.          return old;
  68.       }
  69.  
  70.    protected:
  71.       iterator(TreeNode<T> *t) : const_iterator(t) { }
  72.       friend class BSTreeSet<T>;
  73. };
Now, most of this code is modified code from the Linked List class shown earlier in my book. Basically, the errors I'm getting are saying that the iterator class cannot see current, despite the fact that iterator is a subclass of const_iterator, and that current is protected in const_iterator. The verbose error list is:

Quote:

Originally Posted by My Cygwin Shell

$ g++ BSTSTest.cpp -o BSTest.exe
In file included from BSTSTest.cpp:2:
BSTree.h: In member function `T& BSTreeSet<T>::iterator::operator*()':
BSTree.h:93: error: there are no arguments to `retrieve' that depend on a templa
te parameter, so a declaration of `retrieve' must be available
BSTree.h:93: error: (if you use `-fpermissive', G++ will accept your code, but a
llowing the use of an undeclared name is deprecated)
BSTree.h: In member function `BSTreeSet<T>::iterator& BSTreeSet<T>::iterator::op
erator++()':
BSTree.h:97: error: `current' undeclared (first use this function)
BSTree.h:97: error: (Each undeclared identifier is reported only once for each f
unction it appears in.)
BSTree.h: In member function `BSTreeSet<T>::iterator& BSTreeSet<T>::iterator::op
erator--()':
BSTree.h:120: error: `current' undeclared (first use this function)
BSTSTest.cpp: In function `int main()':
BSTree.h:23: error: `class BSTreeSet<int>::const_iterator' is private
BSTSTest.cpp:25: error: within this context
BSTree.h: In member function `bool BSTreeSet<T>::const_iterator::operator==(cons
t BSTreeSet<T>::const_iterator&) const [with T = int]':
BSTree.h:77: instantiated from `bool BSTreeSet<T>::const_iterator::operator!=(
const BSTreeSet<T>::const_iterator&) const [with T = int]'
BSTSTest.cpp:25: instantiated from here
BSTree.h:73: error: assignment of data-member `BSTreeSet<int>::const_iterator::c
urrent' in read-only structure
BSTree.h: In member function `BSTreeSet<T>::const_iterator& BSTreeSet<T>::const_
iterator::operator++() [with T = int]':
BSTree.h:47: instantiated from `BSTreeSet<T>::const_iterator BSTreeSet<T>::con
st_iterator::operator++(int) [with T = int]'
BSTSTest.cpp:25: instantiated from here
BSTree.h:30: error: cannot call member function `TreeNode<T>* BSTreeSet<T>::find
Min(TreeNode<T>*) const [with T = int]' without object

BTW: Banfa, if you read this, this was the same problem I was having waaaaay back in my very first thread on Trees, back in October, which we never figured out.
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#5: Sep 26 '07

re: Binary Search Tree Set

Shouldn't these classes be template classes?

Savage
ilikepython's Avatar
Expert
  
Join Date: Feb 2007
Posts: 839
#6: Sep 26 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Savage

Shouldn't these classes be template classes?

Savage

Yea, you use T sometimes but I don't see a template. Also, in your == operator you put a single equal sign instead of a double one.
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#7: Sep 26 '07

re: Binary Search Tree Set

UPDATE:

OK. I've fixed all the errors so far, gotten iterators working, gotten .begin() and .end() to work, and I've successfully tested the ++ operators using a for...loop:

Expand|Select|Wrap|Line Numbers
  1. for (itr = BSTS.begin(); itr != BSTS.end(); itr++)
  2.    cout << *itr << " ";
I have yet to test .find(), .erase(), and .insert() using the iterators. So far, I have been using Tree-style inserts and erases, so the iterator style functions may give me trouble.

Again, thank you ALL for your help.
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#8: Sep 26 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

UPDATE:

OK. I've fixed all the errors so far, gotten iterators working, gotten .begin() and .end() to work, and I've successfully tested the ++ operators using a for...loop:

Expand|Select|Wrap|Line Numbers
  1. for (itr = BSTS.begin(); itr != BSTS.end(); itr++)
  2.    cout << *itr << " ";
I have yet to test .find(), .erase(), and .insert() using the iterators. So far, I have been using Tree-style inserts and erases, so the iterator style functions may give me trouble.

Again, thank you ALL for your help.

If you get stuck feel free to post.Someone will(probably) give you a hand.

Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#9: Sep 26 '07

re: Binary Search Tree Set

OK. Here's where I'm at:

Iterators are working OK. I'm required to write the following functions:

Expand|Select|Wrap|Line Numbers
  1. iterator find(T obj); // returns an iterator pointing to the node containing obj
  2. iterator erase(iterator pos); // erases the node pointed to by pos, and returns an iterator pointing to the node before pos.
  3. iterator erase(iterator from, iterator to); // erases the nodes between from and to, and returns an iterator pointing to the node before from.
  4. pair<iterator, bool> insert(T obj); // Insert obj into the set.  The pair returned includes the iterator pointing to the node now containing obj and true if the insertion was successful, or the node already containing obj and false if the insertion failed.
  5. pair<iterator, bool> insert(iterator hint, T obj); // Insert obj into the set.  The return value is identical to the one-parameter insert above.  The hint argument supposedly indicates the node to which obj should be added (i.e. the parent of the new node).  If this hint is bad, the one-parameter insert is called.
I'm pretty sure find() is working, so I won't bother including that. However, the inserts and erases are throwing segfault errors and core dumps all over the place. Here are the definitions of these functions, and a few others that are also used:


Expand|Select|Wrap|Line Numbers
  1. //*******************************************************************************
  2. // The following methods are INSIDE the BSTreeSet class definition
  3. //*******************************************************************************
  4. iterator erase (iterator pos) {
  5.    iterator* ret = new iterator(pos);
  6.    (*ret)++; // NOTE: I realize this advances the iterator forward, rather than backwards, but I'll be able to fix this by reversing the logic of ++.
  7.    cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
  8.    erase(*pos);
  9.    return (*ret);
  10. }
  11.  
  12. iterator erase (iterator from, iterator to) {
  13.    iterator *ret = new iterator(to);
  14.    (*ret)++; // NOTE: I realize this advances the iterator forward, rather than backwards, but I'll be able to fix this by reversing the logic of ++.
  15.    while (from != to) {
  16.       T temp = *from;
  17.       from++;
  18.       erase(temp);
  19.    }
  20.    erase(*to);
  21.    return (*ret);
  22. }
  23.  
  24. //*******************************************************************************
  25. // The following methods are OUTSIDE the BSTreeSet class definition
  26. //*******************************************************************************
  27.  
  28. template <typename T>
  29. void BSTreeSet<T>::erase(T obj) {
  30.     removeHelper(root, obj);
  31. }
  32.  
  33. template <typename T>
  34. void BSTreeSet<T>::removeHelper(TreeNode<T> * & node, T obj) {
  35.     if (node == NULL) return;
  36.     if (node->data < obj) removeHelper(node->right, obj);
  37.     else if (node->data > obj) removeHelper(node->left, obj);
  38.     else if (node->left != NULL && node->right != NULL) {
  39.         TreeNode<T> *temp = node->right;
  40.         while (temp->left != NULL) temp = temp->left;
  41.         node->data = temp->data;
  42.         removeHelper(temp, node->data);
  43.     } else {
  44.         TreeNode<T> *old = node;
  45.         node = (node->left != NULL) ? node->left : node->right;
  46.         node->parent = old->parent;
  47.         delete old;
  48.     }
  49. }
Phew...that's a lot of code. Anyway, I'm fairly sure the problem has to do with my removeHelper. In order to support the iterator's ++, I've added a TreeNode<T> *parent link to each TreeNode. The removeHelper method was written before this parent link was added, and there may be some logic missing in creating parent links, though as you can see (at line 46 here) I've added in at least one case of the parent link changing. I'm going to see what I can do with that while I wait for a response.

As always, THANK YOU SO MUCH for any advice/help.
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#10: Sep 26 '07

re: Binary Search Tree Set

Let's start with this:


Expand|Select|Wrap|Line Numbers
  1. iterator erase (iterator pos) {
  2.  
  3.    iterator* ret = new iterator(pos);
  4.  
  5.    (*ret)++; // NOTE: I realize this advances the iterator forward, rather than backwards, but I'll be able to fix this by reversing the logic of ++.
  6.  
  7.    cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
  8.    erase(*pos);
  9.  
  10.    return (*ret);
  11.  
  12. }
You are returning a pointer which points to function local dynamically allocated iterator.Allocated memory is on heap(and it's never freed as I can see),but pointer is on stack.Function ends,local stack variables are deallocated,and as a result you got yourself my personal favorite,damn, cursed, bloody seg error.

You need to find a way around this.Perhaps a pointer to a iterator as a function argument or new member of the BSTreeSet class.



Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#11: Sep 26 '07

re: Binary Search Tree Set

Unfortunately, I cannot change the function header - it must return an iterator, and the argument must be an iterator. I had thought dynamically allocation the iterator would mean that it would not be destroyed, so that when I return the dereferenced pointer, that copy would be returned. The pointer (res) is indeed de-allocated, but the object I created shouldn't be. Maybe I can access the return value as:

Expand|Select|Wrap|Line Numbers
  1. BSTreeSet<int>::iterator itr = &BSTS.erase(pos);
but in order for this to work, the function itself has to work :\.
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#12: Sep 26 '07

re: Binary Search Tree Set

EDIT: After further research, I found that the erase functions have to return an iterator pointing to the node AFTER the deletions, so the ++ is correct in the above code.
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#13: Sep 26 '07

re: Binary Search Tree Set

OK, for Savage's suggestion:

I looked up the erase methods for the list class, provided in my book:

Expand|Select|Wrap|Line Numbers
  1. iterator erase(iterator itr) {
  2.    Node *p = itr.current;
  3.    iterator retVal(p->next);
  4.    /* List-style deletion here... */
  5.    delete p;
  6.    size--;
  7.  
  8.    return retVal;
  9. }
  10.  
  11. iterator erase(iterator start, iterator end) {
  12.    for (interator itr = from; itr != to; )
  13.       itr = erase(itr);
  14.  
  15.    return to;
  16. }
The main point is that the top function is returning retVal, which is a local object. This code is PROVIDED BY THE BOOK, which means it should probably work. Also, I didn't realize that the node pointed to by to in the second erase was not to be deleted. So I've changed the erase functions to this:

Expand|Select|Wrap|Line Numbers
  1. iterator erase (iterator pos) {
  2.    iterator ret(pos);
  3.    ret++;
  4.    //cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
  5.    erase(*pos);
  6.    return ret;
  7. }
  8.  
  9. iterator erase(iterator from, iterator to) {
  10.    for (interator itr = from; itr != to; )
  11.       itr = erase(itr);
  12.  
  13.    return to;
  14. }
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#14: Sep 26 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

Unfortunately, I cannot change the function header - it must return an iterator, and the argument must be an iterator. I had thought dynamically allocation the iterator would mean that it would not be destroyed, so that when I return the dereferenced pointer, that copy would be returned. The pointer (res) is indeed de-allocated, but the object I created shouldn't be. Maybe I can access the return value as:

Expand|Select|Wrap|Line Numbers
  1. BSTreeSet<int>::iterator itr = &BSTS.erase(pos);
but in order for this to work, the function itself has to work :\.

I'm not sure about that.

Object is not destroyed,but without a pointer that has pointed to it you cannot access it.

I'm suprised that your compiler didn't gaved you a warning,something like:

Temporary allocated variable returned from function.

I know when I make such mistake on bc32 or VC,it throws this warning.

Have you tried adding a iterator member to BSTreeSet class?

Savage
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#15: Sep 26 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

OK, for Savage's suggestion:

I looked up the erase methods for the list class, provided in my book:

Expand|Select|Wrap|Line Numbers
  1. iterator erase(iterator itr) {
  2.    Node *p = itr.current;
  3.    iterator retVal(p->next);
  4.    /* List-style deletion here... */
  5.    delete p;
  6.    size--;
  7.  
  8.    return retVal;
  9. }
  10.  
  11. iterator erase(iterator start, iterator end) {
  12.    for (interator itr = from; itr != to; )
  13.       itr = erase(itr);
  14.  
  15.    return to;
  16. }
The main point is that the top function is returning retVal, which is a local object. This code is PROVIDED BY THE BOOK, which means it should probably work. Also, I didn't realize that the node pointed to by to in the second erase was not to be deleted. So I've changed the erase functions to this:

Expand|Select|Wrap|Line Numbers
  1. iterator erase (iterator pos) {
  2.    iterator ret(pos);
  3.    ret++;
  4.    //cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
  5.    erase(*pos);
  6.    return ret;
  7. }
  8.  
  9. iterator erase(iterator from, iterator to) {
  10.    for (interator itr = from; itr != to; )
  11.       itr = erase(itr);
  12.  
  13.    return to;
  14. }

It can return local variable,but not one allocated on the heap.(without a seg offcourse)

Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#16: Sep 26 '07

re: Binary Search Tree Set

I'm not sure there should be any need to add an iterator member to the tree...what would it be used for? Basically, I'm modeling the set off the list provided in the book (because they're both STL-style), and there's no need for an iterator member in List.
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#17: Sep 26 '07

re: Binary Search Tree Set

UPDATE: It looks like insert is actually working correctly. I'm going to go back and get rid of any code I have for inserts, because I'm getting a sickly feeling that I'm stretching the homework guidelines to their limits.
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#18: Sep 26 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

I'm not sure there should be any need to add an iterator member to the tree...what would it be used for? Basically, I'm modeling the set off the list provided in the book (because they're both STL-style), and there's no need for an iterator member in List.

Does erase works now?

I thought to follow your previous erase idea.So instead of having a local temporary allocated iterator,you could have in class a pointer to a iterator which then can easily be manipulated without segs,but if erase now works then it has no use.

Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#19: Sep 26 '07

re: Binary Search Tree Set

erase still doesn't work. I'm not quite clear on how using a member of the Set class will help me in erase(iterator). What you're saying is:

1) I set this member iterator to the node after pos.
2) I delete the element at pos.
3) I return a copy of the member iterator.

Right?

I'm still pretty sure there's a problem in my actual deletion of the element...represented by the function removeHelper(TreeNode * &, T obj).
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#20: Sep 26 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

erase still doesn't work. I'm not quite clear on how using a member of the Set class will help me in erase(iterator). What you're saying is:

1) I set this member iterator to the node after pos.
2) I delete the element at pos.
3) I return a copy of the member iterator.

Right?

I'm still pretty sure there's a problem in my actual deletion of the element...represented by the function removeHelper(TreeNode * &, T obj).

Yes,something like that.

About removeHelper,you never delete temp.

Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#21: Sep 26 '07

re: Binary Search Tree Set

I assume you're talking about temp in the fourth if clause,

Expand|Select|Wrap|Line Numbers
  1. else if (node->left != NULL && node->right != NULL)
The node pointed to by temp should be deleted in the recursive call at the end of this clause:

Expand|Select|Wrap|Line Numbers
  1. removeHelper(node->right, node->data);
unless I'm mistaken.
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#22: Sep 26 '07

re: Binary Search Tree Set

I realized that, in removeHelper, once the fourth if clause fails (where we test for node being a full node (i.e. having both children)), I assumed that node had at least one child. But node could be a leaf. So I've added a clause, and it now looks like this:

Expand|Select|Wrap|Line Numbers
  1. void removeHelper(TreeNode * & node, T obj) {
  2.    if (node == NULL) return; // Value not found.
  3.    if (node->data < obj) removeHelper(node->right, obj); // Value not here; remove from right subtree.
  4.    else if (node->data > obj) removeHelper(node->left, obj); // Value not here; remove from left subtree.
  5.    else if (node->left != NULL && node->right != NULL) { // Value found!  node has 2 children.
  6.       TreeNode *temp = node->right;
  7.       while (temp->left != NULL) temp = temp->left;
  8.       node->data = temp->data;
  9.       removeHelper(node->right, node->data);
  10.    } else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) { // node has 1 child.
  11.       TreeNode *old = node;
  12.       node = (node->left != NULL) ? node->left : node->right;
  13.       node->parent = old->parent;
  14.       delete old;
  15.    } else delete node; // node is a leaf, and can be directly deleted.
  16. }
Errors were not fixed.

For the record, here's my test program and my results:

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include "BSTreeSet.h"
  3. using namespace std;
  4.  
  5. int main() {
  6.     srand((unsigned)time(NULL));
  7.     BSTreeSet<int> BSTS;
  8.     int delay;
  9.     for (int i = 0; i < 10; i++)
  10.         BSTS.insert(rand() % 100+1);
  11.  
  12.     pair<BSTreeSet<int>::iterator, bool> myPair = BSTS.insert(32);
  13.     if(myPair.second) {
  14.         cout << "32 was inserted correctly. " << *(myPair.first) << endl;
  15.     } else {
  16.         cout << "32 was NOT inserted correctly. " << *(myPair.first) << endl;
  17.     }
  18.  
  19.     BSTreeSet<int>::const_iterator itr;
  20.  
  21.     for (itr = BSTS.begin(); itr != BSTS.end(); ++itr) {
  22.         cout << *itr << " ";
  23.     }
  24.     cout << endl;
  25.  
  26.     /*BSTreeSet<int>::iterator from = BSTS.begin();
  27.     BSTreeSet<int>::iterator to = BSTS.begin();
  28.     for (int i = 0; i < 3; i++) to++;
  29.  
  30.     BSTreeSet<int>::iterator after = BSTS.erase(from, to);
  31.  
  32.     cout << *after << endl;*/
  33.  
  34.     BSTreeSet<int>::iterator test;
  35.     cout << "Which value should I search for? ";
  36.     int val;
  37.     cin >> val;
  38.  
  39.     test = BSTS.find(val);
  40.     cout << *test << endl;
  41.  
  42.     test = BSTS.erase(test);
  43.     /*cin >> val;
  44.     for (itr = BSTS.begin(); itr != BSTS.end(); ++itr) {
  45.         cout << *itr << " ";
  46.         cin >> val;
  47.     }*/
  48.  
  49.     cout << endl;
  50.  
  51.     return 0;
  52. }
Quote:

Originally Posted by My Cygwin Shell

$ g++ BSTSTest.cpp -o BSTest.exe
$ BSTest
32 was inserted correctly. 32
8 14 16 24 32 37 44 63 76 87 97
Which value should I search for? 16
16

27 [main] BSTest 460 _cygtls::handle_exceptions: Error while dumping state
(probably corrupted stack)
Segmentation fault (core dumped)
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#23: Sep 26 '07

re: Binary Search Tree Set

UPDATE: Crap, insert is not working properly, like I thought it was. The iterator it returns within the pair only points to the correct place sometimes. At other times, it was pointing 1 ahead, then 2 ahead, then at the min value...no clue. I'm going to try to work on this; in the meantime, here's the insert code again:
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#24: Sep 26 '07

re: Binary Search Tree Set

ANOTHER UPDATE:

Fixed it. I was making the iterator portion of the pair based on node rather than temp. Re-removing the method definition...

This is getting messy, eh?
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#25: Sep 26 '07

re: Binary Search Tree Set

I've narrowed the problem down to this function:

Expand|Select|Wrap|Line Numbers
  1. void removeHelper(TreeNode * & node, T obj) {
  2.    if (node == NULL) return; // Value not found.
  3.    if (node->data < obj) removeHelper(node->right, obj); // Value not here; remove from right subtree.
  4.    else if (node->data > obj) removeHelper(node->left, obj); // Value not here; remove from left subtree.
  5.    else if (node->left != NULL && node->right != NULL) { // Value found!  node has 2 children.
  6.       TreeNode *temp = node->right;
  7.       while (temp->left != NULL) temp = temp->left;
  8.       node->data = temp->data;
  9.       removeHelper(node->right, node->data);
  10.    } else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) { 
  11.       TreeNode *old = node;
  12.       node = (node->left != NULL) ? node->left : node->right;
  13.       node->parent = old->parent;
  14.       delete old;
  15.    } else delete node;
  16. }
I wrote an explicit remove function which takes a T value and calls removeHelper with root and that value. In my driver program, I ignored erase and used remove - the same error occured. That means the problem shouldn't be in erase() - it must be in removeHelper().
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#26: Sep 26 '07

re: Binary Search Tree Set

After some more testing, I think the problem is in the portions of code where the value has been found, and has either 1 child or is a leaf. The portion where a node has 2 children seems to work until the point where you need to erase the now-repeat value (which, by definition, has either 1 child or is a leaf - thus the error).

My code has become VERY messy, but here's what I'm working with right now:

Expand|Select|Wrap|Line Numbers
  1.         void removeHelper(TreeNode * & node, T obj) {
  2.             cout << "Entering removeHelper..." << endl;
  3.             if (node == NULL) { // Value not found.
  4.                 cout << "Value not found." << endl;
  5.                 return;
  6.             }
  7.             if (node->data < obj) { // Value not here; remove from right subtree.
  8.                 cout << "Moving to right subtree - currently at " << node->data << endl;
  9.                 removeHelper(node->right, obj);
  10.             }
  11.             else if (node->data > obj) { // Value not here; remove from left subtree.
  12.                 cout << "Moving to left subtree - currently at " << node->data << endl;
  13.                 removeHelper(node->left, obj);
  14.             }
  15.             else if ((node->left != NULL) && (node->right != NULL)) { // Value found!  node has 2 children.
  16.                 cout << "The value has been found, and has 2 children.  The value is " << node->data << endl;
  17.                 TreeNode *temp = node->right;
  18.                 while (temp->left != NULL) temp = temp->left;
  19.                 node->data = temp->data;
  20.                 removeHelper(node->right, node->data);
  21.             } else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) { 
  22.                 cout << "The value has been found, and only has one child.  The value is " << node->data << endl;
  23.                 TreeNode *old = node;
  24.                 if (node->left == NULL) {
  25.                     if ((old->parent)->right == node) {
  26.                         node = node->right;
  27.                         (old->parent)->right = node;
  28.                     } else {
  29.                         node = node->right;
  30.                         (old->parent)->left = node;
  31.                     }
  32.                 } else {
  33.                     if ((old->parent)->right == node) {
  34.                         node = node->left;
  35.                         (old->parent)->right = node;
  36.                     } else {
  37.                         node = node->left;
  38.                         (old->parent)->left = node;
  39.                     }
  40.                 }
  41.                 node->parent = old->parent;
  42.                 delete old;
  43.             } else {
  44.                 cout << "The value has been found, and is a leaf.  The value is " << node->data << endl;
  45.                 if ((node->parent)->left == node) {
  46.                     TreeNode *temp = node->parent;
  47.                     (node->parent)->left == NULL;
  48.                     delete temp;
  49.                 } else {
  50.                     TreeNode *temp = node->parent;
  51.                     (node->parent)->right == NULL;
  52.                     delete temp;
  53.                 }
  54.             }
  55.         }
As you can see, there's about 32487632948 cout statements so I can see exactly what's happening.
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#27: Sep 27 '07

re: Binary Search Tree Set

LOL,isn't TreeNode a template struct,I don't see T in your function call?

Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#28: Sep 27 '07

re: Binary Search Tree Set

I moved the TreeNode definition inside the BSTreeSet class definition, along with every single function, so you barely see any T's anywhere anymore. It's still compiling correctly, though.
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#29: Sep 27 '07

re: Binary Search Tree Set

Bah, I can't stand it. I took the remove function straight out of the book for Binary Search Trees, added the parent modifications, and it still segfaults on me. What the heck?

I'm about ready to give up on this - as of right now, I have 4 hours to complete this. I don't think it's happening.
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#30: Sep 27 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

Bah, I can't stand it. I took the remove function straight out of the book for Binary Search Trees, added the parent modifications, and it still segfaults on me. What the heck?

I'm about ready to give up on this - as of right now, I have 4 hours to complete this. I don't think it's happening.

I think i got it Gannon.

It's the parent variable of TreeNode.

That's what producing a seg.

Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#31: Sep 27 '07

re: Binary Search Tree Set

That's what I think, too. If I didn't have that parent link, there wouldn't be a problem with segfault errors. However, in order to implement the incrementation operators in my iterator classes, I need that parent link - it is also dictated in the book. There are other methods of incrementation, but the one I was told to implement was the one with the parent link.
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#32: Sep 27 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

That's what I think, too. If I didn't have that parent link, there wouldn't be a problem with segfault errors. However, in order to implement the incrementation operators in my iterator classes, I need that parent link - it is also dictated in the book. There are other methods of incrementation, but the one I was told to implement was the one with the parent link.

It works:(!!)

in create initialize parent to NULL,in insert I have added these lines:

Expand|Select|Wrap|Line Numbers
  1.  if ((*temp)->data < obj)
  2. {
  3.         insert(&(*temp)->right, obj);
  4.         (*temp)->right->parent=(*temp);//<------
  5.  
  6. }
  7.  
  8.  else if (obj < (*temp)->data)
  9. {
  10.  
  11.         insert(&(*temp)->left, obj);
  12.         (*temp)->left->parent=(*temp);//<------
  13. }
  14. else{
  15.         insert(&(*temp)->left, obj);
  16.         (*temp)->left->parent=(*temp);//<-----
  17. }
  18.  
And it runs without seg on VC.I sure hope it works on your compiler.

Savage
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#33: Sep 27 '07

re: Binary Search Tree Set

Does it work now?

Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#34: Sep 27 '07

re: Binary Search Tree Set

Unfortunately, no, it doesn't work for me. The homework was due today, so I turned in what I had - partial credit should be better than a 0. I did end up getting most of it working, though, so maybe I'll get a high grade anyway. We'll see.

Thanks SO MUCH for your help, Savage.
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#35: Sep 27 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

Unfortunately, no, it doesn't work for me. The homework was due today, so I turned in what I had - partial credit should be better than a 0. I did end up getting most of it working, though, so maybe I'll get a high grade anyway. We'll see.

Thanks SO MUCH for your help, Savage.

I don't understand,this should work.

Have you tried with other compilers?
Are you sure that it's still the parent variable the one producing a seg?

Perhaps,it's something else..

I hope that you will get a high mark..

It's all STL's standards fault.It's to messy. :D

Savage
Ganon11's Avatar
Moderator
  
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#36: Sep 27 '07

re: Binary Search Tree Set

Actually, the STL set uses a different traversal method, so I suspect it's not messy. I haven't tried other compilers...but we're supposed to be using g++, and that's what was throwing errors. Maybe I'll try in Visual C++ (I think my laptop has that...)
Savage's Avatar
Expert
  
Join Date: Feb 2007
Posts: 1,737
#37: Sep 28 '07

re: Binary Search Tree Set

Quote:

Originally Posted by Ganon11

Actually, the STL set uses a different traversal method, so I suspect it's not messy. I haven't tried other compilers...but we're supposed to be using g++, and that's what was throwing errors. Maybe I'll try in Visual C++ (I think my laptop has that...)

I'm just looking to blame something for this slight failure. :D

Savage
Reply

« previous question | next question »

Similar C / C++ bytes

/bytes/development

/bytes/it

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 226,295 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved