CODEWITHSUNDEEP
c++binary-search-tree
Akın Yılmaz
Akın Yılmaz

Reputation: 296

c++ delete in binary search tree

I have a binary search tree consists of nodes like:

struct ProductNode
{
    Product data;
    ProductNode* left;
    ProductNode* right;
};

and I have a delete function that takes ProductNode pointer parameter: 

void ProductCategory::deleteandnull(ProductNode * p) 
{
    if(p!=NULL)
    {
        delete p;
        p=NULL;
    }
}

I have no problem with deletion methods. The left and right pointers are NULL when a new leaf added but when I use this function I see there is no deletion and this operation does not change the binary search tree. What is that problem?

Upvotes: 1

Views: 3455

Answers (3)

rashedcs
rashedcs

Reputation: 3723

   Procedure :
   1. At first locate the node to be deleted.

   2. If the node is a leaf node :
   i. If the node is left child of the parent , make null the left pointer of its parent node and free the space for the node.
   ii. If the node is right child of the parent , make null the right pointer of its parent node and free the space for the node.

   3. If the node has one child
    i. If the node to be deleted is a left chile of its parent , then make link between the left pointer of its parent node and the child node to be deleted. Then delete the node.
    ii.If the node to be deleted is a right child of its parent , then make link between the right pointer of its parent node and the child node to be deleted. Then delete the node.

   4. If the node to be deleted has two child :
     i. Locate the node with maximum value from the left sub-tree of  the node to be deleted.
     ii. Replace the node value to be deleted by the node found in step 4(i)

   5. Now we get updated output

C++ implementation :

    node* Delete(node *root, int data)
    {
      if(root == NULL) return root;

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

      else if (data > root->data) root->right = Delete(root->right,data);

      else
      {
       ///Case 1:  No child
      if(root->left == NULL && root->right == NULL)
      {
        delete root;
        root = NULL;
      }

      ///Case 2: One child
      else if(root->left == NULL)
      {
        struct node *temp = root;
        root= root->right;
        delete temp;
      }

      else if(root->right == NULL)
      {
        struct node *temp = root;
        root = root->left;
        delete temp;
      }

      ///case 3: 2 children
       else
       {
         node *temp = FindMin(root->right);
         root->data = temp->data;
         root->right = Delete(root->right,temp->data);
       }
     }
    return root;  
}

Upvotes: 1

Steve Fallows
Steve Fallows

Reputation: 6434

EDIT: This answer was based on the assumption that the OP was concluding "there is no deletion" because he was expecting to see a NULL pointer in the calling location. If that is not the case he will need to clarify what is leading to that conclusion. As is there is no reason to think the OP's code is not deleting whatever p points to.

p is passed by value into the deleteandnull function. Therefore only a local copy of the pointer is set to NULL. Assuming you have code like this somewhere:

ProductNode *ptr = // Somehow initialize to the parent of the node to delete
.
.
deleteandnull(ptr->left);

You need to add this after the call to deletandnull

ptr->left = NULL;

Note that it is not necessary to test for NULL before calling delete. It will do so itself. And since p in deleteandnull is a local, there is no point to setting it to NULL. So the whole code might as well be reduced to:

ProductNode *ptr = // Somehow initialize to the parent of the node to delete
.
.
delete ptr->left;
ptr->left = NULL;

All that said, in modern C++ you should not be using bare pointers, new and delete. Prefer to use smart pointers, for instance as in the Boost library.

Upvotes: 1

Hicham
Hicham

Reputation: 979

use this instead : 

void ProductCategory::deleteRightChild(ProductNode * p) 
{
    if(p->right!=NULL)
    {
        delete p->right;
        p->right = NULL;
    }
}

write an equivalent fonction for left child.

your function does not work because you dont change the content of the parent node. it still has the adress of the deleted node so (if this content was realllocated elsewhere and changed) it can access to it... !

but the memory is really deallocated.

Upvotes: 3

Related Questions