算法导论13 Problems 答案

13-1

a

如果插入一个节点\(z\)，插入完成后，\(z\)中的所有祖先都需要进行一遍记录。

如果删除一个节点\(z\)，那么如果\(z\)只有一个孩子，那么只需要将\(z\)的所有祖先都进行一次记录；否则，求解\(z\)的后继\(y\)，此时是删除节点\(y\)，那么将\(y\)的所有祖先节点都记录。

b

PERSISTENT-TREE-INSERT(T, z)
  Let T' be a new tree
  if T.root == NIL
    T'.root = z
    return T'
  y = NIL
  x = COPY-NODE(T.root)
  T'.root = x
  while x != NIL
    y = x
    if z.key < x.key
      x = x.left
      if x != NIL
        x = COPY-NODE(x)
        y.left = x
    else
      x = x.right
      if x != NIL
        x = COPY-NODE(x)
        y.right = x
  if z.key < y.key
    y.left = z
  else
    y.right = z
  return T'

c

算法PERSISTENT-TREE-INSERT只是将遍历过的所有节点都克隆一遍，整个过程和TREE-INSERT都是一致的，因此其时间复杂度和TREE-INSERT一致，为\(O(h)\)；由于遍历了\(O(h)\)个节点，新生成了\(O(h)\)了节点，因此其空间复杂度为\(O(h)\)。

d

如果需要维护父亲指针，那么自顶向下考虑这个维护过程。首先，需要克隆新版本的根节点，因此新版本的二叉搜索树中，两个子节点的父亲指针需要指向新的父亲指针，这说明这些子节点也需要克隆出一份新的，这些子节点的子节点的父亲指针也需要更新……最终，整棵树的所有结点都被克隆了一遍，因此维护父亲指针的持久二叉搜索树算法的时间复杂度是\(\Omega(n)\)。

e

由题目13.3-6可以知道，其所有操作仅仅是对插入节点\(z\)的祖先进行了操作，非\(z\)祖先的节点不会受到影响，因此只需要将\(y\)的全部祖先及其涉及到相关的节点都克隆一次，再按照题目13.3-6的算法将它们改成持久算法即可。此外，删除操作也类似。因此整个时间复杂度为\(O(\lg n)\)。

如下给出算法PERSISTENT-RB-INSERT和PERSISTENT-RB-INSER-FIXUP，它们是RB-INSERT'和RB-INSERT-FIXUP的持久化版本。

PERSISTENT-RB-INSERT(T, z)
  // P是从T.root到z的一条路径。并且这里对T'.nil和T.nil不做区分。
  Let T' be a new tree
  if T.root == T.nil
    T'.root = z
    return T'
  y = T.nil
  x = COPY-NODE(T.root)
  T'.root = x
  let P be new array
  INSERT(P, T'.nil)
  INSERT(P, T'.root)
  while x != T.nil
    y = x
    if z.key < x.key
      x = x.left
      if x != NIL
        x = COPY-NODE(x)
        y.left = x
        INSERT(P, x)
    else
      x = x.right
      if x != NIL
        x = COPY-NODE(x)
        y.right = x
        INSERT(P, x)
  if z.key < y.key
    y.left = z
  else
    y.right = z
  z.left = T'.nil
  z.right = T'.nil
  z.color = RED
  INSERT(P, z)
  PERSISTENT-RB-INSERT-FIXUP(T', P)
  return T'

// P是从T.root到z中路径的所有节点
PERSISTENT-RB-INSERT-FIXUP(T, P)
  i = P.size - 1
  while i > 0 and P[i - 1].color == RED
    if P[i - 1] == P[i - 2].left
      y = P[i - 2].right
      if y.color == RED
        P[i - 1].color = BLACK
        // 兄弟节点y不在路径上，它是原来的节点，需要被克隆。
        y = COPY-NODE(y)
        y.color = BLACK
        P[i - 2].color = RED
        P[i - 2].right = y
        i = i - 2
      else
        if P[i] == P[i - 1].right
          LEFT-ROTATE'(T, P[i - 2], P[i - 1])
          exchange P[i] with P[i - 1]
        P[i - 1].color = BLACK
        P[i - 2].color = RED
        RIGHT-ROTATE'(T, P[i - 3], P[i - 2])
        // 此时路径序列已经改变，不过也没有所谓，因为之后由于P[i - 1].color == BLACK使得这个循环被跳出。
    else
      y = P[i - 2].left
      if y.color == RED
        P[i - 1].color = BLACK
        y = COPY-NODE(y)
        y.color = BLACK
        P[i - 2].color = RED
        P[i - 2].right = y
        i = i - 2
      else
        if P[i] == P[i - 1].left
          RIGHT-ROTATE'(T, P[i - 2], P[i - 1])
          exchange P[i] with P[i - 1]
        P[i - 1].color = BLACK
        P[i - 2].color = RED
        LEFT-ROTATE'(T, P[i - 3], P[i - 2])

按照类似的思路，可以写出如下持久红黑树删除的算法PERSISTENT-RB-DELETE和PERSISTENT-RB-DELETE-FIXUP，它们是RB-DELETE'和RB-DELETE-FIXUP的持久化版本。其中，RB-TRANSPLANT'同样是将节点赋值到另一个位置，但是忽略了对属性\(p\)的维护，因此，RB-TRANSPLANT'要比RB-TRANSPLANT多一个参数；ITERATIVE-SEARCH-PARENT是求解某个节点在红黑树中的父亲节点，它由算法ITERATIVE-TREE-SEARCH改造而来，最终整个算法的时间复杂度为\(O(\lg n)\)。

ITERATIVE-SEARCH-PARENT(T, k)
  x = T.root
  y = T.nil
  while x != T.nil and k != x.key
    y = x
    if k < x.key
      x = x.left
    else
      x = x.right
  return y


// p是u的父亲节点
RB-TRANSPLANT'(T, p, u, v)
  if T.root == u
    T.root = v
  else if p.left == u
    p.left = v
  else
    p.right = v


PERSISTENT-RB-DELETE(T, z)
  Let T' be new tree
  Let P be new array
  x = T.root
  x = COPY-NODE(x)
  INSERT(P, T'.nil)
  INSERT(P, x)
  p = T.nil
  while x.key != z.key
    p = x
    if z.key < x.key
      x = x.left
      x = COPY-NODE(x)
      p.left = x
    else
      x = x.right
      x = COPY-NODE(x)
      p.right = y
    INSERT(P, x)
  // 目前P中存储了从T.root到z的路径，这其中的所有节点都被克隆。当前x是z的克隆版本。
  z = x
  y = z
  y-original-color = y.color
  parent-z = ITERATIVE-SEARCH-PARENT(T', z)
  if z.left == T'.nil
    x = z.right
    RB-TRANSPLANT'(T', parent-z, z, z.right)
    INSERT(P, x)
  else if z.right == T.nil
    x = z.left
    RB-TRANSPLANT'(T', parent-z, z, z.left)
    INSERT(P, x)
  else 
    // y = TREE-MINIMUM(z.right)
    // 继续往下补充，补充从z到x的路径，同样的是，x只需要是旧版即可。
    y = z
    p = z.right
    while p != T.nil
      p = COPY-NODE(p)
      INSERT(P, p)
      y = p
      p = p.left
    y-original-color = y.color
    x = y.right
    INSERT(P, x)
    if y ≠ z.right
      parent-y = ITERATIVE-SEARCH-PARENT(T, y)
      RB-TRANSPLANT(T', parent-y, y, y.right)
      y.right = z.right
    RB-TRANSPLANT(T', parent-z, z, y)
    y.left = z.left
    y.color = z.color
  if y-original-color == BLACK
    PERSISTENT-RB-DELETE-FIXUP(T', P)
  return T'

// P是从T.root到x中路径的所有节点
PERSISTENT-RB-DELETE-FIXUP(T, P)
  i = P.size - 1
  while i > 1 and P[i].color == BLACK
    if P[i] == P[i - 1].left
      w = P[i - 1].right
      // Case 1
      if w.color == RED
        w = COPY-NODE(w)
        P[i - 1].right = w
        w.color = BLACK
        P[i - 1].color = RED
        LEFT-ROTATE'(T, P[i - 2], P[i - 1])
        P[i - 1] = w
        if i == P.size - 1
          INSERT(P, P[i])
        else
          P[i + 1] = P[i]
        P[i] = P[i - 1]
        P[i - 1] = w
        i = i + 1
        w = P[i - 1].right
      // Case 2
      if w.left.color == BLACK and w.right.color == BLACK
        w = COPY-NODE(w)
        P[i - 1].right = w
        w.color = RED
        i = i - 1
      else
      // Case 3
        if w.right.color == BLACK
          w = COPY-NODE(w)
          P[i - 1].right = w
          v = w.left
          v = COPY-NODE(v)
          w.left = v
          v.color = BLACK
          w.color = RED
          RIGHT-ROTATE'(T, P[i - 1], w)
          w = P[i - 1].right
      // Case 4
        w = COPY-NODE(w)
        P[i - 1].right = w
        v = w.right
        v = COPY-NODE(v)
        w.right = v
        w.color = P[i - 1].color
        P[i - 1].color = BLACK
        v.color = BLACK
        LEFT-ROTATE'(T, P[i - 2], P[i - 1])
        i = 0
    else
      w = P[i - 1].left
      // Case 1
      if w.color == RED
        w = COPY-NODE(w)
        P[i - 1].right = w
        w.color = BLACK
        P[i - 1].color = RED
        RIGHT-ROTATE'(T, P[i - 2], P[i - 1])
        P[i - 1] = w
        if i == P.size - 1
          INSERT(P, P[i])
        else
          P[i + 1] = P[i]
        P[i] = P[i - 1]
        P[i - 1] = w
        i = i + 1
        w = P[i - 1].right
      // Case 2
      if w.left.color == BLACK and w.right.color == BLACK
        w = COPY-NODE(w)
        P[i - 1].right = w
        w.color = RED
        i = i - 1
      else
      // Case 3
        if w.left.color == BLACK
          w = COPY-NODE(w)
          P[i - 1].right = w
          v = w.right
          v = COPY-NODE(v)
          w.left = v
          v.color = BLACK
          w.color = RED
          LEFT-ROTATE'(T, P[i - 1], w)
          w = P[i - 1].left
      // Case 4
        w = COPY-NODE(w)
        P[i - 1].left = w
        v = w.left
        v = COPY-NODE(v)
        w.left = v
        w.color = P[i - 1].color
        P[i - 1].color = BLACK
        v.color = BLACK
        RIGHT-ROTATE'(T, P[i - 2], P[i - 1])
        i = 0

13-2

a

由于红黑树进行一次RB-INSERT或者是RB-DELETE的时间复杂度为\(O(\lg n)\)。完成一次这类操作后，我们可以随机选择一个叶子节点（红黑树的性质5保证了结果必定是相同的），从根到它进行访问，并计算经过的黑色节点数，得到\(T.bh\)的值。这个过程的时间复杂度同样是\(O(\lg n)\)，它将不会增加这个时间，因此仅凭RB-INSERT和RB-DELETE内部即可维护好\(T.bh\)这个值。当计算出\(T.bh\)值后，考虑对\(T\)进行深度优先搜索，当遇到一个黑色节点时，搜索变量\(d\)需要减去\(1\)，否则不进行任何操作，那么\(d\)就代表了当前节点的黑高。深度优先搜索开始前，会将\(d\)值初始化成\(dT.bh+1\)。由此，每个节点可以以\(O(1)\)的时间求出黑高

b

只要黑高相同，那么在树中的位置越靠右，其值越大。因此，令\(r\)为\(T\)中的最大节点（即最右叶节点），从\(T.root\)到\(r\)这条路径中，黑高为\(T_2.bh\)的黑色节点即为所求。算法由CAL-MAX-NODE-EQ-BLACK-HEIGHT给出。由于只是遍历了红黑树中一条从根到叶子节点的路径，因此其时间复杂度为\(O(\lg n)\)。

CAL-MAX-NODE-EQ-BLACK-HEIGHT(T1, T2)
  k = T1.bh - T2.bh
  y = T1.root
  while y != T1.nil
    if y.color == BLACK
      if k == 0
        break
      else
        k = k - 1
    y = y.right
  return y

c

令\(T\)为所求的树，那么令\(T.root=x,x.left=T_y.root,x.right=T_2.root,T_y.root.p=T_2.root=p\)即可。由于\(T_y\)中的所有值都比\(x\)小，并且\(T_2\)中的所有值都比\(x\)大，因此\(T\)仍然是一棵二叉搜索树。

d

将\(x\)染成红色即可。按照题目13-2-b的算法，在\(T_1\)中找到一个黑高为\(T_2.bh\)的最大节点\(y\)，并且按照题目\(c\)的方式，构造出了一棵黑高为\(T_2.bh\)的松弛红黑树\(T=T_y\cup \{x\}\cup T_2\)（注意\(T\)的根节点\(x\)是红色的），接下来调用RB-TRANSPLANT(T1, y, x)将树\(T\)的根\(x\)覆盖在树\(T_1\)在\(y\)这个位置上。那么在拼接前\(y\)的父节点\(y.p\)看来，左右两边的子树的黑高都是\(T_2.bh\)，因此性质5仍然成立；由于叶子节点\(T.nil\)并未有任何的修改，因此性质3仍然成立；性质1也仍然成立。

如果\(y\)是\(T_1\)的根节点，那么上述操作会违反性质2，因为红节点\(x\)成为了\(T_1\)的新节点。如果原本的\(y\)的父节点\(y.p\)是红色，那么拼接之后\(x\)和\(x.p\)都是红色，它们违反了性质4。因此，可以通过调用子程序RB-INSERT-FIXUP(T1, x)来解决，这只花费\(O(\lg n)\)的时间解决。

e

如果\(T_2.bh\ge T_1.bh\)，按照题目13-2-b的思想，可以在\(T_2\)找到一个最小的黑高为\(T_1.bh\)的节点\(z\)；令\(T_z\)是\(T_2\)中以\(z\)为根的子树，按照题目13-2-c的思想，可以拼接出树\(T=T_1\cup\{x\}\cup T_z\)；按照题目13-3-d的思想，将\(T\)的根\(x\)覆盖在树\(T_2\)在\(z\)这个位置上即可，之后同样需要调用子程序RB-INSERT-FIXUP(T2, x)来解决性质2和性质4被违背的问题。

f

如下是RB-JOIN的伪代码：

CAL-MIN-NODE-EQ-BLACK-HEIGHT(T1, T2)
  k = T2.bh - T1.bh
  z = T2.root
  while z != T2.nil
    if z.color == BLACK
      if k == 0
        break
      else
        k = k - 1
    z = z.left
  return z

RB-JOIN(T1, x, T2)
  if T1.bh >= T2.bh
    y = CAL-MAX-NODE-EQ-BLACK-HEIGHT(T1, T2)
    x.left = y
    x.right = T2.root
    y.p = x
    T2.root.p = x
    RB-TRANSPLANT(T1, y, x)
    RB-INSERT-FIXUP(T1, x)
  else
    z = CAL-MAX-NODE-EQ-BLACK-HEIGHT(T1, T2)
    x.left = T1.root
    x.right = z
    T1.root.p = x
    z.p = x
    RB-TRANSPLANT(T2, z, x)
    RB-INSERT-FIXUP(T2, x)

注意，RB-JOIN算法的前8行和后8行是完全对称的，此处仅分析第1-8行代码的时间复杂度。第2行求解\(T_1\)中黑高为\(T_2.bh\)消耗的时间为\(O(\lg n)\)，第8行修正性质2和4的操作所消耗的时间同样为\(O(\lg n)\)，其它操作的时间复杂度均为\(O(1)\)，因此算法RB-JOIN的时间复杂度为\(O(\lg n)\)。

13-3

a

令\(T(h)\)表示高度为\(h\)的AVL树中最少的节点数。由于这是一棵AVL树，并且我们希望节点数尽量少，因此其较高的子树的高度为\(h-1\)，较矮的子树的高度为\(h-2\)，并且这些子树的节点数也应该尽量少（分别达到\(T(h-1),T(h-2)\)）。因此，可以写出\(T\)的递推式为

\[T(h)=T(h-1)+T(h-2)+1\]

其中，\(T(0)=0,T(1)=1\)，并且\(+1\)是算上了当前AVL树的根节点。

按照题目31-3-a的分析，可以知道\(T(h)=\Theta(\phi^h)\)。又因为\(T(h)\le n\)，因此可以得知\(h=O(\log_{\phi} n)\)，即\(h=O(\lg n)\)。

b

判断两棵子树的高度，然后对根节点\(x\)进行旋转即可，其单次操作的时间复杂度为\(O(1)\)。为了方便，假设NIL节点为T.nil，其高度为\(-1\)。

// 平衡后，返回新的根。
BALANCE(x)
  if x.right.h == x.left.h + 2
    y = x.right
    LEFT-ROTATE(x)
    x.h = max{x.left.h, x.right.h} + 1
    y = max{x.h, y.right.h} + 1
    return y
  else if x.left.h == x.right + 2
    y = x.left
    RIGHT-ROTATE(x)
    x.h = max{x.left.h, x.right.h} + 1
    y.h = max{x.h, y.left.h} + 1
    return y

c

与题目13-3-b一样，为了方便，假设NIL节点为T.nil，其高度为\(-1\)。插入的过程和普通的二叉搜索树插入过程一样，但是之后需要对路径上的节点进行旋转，以保证两棵子树高度一致。

AVL-INSERT(T, z)
  x = T.root
  y = T.nil
  while x ≠ T.nil
    y = x
    if z.key < x.key
      x = x.left
    else
      x = x.right
  z.p = y
  if y == T.nil
    T.root = z
  else if z.key < y.key
    y.left = z
  else y.right = z
  z.h = 0
  x = z.p
  // 自底向上保持平衡，并且旋转后，$y.h$将会被正确计算出来。
  while |x.left.h - x.right.h| > 1
    y = BALANCE(x)
    x = y.p
  

d

由于树的高度为\(h=O(\lg n)\)，因此AVL-INSERT中的while循环至多执行\(h=O(\lg n)\)次，每次循环将会执行一次BALANCE，因此循环也会执行\(O(\lg n)\)次。因此，总体上AVL-INSERT的时间复杂度为\(O(\lg n)\)。