算法导论13.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

13.2-1

算法的伪代码由RIGHT-ROTATE给出，其和LEFT-ROTATE非常类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
RIGHT-ROTATE(T, y)
  x = y.left
  y.left = x.right
  if x.right != T.nil
    x.right.p = y
  x.p = y.p
  if y.p == T.nil
    T.root = x
  else if y == y.p.left
    y.p.left = x
  else
    y.p.right = x
  x.right = y
  y.p = x

13.2-2

对于任意一个节点$x$，如果它有右子节点$r$，那么可以进行左旋，从而将$r$旋转到$x$的位置；如果它有左子节点$l$，那么可以进行右旋，将$l$旋转到$x$的位置。

可见，如果当前节点$x$能够进行旋转，关键在于看它是否包含左/右子节点。只要包含一个子节点就能进行一次旋转。如果$x$拥有一个子节点，那么$x$恰好就需要一条边连接着它，这恰好对应了某一个旋转方案。

由于$T$中一共有$n-1$条边，因此$T$中有$n-1$种不同的旋转方式。

13.2-3

由图可以得知，$a$的深度增加了$1$；$b$的深度保持不变；$c$的深度减少了$1$。

13.2-4

对于任意一棵树$T$，考虑按照如下策略将其旋转成一条向右伸展的链$R$：从根节点出发，一直访问右子节点，直到最右侧的节点，得到一条路径$P=(v_1,v_2,\dots,v_m)$。如果这条路径上存在一个节点$x$，其左子节点非空，那么对$x$进行一次右旋，那么路径$P$将会增加一个节点。

当路径$P$包含了全部节点时，上述右旋过程结束。由于进行一次右旋操作，$P$就会增加一个节点，并且$T$中最多只有$n$个节点，因此最多$n-1$次右旋操作就可以将$T$旋转成$R$。

此外，由于右旋的操作是可逆的（对应一次左旋），因此从$R$旋转成任意一棵树同样至多只需要$n-1$次左旋操作。

那么，假设现在需要从$T$通过旋转操作变成$T’$，那么从$T$变换到$R$需要$c_1$次操作，从$R$变换到$T’$需要$c_2$次操作。那么总操作次数$c$满足$c\le c_1+c_2\le 2n-2$。因此$c=O(n)$，原结论成立。

$\star$ 13.2-5

如下如所示，左边的$T_1$无法通过右旋操作转化为$T_2$。

graph TD
  1((1))
  2((2))
  3(( ))
  4((1))
  5((2))
  6(( ))
  style 3 fill:#f100,stroke-width:0px
  style 6 fill:#f100,stroke-width:0px
  1---3
  1---2
  5---4
  5---6
  linkStyle 0 stroke:#0ff,stroke-width:0px 
  linkStyle 3 stroke:#0ff,stroke-width:0px

如果$T_1$能够只通过右旋操作转换成$T_2$，那么考虑进行递归操作。$T_2$的根节点必定在$T_1$中最左的路径上（即从根节点出发，一直访问左子节点，直到最左侧的叶节点，得到一条路径$P=(v_1,v_2,\dots,v_m)$）。因此，使用$O(n)$次的操作可以将这个根节点旋转到根的位置。那么接下来对这棵树的子树递归进行这种旋转操作。由于这棵树一共有$n$个节点，因此所需要的操作次数最多为$n\cdot O(n)=O(n^2)$。