算法导论17.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 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]\)，满足\(j<i\land A[j]>A[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)\)。