CODEWITHSUNDEEP
c++performancerecursionbinary-search-tree
user1870035
user1870035

Reputation:

Making a delete function for a binary search tree in C++

Edited*: I'm working on the delete function for a binary search tree. I'm just working on the first case right now. I think this is correct, but I'm wondering if it can be done recursively, or more efficiently. Any help is appreciated. Assume BSTSearch searches for a node, isLeaf returns true if the node is a leaf, and each node has a pointer that allows them access to their parent.

void
BinarySearchTree::BSTDelete(int x, BSTNode *node){

    BSTNode *deleteNode;
    deleteNode = BSTSearch(x,node); 

    if(isLeaf(deleteNode)){

        if(deleteNode->sortkey > (deleteNode->parent)->sortkey){
             delete (deleteNode->parent)->right;
            (deleteNode->parent)->right = NULL;
        }

        else{
            delete (deleteNode->parent)->left;
            (deleteNode->parent)->left = NULL;  
        }
    }

Upvotes: 0

Views: 4511

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55589

You don't need a pointer to the parent. Here is a recursive version that should work: (pass by reference (&), in case you don't know, allows you to modify the variable, similar to pass by pointer; BSTNode *& is a pointer passed by reference, so we can modify the value of node->left/right (pointers) (not just what they're pointing to))

void BinarySearchTree::BSTDelete(int x, BSTNode *&node)
{
   if (node == NULL)
      return;
   if (x == node->sortKey)
   {
      if (isLeaf(node))
      {
         delete node;
         node = NULL;
      }
      else
      {
         // other stuff goes here
      }
      return;
   }
   else if (x < node->sortKey)
      BSTDelete(x, node->left);
   else
      BSTDelete(x, node->right);
}

Upvotes: 2

Related Questions