算法导论13.4 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 8.7k 阅读时长 ≈ 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)\)。