CODEWITHSUNDEEP
algorithmrecursiontime-complexitybinary-search-tree
rohit_r
rohit_r

Reputation: 713

Time complexity of right-converting one binary search tree into another

A BST T1 is right-convertible into another BST T2 if T2 can be obtained from T1 by performing only right rotations on T1. I need to prove that this operation can be done in $O(n^2)$ right rotations.

Suppose we are given that T1 is right-convertible to T2. I understand the recursive nature of the algorithm in that we first bring the the root of T2 (which must be in the present in the leftmost path of T1 for it to be right-convertible) to the root of T1 and then repeat this procedure for the 2 subtrees of T1.

However I am not able come up with an example that demonstrates the worst case behaviour. I was able to think of these 2 trees though I am not sure how to prove if this is the worst-case scenario. 

 Tree 1                Tree 2 

          6                  1                   
         /                    \                 
        5                      2              
       /                        \               
      4                          3               
     /                            \                  
    3                              4                
   /                                \
  2                                  6
 /                                  /
1                                  5

Tree 1 can be right-converted to T2 by right-rotating from node 2 onwards for 5+4+3+2 times.

In general, how do I find the case which takes $O(n^2)$ right-rotations to convert one BST to another ?

Upvotes: 0

Views: 654

Answers (1)

collapsar
collapsar

Reputation: 17238

Proof sketch:

Let T1=(V,E), n=#V. Consider the sequence of trees <T1 = X_0, X_1, ..., X_(t-1), X_t = T2> occurring in the course of repeated (right) rotations starting with T1. For any given rotation, let the 'rotation anchor` denote the root node of the rotated subtree.

Observation #1:
Rotating any given subtree does not change its vertex set.

Observation #2:
In any sequence s of right rotations of a given subtree, each vertex is the rotation anchor at most once. (In each right rotation, the anchor migrates into the right child tree. The new root after a right rotation origins with the left child tree; alternatively note that with each rotation, the right child tree grows by 1 vertex; thus for a subtree S, there are at max #V(S)-1 rotations ).

Observation #3:
A right rotation does not change the number of subtrees.

The number of subtrees in any tree is equivalent to the number of available roots which is #V-1. Thus the sequence of right rotations of maximal length involves O(n) subtrees with at max #V(S)-1 (= O(n)) rotations for each of them, O(n^2) in total.

Upvotes: 1

Related Questions