Problem: removing one node from binary search tree
Author Message
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

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

Quote:
}

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

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

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

Sat, 03 Aug 2002 03:00:00 GMT
Problem: removing one node from binary search tree

Quote:
> 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://members.xoom.com/thomasn/s_man.htm (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

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

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

- Zach

Sat, 03 Aug 2002 03:00:00 GMT
Problem: removing one node from binary search tree
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

Sat, 03 Aug 2002 03:00:00 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages