使用旋转的二叉树变换 [英] Binary tree transformation using rotations

问题描述

当我在研究二叉树的中期课程时，我发现一条陈述，即任意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 RIGHT in (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 with Let 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 

这篇关于使用旋转的二叉树变换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！