root replacing algorithm?

[cfan]

i have a bst tree
and i need to build a function which removes the root and rearanges the remaining tree
so it will remain bst.

??

i cant see a general way of solving it.
for

 
     2
   /  \
 1     3

i just make the right one to be the new root and point its left to 3

 
    1
     \
      3

but it doest work for this tree

 
     6
   /  \
 4     7
  \     \
   5    8

and the 5 should be the next root
and my method doesnt work here

??


what is the correct algorithm?

[brewbuck]

What order is the tree supposed to be in? You never said.

[cfan]

they trees are bst

what do you mean by order?

[MK27]

they trees are bst

Sure, but the selection of the root is potentially arbitrary. I haven't worked with binary trees much, but I think there will be no algorithm for replacing the root node and rearranging the tree appropriately unless it is the same one you use to build the tree in the first place.

I say that not because I've done it, but because it seems to me that in order to keep the tree balanced (if the tree has to be balanced, which it will probably work better for searching that way, which is the purpose), you must select the appropriate root node and proceed from there. Presumably, search trees like this are inefficient and awkward to add nodes to -- they are designed for efficiency when searching thru them, not when modifying or creating.

[cfan]

so there is no general algorithm?

[cfan]

i have been given this assignment by my teacher
of course i will go to him with this problem.

but there has to be a basic algorithm for this

[bithub]

so there is no general algorithm?

Of course there is. Read this, and pay special attention to the portion on "Node Deletion".

[MK27]

Of course there is. Read this, and pay special attention to the portion on "Node Deletion".

Ah, see, I was wrong

[cfan]

for one child or no child:
If the node has a left child, replace it with the left child.
If the node has a right child, this is the symmetric case for if the node has a left child.
If the node has no children, just pick one because they're both leaves.
Be sure to reset the parent to point to the child, and it unlinks the node from the tree
It's like removal for a linked list, we replace p's next link with x's next link, thus removing x from the chain so that we can free it safely.

for my case:
these are the inorder predecessor and successor, respectively. All of the work is in finding one of those nodes

The inorder predecessor of a node never has a right child, and the inorder successor never has a left child.

they portrait here a simple tactic

 Copy 7 to 5

           7

       /       \

     2           8

   /   \       /   \

 1       4   7       9

 Remove the external 7

           7

       /       \

     2           8

   /   \       /   \

 1       4   ~       9

but its not working on my case when my successor 7 has right son 8

 
     6
   /  \
 4     7
  \     \
   5    8

what do i do with 8??
it could be not only 8 .
8 could have also sons.
what do i do with 8 in my case

a mirror case is if 5 has a left son
what do i do with it?

they dont cover these cases

[MK27]

If the node has no children, just pick one because they're both leaves.

That's wrong and you know it!

what do i do with 8??
it could be not only 8 .
8 could have also sons.
what do i do with 8 in my case

a mirror case is if 5 has a left son
what do i do with it?

In the example you give, 8 could have children, but does not: so what? If a value of 9 (or greater) is inserted into the tree it will be the right of 8 (and there are no possible children to the left of eight).

On the other hand, 5 could not have children, because there is no non-duplicate whole number that will pass that point in the tree.

As long as you follow the left/less than right/greater than branching and insert at an empty node, you should be alright.

However, I don't think your issue about replacing the root and rearranging the tree is dealt with in that article; the insert algorithm is recursive, so the "root" being returned is always an interior branch node UNLESS the root is null because the list is empty. So maybe I was right: you do have to construct the tree from scratch if you want to replace the top node.

[cfan]

That's wrong and you know it!



In the example you give, 8 could have children, but does not: so what?
On the other hand, 5 could not have children, because there is no non-duplicate whole number that will pass that point in the tree.

thats a direct quote from the text so its not me.
5 could have a left child -1 and its still be the predeccesor

my question is what do i do with this 8
or if i had a -1 as the left son of 5 what do i do with it
by this algorithm presented in the article
?

[MK27]

if i had a -1 as the left son of 5 what do i do with it

If you insert -1 into that tree, it will be the left child of 4, not the left child of 5 -- as I said, in that tree 5 can have no children, it is "logically impossible."

ps. I added a note to my last post while you were writing, you may want to read that -- I still think you have to create the tree from scratch if you want to replace the top.

Anyway, I have to go, but I like trees, maybe I will do a little exercise with this and try and post something here over the weekend.

[cfan]

ok you are correct not -1
but 4.5


what do i do if 5 has a left son 4.5

     6
   /  \
 4     7
  \     \
   5    8
 /
4.5

[brewbuck]

Is this not obvious or something?

Replace the root with either the leftmost leaf of the right subtree, or the rightmost leaf of the left subtree.

The rightmost leaf of the left subtree is guaranteed to be greater than any other value in that subtree, and also guaranteed to be lesser than any value in the right subtree, because this is a BST. Therefore this leaf can be moved to the root while maintaining the BST property.

The same argument (with signs reversed) applies to the right subtree.

[MK27]

Is this not obvious or something?

I was labouring under the impression that this was supposed to be an arbitrary replacement of the root, but I could easily have misunderstood.

Anyway, what you say makes much sense, brewbuck, for finding a good candidate for a new root, but I'm not sure that it solves the problem of how to insert a new root without having to "rebuild" the tree afterward, which I am thinking you can't, ie. if you change the root the tree must be built again from scratch.