While i was studying for midterm about binary trees, i found a statement that any arbitrary n-node binary tree can be transformed into any other n-node binary tree with at most 2*n-2 rotations. Is there any proof for that? I found some kind of proof with asymptotic notations but it was not that clear. I mean could someone explain/show why it is true? And if it says that n-node binary tree, does it include the root?
A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations.
In a binary search tree, a right rotation is the movement of a node, X, down to the right. This rotation assumes that X has a left child (or subtree). X's left child, R, becomes X's parent node and R's right child becomes X's new left child.
The tree shown in following figure is an AVL Tree, however, we,need to insert an element into the left of the left sub-tree of A. the tree can become unbalanced with the presence of the critical node A. The node whose balance factor doesn't lie between -1 and 1, is called critical node.
This answer is from CLRS 3rd Edition textbook question 13.2-4.
Let
LEFT = an entire left linked list binary tree
RIGHT = an entire right linked list binary tree.
You can easily rotate LEFT to RIGHT in (n-1) rotations.
e.g: n = 3 3 2 1 2 to 1 3 to 2 1 3
Proof: Since by definition, each right rotation will increase the length of the right most path by at least 1. Therefore, starting from right most path with length 1 (worst case), you need at most (n-1) rotations performed to make it into RIGHT.
Thus, you can easily conclude that any arbitrary shape of binary tree with n nodes can rotate into RIGHT within (n-1) rotations. Let T_1 be node you begin with Let T_2 be node you end with.
You can rotate T_1 to RIGHT within (n-1) rotations. Similarly, You can rotate T_2 to RIGHT within (n-1) rotations.
Therefore, To rotate T_1 into T_2, simply rotate T_1 into RIGHT , then do the inverse rotation to rotate from RIGHT into T_2.
Therefore, you can do this in (n-1)+(n-1) = 2n-2 rotations in upper bound.
Hope this helps!=) Soon Chee Loong, University of Toronto
If the statement refers to binary trees not BST trees I think the statement is valid, since there is not restriction about the order of the nodes. And a simple mathematical induction should prove the statement.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With