算法导论17.2 Exercises 答案

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

17.2-1

对每个节点添加一个\(prec\)和\(succ\)属性，那么我们考虑维护这两个属性值。不难发现，属性\(prec\)和\(succ\)构成了一个双向链表，为了方便，我们可以用\(T.nil\)作为这个双向链表的头部节点。

对于插入操作，我们对\(z\)完成普通的红黑树插入操作后，直接求取\(z\)的后继\(s\)，并且通过节点\(s\)的\(prev\)得到\(z\)的前驱，然后直接更新\(p.succ=z,s.prev=z\)即可。

对于删除操作，我们先直接求出\(z\)的后继\(s=z.succ\)和前驱\(p=z.prev\)，然后直接更新\(p.succ=s,s.prev=p\)即可。

这两种操作的修改没有改变红黑树的渐进增长时间，同时也将题目所需要的操作的时间复杂度改进到\(O(1)\)。这些算法的改动由如下程序给出。

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)
  return T.nil.succ

RB'-MAXIMUM(T)
  return T.nil.prev

RB'-PREDECESSOR(z)
  return z.prev

RB'-SUCCESSOR(z)
  return z.succ

RB'-INSERT(T, z)
  RB-INSERT(T, z)
  x = z
  y = x.p
  while y != T.nil and z == x.right
    x = y
    y = y.p
  s = y
  p = s.prev
  p.succ = z
  s.prev = z

RB'-DELETE(T, z)
  p = z.prev
  s = z.succ
  p.succ = s
  s.prev = p
  RB-DELETE(T, z)

17.2-2

维护节点的黑高可以做到不改变红黑树插入和删除的渐进时间。在整个过程中，我们只需要在FIXUP阶段计算好子节点的黑高后再计算当前节点的黑高即可（子节点可以任意选择，因为按照性质5，左子树和右子树的黑高是一样的，这里选择左子树即可）。

如下是程序RB-INSERT-FIXUP-BH和RB-INSERT-FIXUP-BH，来维护插入或删除某个节点后调整整棵树，并计算每个节点的黑高。插入算法的主程序是RB-INSERT-BH，它和RB-INSERT的区别在于最后一行调用的是RB-INSERT-FIXUP-BH而不是RB-INSERT-FIXUP；删除算法的主程序是RB-DELETE-BH，它和RB-DELETE的区别在于最后一行调用的是RB-DELETE-FIXUP-BH而不是RB-DELETE-FIXUP。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
RB-UPDATE-BH(z)
  if z.color == BLACK
    z.black-height = z.left.black-height + 1
  else
    z.black-height = z.left.black-height

RB-INSERT-FIXUP-BH(T, z)
  while z.p.color == RED
    if z.p == z.p.p.left
      y = z.p.p.right
      if y.color == RED
        z.p.color = BLACK
        y.color = BLACK
        z.p.p.color = RED
        z = z.p.p
        RB-UPDATE-BH(z.left)
        RB-UPDATE-BH(z.right)
        RB-UPDATE-BH(z)
      else
        if z == z.p.right
          z = z.p
          LEFT-ROTATE(T, z)
        z.p.color = BLACK
        z.p.p.color = RED
        RIGHT-ROTATE(T, z.p.p)
        RB-UPDATE-BH(z.p.right)
        RB-UPDATE-BH(z.p)
    else
      y = z.p.p.left
      if y.color == RED
        z.p.color = BLACK
        y.color = BLACK
        z.p.p.color = RED
        z = z.p.p
        RB-UPDATE-BH(z.left)
        RB-UPDATE-BH(z.right)
        RB-UPDATE-BH(z)
      else
        if z == z.p.right
          z = z.p
          RIGHT-ROTATE(T, z)
        z.p.color = BLACK
        z.p.p.color = RED
        RIGHT-ROTATE(T, z.p.p)
        RB-UPDATE-BH(z.p.left)
        RB-UPDATE-BH(z.p)
  T.root.color = BLACK

RB-DELETE-FIXUP-BH(T, x)
  while x != T.root and x.color == BLACK
    if x == x.p.left
      w = x.p.right
      if w.color == RED
        w.color = BLACK
        x.p.color = RED
        LEFT-ROTATE(T, x.p)
        w = x.p.right
        RB-UPDATE-BH(x.p)
        RB-UPDATE-BH(x.p.p)
      if w.left.color == BLACK and w.right.color == BLACK
        w.color = RED
        x = x.p
        RB-UPDATE-BH(x.right)
        RB-UPDATE-BH(x)
      else
        if w.right.color == BLACK
          w.left.color = BLACK
          w.color = RED
          RIGHT-ROTATE(T, w)
          w = x.p.right
          RB-UPDATE-BH(w.right)
          RB-UPDATE-BH(w)
        w.color = x.p.color
        x.p.color = BLACK
        w.right.color = BLACK
        LEFT-ROTATE(T, x.p)
        RB-UPDATE-BH(x)
        RB-UPDATE-BH(w.right)
        RB-UPDATE-BH(w)
        x = T.root
    else
      w = x.p.left
      if w.color == RED
        w.color = BLACK
        x.p.color = RED
        RIGHT-ROTATE(T, x.p)
        w = x.p.left
        RB-UPDATE-BH(x.p)
        RB-UPDATE-BH(x.p.p)
      if w.left.color == BLACK and w.right.color == BLACK
        w.color = RED
        x = x.p
        RB-UPDATE-BH(x.left)
        RB-UPDATE-BH(x)
      else
        if w.left.color == BLACK
          w.right.color = BLACK
          w.color = RED
          LEFT-ROTATE(T, w)
          w = x.p.left
          RB-UPDATE-BH(w.left)
          RB-UPDATE-BH(w)
        w.color = x.p.color
        x.p.color = BLACK
        w.left.color = BLACK
        RIGHT-ROTATE(T, x.p)
        RB-UPDATE-BH(x)
        RB-UPDATE-BH(w.right)
        RB-UPDATE-BH(w)
        x = T.root
  x.color = BLACK

维护节点的深度无法做到不改变红黑树插入和删除的渐进时间，因为插入和删除涉及到旋转操作。旋转操作会将某些子树的所有节点都增加\(1\)或者是减少\(1\)，这是无法在\(O(\lg n)\)的时间内完成的。

17.2-3

由于属性\(f\)是可结合的，因此\(x.f\)可以写成\(x.left.f\otimes x.a\otimes x.right.f\)。

对于旋转操作导致\(f\)值更新，其基本更新操作如下：

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
OS-LEFT-ROTATE-UPDATE-F(T, x)
  y = x.right
  x.right = y.left
  if y.left != T.nill
    y.left.p = x
  y.p = x.p
  if x.p == T.nil
    T.root = y
  else if x == x.p.left
    x.p.left = y
  else
    x.p.right = y
  y.left = x
  x.p = y
  y.f = x.f
  x.f = x.left.f ⊗ x.a ⊗ x.right.f

OS-RIGHT-ROTATE-UPDATE-F(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
  x.f = y.f
  y.f = y.left.f ⊗ y.a ⊗ y.right.f

最终，将上述代码的\(f\)替换成\(size\)，\(\otimes\)替换成\(+\)，\(x.a\)和\(y.a\)替换成\(1\)，就成为了更新子树大小的代码。