algorithm - 证明两棵树变得相等的最大旋转次数

Question

在算法导论 - 一种创造性的方法一书中，问题 4.24:

Let T1, and T2 be two arbitrary trees, each having n nodes. Prove that it is sufficient to apply at most 2n rotations to T1, so that it becomes equal to T2.

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

1. 找到等于 T2 根的元素，我们称它为目标根。

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 的节点，该节点被认为是等效树的新树的根。假设rotateAbout(K) 对根进行适当的旋转，以获得新树左右子树上的等价节点。然后我们可以递归地解决较小子树上的较小子问题。

No of Rotations:正如您在伪代码中看到的那样，旋转次数等同于 pre-order 树的遍历，即 O(N)

注意:您始终可以扩展上述一般树的伪代码，并仍然获得相同的复杂度。