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.
-
-
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.Comment
-
Does erase works now?Originally posted by Ganon11
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.
SavageComment
-
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...repre sented by the function removeHelper(Tr eeNode * &, T obj).Comment
-
Yes,something like that.Originally posted by Ganon11
About removeHelper,yo u never delete temp.
SavageComment
-
I assume you're talking about temp in the fourth if clause,
[CODE=cpp]else if (node->left != NULL && node->right != NULL)[/CODE]
The node pointed to by temp should be deleted in the recursive call at the end of this clause:
[CODE=cpp]removeHelper(no de->right, node->data);[/CODE]
unless I'm mistaken.Comment
-
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:
[CODE=cpp]void removeHelper(Tr eeNode * & node, T obj) {
if (node == NULL) return; // Value not found.
if (node->data < obj) removeHelper(no de->right, obj); // Value not here; remove from right subtree.
else if (node->data > obj) removeHelper(no de->left, obj); // Value not here; remove from left subtree.
else if (node->left != NULL && node->right != NULL) { // Value found! node has 2 children.
TreeNode *temp = node->right;
while (temp->left != NULL) temp = temp->left;
node->data = temp->data;
removeHelper(no de->right, node->data);
} else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) { // node has 1 child.
TreeNode *old = node;
node = (node->left != NULL) ? node->left : node->right;
node->parent = old->parent;
delete old;
} else delete node; // node is a leaf, and can be directly deleted.
}[/CODE]
Errors were not fixed.
For the record, here's my test program and my results:
[CODE=cpp]#include <iostream>
#include "BSTreeSet. h"
using namespace std;
int main() {
srand((unsigned )time(NULL));
BSTreeSet<int> BSTS;
int delay;
for (int i = 0; i < 10; i++)
BSTS.insert(ran d() % 100+1);
pair<BSTreeSet< int>::iterator, bool> myPair = BSTS.insert(32) ;
if(myPair.secon d) {
cout << "32 was inserted correctly. " << *(myPair.first) << endl;
} else {
cout << "32 was NOT inserted correctly. " << *(myPair.first) << endl;
}
BSTreeSet<int>: :const_iterator itr;
for (itr = BSTS.begin(); itr != BSTS.end(); ++itr) {
cout << *itr << " ";
}
cout << endl;
/*BSTreeSet<int> ::iterator from = BSTS.begin();
BSTreeSet<int>: :iterator to = BSTS.begin();
for (int i = 0; i < 3; i++) to++;
BSTreeSet<int>: :iterator after = BSTS.erase(from , to);
cout << *after << endl;*/
BSTreeSet<int>: :iterator test;
cout << "Which value should I search for? ";
int val;
cin >> val;
test = BSTS.find(val);
cout << *test << endl;
test = BSTS.erase(test );
/*cin >> val;
for (itr = BSTS.begin(); itr != BSTS.end(); ++itr) {
cout << *itr << " ";
cin >> val;
}*/
cout << endl;
return 0;
}[/CODE]
Originally posted by My Cygwin ShellComment
-
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:Comment
-
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?Comment
-
I've narrowed the problem down to this function:
[CODE=cpp]void removeHelper(Tr eeNode * & node, T obj) {
if (node == NULL) return; // Value not found.
if (node->data < obj) removeHelper(no de->right, obj); // Value not here; remove from right subtree.
else if (node->data > obj) removeHelper(no de->left, obj); // Value not here; remove from left subtree.
else if (node->left != NULL && node->right != NULL) { // Value found! node has 2 children.
TreeNode *temp = node->right;
while (temp->left != NULL) temp = temp->left;
node->data = temp->data;
removeHelper(no de->right, node->data);
} else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) {
TreeNode *old = node;
node = (node->left != NULL) ? node->left : node->right;
node->parent = old->parent;
delete old;
} else delete node;
}[/CODE]
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().Comment
-
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:
[CODE=cpp] void removeHelper(Tr eeNode * & node, T obj) {
cout << "Entering removeHelper... " << endl;
if (node == NULL) { // Value not found.
cout << "Value not found." << endl;
return;
}
if (node->data < obj) { // Value not here; remove from right subtree.
cout << "Moving to right subtree - currently at " << node->data << endl;
removeHelper(no de->right, obj);
}
else if (node->data > obj) { // Value not here; remove from left subtree.
cout << "Moving to left subtree - currently at " << node->data << endl;
removeHelper(no de->left, obj);
}
else if ((node->left != NULL) && (node->right != NULL)) { // Value found! node has 2 children.
cout << "The value has been found, and has 2 children. The value is " << node->data << endl;
TreeNode *temp = node->right;
while (temp->left != NULL) temp = temp->left;
node->data = temp->data;
removeHelper(no de->right, node->data);
} else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) {
cout << "The value has been found, and only has one child. The value is " << node->data << endl;
TreeNode *old = node;
if (node->left == NULL) {
if ((old->parent)->right == node) {
node = node->right;
(old->parent)->right = node;
} else {
node = node->right;
(old->parent)->left = node;
}
} else {
if ((old->parent)->right == node) {
node = node->left;
(old->parent)->right = node;
} else {
node = node->left;
(old->parent)->left = node;
}
}
node->parent = old->parent;
delete old;
} else {
cout << "The value has been found, and is a leaf. The value is " << node->data << endl;
if ((node->parent)->left == node) {
TreeNode *temp = node->parent;
(node->parent)->left == NULL;
delete temp;
} else {
TreeNode *temp = node->parent;
(node->parent)->right == NULL;
delete temp;
}
}
}[/CODE]
As you can see, there's about 32487632948 cout statements so I can see exactly what's happening.Comment
-
LOL,isn't TreeNode a template struct,I don't see T in your function call?
SavageComment
-
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.Comment
-
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.Comment
-
I think i got it Gannon.Originally posted by Ganon11
It's the parent variable of TreeNode.
That's what producing a seg.
SavageComment
Comment