Solution:
It is obvious that if a node is in the right subtree, then it can never be in the left subtree by right-rotations.
There's a corresponding right-rotation for each left-edge. It can not be right-rotated if the left-edge is right-rotated once.
Therefore, if we fix the root of the tree, then there's O(n) left-edges, so there's O(n) possible right-rotations.
There're n possible roots. If the root is fixed, then the elements in the left and right subtrees are fixed.
Thus the total right-rotations between two possible trees T1 and T2 is n times O(n), which is O(n^2).
Hi. I have been thinking on this problem and I am not able to understand one point. Why might we require O(n^2) rotations? Can't we get away with O(n) rotations? Taking the question 13.2-4 itself, we can rotate any tree into an entire right going chain within O(n) rotations. And I cannot see why any particular edge will be involved in a right rotation more than once. Can you give me an example in which we might need quadratic number of rotations?
ReplyDelete