By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,190 Members | 833 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,190 IT Pros & Developers. It's quick & easy.

Removing a node from a binary tree

P: n/a
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!?!?
{
}
}
Jul 22 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a
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.

Jul 22 '05 #2

P: n/a
"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
Jul 22 '05 #3

P: n/a
"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
Jul 22 '05 #4

P: n/a
"Victor Bazarov" <v.********@comAcast.net> 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.
Jul 22 '05 #5

P: n/a
"Ali R." wrote:

"Victor Bazarov" <v.********@comAcast.net> 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
kb******@gascad.at
Jul 22 '05 #6

P: n/a

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...
"Ali R." wrote:

"Victor Bazarov" <v.********@comAcast.net> 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.


Jul 22 '05 #7

P: n/a
"Ali R." <no****@nospam.com> wrote...
"Victor Bazarov" <v.********@comAcast.net> 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
Jul 22 '05 #8

P: n/a
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

Jul 22 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.