5

在《Introduction To Algorithms - A Creative Approach 》一书中，问题 4.24：

令 T1 和 T2 是两棵任意树，每棵树都有 n 个节点。证明对 T1 最多应用 2n 次旋转就足够了，因此它等于 T2。

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

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

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

  3. 对于 T1 和 T2 的左子树，递归处理如上。
    对于 T1 和 T2 的右子树，递归处理如上。

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

我不太明白“任意树”这个短语，我不知道如何使 T1 等于 T2。

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

4

1 回答 1

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)对根进行适当的旋转以获得新树的左右子树上的等效节点。然后我们可以递归地解决较小子树上的较小子问题。

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

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

于 2013-11-24T15:31:25.677 回答