这个较早的问题询问是否总是可以将一组值的一个 BST 转换为仅使用树旋转的同一组值的另一个 BST（答案是肯定的）。但是，是否总是可以使用最多 O(n) 总树旋转来做到这一点？
问问题
1365 次
2 回答
3
是的，始终可以使用最多 O(n) 次树旋转将一个 BST 转换为另一个。这个答案遵循与另一个答案相同的一般方法，通过选择一些规范的树形状 T* 并限制将任意树变成我们的规范树所需的旋转次数。然后，您可以通过将 T1 转换为 T*，然后将 T* 转换为 T2，将任意树 T1 转换为另一棵树 T2。
正如评论中所建议的，您可以选择规范树作为退化链表。对于 n 个节点的树，这个上限是2n-2所需的旋转次数。
在论文Rotation Distance, Triangulation, and Hyperbolic Geometry中，Daniel Sleator、Robert Tarjan 和 William Thurston 证明了 n 个节点的任意两棵二叉树之间的旋转距离最多为 2n−6（比我们在转换为一个链表）。
在高层次上，他们通过引入一种将任何二叉树表示为多边形三角剖分的方法来做到这一点，其中树旋转具有相应的三角剖分操作。然后，本文不再以通常的表示来推理二叉树，而是选择了一个规范的三角剖分，并展示了如何将任意三角剖分转换为所需的三角剖分。
他们选择的规范三角剖分是所有对角线都从单个顶点以扇形发出，最终对应于有点不直观的二叉树形状（链表的概括，还包括由根组成的菱形树，一个左孩子的右孩子是一个链表，一个右孩子的左孩子是一个链表）。
这是一种非常酷的技术，它展示了数据结构中等距的力量，展示了如何改变我们的表示形式可以为我们提供一种解决问题的新方法。如果您想更详细地探讨这一点， 我和一些朋友最近整理了一篇文章，介绍了 Sleator、Tarjan 和 Thurston 的证明。
于 2018-07-10T18:49:25.323 回答
1
是的，这总是可能的。我担心我现在能做的最好的事情就是给你一个愚蠢的算法来证明这是可能的，尽管我怀疑一定有更好的方法来做到这一点。
Day-Stout-Warren 算法是一种算法，它从任何 BST 开始，使用树旋转将其转换为完美平衡的 BST。它在 O(n) 时间内运行并进行 O(n) 总旋转。
因此，假设您想使用树旋转将一棵树 T 1变成另一棵树 T 2。在两棵树上运行 Day-Stout-Warren 以将它们转换为相同的平衡树 T*，并记录在这两种情况下需要进行的旋转。然后，您可以通过首先运行完美平衡 T 1所需的所有旋转，然后运行将 T 2变为平衡树所需的反向旋转，将 T 1变为T 2 。这会将 T 1变成 T* ，然后将 T* 变成 T 2。由于 Day-Stout-Warren 算法仅进行 O(n) 次总旋转，因此这也仅进行 O(n) 次总旋转。
我觉得必须有更好的方法来做到这一点，但我不确定如何实现这一目标。如果我想到什么，我会告诉你的！
于 2017-07-25T21:10:12.557 回答