是否总是可以使用最多 O(n) 树旋转将一个 BST 转换为另一个 BST？

Question

这个较早的问题询问是否总是可以纯粹使用树旋转将一组值的一个 BST 转换为同一组值的另一个 BST（答案是肯定的）。然而，是否总是可以使用最多 O(n) 总树旋转来做到这一点？

Answer 1

是的，这总是可能的。我担心我现在能做的最好的事情就是给你一个愚蠢的算法来证明它是可能的，尽管我怀疑一定有更好的方法来做到这一点。

Day -Stout-Warren 算法是一种从任何 BST 开始，使用树旋转将其转换为完美平衡的 BST 的算法。它的运行时间为 O(n)，总旋转次数为 O(n)。

因此，假设您想使用树旋转将一棵树 T ₁变成另一棵树 T ₂。在两棵树上运行 Day-Stout-Warren，将它们转换为相同的平衡树 T*，并记录在这两种情况下需要进行的旋转。然后，您可以通过首先运行完美平衡_{T 1所需}的所有旋转，然后运行将 T 2 转变_为平衡树所需的相反旋转，将 T _{1转变为 T 2 。}这将 T ₁转换为 T*，然后将 T* 转换为 T ₂。由于 Day-Stout-Warren 算法仅进行 O(n) 次总旋转，因此这也仅进行 O(n) 次总旋转。

我觉得必须有更好的方法来做到这一点，但我不确定如何实现这一目标。如果我想到什么，我会告诉你的！