本文介绍了使用旋转的二叉树变换的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

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

10-31 12:00