Other Versions
Table of Contents

http://www.cplusplus.happycodings.com/Algorithms/code5.html

void BinarySearchTree::remove(int d)
{
    //Locate the element
    bool found = false;
 
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
 
    //first we do look up
    curr = root;
    while(curr != NULL)
    {
         if(curr->data == d)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(d > curr->data) 
                         curr = curr->right;
             else 
                         curr = curr->left;
         }
    }
 
   if(!found)
   {
        cout<<" Data not found! "<<endl;
        return;
    }
 
    // There are 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children
 
    //We're looking at a leaf node, just assign parent's left or right=NULL, delete node
    if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) 
                parent->left = NULL;
        else 
                parent->right = NULL;
        delete curr;
        return;
    }
 
    // Node with single child,  just assign parent's left or right= node's single child, delete node
    if((curr->left == NULL && curr->right != NULL) || 
       (curr->left != NULL  && curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else // left child present, no right child
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
        return;
    }
 
    //Node with 2 children, replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
 
        //if the node's right child has a left child
        // Move all the way down left to locate smallest element
 
        if(chkr ->left != NULL)
        {
                tree_node* lcurr;
                tree_node* lcurrp;
 
                lcurr = chkr ->left; 
                lcurrp = chkr ;
 
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }
 
        curr->data = lcurr->data;
        lcurrp->left = lcurr->right; 
 
                delete lcurr;
 
        }
        else
        {
              //swap curr data with right node, and assign right's right child.
 
               curr->data = chkr ->data;
           curr->right = chkr ->right;
 
               delete chkr;
        }
    return;
    }
 
}

http://en.wikipedia.org/wiki/Binary_search_tree#Deletion

def spliceOut(self,parent):
    if (! self.leftChild && ! self.rightChild):
        if self == parent.leftChild:
            parent.leftChild = None
        else:
            parent.rightChild = None

        return self;

    elif ( (self.leftChild && ! self.rightChild) || (!self.leftChild && self.rightChild) )
        if self.leftChild:
            if self == parent.leftChild:
                parent.leftChild = self.leftChild
            else:
                parent.rightChild = self.leftChild
        else:
            if self == parent.leftChild:
                parent.leftChild = self.rightChild
            else:
                parent.rightChild = self.rightChild

         return self;

    else :
           not doable;

def binary_tree_delete(self, key):
    if self.key == key:
           if(self has only one child)
                   self.spliceOut()
                   delete self 

/*        if (! self.leftChild && ! self.rightChild):
            if self == self.parent.leftChild:
                self.parent.leftChild = None
            else:
                self.parent.rightChild = None

            delete self

        elif  ( (self.leftChild && ! self.rightChild) || (!self.leftChild && self.rightChild) )
            if self.leftChild:
                if self == parent.leftChild:
                    parent.leftChild = self.leftChild
                else:
                    parent.rightChild = self.leftChild
            else:
                if self == parent.leftChild:
                    parent.leftChild = self.rightChild
                else:
                    parent.rightChild = self.rightchild

             delete self
*/
        else:
            succ = self.findSuccessor()
            succ.spliceOut()

            self.data = succ.data
            delete succ;
/*
    or
            succ.leftChild = self.leftChild
            succ.rightChild = self.rightChild

            if self == parent.leftChild:
                parent.leftChild = succ
            else:
                parent.rightChild = succ

            delete self
*/
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License