Good day,

I have written a C++ template class for a binary search tree.
(Implemented in Visual C++ 6.0). (See the link below to get
the source code).

Everything works fine, except my method to remove one node from
the BST.  I would appreciate it if someone could comment on my
algorithm for removing the node - I just can't find the problem!
I used the basic theory from Thomas Niemann's e-papers
at http://www.*-*-*.com/ (great site)
although the code itself is my own.

A high level description of the theory would go like this:

First, find the node we want to delete.
There are three cases when deleting:
1. If the node is a leaf, simply remove it.
2. If the node has only one child (subtree), link past the node by
simply connecting the node's only child to the node's parent.
3. If node has two subtrees, instead of removing the node, we replace
the value of that node with the smallest value in the right subtree
of the node, and delete that smallest node.
Case 3(a): Node is root with two subtrees
Case 3(b): Node is sub-node with two subtrees

More background information on my implementation (typed here in "pseudo"
as to not confuse you with my Windows programming style) (I will also show
how AddItem works to help you understand how my tree works):

struct NODE {
    NODE *parent;
    NODE *left;
    NODE *right;

bool AddItem(data) {
    NODE *parent = NULL;
    NODE *current = root;
    bool left;

    while (current) {
        if (current->data == data) return false; // item already exists
        parent = current;
        left = data < current->data;
        current = left ? current->left : current->right;
    }

    NODE *new = allocate new NODE;
    new->data = data;
    new->parent = parent;

    if (root == NULL) root = new;
    else (left ? parent->left : parent->right) = new;
    return true;

NODE * FindNode(data) {
    NODE *current = root;
    while (current) {
        if (current->data = data) return current;
    }
    return NULL;  // not found

// ---- this is where I have some problem ----
bool RemoveNode(data) {
    NODE *node;    // the node to delete
    NODE *parent;
    bool left; // true if node is in the left subtree of its parent

    node = FindNode(data);
    if (node == NULL) return false; // not found

    parent = node->parent;
    if (parent) left = data < parent->data;

    // case 1: node is a leaf - just remove it
    (if node->left == node->right == NULL) {
        if (parent)
            (left ? parent->left : parent->right) = NULL;
        else
            root = NULL;
        delete node; // free the memory
        return true;
    }

    // case 3: node has two subtrees - replace with smallest value from
right subtree.
    // ---- I suspect this is where my problem lies ----
    if (node->left && node->right) {
        NODE *smallest = node->right; // go one step to the right...
        if (smallest->left) {
            while (smallest->left) smallest = smallest->left; // ...then
keep going left to find smallest
            smallest->parent->left = NULL; // remove smallest leaf node from
right subtree
        }
        else {
            // node's left subtree has no left subtree, so relink
node->right with node->right->right
            node->right = smallest->right;
            if (smallest->right) smallest->right->parent = node; // and link
upwards too
        }
        node->data = smallest->data; // replace node's value with smallest's
value
        delete smallest; // free memory
        return true;
    }

    // case 2: node has only one subtree, remove node by linking parent to
the subtree
    NODE *subtree = (node->left? node->left : node->right);
    subtree->parent = parent; // link up with parent
    if (parent) (left ? parent->left : parent->right) = subtree; // link
down with subtree
    else root = subtree;
    delete node; // free memory
    return true;

Example of use of the actual class (for type int):
CTree<int> Tree;
Tree.AddItem(1);
Tree.AddItem(2);
if (Tree.FindItem(2)) cout << "2 occurs in the tree" << endl;
Tree.RemoveItem(2);
if (NULL == Tree.FindItem(2)) cout << "Now 2 does not occurs in the tree" <<
endl;

Please email me if you've got any ideas on my RemoveNode implementation or
any
other comments.  You can get the source files from here:
http://www.*-*-*.com/
http://www.*-*-*.com/

Thanks!

Gert Lombard
OSI Airport Systems
South Africa

I don't really have time to dissect code, but I can comment on these steps.

In step 2, if the node has only one child, you need to make more than one
connection.  For simplicity, let's call the parent node A, the node to be
removed B, and the child node C.  Therefore, A, B, and C are of type NODE*
or LPNODE if you're a Windows programmer, and furthermore, the following
relationships are true before the deletion.
(A && B && C)        // All are non-NULL
(A == B->parent)        // B's parent is A
(B == A->left) || (B == A->right)    // One of A's children is B
((A->left && !A->right) || (A->right && !A->left))    // A only has one
child (B)
(B == C->parent)                            // C's parent is B
(C == B->left) || (C == B->right)    // One of B's children is C

// USE PREVENTATIVE DEBUGGING!  IT IS YOUR FRIEND!

In fact, you could and should ASSERT these at the beginning of your delete
function.  The following should be true after the deletion.
(C->parent == A)

if (B was A->left)
    (C == A->left)
else
    (C == A->right)

So we get from this that C's parent must be set to B's parent, and the
correct child pointer from A must now point to C instead of B.  The best way
to do this is using a friend function which can access a Tree's private
data.  It looks to me like you're using C though, in which case you can it's
already public.

A = node->parent;
B = node;
C = (node->right) ? node->right : node->left;

C->parent = A;
LPNODE* pAChild = (B == A->left) ? (&A->left) : (&A->right);
*pAChild = C;
delete B;
B = NULL;

Case 3 is Identical to case 2 except for the way we set *pAChild;  More on
this later, because I've got to go to a meeting and I'd hate to waste what
I've already written.

 - Zach

I found the problem (with my wife's help, haha)...

The problem was in my "case 3", where I had the following:

If the node we want to delete has two (i.e. both) subtrees, we find the
smallest node in the right subtree.  We do this by going one step right
(i.e. to node->right) and then follow this down to the left to find the
left-most leaf of the right subtree.

What I did was to remove that left-most leaf node by setting its parent's
left
to NULL.

What I forgot was that this leaf node could have a right subtree, so I
should
instead have linked the leaf's parent's left to the leaf's right, and the
other
way around.

THUS, on line 192:

    pSmallest->m_pParent->m_pLeft = NULL;   // Remove smallest leaf node.

becomes:

    pSmallest->m_pParent->m_pLeft = pSmallest->m_pRight;   // Remove
smallest leaf node.
    if (pSmallest->m_pRight)
    {
        pSmallest->m_pRight->m_pParent = pSmallest->m_pParent;
    }

The updated sources can be found here:
http://www.spook.co.za/gertl/tree.cpp
http://www.spook.co.za/gertl/tree.h

-gertl