Binary Search Tree Set

[Ganon11]

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:

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:
[CODE=cpp]
template <typename T>
struct TreeNode {
T data;
TreeNode *left, *right, *parent;
~TreeNode() {
delete left;
delete right;
parent = 0;
}
};

template <typename T>
class BSTreeSet {
/*friend ostream& operator<<(ostr eam& out, const BSTreeSet<T> BST) {
BST.inorderPrin t(out);
return out;
}*/

public:
BSTreeSet();
BSTreeSet(T initRoot);
~BSTreeSet() { delete root; }
bool insert(T obj);
void remove(T obj);
bool contains(T obj);
bool isEmpty() const { return root == NULL; };
void inorderPrint(os tream& out);

private:
bool insertHelper(Tr eeNode<T> *node, T obj);
void removeHelper(Tr eeNode<T> *node, T obj);
bool containsHelper( TreeNode<T> *node, T obj);
void IOPrint(TreeNod e<T> *node, ostream& out);
TreeNode<T> *root;
};

template <typename T>
void BSTreeSet<T>::r emove(T obj) {
return removeHelper(ro ot, obj);
}

template <typename T>
void BSTreeSet<T>::r emoveHelper(Tre eNode<T> *node, T obj) {
if (node == NULL) return;
if (node->data < obj) removeHelper(no de->right, obj);
else if (node->data > obj) removeHelper(no de->left, obj);
else if (node->left != NULL && node->right != NULL) {
TreeNode<T> *temp = node->right;
while (temp->left != NULL) temp = temp->left;
node->data = temp->data;
removeHelper(te mp, temp->data);
} else {
TreeNode<T> *old = node;
node = (node->left != NULL) ? node->left : node->right;
delete old;
}
}[/CODE]

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:

Aborted (core dumped)

at that point in the program. Any ideas?

[Ganon11]

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]

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]

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:

[CODE=cpp]class const_iterator {
public:
const_iterator( ) : current(NULL) { }
const T & operator*() const { return retrieve(); }

const_iterator& operator++() {
// Code removed to follow Guidelines
}

const_iterator operator++(int) {
const_iterator old = *this;
++(*this);
return old;
}

const_iterator& operator--() {
// Code removed to follow Guidelines
}

const_iterator operator--(int) {
const_iterator old = *this;
--(*this);
return old;
}

bool operator==(cons t const_iterator & rhs) const {
return current = rhs.current;
}

bool operator!=(cons t const_iterator & rhs) const {
return !(*this == rhs);
}

protected:
TreeNode<T> *current;
T & retrieve() const {
return current->data;
}
const_iterator( TreeNode<T> *t) : current(t) { }
friend class BSTreeSet<T>;
};

class iterator : public const_iterator {
public:
iterator() { }

T& operator*() { return retrieve(); }
const T& operator*() const { return const_iterator: :operator*(); }

iterator& operator++() {
// Code removed to follow Guidelines
}

iterator operator++(int) {
iterator old = *this;
++(*this);
return old;
}

iterator& operator--() {
// Code removed to follow Guidelines
}

iterator operator--(int) {
iterator old = *this;
--(*this);
return old;
}

protected:
iterator(TreeNo de<T> *t) : const_iterator( t) { }
friend class BSTreeSet<T>;
};[/CODE]

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:

$ g++ BSTSTest.cpp -o BSTest.exe
In file included from BSTSTest.cpp:2:
BSTree.h: In member function `T& BSTreeSet<T>::i terator::operat or*()':
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>::i terator::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>::i terator::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>::c onst_iterator:: operator==(cons
t BSTreeSet<T>::c onst_iterator&) const [with T = int]':
BSTree.h:77: instantiated from `bool BSTreeSet<T>::c onst_iterator:: operator!=(
const BSTreeSet<T>::c onst_iterator&) const [with T = int]'
BSTSTest.cpp:25 : instantiated from here
BSTree.h:73: error: assignment of data-member `BSTreeSet<int> ::const_iterato r::c
urrent' in read-only structure
BSTree.h: In member function `BSTreeSet<T>:: const_iterator& BSTreeSet<T>::c onst_
iterator::opera tor++() [with T = int]':
BSTree.h:47: instantiated from `BSTreeSet<T>:: const_iterator BSTreeSet<T>::c on
st_iterator::op erator++(int) [with T = int]'
BSTSTest.cpp:25 : instantiated from here
BSTree.h:30: error: cannot call member function `TreeNode<T>* BSTreeSet<T>::f ind
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]

Shouldn't these classes be template classes?

Savage

[ilikepython]

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]

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:

[CODE=cpp]for (itr = BSTS.begin(); itr != BSTS.end(); itr++)
cout << *itr << " ";[/CODE]

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]

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:

[CODE=cpp]for (itr = BSTS.begin(); itr != BSTS.end(); itr++)
cout << *itr << " ";[/CODE]

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]

OK. Here's where I'm at:

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

[CODE=cpp]iterator find(T obj); // returns an iterator pointing to the node containing obj
iterator erase(iterator pos); // erases the node pointed to by pos, and returns an iterator pointing to the node before pos.
iterator erase(iterator from, iterator to); // erases the nodes between from and to, and returns an iterator pointing to the node before from.
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.
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.[/CODE]

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:


[CODE=cpp]//*************** *************** *************** *************** *************** ****
// The following methods are INSIDE the BSTreeSet class definition
//*************** *************** *************** *************** *************** ****
iterator erase (iterator pos) {
iterator* ret = new iterator(pos);
(*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 ++.
cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
erase(*pos);
return (*ret);
}

iterator erase (iterator from, iterator to) {
iterator *ret = new iterator(to);
(*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 ++.
while (from != to) {
T temp = *from;
from++;
erase(temp);
}
erase(*to);
return (*ret);
}

//*************** *************** *************** *************** *************** ****
// The following methods are OUTSIDE the BSTreeSet class definition
//*************** *************** *************** *************** *************** ****

template <typename T>
void BSTreeSet<T>::e rase(T obj) {
removeHelper(ro ot, obj);
}

template <typename T>
void BSTreeSet<T>::r emoveHelper(Tre eNode<T> * & node, T obj) {
if (node == NULL) return;
if (node->data < obj) removeHelper(no de->right, obj);
else if (node->data > obj) removeHelper(no de->left, obj);
else if (node->left != NULL && node->right != NULL) {
TreeNode<T> *temp = node->right;
while (temp->left != NULL) temp = temp->left;
node->data = temp->data;
removeHelper(te mp, node->data);
} else {
TreeNode<T> *old = node;
node = (node->left != NULL) ? node->left : node->right;
node->parent = old->parent;
delete old;
}
}[/CODE]

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]

Let's start with this:


[CODE="cpp"]iterator erase (iterator pos) {

iterator* ret = new iterator(pos);

(*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 ++.

cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
erase(*pos);

return (*ret);

}[/CODE]

You are returning a pointer which points to function local dynamically allocated iterator.Alloca ted 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]

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:

[CODE=cpp]BSTreeSet<int>: :iterator itr = &BSTS.erase(pos );[/CODE]

but in order for this to work, the function itself has to work :\.

[Ganon11]

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]

OK, for Savage's suggestion:

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

[CODE=cpp]iterator erase(iterator itr) {
Node *p = itr.current;
iterator retVal(p->next);
/* List-style deletion here... */
delete p;
size--;

return retVal;
}

iterator erase(iterator start, iterator end) {
for (interator itr = from; itr != to; )
itr = erase(itr);

return to;
}[/CODE]

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:

[CODE=cpp]iterator erase (iterator pos) {
iterator ret(pos);
ret++;
//cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
erase(*pos);
return ret;
}

iterator erase(iterator from, iterator to) {
for (interator itr = from; itr != to; )
itr = erase(itr);

return to;
}[/CODE]

[Savage]

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:

[CODE=cpp]BSTreeSet<int>: :iterator itr = &BSTS.erase(pos );[/CODE]

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,somethi ng 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]

OK, for Savage's suggestion:

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

[CODE=cpp]iterator erase(iterator itr) {
Node *p = itr.current;
iterator retVal(p->next);
/* List-style deletion here... */
delete p;
size--;

return retVal;
}

iterator erase(iterator start, iterator end) {
for (interator itr = from; itr != to; )
itr = erase(itr);

return to;
}[/CODE]

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:

[CODE=cpp]iterator erase (iterator pos) {
iterator ret(pos);
ret++;
//cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
erase(*pos);
return ret;
}

iterator erase(iterator from, iterator to) {
for (interator itr = from; itr != to; )
itr = erase(itr);

return to;
}[/CODE]

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

Savage