Problem: removing one node from binary search tree

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;

Quote:

}

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;

Quote:

}

NODE * FindNode(data) {

NODE *current = root;

while (current) {

if (current->data = data) return current;

}

return NULL; // not found

Quote:

}

// ---- 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;

Quote:

}

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