
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