Binary tree question

As i am understanding, if you delete the root node of a binary tree, there are two ways to re-order/re-connect the data. Left promotion and Right promotion.
Could someone check to see if this is correct.

Code:

10 / \ 6 14 / \ / \ 5 8 11 18

Here is how i'm thinking it works.
If i delete the root 10, and use left promotion...
the right subtree would move under 8 to the right?

Code:

6 / \ 5 8 \ 14 / \ 11 18

and if it is right promotion and i delete 10 it moves the left subtree under the 11
and would be:

Code:

14 / \ 11 18 / 6 / \ 5 8

is this correct?

google "reheapification for binary trees"

don't remember all the properties off the top of my head, but both of your reheapifications look correct. Keep in mind that whether you use left subtree reheapification or right subtree reheapification it could affect algorithm performance based on whether you're useing inorder, preorder, postorder processing...

Quote:

Originally Posted by brooksbp

google "reheapification for binary trees"

don't remember all the properties off the top of my head, but both of your reheapifications look correct. Keep in mind that whether you use left subtree reheapification or right subtree reheapification it could affect algorithm performance based on whether you're useing inorder, preorder, postorder processing...

Look closer, they are not correct.

Using left-propotion you would get:

Code:

8 / \ 6 14 / / \ 5 11 18

And for right...

Code:

11 / \ 6 14 / \ \ 5 8 18

The promoted node becomes the root, by means of replacing the old root with the promoted node. You don't just cut the left half of the tree off and plonk it on at the top.

A valuable resource is Prelude's web-site.