BST & recursion

[Andrew Edwards]

Gentlemen,

I have a Binary Search Tree ADT that should use recursion for all operation
except for isEmpty() and isFull();

I have completed the insert function, and after inserting the numbers 10,
20, 30, 15, 5, 9, 3, 17, 4, 7, 6, 8, 11 and calling showStructure() I get
the following (works perfectly):

30
20<
17
15<
11
10<
9\
8
7<
6
5<
4
3/

After deleting 10 and calling showStructure() I get the following (lost the
right half of my tree):


30\
9\
8
7<
6
5<
4
3/

What am I doing wrong?


Thanks in advance,
Andrew
====================================================
Here is the code for my remove() function:

template < class DT, class KF >
bool BSTree<DT,KF>:: remove ( KF deleteKey )
{
return removeSub( root, deleteKey );
}

template < class DT, class KF >
bool BSTree<DT,KF>:: removeSub ( BSTreeNode<DT,KF>*& p, KF deleteKey )
{
if ( deleteKey < p->dataItem.key() )
{
removeSub ( p->left, deleteKey );
}
else if ( deleteKey > p->dataItem.key() )
{
removeSub ( p->right, deleteKey );
}
else
{
DT temp_data;
BSTreeNode<DT,KF>* temp_node = p;
if ( p->left == NULL )
{
p = p->right;
delete temp_node;
cout << "\nNode deleted";
return true;
}
else if ( p->right == NULL )
{
p = p->left;
delete temp_node;
return true;
}
else
{ int count=0;
while (p->right != NULL)
{
p->right->left = p->left;
// p->right->right = p->right; // causes infinite loop.
p = p->right;
}
delete temp_node;
}
}
return false;
}

 

[Andrew Edwards]

Not ladies as well?

Sorry if this offends anyone.

I don't have time to analyse your code right now. But I see that you have
declared 'p' as a reference to a pointer, just as you did in your linked
list. I just thought I'd check that this is what you intended this time.

Yes this is intentional(actually, the choice is not mine). It is also one of
the reason why I have so much problem: I truly am missing something when it
comes to reference pointers and recursion.

An essential part of programming is debugging. What have you done to try to
see where it's going wrong? An obvious starting point is to display a
message at each place you change the part of the tree that is attached to
another, and each time you delete a node. You call also try calling a
function to display the entire tree at certain points, so you can see the
total changes that have occurred so far. If you have the tools available,
single-stepping through the code would also help you find the problem.

DW

I have done this: the printout of the trees provided were done inside the
removeSub() function before and after removing the node containing 10.

I did not include that debugging information because I was advised that it's
not good practice to include such code within classes in an earlier post.
From debugging I see that the right portion of the tree falls off every time
I try to remove a node that has two children. Attempts to correct this
problem have left me with: 1) the reverse of the previous example (missing
left half of the tree). 2) infinite loops, 3) minimal amount of time to
find a solution, and 4) migraines.

Removal of leaves with one or no children woks fine, my real problem is with
nodes that have two children.

Thanks,
Andrew

 

[John Harrison]

[snip]

I did not include that debugging information because I was advised that it's
not good practice to include such code within classes in an earlier post.
From debugging I see that the right portion of the tree falls off every time
I try to remove a node that has two children. Attempts to correct this
problem have left me with: 1) the reverse of the previous example (missing
left half of the tree). 2) infinite loops, 3) minimal amount of time to
find a solution, and 4) migraines.

Removal of leaves with one or no children woks fine, my real problem is with
nodes that have two children.

Thanks,
Andrew

This is how I was taught to remove an internal node from a binary tree.

If the node has two children, find the next node in sequence (i.e. go right
once, and then left as far as you can). This node must have at most one
child, so you can delete it using the techniques that have already worked
for you. But before you delete it, copy its value to the node you are trying
to delete.

HTH

john

 

[David White]

I have done this: the printout of the trees provided were done inside the
removeSub() function before and after removing the node containing 10.

I did not include that debugging information because I was advised that it's
not good practice to include such code within classes in an earlier post.

Yes, for those trying to see what's wrong it's better without debugging
code.

From debugging I see that the right portion of the tree falls off every time
I try to remove a node that has two children. Attempts to correct this
problem have left me with: 1) the reverse of the previous example (missing
left half of the tree). 2) infinite loops, 3) minimal amount of time to
find a solution, and 4) migraines.

Removal of leaves with one or no children woks fine, my real problem is with
nodes that have two children.

In case you don't get an answer that solves the problem, I suggest that you
post the entire class, incuding the class definition, and your test code
that inserts the values. Though it's usually best to post the minimum code
that exhibits the problem, this kind of recursive tree code isn't trivial to
get one's head around without spending some time on it, so having a
complete, compilable test program might make it easier for someone to find
what's wrong.

Also, it isn't obvious at a glance what the loop in your final 'else' is
aiming to do. To delete one value, I can't see the necessity in any
circumstance to alter all the nodes below it, unless it is some sort of
optimization to make the tree more balanced. If it is re-balancing, try
replacing the node to be deleted with the appropriate one of its two
branches instead, just to see if you still have the same problem. At least
you might narrow it down.

DW

 

[David White]

Gentlemen,

I have a Binary Search Tree ADT that should use recursion for all operation
except for isEmpty() and isFull();

I have completed the insert function, and after inserting the numbers 10,
20, 30, 15, 5, 9, 3, 17, 4, 7, 6, 8, 11 and calling showStructure() I get
the following (works perfectly):

30
20<
17
15<
11
10<
9\
8
7<
6
5<
4
3/

After deleting 10 and calling showStructure() I get the following (lost the
right half of my tree):


30\
9\
8
7<
6
5<
4
3/

What am I doing wrong?


Thanks in advance,
Andrew
====================================================
Here is the code for my remove() function:

template < class DT, class KF >
bool BSTree<DT,KF>:: remove ( KF deleteKey )
{
return removeSub( root, deleteKey );
}

template < class DT, class KF >
bool BSTree<DT,KF>:: removeSub ( BSTreeNode<DT,KF>*& p, KF deleteKey )
{

I think I see a problem now. You are assuming that 'p' is not a null
pointer.

if ( deleteKey < p->dataItem.key() )
{
removeSub ( p->left, deleteKey );

But is it not possible that p->left is null here?

From the look of your tree, the node with value 20 has a null left node, and
10 is less than 20.

Or have I misunderstood your tree diagram?

DW

 

[David White]

You are not using paper and pencil to follow the operation of
your delete function:


called with deleteKey == 10
p points to the root of the tree


deleteKey p
+---------+ +-------+
| 10 | | o |
+---------+ +---|---+
|
+---------+
|
|
| 30
| 20<
| 17
| 15<
v 11
10<
9\
8
7<
6
5<
4
3/



not true

Doesn't this test whether 10 is less than 30, and isn't it true that 10 is
less than 30?

DW

P.S. After having read your extraordinary response with increasing awe as
each line passed, I sincerely hope I am wrong!

 

[Howard]

Gentlemen,

I have a Binary Search Tree ADT that should use recursion for all operation
except for isEmpty() and isFull();

Just curious: what's an ADT??? I know what a binary search tree is, but a
"binary search tree ADT"?

-Howard

 

[David White]

Oh. I see where your problem is. You need to rotate the
tree 90 degrees clockwise. The tree is drawn this way

+-- right child
|
root =
|
+-- left child

It is easier to draw a tree this way. A simple recursive
function can do it. Drawing the tree in an upward position ...


+--- root ---+
| |
v v
left child right child

... is much more complicated.

Yes, I had got it the wrong way. I thought there was something odd about the
structure I saw.

DW

 

[Andrew Edwards]

Please: In the future. If you post to 2 newsgroups, do so by
crossposting. Do *not* post the same message 2 times to 2
different newsgroups.

I apologize! I was simply overwhelmed when I decided to post that message
(after having worked on it for two days without coming any closer to
understanding what I was doing wrong). BTW, how does one post messages to
multiple newsgroups simultaneously? Just send it to all of them at the same
time? Will responses in one newsgroup automatically be submitted on all
others?

[snip]

I think you haven't understood what you need to do in the case
that a node has 2 subtrees and is to be deleted: You need to
*locate* the largest node in the right subtree and make that
one the new root. But locate does not mean that the intermediate
nodes are reconnected, yet this is what your code does.

You are 100% correct. I haven't a full grasp on correctly using reference
pointers and recursion as yet! Guess it's back to the drawing board for me.

When working with dynamic data structures, it is important
to use paper and pencil to draw an image of the data structure
and use that to verify each code line if it really is correct.
It is the only way to visually see, what your code does in reality!

Point well taken, I will be sure to incorporate this into my programming
practices.

Thanks allot,
I'll be sure to update you on my progress.
Andrew

 

[Andrew Edwards]

Just curious: what's an ADT??? I know what a binary search tree is, but a
"binary search tree ADT"?

-Howard

Abstract Data Type:

http://www.nist.gov/dads/HTML/abstractDataType.html

 

[David White]

I apologize! I was simply overwhelmed when I decided to post that message
(after having worked on it for two days without coming any closer to
understanding what I was doing wrong). BTW, how does one post messages to
multiple newsgroups simultaneously?

It depends on your newsreader. Somewhere there should be an editable field
for the newsgroup. Try listing all newsgroups you want to post to there,
separated by commas.

DW

 

[Oliver S.]

What am I doing wrong?

You're not re-balancing the nodes. I've written an AVL-tree
implementation some time ago that does this balancing:
http://520032173347-0001.bei.t-online.de/avl.h

 

[Karl Heinz Buchegger]

You're not re-balancing the nodes. I've written an AVL-tree
implementation some time ago that does this balancing:
http://520032173347-0001.bei.t-online.de/avl.h

Wait with rebalancing until the delete code works correctly