BST & recursion

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

  1. 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, Jul 30, 2003
    #1
    1. Advertising

  2. "David White" <> wrote...

    > Not ladies as well?


    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
    #2
    1. Advertising

  3. [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
    #3
  4. Andrew Edwards

    David White Guest

    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
    #4
  5. Andrew Edwards

    David White Guest

    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?
    >
    >
    > 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, Jul 30, 2003
    #5
  6. Andrew Edwards

    David White Guest

    "Karl Heinz Buchegger" <> wrote in message
    news:...
    > You are not using paper and pencil to follow the operation of
    > your delete function:
    >
    > > 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

    P.S. After having read your extraordinary response with increasing awe as
    each line passed, I sincerely hope I am wrong!
     
    David White, Jul 30, 2003
    #6
  7. Andrew Edwards

    Howard Guest

    [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
    "binary search tree ADT"?

    -Howard
     
    Howard, Jul 30, 2003
    #7
  8. Andrew Edwards

    David White Guest

    "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
    #8
  9. "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
    #9
  10. Andrew Edwards, Jul 30, 2003
    #10
  11. Andrew Edwards

    David White Guest

    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
    #11
  12. Andrew Edwards

    Oliver S. Guest

    Oliver S., Aug 3, 2003
    #12
  13. "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
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Rupert harrison

    BST

    Rupert harrison, Sep 15, 2003, in forum: C++
    Replies:
    2
    Views:
    571
    Karl Heinz Buchegger
    Sep 15, 2003
  2. Ridimz

    BST: remove less than

    Ridimz, Oct 4, 2003, in forum: C++
    Replies:
    8
    Views:
    549
    Josh Sebastian
    Oct 7, 2003
  3. Ice
    Replies:
    4
    Views:
    5,075
  4. puzzlecracker

    LL TO BST

    puzzlecracker, Jan 19, 2005, in forum: C++
    Replies:
    2
    Views:
    411
    Joseph Turian
    Jan 19, 2005
  5. Replies:
    8
    Views:
    799
    John Reye
    Apr 26, 2012
Loading...

Share This Page