算法导论17.1 Exercises 答案

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

17.1-1

一开始$x$在根节点$T.root,i=10$。

  • 现在计算出$r=x.left.size+1=12+1=13>i$，因此将从$x$转移到左子节点$x.left$；此时$x.key=17$。
  • 现在计算出$r=x.left.size+1=7+1=8<i$，因此将从$x$转移到右子节点$x.right$，并从$i$减去$r$，得到$i=2$；此时$x.key=21$。
  • 现在计算出$r=x.left.size+1=2+1=3>i$，因此将从$x$转移到左子节点$x.left$；此时$x.key=19$。
  • 现在计算出$r=x.left.size+1=0+1=1<i$，因此将从$x$转移到右子节点$x.right$，并从$i$减去$r$，得到$i=1$；此时$x.key=20$。
  • 现在计算出$r=x.left.size+1=0+1=1=i$，这说明$x$节点为所求，算法结束。

17.1-2

一开始$y$指向$x$，并且$r=x.left.size+1=0+1=1$。

  • 由于目前$x==x.p.left$，因此不做任何操作，并将$x$指向它的父节点；此时$x.key=38$。
  • 由于目前$x==x.p.right$，因此对$r$添加$r.left.size+1$，得到$r=1+1+1=3$，并将$x$指向它的父节点；此时$x.key=30$。
  • 由于目前$x==x.p.left$，因此不做任何操作，并将$x$指向它的父节点；此时$x.key=41$。
  • 由于目前$x==x.p.right$，因此对$r$添加$r.left.size+1$，得到$r=3+12+1=16$，并将$x$指向它的父节点；此时$x.key=26$，并且算法终止。

17.1-3

算法OS-SELECT的非递归版本如下：

1
2
3
4
5
6
7
8
9
10
OS-SELECT-NONRECURSIVE(T, i)
  while True
    r = x.left.size + 1
    if i == r
      return x
    else if i < r
      x = x.left
    else
      x = x.right
      i = i - r

17.1-4

如下是OS-KEY-RANK的伪代码，它是自顶向下实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
OS-KEY-RANK(T, k)
  x = T.root
  rk = 0
  while x != T.nil
    r = x.left.size + 1
    if x.key < k
      rk = rk + r
      x = x.right
    else if x.key == k
      rk = rk + r
      return rk
    else
      x = x.left
  // k不在T中，那么有rk个比k小的键。
  return rk + 1

17.1-5

先求出节点$x$的排名$r$，再查找排名为$r+i$的节点，即为$x$的第$i$个后继，具体过程由算法ITH-SUCCESSOR给出，由于它仅仅是调用了一次OS-SELECT和一次OS-RANK，因此其时间复杂度仅为$O(\lg n)$。

1
2
3
4
ITH-SUCCESSOR(T, x, i)
  r = OS-RANK(T, x)
  y = OS-SELECT(T, r + i)
  return y

17.1-6

令属性$x.rank’$表示以$x$为根节点的子树中，节点$x$所在这棵子树的排名。因此可以发现，$x.rank’$和$x.size$的关系满足$x.rank’=x.left.size+1$。考虑直接维护属性$rank’$的值。

那么对于一次插入节点$z$的操作，如果$z$在$x$的左子树，那么$x$的排名需要增加$1$（因为$x.key>z.key$）。完成插入操作后，只需要执行平常的FIXUP操作即可，插入算法由OS-INSERT'给出。其中，OS-INSERT-FIXUP'操作和RB-INSERT-FIXUP基本相同，它的区别仅仅是旋转子程序将使用后面编写的OS-LEFT-ROTATE'和OS-RIGHT-ROTATE'，之后子程序OS-DELETE-FIXUP'和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
OS-INSERT'(T, z)
  x = T.root
  y = T.nil
  while x != T.nil
    y = x
    if z.key < x.key
      x.rank' = x.rank' + 1
      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.rank' = 1
  OS-INSERT-FIXUP'(T, z)

删除算法由OS-DELTTE'给出。对于即将被删除的$y$节点的唯一一个儿子$x$，自底向上遍历其所有祖先$p$，如果$x$在$p$的左子树，那么需要对$p$的排名减去$1$。此外，他这里使用的是子程序RB-TRANSPLANT，因为这个操作并不会对原来的节点的排名$rank’$产生任何改变。

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
OS-DELETE'(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.root
    if w == w.p.left
      w.p.rank' = w.p.rank' - 1
    w = w.p
  if y-original-color == BLACK
    OS-DELETE-FIXUP'(T, x)

其中，OS-INDERT-FIXUP'和OS-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
OS-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.rank' = y.rank' + x.rank'

OS-RIGHT-ROTATE'(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
  y.rank' = y.rank' - x.rank'

17.1-7

对于序列$A$的第$i$个数$A[i]$，满足$jA[i]$的$j$的个数相当于是$i$减去$A[i]$在以$A[1:i]$中构成的红黑树的排名$r$，因为数组$A[1:i]$中，有$i-r$个数大于$A[i]$，因此，计算逆序数的算法由程序CAL-INVERSION'给出。每轮迭代都需要进行两个操作：加入一个节点和进行一次查询，它们都需要$O(\lg n)$的时间复杂度，因此整个算法的时间复杂度为$O(n\lg n)$。

1
2
3
4
5
6
7
8
9
10
CAL-INVERSION'(A, n)
  let T be a new red-black tree that support size attribute.
  inversion = 0
  for i = 1 to n
    Let p be a new node
    p.key = A[i]
    p.left = T.nil
    P.right = T.nil
    OS-INSERT(T, p)
    inversion = inversion + (i - OS-RANK(T, p))

$\star$ 17.1-8

假设所有输入是区间$[0,2\pi)$中的一个数。那么对于任意一条弦$C_i=(l_i,r_i),l_i\le r_i$，如果弦$C_j$和$C_i$相交，那么$l_j$和$r_j$有且仅有一个节点在区间$(l_i,r_i)$中。不是一般性，假设满足$l_i<l_j$当且仅当$i<j$，那么$C_i$和$C_j$相交此时满足$l_j<r_i<r_j$。

为此，我们可以提出如下算法：首先对弦按照左端点进行排序，接下来依次枚举每条弦$C_j$，计算出此前已经有多少个$r_i$在区间$(l_j,r_j)$中，之后再将$r_j$插入红黑树中即可。具体算法由CAL-PAIRS-INTERSECT给出。

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
// 计算树中有多少个键小于k
OS-LT-OR-LE-COUNT(T, k, op)
  x = T.root
  count = 0
  while x != T.nil
    r = x.left.size + 1
    if (op == LT and x.key < k) or (op == LE and x.key <= k)
      count = count + r
      x = x.right
    else
      x = x.left
  return count

CAL-PAIRS-INTERSECT(C, n)
  let T be a new red-black tree that support size attribute.
  for i = 1 to n
    if C[i].left > C[i].right
      exchange C[i].left with C[i].right
  sort C by C[i].left nondecreasingly
  pairs-cnt = 0
  for i = 1 to n
    t = OS-LT-OR-LE-COUNT(T, C[i].right, LT) - OS-LT-OR-LE-COUNT(T, C[i].right, LE)
    pairs = pairs + t
    Let p be a new node
    p.key = C[i].right
    p.left = T.nil
    P.right = T.nil
    OS-INSERT(T, p)
  return pairs

子程序OS-LT-OR-LE-COUNT是从根节点遍历到某一个叶节点，因此其时间复杂度为树高$O(\lg n)$。程序CAL-PAIRS-INTERSECT一开始先对所有弦进行排序，花费了$O(n\lg n)$的时间。之后每次迭代中，进行了两次OS-LT-OR-LE-COUNT询问和一次插入节点，总共需要花费$O(\lg n)$的时间，因此这个算法的总体运行时间为$O(n\lg n)$。