算法导论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=(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)\)。