- node deletion in B.S.T
- Posted by sophia on May 11th, 2008
Dear all,
is node deletion in BST commutative?,commutative in the sense,
deletion of a node x and then y leave the tree same as that of
deleting y first and then x?
- Posted by moi on May 11th, 2008
On Sun, 11 May 2008 02:18:55 -0700, sophia wrote:
Why would you want to know ?
As long as the resulting trees still represent the right ordering af,
they can be _considered_ equal.
(re-)Balancing is another aspect, which may need to be taken care of.
Do you consider the trees before and after balancing the same ?
Please first give your definition of "same tree"
AvK
- Posted by Richard Harter on May 11th, 2008
On Sun, 11 May 2008 02:18:55 -0700 (PDT), sophia
<sophia.agnes@gmail.com> wrote:
If by "the tree the same" you mean having the same shape and
linkage then the answer depends upon how you implement the
deletion. What happens when you delete a node that has both left
and right childre is that the tree is split into two trees that
must then be relinked. There are many ways that this can be done.
That said, one fairly standard way to do this is to replace the
node by its immediate successor. IIANM replacement by the
successor (or predecessor) is commutative in your sense.
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
- Posted by sophia on May 12th, 2008
On May 11, 10:35 pm, c...@tiac.net (Richard Harter) wrote:
the deletion method i am used to is as follows:-
http://s297.photobucket.com/albums/mm220/sophiaagnes/
based on this method will the node deletion be commutative ?
BTW , which is the easier method for node deletion
can you give any links ?
- Posted by moi on May 12th, 2008
On Mon, 12 May 2008 05:57:18 -0700, sophia wrote:
Well, you could try this out on paper.
Delete node #52, then #55.
Do it again, in the opposite order.
[ my guess is: the resulting trees will be different]
Depends on your definition of easy :-}
Simplest case (delete node X from a tree):
X has no children: we are done.
X has only one non-null child: put the child in X's place
X has two non empty children: choose one of them to take X's place,
insert the other (including subtree, which is already ordered, and
guaranteed not to overlap) onto the new X'.
This cheap method will maintain order, but destroys balance.
It is up to you to decide if it is "commutative" :-}
AvK
- Posted by Richard Harter on May 12th, 2008
On Mon, 12 May 2008 05:57:18 -0700 (PDT), sophia
<sophia.agnes@gmail.com> wrote:
I'm sorry, the page you referred me to has unreadable diagrams
and text. I suspect, though, that they are copies of Ben's
libavl pages, URL
http://www.stanford.edu/~blp/avl/lib...rch-Trees.html.
Would that be correct?
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
- Posted by Ben Pfaff on May 12th, 2008
cri@tiac.net (Richard Harter) writes:
I was able to read each of the diagrams by clicking on it to
enlarge. However, this also brought up some annoying
advertising.
They are different diagrams.
--
"doe not call up Any that you can not put downe."
--H. P. Lovecraft
- Posted by Richard Harter on May 12th, 2008
On Mon, 12 May 2008 09:23:25 -0700, Ben Pfaff
<blp@cs.stanford.edu> wrote:
Live and learn. It seems I didn't think of that.
They are indeed, and if I am not mistaken the method there is
inferior to the method in your pages in that the method in
Sophia's page produces more poorly balanced trees.
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
- Posted by aarklon@gmail.com on May 14th, 2008
On May 11, 10:35 pm, c...@tiac.net (Richard Harter) wrote:
what about this method ..???
http://www.cs.usask.ca/resources/tut...ntree/2-5.html
- Posted by Richard Harter on May 14th, 2008
On Tue, 13 May 2008 21:32:31 -0700 (PDT), aarklon@gmail.com
wrote:
It's a reasonable way to do deletions. What is your question?
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
- Posted by aarklon@gmail.com on May 16th, 2008
On May 14, 10:17 am, c...@tiac.net (Richard Harter) wrote:
my question is if I follow the above deletion procedure will the
resulting tree be commutative as per sophia's question, without
considering balancing issues ?
- Posted by Richard Harter on May 19th, 2008
On Thu, 15 May 2008 20:27:16 -0700 (PDT), aarklon@gmail.com
wrote:
Unless I have overlooked a case, yes.
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
