算法导论 13.2 Exercises 答案

发表于 更新于 分类于 本文字数： 1.3k 阅读时长 ≈ 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=(v1,v2,…,vm)。如果这条路径上存在一个节点 x，其左子节点非空，那么对 x 进行一次右旋，那么路径 P 将会增加一个节点。

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

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

那么，假设现在需要从 T 通过旋转操作变成 T′，那么从 T 变换到 R 需要 c1 次操作，从 R 变换到 T′ 需要 c2 次操作。那么总操作次数 c 满足 c≤c1+c2≤2n−2。因此 c=O(n)，原结论成立。

⋆ 13.2-5

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

1
2
1
2

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