Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Binary tree transformation using rotations

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?

like image 339
fhuseynli Avatar asked Oct 28 '13 00:10

fhuseynli


People also ask

What is the purpose of rotations in binary search trees?

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.

What is a right rotation in binary tree?

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.

What is LL rotation in AVL tree?

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.


2 Answers

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 
like image 109
Chee Loong Soon Avatar answered Sep 19 '22 05:09

Chee Loong Soon


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.

like image 42
Pandrei Avatar answered Sep 21 '22 05:09

Pandrei