How to fix fringe cases in BST delete function?

Question

Assume that my delete tries to rebalance the tree inorder (left to right).

I'm writing a BinarySearchTree class currently, and my delete function currently works (I believe - I hope <3) in most cases. I have a few fringe cases to contend with:

• Deleting the root node won't work, because it has no parent.
• In the final case where next has two children, if its left most right descendant is the right child itself, then newCurr will point to next, this will cause problems as newCurr (aka next) will end up swapped with New.

Proposed solutions for root deletion:

1. My solution, which is to delete the root and use a member function of my BST class to setRoot to New (making that node the root) and then setting where New used to be to 0/NULL.

   A: This works, but I have to put case work all over the place.

2. Have a dummy parent node in the BST class that will simply have the root node as it's right hand object (suggested by billyswong).

   A: This might work, but I feel like I should have special case work to deal with it.

Proposed solution for two children deletion:

1. My solution, which is to temporarily store the location of New, set New's location in its parent to New's right child, and then delete the temporary pointer.

   A:This will work, but it is not as elegant as I think it could be.

2. "Rotate the nodes" (not sure how I would do this, suggested by Agor).

Here is my code:

if (root()->value() == val)
{
    delete root();
    this->setRoot(New);
    newCurr->setLeft(0);
}    
else if (newCurr == next)
{
    Node *temp = New;
    newCurr->setRight(New->right());
    delete temp;
}

Would posters please tell me if this code 1) works 2) is optimal.

Edit: sorry about my inconsistent use of camelcaps near the end of the function. I could not think of a better description for my variable names, but new is a defined keyword in C++.

Edit2: Posted refactored code, but the errors persist.

void BinarySearchTree::del(int val)
{
//curr refers to the parent of next
//next is the node we will want to delete
    Node* curr = 0;
    Node* next = root(); 

//these will only be used if you get into
//the last case, where you have two children
//on next
    Node* newCurr = curr;
    Node* New = next;

//boolean value to check if you found the value
//in the binary search tree
    bool found;

//set curr and next; will be false if val not found
    found = setCurrAndNext(val, curr, next);


//get next to the node needing deletion
//and set curr to its parent
//pass by ref function  
//return value is that you found it  
    if (found)
    {
        setNewCurrAndNew (newCurr, New);
    }   
    else
    { 
        return;    
    }

/* next is a leaf */

    if (nextIsLeaf(next))
    {
        handleLeafCase(curr, next);
        return;
    }   
/* next has a single child */        
    else if (nextHasSingleChild(next))       
    {
        if(leftIsChild(next))  
        {
            handleLeftCase(curr, next);
        }
        else
        {
            handleRightCase(curr, next);
        }
    }
/* next has two children */    
    else
    {  
       if (newCurr == next)
       {
            Node *temp = New;
            newCurr->setRight(New->right());
            delete temp;
       } 
       else if (next == curr->left())
       {
            if (New == newCurr->left())
            {
               curr->setLeft(New);
               newCurr->setLeft(next);
            }
            else
            {
               curr->setLeft(New);
               newCurr->setRight(next);
            }
       }
       else
       {
            if (New == newCurr->left())
            {
               curr->setRight(New);
               newCurr->setLeft(next);
            }    
            else
            {
               curr->setRight(New);
               newCurr->setRight(next);
            }
       }

       if (next->left() == 0 && next->right() == 0)
       {
            newCurr->setRight(0);
            newCurr->setLeft(0);

            delete next;
       }
       else
       {
            if (next->left() == 0)
            {
               newCurr->setRight(next->left());
            }
            else
            {
               newCurr->setLeft(next->right());
            }

               delete next;
            }
        }
    }
}

Answer 1

Deleting the root node won't work, because it has no parent

My thought on this one is, give your root a dummy parent, a node that contains no actual useful value but the root as its right child. Then every deletable nodes will all have their parents now, and root() will be able to be handled more uniformly like other nodes. Then you won't need special method(s) to remember if the tree is empty too.

Edit: How can found = setCurrAndNext(val, curr, next); set the curr and next outside? AFAIK C/C++ always pass by value. I smell something wrong in those helper functions.

Answer 2

I can't give you code or anything, but what you're looking for is a "rotate" operator. Basically, it deals with the "annoying" deletion cases -- when you delete a tree with 2 children who both have 2 children, such as the root, but also any other node in the tree.

What rotate does is basically swap children (traumatizing, I know) between the involved nodes, in a very local area, so that the ordering of children (smaller on the left, bigger on the right) is maintained. It is similiar to the "bubble up" function for priority queues.

Here is the wikipedia (http://en.wikipedia.org/wiki/Tree_rotation) page.

Hope this sets you on the right track!

Edit in response to comment: Sorry, I should have explained. When I say "tree", I mean node, and the wikipedia page should still be helpful. Due to the mathematical, recursive definition of a binary search tree, you can view each node as its own sub-tree, hence my initial statement (left unchanged). But that is only tangentially related to your question, so carry on... :)