algorithm - 使用旋转的二叉树变换

Question

当我在学习二叉树的中期时，我发现了一个声明，即任何任意 n 节点二叉树都可以转换为任何其他 n 节点二叉树，最多 2*n-2 次旋转。有什么证据吗？我找到了某种渐近符号的证明，但不是那么清楚。我的意思是有人可以解释/说明为什么这是真的吗？如果它说 n 节点二叉树，它是否包括根？

Answer 1

这个答案来自 CLRS 第 3 版教科书问题 13.2-4。

让

LEFT = 整个左链表二叉树

RIGHT = 整个右链表二叉树。

您可以轻松地从左到右旋转 (n-1) 次。

例如：n = 3
    3 2 1
  2 比 1 3 比 2
1 3

证明：因为根据定义，每次右旋转都会将最右边路径的长度至少增加 1。因此，从长度为 1 的最右边路径开始（最坏情况），您最多需要执行 (n-1) 次旋转把它变成正确的。

因此，您可以轻松得出结论，任何具有 n 个节点的任意形状的二叉树都可以在 (n-1) 次旋转内旋转为 RIGHT。让 T_1 成为您开始的节点 让 T_2 成为您结束的节点。

您可以在 (n-1) 次旋转内将 T_1 旋转到 RIGHT。同样，您可以在 (n-1) 次旋转内将 T_2 旋转到 RIGHT。

因此，要将 T_1 旋转到 T_2，只需将 T_1 旋转到 RIGHT ，然后进行反向旋转以从 RIGHT 旋转到 T_2。

因此，您可以在 (n-1)+(n-1) = 2n-2 次旋转上限中执行此操作。

希望这会有所帮助！=）
顺志龙，
多伦多大学

Answer 2

如果该语句指的是二叉树而不是 BST 树，我认为该语句是有效的，因为对节点的顺序没有限制。一个简单的数学归纳应该证明这个陈述。