-
BST node deletion help!
this is my code snippet:
Code:
void deletenodebst(bst **rootptr,bst *node) {
bst *ptr, *ptr1;
if(node->left==NULL || node->right==NULL){
ptr = node;
}else ptr = successorbst(node);
if(ptr != NULL){
if(ptr->left!=NULL){
ptr1 = ptr->left;
}
else{
ptr1 = ptr->right;
}
if(ptr->parent==NULL){
*rootptr = ptr1;
}
else{
if(ptr == ptr->parent->left){
ptr->parent->left = ptr1;
}
else{
ptr->parent->right = ptr1;
}
}
}
if(ptr!=node) node->value = ptr->value;
free(ptr);
}
"bst *node" is the node to be deleted..
my problem is that when I try to perform this sequence:
Code:
insert 6
insert 20
insert 3
insert 2
insert 10
insert 100
insert 4
delete 20
delete 6
insert 16
insert 8
delete 8
delete 3
delete 16
delete 8
delete 4
delete 2
delete 10
delete 100
a "dumping stack trace" error occurs on the delete 2 part.. help please? thanks..
-
You set parent to point at ptr1, but you never set ptr1's parent back upwards (it will point at ptr, still, which is going to go away).
-
sorry for the late reply..
are you pertaining to this part?
Code:
else{
if(ptr == ptr->parent->left){
ptr->parent->left = ptr1;
//should I insert something here...
}
else{
ptr->parent->right = ptr1;
//...or here?
}
}
can you explain it more? i'm sorry but i'm really having difficulty in getting this...
-
I don't see that it could be any clearer than what tabstop posted already, unless we posted the exact line of code required. You do understand the code you posted right?
I would not put more code in the places you've guessed as you'd then need to put it in 3 places. One line just inside the end of the large if-block to set the parent of ptr1 is what you need.
-
