Removing a node from a binary tree

Discussion in 'C++' started by Jimmy, Dec 4, 2003.

  1. Jimmy

    Jimmy Guest

    Hi everyone,

    I am working with a binary tree, and I am having a bit of trouble
    visuallizing what needs to happen when I am trying to
    delete a node that has two children. (no child node and one child node were
    trivial).

    Does anyone know the solution to this problem?

    void CTree::Delete(CPerson *&pPerson)
    {
    if (pPerson->pLeft == NULL && pPerson->pRight == NULL)
    {
    delete pPerson;
    pPerson = NULL;
    }
    else if (pPerson->pLeft == NULL)
    {
    CPerson *pTemp = pPerson;
    pPerson = pPerson->pRight;
    delete pTemp;
    }
    else if (pPerson->pRight == NULL)
    {
    CPerson *pTemp = pPerson;
    pPerson = pPerson->pLeft;
    delete pTemp;
    }
    else //if the right and left are not null!?!?
    {
    }
    }
     
    Jimmy, Dec 4, 2003
    #1
    1. Advertising

  2. Jimmy

    Jimmy Guest

    One thing I forgot to mention is: The solution that I have in my head is to
    replace the the node that is begin deleted with the left most node of it's
    right child. But not sure if that will work in all cases.
     
    Jimmy, Dec 4, 2003
    #2
    1. Advertising

  3. "Jimmy" <adfj;fd@dafj;dlf.sds> wrote...
    > I am working with a binary tree, and I am having a bit of trouble
    > visuallizing what needs to happen when I am trying to
    > delete a node that has two children. (no child node and one child node

    were
    > trivial).
    >
    > Does anyone know the solution to this problem?


    I think you need to find a leaf that is between the left and the right
    nodes and move it into the "deleted" node.

    >
    > void CTree::Delete(CPerson *&pPerson)
    > {
    > if (pPerson->pLeft == NULL && pPerson->pRight == NULL)
    > {
    > delete pPerson;
    > pPerson = NULL;
    > }
    > else if (pPerson->pLeft == NULL)
    > {
    > CPerson *pTemp = pPerson;
    > pPerson = pPerson->pRight;
    > delete pTemp;
    > }
    > else if (pPerson->pRight == NULL)
    > {
    > CPerson *pTemp = pPerson;
    > pPerson = pPerson->pLeft;
    > delete pTemp;
    > }
    > else //if the right and left are not null!?!?
    > {


    // this is a bit more complicated.
    // you need to search the left and right for a leaf node
    // that is smaller than right and greater than left
    // then prune that leaf and stick the value in *this.

    > }
    > }


    I may be mistaken, of course. That's all off the top of my head.

    Victor
     
    Victor Bazarov, Dec 4, 2003
    #3
  4. "Jimmy" <adfj;fd@dafj;dlf.sds> wrote...
    > One thing I forgot to mention is: The solution that I have in my head is

    to
    > replace the the node that is begin deleted with the left most node of it's
    > right child. But not sure if that will work in all cases.


    It probably will. The leftmost [leaf] node of the right child is
    (a) greater than the current node (otherwise it would be in the left
    child) and (b) the smallest in the right subtree (otherwise it would
    not be the leftmost). So, with the current node gone, it's the
    primary candidate for its place :)

    Victor
     
    Victor Bazarov, Dec 4, 2003
    #4
  5. Jimmy

    Ali R. Guest

    "Victor Bazarov" <> wrote in message
    news:kDJzb.419070$HS4.3341389@attbi_s01...
    > "Jimmy" <adfj;fd@dafj;dlf.sds> wrote...
    > > One thing I forgot to mention is: The solution that I have in my head is

    > to
    > > replace the the node that is begin deleted with the left most node of

    it's
    > > right child. But not sure if that will work in all cases.

    >
    > It probably will. The leftmost [leaf] node of the right child is
    > (a) greater than the current node (otherwise it would be in the left
    > child) and (b) the smallest in the right subtree (otherwise it would
    > not be the leftmost). So, with the current node gone, it's the
    > primary candidate for its place :)
    >
    > Victor
    >
    >


    What about a case like this

    10
    / \
    2 19
    / \ / \
    1 4 14 20
    \
    15
    if you try to delete 10, and replace it with the left most node of it's
    right node (which is 14). what will happen to 15?

    Ali R.
     
    Ali R., Dec 4, 2003
    #5
  6. "Ali R." wrote:
    >
    > "Victor Bazarov" <> wrote in message
    > news:kDJzb.419070$HS4.3341389@attbi_s01...
    > > "Jimmy" <adfj;fd@dafj;dlf.sds> wrote...
    > > > One thing I forgot to mention is: The solution that I have in my head is

    > > to
    > > > replace the the node that is begin deleted with the left most node of

    > it's
    > > > right child. But not sure if that will work in all cases.

    > >
    > > It probably will. The leftmost [leaf] node of the right child is
    > > (a) greater than the current node (otherwise it would be in the left
    > > child) and (b) the smallest in the right subtree (otherwise it would
    > > not be the leftmost). So, with the current node gone, it's the
    > > primary candidate for its place :)
    > >
    > > Victor
    > >
    > >

    >
    > What about a case like this
    >
    > 10
    > / \
    > 2 19
    > / \ / \
    > 1 4 14 20
    > \
    > 15
    > if you try to delete 10, and replace it with the left most node of it's
    > right node (which is 14). what will happen to 15?


    Is this question addressed to the OP (you want to make him think
    about some cases), or are you asking for yourself?

    If first, I apologize for interfering.
    else scroll down a little bit









































    15 has to be reconnected to 20 (if the leftmost child of
    the right subtree has a right child on its own, then this
    child will replace that leftmost child).

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Dec 4, 2003
    #6
  7. Jimmy

    Ali R. Guest

    "Karl Heinz Buchegger" <> wrote in message
    news:...
    > "Ali R." wrote:
    > >
    > > "Victor Bazarov" <> wrote in message
    > > news:kDJzb.419070$HS4.3341389@attbi_s01...
    > > > "Jimmy" <adfj;fd@dafj;dlf.sds> wrote...
    > > > > One thing I forgot to mention is: The solution that I have in my

    head is
    > > > to
    > > > > replace the the node that is begin deleted with the left most node

    of
    > > it's
    > > > > right child. But not sure if that will work in all cases.
    > > >
    > > > It probably will. The leftmost [leaf] node of the right child is
    > > > (a) greater than the current node (otherwise it would be in the left
    > > > child) and (b) the smallest in the right subtree (otherwise it would
    > > > not be the leftmost). So, with the current node gone, it's the
    > > > primary candidate for its place :)
    > > >
    > > > Victor
    > > >
    > > >

    > >
    > > What about a case like this
    > >
    > > 10
    > > / \
    > > 2 19
    > > / \ / \
    > > 1 4 14 20
    > > \
    > > 15
    > > if you try to delete 10, and replace it with the left most node of it's
    > > right node (which is 14). what will happen to 15?

    >
    > Is this question addressed to the OP (you want to make him think
    > about some cases), or are you asking for yourself?
    >
    > If first, I apologize for interfering.
    > else scroll down a little bit
    >


    No Apology need! :)

    I was the one butting in to begin with.
    I was thinking about a solutions but couldn't seem to find a good one. It's
    been 15 years since I have looked at a binary tree. The cumulative solution
    from this thread seem to involve alot of IF statements. I was just picking
    Victor's brain there.

    Ali R.
     
    Ali R., Dec 4, 2003
    #7
  8. "Ali R." <> wrote...
    > "Victor Bazarov" <> wrote in message
    > news:kDJzb.419070$HS4.3341389@attbi_s01...
    > > "Jimmy" <adfj;fd@dafj;dlf.sds> wrote...
    > > > One thing I forgot to mention is: The solution that I have in my head

    is
    > > to
    > > > replace the the node that is begin deleted with the left most node of

    > it's
    > > > right child. But not sure if that will work in all cases.

    > >
    > > It probably will. The leftmost [leaf] node of the right child is
    > > (a) greater than the current node (otherwise it would be in the left
    > > child) and (b) the smallest in the right subtree (otherwise it would
    > > not be the leftmost). So, with the current node gone, it's the
    > > primary candidate for its place :)
    > >
    > > Victor
    > >
    > >

    >
    > What about a case like this
    >
    > 10
    > / \
    > 2 19
    > / \ / \
    > 1 4 14 20
    > \
    > 15
    > if you try to delete 10, and replace it with the left most node of it's
    > right node (which is 14). what will happen to 15?


    Deletion of a node is not a one shot operation. Since '15' is hanging
    off the '14', and '14' is the one being deleted, then '15' should take
    its place, I believe.

    Victor
     
    Victor Bazarov, Dec 4, 2003
    #8
  9. Victor Bazarov wrote:
    > "Jimmy" <adfj;fd@dafj;dlf.sds> wrote...
    >
    >>One thing I forgot to mention is: The solution that I have in my head is

    >
    > to
    >
    >>replace the the node that is begin deleted with the left most node of it's
    >>right child. But not sure if that will work in all cases.

    >
    >
    > It probably will. The leftmost [leaf] node of the right child is
    > (a) greater than the current node (otherwise it would be in the left
    > child) and (b) the smallest in the right subtree (otherwise it would
    > not be the leftmost). So, with the current node gone, it's the
    > primary candidate for its place :)
    >
    > Victor
    >
    >

    Ahh, the binary tree; balance and symmetry.

    One could also seek out the rightmost leaf node of the left subtree
    of the victim node. I'm talking about the victim's predecessor when
    traversing in LNR order.

    I guess whether to replace the victim node with its predecessor or
    successor is a design choice.

    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c -faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.raos.demon.uk/acllc-c /faq.html
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
     
    Thomas Matthews, Dec 4, 2003
    #9
    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. Replies:
    0
    Views:
    1,468
  2. JoeAley2003

    Removing Binary Tree Node!

    JoeAley2003, Jul 17, 2003, in forum: C++
    Replies:
    4
    Views:
    484
    Ben Pfaff
    Jul 17, 2003
  3. Tjerk Wolterink
    Replies:
    2
    Views:
    1,439
    Dimitre Novatchev
    Aug 24, 2006
  4. Replies:
    0
    Views:
    521
  5. Peter Mueller
    Replies:
    6
    Views:
    4,575
    Stefan Ram
    Jan 13, 2008
Loading...

Share This Page