将一个二进制搜索树正确转换为另一个的时间复杂度

Question

如果仅通过对T1进行右旋转可以从T1获得T2，则BST T1可以右转换为另一个BST T2。我需要证明此操作可以在$ O（n ^ 2）$右旋转中完成。

假设我们得到T1可以右转换为T2。我了解算法的递归性质，因为我们首先将T2的根（必须是T1的最左路径中的当前值，才能使其可右转换）带到T1的根，然后对T1的2个子树。

但是我无法提出一个例子来说明最坏的情况。尽管我不确定如何证明这是最坏的情况，但我能够想到这两棵树。

 Tree 1                Tree 2 

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

通过从节点2向前右旋转5 + 4 + 3 + 2次，可以将树1右转换为T2。

通常，我如何找到需要$ O（n ^ 2）$右旋转将一个BST转换为另一个BST的情况？

Answer 1

校样：

让T1=(V,E)，n=#V。考虑从<T1 = X_0, X_1, ..., X_(t-1), X_t = T2>开始重复（右）旋转的过程中出现的树木T1的顺序。对于任何给定的旋转，让“旋转锚点”表示旋转后的子树的根节点。

观察＃1：旋转任何给定的子树不会更改其顶点集。

观察＃2：在给定子树向右旋转的任何顺序s中，每个顶点最多为旋转锚点一次。 （在每个右旋转中，锚点都迁移到右子树中。右旋转后的新根源于左子树；或者请注意，每旋转一次，右子树将增长1个顶点；因此对于子树[ C0]，最大S旋转数）。

观察＃3：向右旋转不会更改子树的数量。

任何树中子树的数量等于可用根数#V(S)-1。因此，最大长度的右旋转序列涉及#V-1个子树，每个子树最大旋转O(n)（= #V(S)-1）个，总共O(n)个。]