算法导论17.3 Exercises 答案

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

17.3-1

如下是左旋算法的改写版本INTERVAL-LEFT-ROTATE，它可以\(O(1)\)来维护每个节点的\(max\)属性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
INTERVAL-LEFT-ROTATE(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.max = x.max
  x.max = max{x.left.max, x.int.high, x.right.max}

17.3-2

与算法INTERVAL-SEARCH相比，将要设计的算法INTERVAL-SEARCH'将不会搜索到就停止，而是不停地递归寻找节点，直到遇到空节点T.nil才结束。

1
2
3
4
5
6
7
8
9
10
11
12
INTERVAL-SEARCH'(T, i)
  y = T.nil
  x = T.root
  while x != T.nil
    if i overlap x.int
      y = x
      // 更优秀的只会在x的左子树中。
      x = x.left
    else if x.left != T.nil and x.left.max >= i.low
      x = x.left
    else
      x = x.right

17.3-3

这个遍历所有覆盖区间的算法由程序INTERVAL-ENUMERATE-OVERLAP给出。由于子程序GEN-INTERVAL可以视作是对\(T\)进行有条件的前序遍历，每个节点只会被遍历一次；此外，对于\(k\)个可以输出的区间，这些区间至多分布在从根节点到各个叶节点的不同\(k\)条路径中，遍历这些所有路径需要\(O(k\lg n)\)的时间。因此，INTERVAL-ENUMERATE-OVERLAP的时间复杂度为\(O(\min\{n,k\lg n\})\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
GEN-INTERVAL(T, x, i)
  if i overlap x.int
    INSERT(L, x.int)
  if x.left != T.nil and x.left.max >= i.low
    GEN-INTERVAL(T, x.left, x)
  if x.right != T.nil and x.int.low <= i.high and x.right.max >= i.low
    GEN-INTERVAL(T, x.right, x)
   
INTERVAL-ENUMERATE-OVERLAP(T, i)
  // L是一个全局变量，用来存储所有被遍历的区间。
  Let L be an array
  GEN-INTERVAL(T, T.root, i)
  return L

17.3-4

为了保证程序能够找到正确的区间，我们假设如果区间的左端点相同，那么区间的中序顺序按照右端点的大小来决定。基于这个假设，查找算法退化成普通的查找算法，由INTERVAL-SEARCH-EXACTLY给出，因此其时间复杂度取决于树高，即\(O(\lg n)\)。

1
2
3
4
5
6
7
8
INTERVAL-SEARCH-EXACTLY(T, i)
  x = T.root
  while x != T.nil and not(i.low == x.int.low and i.high == x.int.high)
    if i.low < x.int.low or (i.low == x.int.low and i.high < x.int.high)
      x = x.left
    else
      x = x.right
  return x

17.3-5

在题目12.7-1的基础上，我们再增加一个属性\(x.mingap\)来表示以\(x\)为根的子树中，最接近的两个数的差值。对于所有叶节点\(l\)，都有\(l.mingap=\infty\)。

那么，对于所有非叶节点，\(mingap\)属性满足

\[x.mingap=min\{x.left.mingap, x.key-x.prev.key,x.succ.key-x.key,x.right.mingap\}\]

因此，根据这个更新策略，可以在树上自底向上地更新。我们可以写出插入算法RB-INSERT-MINGAP和删除算法RB-DELETE-MINGAP的代码：

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
RB-UPDATE-MINGAP(T, z)
  z.mingap = min{z.left.mingap, z.right.mingap}
  if z.prev != T.nil
    z.mingap = z.key - z.prec.key
  if z.succ != T.nil
    z.mingap = min{z.mingap, z.succ.key - z.key}

RB-INSERT-MINGAP(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.left = T.nil
  z.right = T.nil
  z.color = RED
  z.mingap = ∞
  // 先维护好其前驱和后继
  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
  w = z
  while w != T.nil
    RB-UPDATE-MINGAP(T, w)
    w = w.p
  OS-INSERT-FIXUP-MINGAP(T, w)

OS-DELETE-MINGAP(T, z)
  y = z
  y-original-color = y.color
  if z.left == T.nil
    x = z.right
    RB-TRANSPLANT(T, z, z.right)
  else if z.right == T.nil
    x = z.left
    RB-TRANSPLANT(T, z, z.left)
  else
    y = RB-MINIMUM(T, z.right)
    y-original-color = y.color
    x = y.right
    if y != z.right
      RB-TRANSPLANT(T, y, y.right)
      y.right = z.right
      y.right.p = y     
    else 
      x.p = y
    RB-TRANSPLANT(T, z, y)
    y.left = z.left
    y.rank' = z.rank'
    y.left.p = y
    y.color = z.color
  w = x
  while w != T.nil
    RB-UPDATE-MINGAP(T, w)
    w = w.p
  if y-original-color == BLACK
    OS-DELETE-FIXUP-MINGAP(T, x)

其中，子程序OS-INSERT-FIXUP-MINGAP和题目17.2-2的OS-INSERT-FIXUP-BH基本相同，除了更新节点使用的是RB-UPDATE-MINGAP而不是RB-UPDATE-MINGAP；类似的，子程序OS-DELETE-FIXUP-MINGAP和题目17.2-2的OS-DELETE-FIXUP-BH有着相同的区别。

\(\star\) 17.3-6

令矩形数组是存储在\(R\)中，并且每个矩形具有4\(个属性\)x,X,y,Y\(，分别表示\)x\(坐标的最小值和最大值；\)y$坐标的最小值和最大值。

那么考虑有一条平行于\(y\)轴的直线从左到右扫描整个图形。如果直线检测到有两条矩形的边界相交，那么说明这两个矩形相交。

因此，具体做法是，先将所有矩形的左右边界按\(x\)坐标排序好，接下来从左到右枚举每条左右边界。如果遇到的是左边界，那么就需要判断树中有没有和当前边界相交，并将这条边界添加到区间树中；如果遇到的是有边界，那么就从树中删除掉这条边界。

算法的具体过程由CHECK-RECTANGLE-INTERSEC给出。由于每个矩形的左右边界都总共需要\(3\)次\(O(\lg n)\)的处理，再加上排序的时间，因此其总体时间复杂度为\(O(n\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
CHECK-RECTANGLE-INTERSEC(R, n)
  let E be a new array
  for i = 1 to n
    if C[i].x > C[i].X
      exchange C[i].x with C[i].X
    if C[i].y > C[i].Y
      exchange C[i].y with C[i].Y
    let e, e' be new edges
    let z be a new node
    z.int.low = C[i].y
    z.int.high = C[i].Y
    e.x, e.z, e.type = C[i].x, z, 1
    e'.x, e'.z, e'.type = C[i].X, z, -1
    INSERT(E, e)
    INSERT(E, e')
  sort E using this rule : e.x < e'.x or (e.x == e'.x and e.type < e'.eype)
  Let T be a new interval tree
  for e in E
    if e.type == 1
      if INTERVAL-SEARCH(T, x.int) != T.nil
        return True
      else
        INTERVAL-INSERT(T, x)
    else
      INTERVAL-DELETE(T, x)
  return False