算法导论13.4 Exercises 答案

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

13.4-1

首先考虑RB-DELETE的第1-8行代码，这个时候$y=z$。令$p=y.p$，由于删除的节点是$y$是一个红色节点，拼接上去的是其唯一一个儿子$son$（要么是$left$，要么是$right$）的子树，因此$p$的右子树和$son$相同，黑高保持不变，那么就与左子树的黑高相同。因此，原结论成立。

13.4-2

由于情况1可以转换成情况2,3,4，并且情况3还可以转换成情况4，因此此处证明仅讨论情况2和情况4来解决（同样的，这里只考虑$x$是它父亲的左儿子的情况）：

  • 情况2不会改变父节点的位置，也不会改变父节点的颜色，因此只要向上迭代，父节点的颜色永远不会发生改变。因此，由于$T$在之前根节点就是黑色的，因此在之后仍然是黑色的，原结论成立。

  • 情况4有两种情况需要考虑：如果$x$的父节点是根节点，那么经过左旋后，根节点成为$x$原来的兄弟节点$w$，由于$w$是黑色节点，因此根节点也将会染成黑色节点，原结论成立；如果$x$的父节点不是根节点，那么根节点不会进行任何改变，保持原来的颜色，故原结论成立。

13.4-3

这种情况只会发生在$z$具有两个儿子的情况。删除$y$前，$y$的父节点$p=x.p$为红色，且$x$也为红色；删除$y$后，$y$原本的父节点$p$成为了$x$的父节点，这时RB-DELETE-FIXUP被调用。

根据算法RB-DELETE-FIXUP的第一行，由于$x$是红色，因此WHILE循环不被执行，被跳过。在第44行，$x$被修改成黑色。由于$p$原本是红色节点，因此$x$的兄弟节点必定是黑色。这时$p$的两个子节点都为黑色，性质4保持成立。

13.4-4

一开始整棵的形状如下：

graph TD
  41((41));38((38));19((19));12((12));
  31((31));8((8));
  A(( ));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 12,31,38,41 black-node;
  class 8,19 red-node;
  38---19;38---41;19---12;19---31;
  12---8;
  12---A;
  style A fill:#f100,stroke-width:0px
  linkStyle 5 stroke:#0ff,stroke-width:0px

如下是按顺序删除每个节点后得到的红黑树：

  • $8$
graph TD
  41((41));38((38));19((19));12((12));
  31((31));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 12,31,38,41 black-node;
  class 19 red-node;
  38---19;38---41;19---12;19---31;
  • $12$
graph TD
  41((41));38((38));19((19));31((31));
  A(( ));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 31,38,41 black-node;
  class 19 red-node;
  38---19;38---41;19---A;19---31;
  style A fill:#f100,stroke-width:0px
  linkStyle 2 stroke:#0ff,stroke-width:0px
  • $19$
graph TD
  41((41));38((38));31((31));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 31,38,41 black-node;
  38---31;38---41;
  • $38$
graph TD
  41((41));38((38));
  A(( ));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 31,38 black-node;
  class 41 red-node;
  38---A;38---41;
  style A fill:#f100,stroke-width:0px
  linkStyle 0 stroke:#0ff,stroke-width:0px
  • $38$
graph TD
  41((41));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 41 black-node;
  • $41$
graph TD
  A[NIL]
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class A black-node;

13.4-5

前文提到，由于RB-DELETE-FIXUP传入的参数$x$可能是$T.nil$，因此节点$x$被访问或修改的代码都符合要求。例如第1行就检查了哨兵的颜色，第2行就检查了当前哨兵节点$x$是否为$x.p$的左子节点。

当最后一个节点从$T$被删除时，$T$为空，WHILE循环会被跳过，第44行代码会对哨兵赋予了一次黑色。

13.4-6

以下图示中，$v/k$表示从根节点到子树$\omega$之间有$k$个黑色节点（包括多重的黑色节点）。它们分别代表a,b,c,d这$4$种情况。

a

graph TD
    A((A));B((B));C((C));D((D));E((E));
    a[a/3];b[β/3];c[γ/2];d[δ/2];e[ε/2];f[ζ/2]
    Z(( ));Z2(( ));
    classDef hide-appearance fill:transparent, stroke:transparent;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    class A,B,C,E black-node;
    class D red-node;
    class a,b,c,d,e,f hide-appearance;
    class Z,Z2 hide-node;
    Z---B;B---A;B---D;
    D---C;D---E;a---Z2;
    A---a;A---b;C---c;C---d;
    E---e;E---f;
    linkStyle 5 stroke:#0ff,stroke-width:0px
graph TD
    A'((A));B'((B));C'((C));D'((D));E'((E));
    a'[α/3];b'[β/3];c'[γ/2];d'[δ/2];e'[ε/2];f'[ζ/2]
    Z'(( ));
    classDef hide-appearance fill:transparent, stroke:transparent;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    class A',D',C',E' black-node;
    class B' red-node;
    class a',b',c',d',e',f' hide-appearance;
    class Z' hide-node;
    Z'---D';D'---B';D'---E';B'---A';B'---C';
    A'---a';A'---b';C'---c';C'---d';
    E'---e';E'---f'

b

graph TD
    A((A));B((B));C((C));D((D));E((E));
    a["α/2+count(c)"];b["β/2+count(c)"];c["γ/2+count(c)"];d["δ/2+count(c)"];e["ε/2+count(c)"];f["ζ/2+count(c)"]
    Z(( ));Z2(( ));
    classDef hide-appearance fill:transparent, stroke:transparent, stroke-width:21px;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    classDef brown-node fill:#bc987e, color:white;
    class A,D,C,E black-node;
    %% class D red-node;
    class B brown-node;
    class a,b,c,d,e,f hide-appearance;
    class Z,Z2 hide-node;
    Z---B;B---A;B---D;
    D---C;D---E;a---Z2;
    A---a;A---b;C---c;C---d;
    E---e;E---f;
    linkStyle 5 stroke:#0ff,stroke-width:0px
graph TD
    A'((A));B'((B));C'((C));D'((D));E'((E));
    a'["α/1+count(c)"];b'["β/1+count(c)"];c'["γ/1+count(c)"];d'["δ/1+count(c)"];e'["ε/1+count(c)"];f'["ζ/1+count(c)"]
    Z'(( ));Z2'(( ));
    classDef hide-appearance fill:transparent, stroke:transparent, stroke-width:21px;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    classDef brown-node fill:#bc987e, color:white;
    class A',C',E' black-node;
    class D' red-node;
    class B' brown-node;
    class a',b',c',d',e',f' hide-appearance;
    class Z',Z2' hide-node;
    Z'---B';B'---A';B'---D';
    D'---C';D'---E';a'---Z2';
    A'---a';A'---b';C'---c';C'---d';
    E'---e';E'---f';
    linkStyle 5 stroke:#0ff,stroke-width:0px

c

graph TD
    A((A));B((B));C((C));D((D));E((E));
    a["α/2+count(c)"];b["β/2+count(c)"];c["γ/1+count(c)"];d["δ/1+count(c)"];e["ε/2+count(c)"];f["ζ/2+count(c)"]
    Z(( ));Z2(( ));
    classDef hide-appearance fill:transparent, stroke:transparent, stroke-width:21px;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    classDef brown-node fill:#bc987e, color:white;
    class A,D,E black-node;
    class C,D red-node;
    class B brown-node;
    class a,b,c,d,e,f hide-appearance;
    class Z,Z2 hide-node;
    Z---B;B---A;B---D;
    D---C;D---E;a---Z2;
    A---a;A---b;C---c;C---d;
    E---e;E---f;
    linkStyle 5 stroke:#0ff,stroke-width:0px
graph TD
    A'((A));B'((B));C'((C));D'((D));E'((E));
    a'["α/2+count(c)"];b'["β/2+count(c)"];c'["γ/1+count(c)"];d'["δ/1+count(c)"];e'["ε/2+count(c)"];f'["ζ/2+count(c)"]
    Z'(( ));Z2'(( ));
    classDef hide-appearance fill:transparent, stroke:transparent, stroke-width:21px;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    classDef brown-node fill:#bc987e, color:white;
    class A',C',E' black-node;
    class D' red-node;
    class B' brown-node;
    class a',b',c',d',e',f' hide-appearance;
    class Z',Z2' hide-node;
    Z'---B';B'---A';B'---C';
    A'---a';A'---b';C'---c';C'---D';
    D'---d';D'---E';E'---e';E'---f';
    %% linkStyle 17 stroke:#0ff,stroke-width:0px

d

graph TD
    A((A));B((B));C((C));D((D));E((E));
a["α/2+count(c)"];b["β/2+count(c)"];c["γ/1+count(c)+count(c')"];d["δ/1+count(c)+count(c')"];e["ε/2+count(c)"];f["ζ/2+count(c)"]
    Z(( ));Z2(( ));
    classDef hide-appearance fill:transparent, stroke:transparent;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    classDef brown-node fill:#bc987e, color:white;
    class A,D black-node;
    class E red-node;
    class B,C brown-node;
    class a,b,c,d,e,f hide-appearance;
    class Z,Z2 hide-node;
    Z---B;B---A;B---D;
    D---C;D---E;a---Z2;
    A---a;A---b;C---c;C---d;
    E---e;E---f;
    linkStyle 5 stroke:#0ff,stroke-width:0px
graph TD
    A'((A));B'((B));C'((C));D'((D));E'((E));
a'["α/2+count(c)"];b'["β/2+count(c)"];c'["γ/1+count(c)+count(c')"];d'["δ/1+count(c)+count(c')"];e'["ε/2+count(c)"];f'["ζ/2+count(c)"]
    Z'(( ));
    classDef hide-appearance fill:transparent, stroke:transparent;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    classDef brown-node fill:#bc987e, color:white;
    class A',B',E' black-node;
    %% class B' red-node;
    class a',b',c',d',e',f' hide-appearance;
    class Z' hide-node;
    class C',D' brown-node;
    Z'---D';D'---B';D'---E';B'---A';B'---C';
    A'---a';A'---b';C'---c';C'---d';
    E'---e';E'---f'

13.4-7

考虑使用反证法来证明。可见，$w$节点是$x$的兄弟叶节点，也就是说，$w.p=x.p$。如果进入了情况1，那么意味着节点$w$是红色。如果$x.p$也是红色，那么这将违反红黑树的性质4。这说明，节点$w$和$w.p$的颜色在调用RB-DELETE-FIXUP之前都是红色，这说明$T$此前就不是一棵红黑树，这是不可能的。因此不需要担心$x.p$是红色，因为$T$此前是一棵红黑树。

13.4-8

不是。考虑如下$4$步操作。一开始$T$是一棵空树。

  1. 插入$1$
graph TD
  1((1))
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 1 black-node;
  1. 插入$2$
graph TD

  1((1));2((2));
  A(( ));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 1 black-node;
  class 2 red-node;
  1---A;1---2;
  style A fill:#f100,stroke-width:0px
  linkStyle 0 stroke:#0ff,stroke-width:0px
  1. 插入$3$
graph TD

  1((1));2((2));3((3));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 1,3 black-node;
  class 2 red-node;
  2---1;2---3;
  1. 删除$3$
graph TD
  1((1));2((2));
  A(( ));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 2 black-node;
  class 1 red-node;
  2---1;2---A;
  style A fill:#f100,stroke-width:0px
  linkStyle 1 stroke:#0ff,stroke-width:0px

由此可见，添加一个节点后再立刻删除它，并不能使红黑树恢复成原样。

$\star$ 13.4-9

代入题目12.2-8的结论，$h=\Theta(\lg n)$，那么可以知道依次遍历$x$的第$1,2,\dots,m$个后继，可以以$\Theta(m+\lg n)$的时间求解出来。

一个简单的做法是找到第一个大于等于$a$的节点，不断地求后继并输出，直到这个后继为T.nil或者是超出了所求范围。我们将设计RB-LOWER-BOUND算法用于求解最小的大于等于某个值的节点，以及BR-SUCCESSOR算法求解某个节点的后继的后继，其中使用到的子程序RB-MINIUM用于求解子树$r$中的最小节点。

由于现在是求取子树$r$中，满足$a\le k\le b$的所有节点，但是$[a,b]$所覆盖的范围有可能覆盖了子树$T$以外的节点。因此在这一步中，我们需要将右边界$b$缩小，以保证最大值恰好在子树$r$内，在红黑树上求解子树$r$的最大节点由RB-MAXIMUM给出，它和TREE-MAXIMUM非常类似：

这些程序的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
RB-MINIMUM(T, x)
  while x.left ≠ T.nil
    x = x.left
  return x

RB-MAXIMUM(T, x)
  while x.right ≠ T.nil
    x = x.right
  return x

BR-SUCCESSOR(T, x)
  if x.right ≠ T.nil
    return BR-MINIMUM(T, x.right)
  else
    y = x.p
    while y ≠ T.nil and x == y.right
      x = y
      y = y.p
    return y

// 求解以x为子树中，第一个大于等于a的节点。
BR-LOWER-BOUND(T, x, a)
  result = T.nil
  while x != T.nil
    if x.key >= a
      result = x
      x = x.left
    else
      x = x.right
  return result

那么接下来则是对RB-ENUMERATE的实现，这种实现考虑了$a,b$不在树$T$中的情形。

1
2
3
4
5
6
7
RB-ENUMERATE(T, r, a, b)
  t = RB-MAXIMUM(T, r)
  b = min{b, r.key}
  x = BR-LOWER-BOUND(T, x, a)
  while x != T.nil and x.key <= b
    print x.key
    x = BR-SUCCESSOR(T, x)

由于对RB-MAXIMUM和BR-LOWER-BOUND的调用仅有$1$次，再加上迭代求解$x$的后继（假设有$m$个），因此整个算法的时间复杂度为$\Theta(m+\lg n)$。