Thread: Need help with mah BSTree (aka jumbled mess)

Okay, I'm finishing up my Binary Search Tree implementation that I'm doing out of boredom. The one thing that I'm having trouble on is a delete algorithm that isn't recursive. Most cases work great. When the deleted node has only one subtree (left or right), deleting a leaf, and for the most part deleting a node with two subtrees works alright. Here is my implementation. If it's too messy, tell me, I'll clean it up and repost it . But I'll hilight the problem area

Code:

template <typename T>
void BSTree<T>::Delete(T x)
{
    if (root == NULL)
    {
        std::cout << "-- Tree is empty --" << std::endl;
        return;
    }

    BinaryTreeNode<T>* prev = root;    //points to previous node
    BinaryTreeNode<T>* next = root;    //points ahead
    size_t dir = 0;                 //globally stores pointer direction

    while (true)
    {
        if(next == NULL)
        {
            std::cout << "-- " << x << " not found --" << std::endl;
            return;
        }
        else if (next->data == x)    //if the data has been found and...
        {
            //...both children are null
            if (next->child[0] == NULL && next->child[1] == NULL)
            {
                if (next == root)   //delete if data is at root
                    root = NULL;
                else
                    prev->child[dir] = NULL;

                delete next;
            }
            else if (next->child[0] == NULL)    //...the left child is null
            {
                if (next == root)
                {
                    root = next->child[1];  //point root to it's only child
                }
                else
                    prev->child[dir] = next->child[1];

                next->child[1] = NULL;
                delete next;
            }
            else if (next->child[1] == NULL)    //...the right child is null
            {
                if (next == root)
                    root = next->child[0];
                else
                    prev->child[dir] = next->child[0];

                next->child[0] = NULL;
                delete next;
            }
            else    //...neither child is null
            {
                //pointers to right subtree
                BinaryTreeNode<T>* prevR = next->child[1];
                BinaryTreeNode<T>* nextR = prevR;

                //find the smallest node in right subtree and replace
                while (true)
                {
                    if (nextR->child[0] == NULL)
                    {
                        //Connect smallest node's parent
                        //with smallest node's right child
                        //will be null if no right child exists
                        prevR->child[0] = nextR->child[1];

                        //replace node
                        next->data = nextR->data;

                        //if the rightmost node has no children
                        //set next's right child to NULL
                        if (prevR == nextR && nextR->child[1] == NULL)
                            next->child[1] = NULL;
                        else
                            next->child[1] = nextR->child[1];

                        //nullify node's children array
                        nextR->child[0] = nextR->child[1] = NULL;
                        delete nextR;
                        break;
                    }
                    else
                    {
                        prevR = nextR;
                        nextR = nextR->child[0];
                    }
                }
            }

            std::cout << "-- " << x << " has been deleted --" << std::endl;
            return;
        }
        else
        {
            prev = next;
            dir = x < next->data ? 0 : 1;
            next = next->child[dir];
        }
    }
}

If my tree/subtree is in the form

------O
-----/-\
----O---O

nd I need to delete the root of that tree, I have a problem with the getting the root of that tree to have their right child nulled. What I'm basically saying is that is there a more "modular" way to implement this without being recursive, and without confusing myself by trying to find clever ways to make use of as few pointers as possible.

Edit: Okay new and improved BST deletion, if there's anything missing which I can't tell at the moment please advise me on some ways to improve it.

was it this easy

Code:

                        if(prevR == nextR)
                            next->child[1] = NULL;

NO, DO NOT WORK!