证明的最大转数为两棵树成为等于

在书中算法导论 - 创造性的方法，问题4.24：证明的最大转数为两棵树成为等于

设T1和T2是两个任意的树，每个都具有n个节点。证明对T1应用至多2n的旋转是足够的，以便它等于T2。

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

查找等于T2的根元素，让我们把它定位根。
使用AVL旋转策略，旋转target-root使其成为T1的新根。
在此过程中，可能会执行多次旋转。
对于T1和T2的左子树，按照上面的方式递归处理它们。
对于T1和T2的右子树，按递归方式处理它们。

该算法在最坏的情况下以O（N^2）运行。

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

任何人都可以帮助解决这个问题吗？

来源

2013-11-24 Guocheng

我不知道有没有简单的答案。我认为这篇论文是一个很好的起点。 Daniel Sleator，Robert Tarjan和William Thurston指出，任何两棵n节点树（n≥11）之间的旋转距离至多为2n-6，并且无限多对树相距甚远。 http://www.ams.org/journals/jams/1988-01-03/S0894-0347-1988-0928904-4/home.html – amald

@amald谢谢，我将阅读文件 – Guocheng

无论从什么我有，我可以建议可以在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-24 15:31:25

我不认为rotateAbout （K）需要一段时间。假设T1是通过插入10,9,8,7,6,5,4,3,2,1生成的树，T2是通过插入1,2,3,4,5， 6,7,8,9,10。然后首先我们旋转关于（1），如果我们使用单次旋转（AVL单次旋转），则需要9个步骤。 – Guocheng

@ Guocheng在对齐两棵树时，我们不匹配树的键，但只有两棵树的结构必须相同，所以根始终是左右两侧具有相同节点的节点。此外，我们不用计算算法的时间复杂度，而只需要对齐树的旋转数。 –

那么我们如何决定T1的新根节点以及如何旋转以确保子树具有相同数量的节点？ – Guocheng

证明的最大转数为两棵树成为等于

回答

相关问题