算法导论13.3 Exercises 答案

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

13.3-1

因为使用黑色节点进行处理会破坏性质5。假设\(T\)的根节点为\(r\)，新增的黑色节点\(z\)的父节点是\(p\)，那么从\(r\)到\(p\)这条路径中，左右子树的黑高都不一致，极难维护。

13.3-2

如下是按顺序插入的红黑树形态。

  • \(41\)
1
2
3
4
5
graph TD
  41((41))
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 41 black-node;
  • \(38\)
1
2
3
4
5
6
7
8
9
10
11
12
graph TD

  41((41));38((38));
  A(( ));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 41 black-node;
  class 38 red-node;
  41---38;
  41---A;
  style A fill:#f100,stroke-width:0px
  linkStyle 1 stroke:#0ff,stroke-width:0px
  • \(31\)
1
2
3
4
5
6
7
8
graph TD

  41((41));38((38));31((31));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 38 black-node;
  class 31,41 red-node;
  38---31;38---41;
  • \(31\)
1
2
3
4
5
6
7
8
9
10
11
graph TD
  41((41));38((38));31((31));12((12));
  A(( ));
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 38,31,41 black-node;
  class 12 red-node;
  38---31;38---41;31---12;
  31---A;
  style A fill:#f100,stroke-width:0px
  linkStyle 3 stroke:#0ff,stroke-width:0px
  • \(19\)
1
2
3
4
5
6
7
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 38,19,41 black-node;
  class 12,31 red-node;
  38---19;38---41;19---12;19---31;
  • \(8\)
1
2
3
4
5
6
7
8
9
10
11
12
13
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

13.3-3

以下图示中，\(v/k\)表示节点\(v\)的黑高为\(k\)。

下图是对图13.5(a)的标记，可以看出，变化前和变化后，节点\(C\)的父节点（如果存在）黑高仍然是\(k+1\)，并没有改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph TD
    A((A/k));B((B/k));C((C/k));D((D/k))
    a[α/k];b[β/k];c[γ/k];d[δ/k];e[ε/k];
    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 C black-node;
    class A,B,D red-node;
    class a,b,c,d,e hide-appearance;
    class Z hide-node;
    Z---C;C---A;C---D;
    A---B;B---a;B---b;A---c;D---d;
    D---e;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph TD
    A'((A/k));B'((B/k));C'((C/k+1));D'((D/k))
    a'[α/k];b'[β/k];c'[γ/k];d'[δ/k];e'[ε/k];
    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' black-node;
    class C',B' red-node;
    class a',b',c',d',e' hide-appearance;
    class Z' hide-node;
    Z'---C';C'---A';C'---D';A'---B';
    B'---a';B'---b';A'---c';D'---d';
    D'---e';

下图是对图13.5(b)的标记。与图13.5(a)的情形类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph TD
    A((A/k));B((B/k));C((C/k));D((D/k))
    a[α/k];b[β/k];c[γ/k];d[δ/k];e[ε/k];
    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 C black-node;
    class A,B,D red-node;
    class a,b,c,d,e hide-appearance;
    class Z hide-node;
    Z---C;C---B;B---A;C---D;A---a;
    A---b;B---c;D---d;
    D---e;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph TD
    A'((A/k));B'((B/k));C'((C/k+1));D'((D/k))
    a'[α/k];b'[β/k];c'[γ/k];d'[δ/k];e'[ε/k];
    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 B',D' black-node;
    class C',A' red-node;
    class a',b',c',d',e' hide-appearance;
    class Z' hide-node;
    Z'---C';C'---B';B'---A';C'---D';A'---a';
    A'---b';B'---c';D'---d';
    D'---e';

下图是对图13.6的标记，可以看出，\(3\)种变化形式下，节点\(C\)的父节点（如果存在）黑高仍然是\(k+1\)，并没有改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
graph TD
    A((A/k));B((B/k));C((C/k));
    a[α/k];b[β/k];c[γ/k];d[δ/k];
    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 C black-node;
    class A,B red-node;
    class a,b,c,d hide-appearance;
    class Z hide-node;
    Z---C;C---A;A---a;A---B;
    B---b;B---c;C---d;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
graph TD
    A'((A/k));B'((B/k));C'((C/k));
    a'[α/k];b'[β/k];c'[γ/k];d'[δ/k];
    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 C' black-node;
    class A',B' red-node;
    class a',b',c',d' hide-appearance;
    class Z' hide-node;
    Z'---C';C'---B';A'---a';A'---b';
    B'---A';B'---c';C'---d';
1
2
3
4
5
6
7
8
9
10
11
12
13
14
graph TD
    A''((A/k));B''((B/k));C''((C/k));
    a''[α/k];b''[β/k];c''[γ/k];d''[δ/k];
    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 B'' black-node;
    class A'',C'' red-node;
    class a'',b'',c'',d'' hide-appearance;
    class Z'' hide-node;
    Z''---B'';B''---A'';B''---C'';A''---a'';
    A''---b'';C''---c'';C''---d'';

13.3-4

当\(z\)是根节点时，由于\(z.p=T.nil\)，并且\(T.nil\)是黑色的，因此它在while循环的判断就会失败，此时循环直接跳出，并将根节点\(z\)改成黑色。

它并不会对\(T.nil\)进行任何操作，因此这个担心是多余的。

13.3-5

由于节点数\(n>1\)，因此第二次插入的节点\(z\)一开始所在位置必定不在根中。类似的，我们只考虑\(z.p==z.p.p.left\)时的一种情形（另一种是对称的，证明方法相同，此处忽略）。考虑这两种情况：

  1. WHILE循环体的内部没有被执行过。这说明新加入\(z\)节点后，整棵树的形态没有发生变化（哪怕原来的树全部节点都是黑色）。由于\(z\)不是根节点，因此第RB-INSERT第30行的代码不可能是对\(z\)染成黑色。因此这种情况下，\(z\)是在这棵树中存在的红色节点，原结论成立。

  2. WHILE循环体的内部有被执行过。那么先考虑Case 1，由于当前的叔节点是红色，因此\(z\)的父节点\(z.p\)和其兄弟节点被染成黑色后，其祖父节点\(z.p.p\)染成红色。后续只处理\(z.p.p\)及其祖先上的情况，这时的\(z\)仍然是树中的一个红色节点，因此原结论成立。接下来同时考虑Case 2和3，由于Case 2包含在Case 3中，因此只考虑Case 3的情况。在对\(z.p.p\)进行右旋后，\(z.p\)被染成黑色，此时WHILE循环终止，\(z\)节点仍然是红色。这个\(z\)节点说明树中仍存在红色节点，原结论成立。

综上所述，原结论是正确的。

13.3-6

首先旋转操作都需要提供父节点来保证父节点可以指向正确的儿子，改动后的旋转算法为LEFT-ROTATE'和RIGHT-ROTATE'所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LEFT-ROTATE'(T, p, x)
  y = x.right
  x.right = y.left
  if p == T.nil
    T.root = y
  else if p.left == x
    p.left = y
  else
    p.right = y
  y.left = x

RIGHT-ROTATE'(T, p, y)
  x = y.left
  y.left = x.right
  if p == T.nil
    T.root = x
  else if p.left == y
    p.left = x
  else
    p.right = x
  x.right = y

那么由于没有了父节点指针，在普通的插入过程中，我们需要记录插入时遍历所遍历出来的一条路径，并且在FIXUP操作过程中，逆序遍历这条路径并且进行对应的操作。整个算法分别由RB-INSERT'和RB-INSERT-FIXUP'给出。因此，整个完整的插入过程的时间复杂度为\(O(\lg n)\)。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
RB-INSERT'(T, z)
  // P是从T.root到z的一条路径。
  let P be new array
  INSERT(P, T.nil)
  x = T.root
  y = T.nil
  while x ≠ T.nil
    INSERT(P, x)
    y = x
    if z.key < x.key
      x = x.left
    else
      x = x.right
  if y == T.nil
    T.root = z
  else 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)
  RB-INSERT-FIXUP'(T, P)

// P是从T.root到z中路径的所有节点
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.color = BLACK
        P[i - 2].color = RED
        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.color = BLACK
        P[i - 2].color = RED
        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])