证明两棵树的最大转数变得相等

Question

在" 算法导论 - 创造性方法 "一书中,问题4.24:

设T1和T2为两个任意树,每个树有n个节点.证明足以将最多2n次旋​​转应用于T1,使其等于T2.

对于二叉搜索树,我想出了一个算法:

1. 找到等于T2根的元素,我们称之为target-root.

2. 使用AVL旋转策略,旋转target-root使其成为T1的新根.
   在此过程中,可以执行多次旋转.

3. 对于T1和T2的左子树,以递归方式处理它们.
   对于T1和T2的右子树,以递归方式处理它们.

在最坏的情况下,该算法在O(N ^ 2)中运行.

我不太明白"任意树"这个短语,我无法弄清楚如何使T1等于T2.

有人可以帮忙解决这个问题吗？

Answer 1

无论我得到什么，我都可以提出一种算法，可以在 O(N) 旋转中解决这个问题，但无法获得确切的上限，但认为你可以在此基础上构建：-

这是算法的伪代码：-

 //Method to make T1 equivalent to T2

    alignTree(T1,T2) {

     if(length(T1)==1)
        return

     else {

        Node k = FindRoot(T1,T2)
        rotateAbout(k)
        align(T1.left,T2.left)
        align(T1.right,T2.right)
     }


    }

假设FindRoot找到 T1 的节点，该节点被认为是新 Tree 的根，该新 Tree 是等效树。假设rotateAbout(K)对根进行适当的旋转以获得新树的左右子树上的等效节点。然后我们可以递归地解决较小子树上的较小子问题。

旋转次数：正如您在伪代码中看到的，旋转次数相当于pre-order树的遍历，即O(N)

注意：您始终可以将上述伪代码扩展为通用树，并且仍然获得相同的复杂性。