Reputation: 131
I'm trying to implement a Binary Search Tree and I have a problem with node removal. I did some tests and I think the only problem with my function is the case in which the node to be removed has two children. I seem to have messed up somewhere in the references. It seems to be a simple problem, but I've been trying to fix it by myself for too long
struct node
{
int val;
struct node *l;
struct node *r;
}*Head=NULL;
void del_x(struct node *&k,int x)
{
struct node *tmp,*tmp2,*rem;
if (k==NULL) return;
if (x > k->val) {if(k->r==NULL)return;else del_x(k->r,x);}
if (x < k->val) {if(k->l==NULL)return;else del_x(k->l,x);}
if (x == k->val)
{
tmp=k;
if (k->l==NULL && k->r==NULL) {tmp=k->l;k=tmp;delete tmp;return;}//no children
else if (k->l==NULL) {tmp=k->r;k=tmp;return;}//one child on the left
else if (k->r==NULL) {tmp=k->l;k=tmp;return;}//one child on the right
else //two children <-I think the problem lies in this else
{
rem=k;
tmp=k->r; //go to right subtree
while(tmp->l!=NULL) {tmp2=tmp;tmp=tmp->l;} //search minimum
tmp2->l=NULL;
k=tmp;
rem->val=tmp->val;
k=rem;
return;
}
}
}
Upvotes: 1
Views: 347
Reputation: 73627
There are several problems.
First, whatever the case if you reach the x==k->val
condition and it's true, you'll always need to delete the node currently pointed by k.
if (x == k->val)
{
tmp=k; // keep track of the node to delete
... // update k but don't return (and don't change tmp)
delete tmp; // get rid of the deleted node for good
}
Then the item has no child at all, you just need to set the pointer in the parent to nullptr. If the iem has one child, you just do a pass-trhough.
if (k->l==nullptr && k->r==nullptr)
k=nullptr;
else if (k->l==nullptr)
k=k->r;
else if (k->r==nullptr)
k=k->l;
else { //two children
...
}
If the node has to children, it's more tricky
else { //two children
k=k->l; // take the left subtree
for (rem=k; rem->r!=nullptr; rem=rem->r)
; // find the end of its right subtree
rem->r = tmp->r; // append the right subtree at its end.
}
Here the graphical explanation of what happens here:
Upvotes: 1