使用旋转的二叉树转换

当我在中期研究二叉树时，发现任何任意的n节点二叉树可以转换成任何其他n节点二叉树，最多2 * n-2个旋转。有没有证据呢？我发现了一些有渐近符号的证明，但它并不那么清楚。我的意思是有人可以解释/说明它为什么是真的？如果它说n节点二叉树，它是否包含根？使用旋转的二叉树转换

来源

2013-10-28 user1722022

这听起来不对，因为旋转不会改变节点的顺序。你确定没有其他限制吗？ – Beta

http://repository.cmu.edu/cgi/viewcontent.cgi?article=2663&context=compsci也许你想参考这篇论文。 –

本答案来自CLRS第3版教材13.2-4。

让

左=整个左链表二叉树

RIGHT =整个右链表二叉树。

在（n-1）旋转中，您可以轻松地将左旋转至右旋。

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

证明：由于根据定义，各右旋转将增加的最右边的路径长度由至少1。因此，从与长度为1（最差情况）最右边的路径开始，则需要最多（n-1）旋转以使其进入右侧。因此，你可以很容易得出结论，任何具有n个节点的二叉树的任意形状都可以在（n-1）个旋转内旋转为RIGHT。设T_1为您开始的节点设T_2为您结束的节点。

您可以在（n-1）次旋转内将T_1旋转到右侧。同样，您可以在（n-1）次旋转中将T_2旋转到RIGHT。

因此，要将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

来源

2014-11-02 08:55:29

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

来源

2013-11-18 14:57:22 Pandrei

使用旋转的二叉树转换

回答

相关问题