问题描述
当我在研究二叉树的中期课程时，我发现一条陈述，即任意n节点二叉树都可以转换为最多2 * n-2旋转的任何其他n节点二叉树.有什么证据吗?我发现了一些带有渐近符号的证明，但还不是很清楚.我的意思是有人可以解释/显示为什么这是真的吗?如果它说出n节点的二叉树，它是否包括根?
While i was studying for midterm about binary trees, i found a statement that any arbitrary n-node binary tree can be transformed into any other n-node binary tree with at most 2*n-2 rotations. Is there any proof for that? I found some kind of proof with asymptotic notations but it was not that clear. I mean could someone explain/show why it is true? And if it says that n-node binary tree, does it include the root?
推荐答案
此答案来自CLRS 3rd Edition教科书问题13.2-4.
This answer is from CLRS 3rd Edition textbook question 13.2-4.
让
LEFT =整个左链表二叉树
LEFT = an entire left linked list binary tree
RIGHT =整个右链表二进制树.
RIGHT = an entire right linked list binary tree.
您可以轻松地向左旋转到右旋转(n-1)次.
You can easily rotate LEFT to RIGHTin (n-1) rotations.
e.g: n = 3
3 2 1
2 to 1 3 to 2
1 3
证明:根据定义，由于每次右旋转都会使最右路径的长度至少增加1.因此，从长度为1(最坏的情况)的最右路径开始，最多需要执行(n-1)次旋转才能使其正确.
Proof:Since by definition, each right rotation will increase the length of the right most path by at least 1. Therefore, starting from right most path with length 1 (worst case), you need at most (n-1) rotations performed to make it into RIGHT.
因此，您可以轻松得出结论:具有(n-1)个旋转的任意形状的具有n个节点的二叉树都可以旋转为RIGHT.让T_1作为您开始的节点让T_2作为结点.
Thus, you can easily conclude that any arbitrary shape of binary tree with n nodes can rotate into RIGHT within (n-1) rotations. Let T_1 be node you begin withLet T_2 be node you end with.
您可以在(n-1)圈内将T_1旋转到RIGHT.相似地，您可以在(n-1)圈内将T_2旋转到RIGHT.
You can rotate T_1 to RIGHT within (n-1) rotations. Similarly, You can rotate T_2 to RIGHT within (n-1) rotations.
因此，要将T_1旋转到T_2，只需将T_1旋转到RIGHT，然后进行反向旋转以从RIGHT旋转到T_2.
Therefore, To rotate T_1 into T_2, simply rotate T_1 into RIGHT , then do the inverse rotation to rotate from RIGHT into T_2.
因此，您可以在(n-1)+(n-1)= 2n-2上限旋转中进行此操作.
Therefore, you can do this in (n-1)+(n-1) = 2n-2 rotations in upper bound.
Hope this helps!=)
Soon Chee Loong,
University of Toronto
这篇关于使用旋转的二叉树变换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！