This earlier question询问是否总是可以将一组值的一个 BST 转换为同一组值的另一个 BST，完全使用树旋转(答案是肯定的)。但是，是否总是可以使用最多 O(n) 次总树旋转来做到这一点？
最佳答案
是的，总是可以使用至多 O(n) 次树旋转将一个 BST 转换为另一个 BST。这个答案遵循与另一个答案相同的一般方法，通过选择一些规范的树形状 T* 并限制将任意树变成我们的规范树所需的旋转次数。然后，您可以通过将 T₁ 转换为 T*，然后将 T* 转换为 T₂，将任意树 T₁ 转换为另一棵树 T₂。
正如评论中所建议的，您可以选择规范树作为退化链表。对于 n 个节点的树，这个 upper bounds the number of rotations needed at 2n−2 .
论文中Rotation Distance, Triangulation, and Hyperbolic Geometry , Daniel Sleator, Robert Tarjan, 和 William Thurston 证明了任意两棵 n 节点的二叉树之间的旋转距离至多为 2n−6(优于我们在转换为链表时得到的界限) .
在高层次上，他们通过引入一种将任何二叉树表示为 polygon triangulation 的方法来做到这一点，其中树旋转具有相应的三角剖分操作。然后，本文选择了一个规范的三角剖分，而不是对二叉树的通常表示进行推理，并展示了如何将任意三角剖分转换为所需的三角剖分。
他们选择的规范三角剖分是所有对角线都从扇形形状的单个顶点发出的三角剖分，最终对应于有点不直观的二叉树形状(链表的概括，还包括由以下组成的菱形树一个根，一个左 child ，其右 child 是一个链表，一个右 child ，其左 child 是一个链表)。
这是一种非常酷的技术，它展示了数据结构中等距的力量，展示了改变我们的表示如何为我们提供解决问题的新方法。我和一些 friend 最近一起整理了a writeup walking through Sleator, Tarjan, and Thurston's proof如果您想更详细地探讨这一点。
关于algorithm - 是否总是可以使用至多 O(n) 树旋转将一个 BST 转换为另一个？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37305824/