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

Question

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

Answer 1

此答案来自 CLRS 第三版教科书问题 13.2-4。

让

LEFT = 整个左链表二叉树

RIGHT = 一个完整的右链表二叉树。

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

e.g: n = 3     3              2              1  2     to        1  3   to        21                                    3

证明:由于根据定义，每次向右旋转都会使最右边路径的长度至少增加 1。因此，从长度为 1 的最右边路径(最坏情况)开始，您最多需要执行 (n-1) 次旋转才能完成正确。

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

您可以在 (n-1) 圈内将 T_1 向右旋转。相似地，您可以在 (n-1) 圈内将 T_2 向右旋转。

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

因此，您可以在上限 (n-1)+(n-1) = 2n-2 圈内执行此操作。

Hope this helps!=)Soon Chee Loong, University of Toronto