# BST & recursion

Discussion in 'C++' started by Andrew Edwards, Jul 30, 2003.

1. ### Andrew EdwardsGuest

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?

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, Jul 30, 2003

2. ### Andrew EdwardsGuest

"David White" <> wrote...

Sorry if this offends anyone.

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

> 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

Andrew Edwards, Jul 30, 2003

3. ### John HarrisonGuest

[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

John Harrison, Jul 30, 2003
4. ### David WhiteGuest

Andrew Edwards <> wrote in message
news:TGHVa.364505\$...
> "David White" <> wrote...
> > 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.
> >

>
> 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, Jul 30, 2003
5. ### David WhiteGuest

Andrew Edwards <> wrote in message
news:8vGVa.300089\$...
> 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?
>
>
> 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, Jul 30, 2003
6. ### David WhiteGuest

"Karl Heinz Buchegger" <> wrote in message
news:...
> You are not using paper and pencil to follow the operation of
>
> > template < class DT, class KF >
> > bool BSTree<DT,KF>:: removeSub ( BSTreeNode<DT,KF>*& p, KF deleteKey )

>
> 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/
>
>
> > {
> > if ( deleteKey < p->dataItem.key() )

>
> not true

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

DW

each line passed, I sincerely hope I am wrong!

David White, Jul 30, 2003
7. ### HowardGuest

[OT] Re: BST & recursion

"Andrew Edwards" <> wrote in message
news:8vGVa.300089\$...
> 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

-Howard

Howard, Jul 30, 2003
8. ### David WhiteGuest

"Karl Heinz Buchegger" <> wrote in message
news:...
> 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

David White, Jul 30, 2003
9. ### Andrew EdwardsGuest

"Karl Heinz Buchegger" <> wrote...
>
> 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, Jul 30, 2003
10. ### Andrew EdwardsGuest

Andrew Edwards, Jul 30, 2003
11. ### David WhiteGuest

Andrew Edwards <> wrote in message
news:vUVVa.364591\$...
> "Karl Heinz Buchegger" <> wrote...
> >
> > 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?

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

David White, Jul 30, 2003
12. ### Oliver S.Guest

Oliver S., Aug 3, 2003
13. ### Karl Heinz BucheggerGuest

"Oliver S." wrote:
>
> > 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

Wait with rebalancing until the delete code works correctly

--
Karl Heinz Buchegger

Karl Heinz Buchegger, Aug 4, 2003