CODEWITHSUNDEEP
c++pointersbinary-search-tree
vois
vois

Reputation: 131

Removing a node with two children in BST

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

Answers (1)

Christophe
Christophe

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:

enter image description here There you are !

Upvotes: 1

Related Questions