Skip to content

Latest commit

 

History

History
49 lines (34 loc) · 2.09 KB

13.2.md

File metadata and controls

49 lines (34 loc) · 2.09 KB

Exercises 13.2-1


Write pseudocode for RIGHT-ROTATE.

Answer

image 就模仿书上的left,right对调一下哈

Exercises 13.2-2


Argue that in every n-node binary search tree, there are exactly n - 1 possible rotations.

Answer

有n个节点,就有n-1对父子节点(root节点没有).对于每一个对,都有一个对应的旋转,所以是n-1.

Exercises 13.2-3


Let a, b, and c be arbitrary nodes in subtrees α, β, and γ, respectively, in the left tree of Figure 13.2. How do the depths of a, b, and c change when a left rotation is performed on node x in the figure?

Answer

图上都告诉我们了.

  • a的深度+1
  • b的深度不变
  • c的深度-1

Exercises 13.2-4


Show that any arbitrary n-node binary search tree can be transformed into any other arbitrary n-node binary search tree using O(n) rotations. (Hint: First show that at most n - 1 right rotations suffice to transform the tree into a right-going chain.)

Answer

思路挺有意思的. 对于根节点左边的节点,如果有右儿子就左旋;对于根节点右边的节点,如果有左儿子就右旋;最后我们得到了一根排序好的链表.

对于另外一棵树,我们也能通过相同的方法转换为这根链表.

因此,通过逆变换就能转换回去,自然是O(n)的.

Exercises 13.2-5 ⋆


We say that a binary search tree T1 can be right-converted to binary search tree T2 if it is possible to obtain T2 from T1 via a series of calls to RIGHT-ROTATE. Give an example of two trees T1 and T2 such that T1 cannot be right-converted to T2. Then show that if a tree T1 can be right-converted to T2, it can be right-converted using O(n^2) calls to RIGHT-ROTATE.

Answer

反例很好举,T1(1,#,2),T2(2,1,#),T1无法右旋成T2.

O(n^2)是这样来的. 如果T1和T2的根节点不同,那么可以通过O(n)次右旋将T1的根节点变成T2的根节点. 接下来递归调用root的右节点. 可以得到T(n) = T(n-1) + O(n). 所以是O(n^2).


Follow @louis1992 on github to help finish this task.