c++ delete in binary search tree

Question

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?

i said i have no problem with deletion logic.i am ok with them (one child,two child,childless) i asked why when i use this function there is no deletion. — Akın Yılmaz
– Akın Yılmaz, Commented Dec 24, 2011 at 12:57
so you say the function hasn't got any problem, but then you say it isn't working. Really, you should clear your mind up before asking questions here :) — akappa
– akappa, Commented Dec 24, 2011 at 13:34
Akın Yılmaz : "there is no deletion". in fact, deletion is correctly done ! check my answer for details — Hicham
– Hicham, Commented Dec 24, 2011 at 13:39
Post some code how you are going to use this. You probably should think about how function arguments are passed in C++. — Kerrek SB
– Kerrek SB, Commented Dec 24, 2011 at 14:24

Hicham · Accepted Answer · 2011-12-24 13:43:44Z

3

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.

edited Dec 24, 2011 at 13:43

answered Dec 24, 2011 at 13:30

Hicham

9776 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Steve Fallows · Accepted Answer · 2011-12-24 15:32:37Z

1

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.

edited Dec 24, 2011 at 15:32

answered Dec 24, 2011 at 13:05

Steve Fallows

6,4445 gold badges51 silver badges68 bronze badges

1 Comment

Akın Yılmaz Over a year ago

thanks bro but it is still not deleting even if i used delete p; p=NULL; instead of deleteandnull function.i use this deletion operations in a function deletespecified(paramaters) may it be because of this function or because of some & symbol?

rashedcs · Accepted Answer · 2016-11-01 00:54:46Z

1

   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;  
}

edited Nov 1, 2016 at 0:54

answered Oct 5, 2016 at 18:50

rashedcs

3,7632 gold badges43 silver badges44 bronze badges

3 Comments

Marcus Müller Over a year ago

please properly format your text as text and your code as code.

rashedcs Over a year ago

I already properly formatted my code. Please Focus on code not the format. If you find wrong , you will inform me.

rashedcs Over a year ago

@ Marcus Müller please check my answer.

Collectives™ on Stack Overflow

c++ delete in binary search tree

3 Answers 3

Comments

1 Comment

C++ implementation :

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

C++ implementation :

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related