CODEWITHSUNDEEP
cbinary-search-tree
angel208
angel208

Reputation: 281

Deleting a Leaf node BST

I'm trying to implement an AVL tree just for the sake of learning. I managed to make the insertion, but I'm stuck at the deletion. I have a problem deleting a leaf node (the one-child case works just fine). The problem is that when I delete the node it doesn't get erased form the BST, instead, its value just turns 0, so the tree never goes unbalanced when a node is deleted. What I'm basically doing is, if I encounter with a node with no childs, I just free it. Here is the code of the function (without the re balancing part):

node_t *Delete ( node_t *root, int num ){

   if ( !root ){
     printf ("Not Found\n");
     return root;
   }

//=======Search for the Element=============

   if ( num > root->data )
       Delete ( root->right , num );

   else if ( num < root->data )
       Delete ( root->left , num );

//======Delete element==============

   else if ( num == root->data ){

     if ( root->right && root->left ){ //two child case

         node_t *auxP = root->right;

         while ( auxP->left ) //finding the successor 
            auxP=auxP->left; 

         root->data = auxP->data; 

         root->right = Delete ( root->right, auxP->data );     
     }

     else{ //one or no child

         if ( !root->right && !root->left ){ // no childs
           free(root);       
         }
         else{ //one child
             node_t *auxP = ( root->right ?  root->right : root->left );
             *root=*auxP;
             free(auxP);
         }                
     }  

   }
  return root;
}

If i have a tree like this:

        10
       /  \
      5    15 
     / \    \
    2   6    17

and i try to delete 6, it ends like this

        10
       /  \
      5   15 
     / \    \
    2   0    17

It may be an obvious error, but I cant find it. Any explanation of why it isn't working will be greatly appreciated.

Upvotes: 1

Views: 2133

Answers (1)

Eric Z
Eric Z

Reputation: 14505

When you delete a node, you need change the according child field of its parent. But in your code, you only pass in the node-to-delete itself (node_t *root) so the parent node is left unchanged. In the single child case, you work around it by copying the single child to the node-to-delete, and remove the single child instead. But in the leaf case, you do nothing to fix the link in parent.

One way is to somehow pass the parent node in so that when the node-to-delete is a leaf, break the link from the parent and set the according child of parent to NULL.

Alternatively, you can add a parent link to the node definition so that when you delete a node, you can derive the parent link from it.

Upvotes: 1

Related Questions