Velocity Reviews > C++ > Removing a node from a binary tree

# Removing a node from a binary tree

Jimmy
Guest
Posts: n/a

 12-04-2003
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:elete(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
Guest
Posts: n/a

 12-04-2003
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.

Victor Bazarov
Guest
Posts: n/a

 12-04-2003
> 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:elete(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
Guest
Posts: n/a

 12-04-2003
> 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

Ali R.
Guest
Posts: n/a

 12-04-2003
"Victor Bazarov" <(E-Mail Removed)> wrote in message
news:kDJzb.419070\$HS4.3341389@attbi_s01...
> > 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.

Karl Heinz Buchegger
Guest
Posts: n/a

 12-04-2003
"Ali R." wrote:
>
> "Victor Bazarov" <(E-Mail Removed)> wrote in message
> news:kDJzb.419070\$HS4.3341389@attbi_s01...
> > > 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

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
http://www.velocityreviews.com/forums/(E-Mail Removed)

Ali R.
Guest
Posts: n/a

 12-04-2003

"Karl Heinz Buchegger" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "Ali R." wrote:
> >
> > "Victor Bazarov" <(E-Mail Removed)> 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

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

Victor Bazarov
Guest
Posts: n/a

 12-04-2003
"Ali R." <(E-Mail Removed)> wrote...
> "Victor Bazarov" <(E-Mail Removed)> wrote in message
> news:kDJzb.419070\$HS4.3341389@attbi_s01...
> > > 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

Thomas Matthews
Guest
Posts: n/a

 12-04-2003
Victor Bazarov 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