算法导论18 Problems 答案

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

18-1

a

在最坏情况下是\(n\)个操作都是PUSH操作，这意味着每次操作都会引起一个页的磁盘存取。也就是说，总共引起\(n\)次磁盘存取，所花费的CPU时间为\(\Theta(nm)\)。

b

在这种情况下，只有\(m\)个PUSH操作才能够填充满一个页。这\(n\)个操作一共产生了\(\left\lceil\dfrac{n}{m}\right\rceil\)个不同的页，因此其磁盘存取次数为\(\left\lceil\dfrac{n}{m}\right\rceil\)，所花费的CPU时间为\(\left\lceil\dfrac{n}{m}\right\rceil\cdot\Theta(m)=\Theta(n)\)。

c

首先将执行\(m\)次PUSH操作，这时整个页面都会被占满。然后剩下的\(n-m\)次操作中，循环执行PUSH, POP, POP, PUSH这\(4\)个操作，每一个周期的第\(1\)个PUSH操作和第\(3\)个POP操作都会进行一次磁盘读取操作。因此，最终所需要的磁盘读取次数为\(\Theta(n)\)次，所花费的CPU时间为\(\Theta(nm)\)。

d

考虑如下场景：快速主存中只有\(2\)个页面，它们用于存储磁盘中的两个相邻的页面\(p,q=p+1\)。完整的PUSH操作和POP操作如下：

  • PUSH操作：如果这\(2\)个页面已经是满的，那么再进行一次PUSH操作后，将第\(p\)个磁盘页面所对应的主存页面写入磁盘，并且将另一个主存页面挪到当前的主存页面（也就是将指针\(p\)加上\(1\)。当然也可以不挪，可以应用类似于循环队列的思想进行管理）。之后再将这个字写入这个内存的字即可。否则直接写入内存的这个字，不执行磁盘存取操作。

  • POP操作：如果这\(2\)个页面都已经是空的，那么将第\(p-1\)个磁盘页面读入主存（也就是将指针\(p\)减去\(1\)），然后再将栈指针减去\(1\)。否则，仅仅是将栈指针减去\(1\)，不执行磁盘存取操作。

那么接下来将证明这个操作的均摊CPU时间为\(O(1)\)，从而证明可以得到均摊的磁盘存取次数为\(O(1/m)\)。

令\(c_i\)表示第\(i\)个操作的实际CPU时间，\(\widehat{c_i}\)表示均摊后的CPU时间。由于一次存取操作花费的CPU时间是\(\Theta(m)\)，因此假设其至多花费的时间为\(cm\)，其中\(c\)是一个常数。令\(\Phi(T_i)\)表示第\(i\)次操作后，主存的两个页面中总共包含的字的个数的\(c\)倍，那么有\(0\le \Phi(T_i)\le 2cm\)。

一开始主存的这两个页面都为空，因此\(\Phi(T_0)=0\)，由于字的个数必定是一个非负整数，因此\(\forall i\in[0,n],\Phi(T_i)\ge \Phi(T_0)\)必定成立，因此\(\Phi\)是一个合适的势函数。对于\(i\in[1,n]\)，令\(\Delta \Phi_i=\Phi(T_i)-\Phi(T_{i-1})\)，那么有\(\widehat{c_i}=c_i+\Delta\Phi_{i}\)，接下来考虑这两个操作的均摊时间。

  • PUSH操作：如果这\(2\)个页面已经是满的，那么这个时候需要花费的CPU时间为\(cm\)。此时\(\Phi(T_{i-1})=2cm,\Phi(T_i)=c(m+1)\)，因此\(\widehat{c_i}=c_i+\Delta\Phi_i\le cm+c((m+1)-2m)=c\)；否则，\(\Delta\Phi_i=c\cdot 1=c,c_i=0\)，此时有\(\widehat{c_i}=c_i+\Delta\Phi_i=c\)，因此总有\(\widehat{c_i}\le c\)成立。

  • POP操作：如果这\(2\)个页面已经是空的，那么这个时候需要花费的CPU时间为\(cm\)。此时\(\Phi(T_{i-1})=c\cdot 0=0,\Phi(T_i)=c(m-1)\)，因此\(\widehat{c_i}=c_i+\Delta\Phi_i\le cm+c(0-(m-1))=c\)；否则，\(\Delta\Phi_i=c\cdot -1=-c,c_i=0\)，此时有\(\widehat{c_i}=c_i+\Delta\Phi_i=-c\)，因此仍总有\(\widehat{c_i}\le c\)成立。

也就是说，\(\forall i\in[1,n],\widehat{c_i}\le c\)均成立。那么根据\(\displaystyle{\sum_{i=1}^n \widehat{c_i}=\sum_{i=1}^n c_i+\Phi(T_n)-\Phi(T_0)}\)，那么得到\(\displaystyle{\sum_{i=1}^n c_i =\sum_{i=1}^n \widehat{c_i}-\Phi(T_n)+\Phi(T_0)\le\sum_{i=1}^n \widehat{c_i}=cn}\)。

也就是说，每一个栈操作的平均运行时间不超过\(c\)，因此其均摊时间复杂度为\(O(1)\)，原结论成立。

18-2

a

维护整棵2-3-4树的所有节点的\(heigh\)属性只有在插入操作中的分裂节点所需要；由于维护\(height\)属性的过程中不会影响树的形态，因此并不会改变查找、插入和删除的属性，如下是维护\(height\)属性的伪代码：

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
2-3-4-TREE-CREATE-H(T)
  x = ALLOCATE-NODE()
  x.leaf = TRUE
  x.height = 0        // 只有一个节点的树的高度为0。
  x.n = 0
  DISK-WRITE(x)
  T.root = x

2-3-4-TREE-SPLIT-CHILD-H(x, i)
  y = x.c_{i}
  z = ALLOCATE-NODE()
  z.leaf = y.leaf
  z.n = t - 1
  for j = 1 to t - 1
    z.key_{j} = y.key_{j+t}
  if not y.leaf
    for j = 1 to t
      z.c_{j} = y.c_{j+t}
  y.n = t - 1
  for j = x.n + 1 downto i + 1
    x.c_{j+1} = x.c_{j}
  x.c_{i+1} = z
  for j = x.n downto i
    x.key_{j+1} = x.key_{j}
  x.key_{i} = y.key_{t}
  x.n = x.n + 1
  DISK-WRITE(y)
  DISK-WRITE(z)
  DISK-WRITE(x)
  z.height = y.height   // 由于是从兄弟节点分裂而来，因此根据B树的性质4，这两棵子树的高度相等。

2-3-4-TREE-INSERT-H(T, k)
  r = T.root
  if r.n == 2 * t - 1
    s = 2-3-4-TREE-SPLIT-ROOT-H(T)
    2-3-4-TREE-INSERT-NONFULL-H(s, k)
  else 2-3-4-TREE-INSERT-NONFULL-H(r, k)

2-3-4-TREE-SPLIT-ROOT-H(T)
  s = ALLOCATE-NODE()
  s.leaf = FALSE
  s.n = 0
  s.c_{1} = T.root
  s.height = T.root.height + 1
  T.root = s
  2-3-4-TREE-SPLIT-CHILD-H(s, 1)
  return s

其中，对于主插入程序2-3-4-TREE-INSERT-H，它和B-TREE-INSERT基本相同，区别在于使用了子程序2-3-4-TREE-SPLIT-ROOT-H来代替B-TREE-SPLIT-ROOT；使用了2-3-4-TREE-INSERT-NONFULL-H来代替B-TREE-INSERT-NONFULL。对于非满插入程序2-3-4-TREE-INSERT-NONFULL-H，它和B-TREE-INSERT-NONFULL基本相同，区别在于使用了子程序2-3-4-TREE-SPLIT-CHILD-H来代替B-TREE-SPLIT-CHILD；以及最后一行递归调用的也是自身。

由于删除操作只是将两个同层的节点合并了（有时是把根节点去掉），查询操作并不影响树的形态，因此查询和删除操作不需要维护\(height\)属性。

b

不失一般性，假设\(T'.root.height> T''.root.height\)，那么求解\(T'\)中属性\(height\)为\(T''.root.height+1\)最右边的节点，设其为\(r\)，那么对节点\(r\)右边添加键\(k\)，并且键\(k\)的右儿子将指向\(T''.root\)，即可得到\(T.root\)。

如果\(T'.root=T''.root\)，那么将键\(k\)独立作为一个节点\(z\)，其中\(T'.root\)是\(z\)的第一棵子树\(z.c_1，T''.root\)是\(z\)的第二棵子树\(z.c_2\)。

更具体的过程由2-3-4-TREE-JOIN给出。可以发现，for循环的迭代次数只取决于\(|h'-h''|\)的值，因此其时间复杂度为\(O(1+|h'-h''|)\)。

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
// 假设全局变量值是t = 2。
2-3-4-TREE-JOIN(T', k, T'')
  Let T be a new 2-3-4-tree
  if T'.root.n == 2 * t - 1
    2-3-4-TREE-SPLIT-ROOT-H(T')
  if T''.root.n == 2 * t - 1
    2-3-4-TREE-SPLIT-ROOT-H(T'')
  if T'.root.height == T''.root.height
    z = ALLOCATE-NODE()
    z.leaf = False
    z.c_{1} = T'.root
    z.c_{2} = T''.root
    z.n = 1
    z.key_{1} = k
    z.height = T'.root.height + 1
    T.root = z
  else if T'.root.height > T''.root.height
    d = T'.root.height - T''.root.height - 1
    z = T'.root
    for i = 1 to d
      DISK-READ(z, z.c_{z.n})
      if z.c_{z.n} == 2 * t - 1
        2-3-4-TREE-SPLIT-CHILD-H(z, z.n)
      z = z.c_{z.n}
    z.n = z.n + 1
    z.key_{z.n} = k
    z.c_{z.n + 1} = T''.root
    T.root = T'.root
  else
    d = T''.root.height - T'.root.height - 1
    z = T''.root
    for i = 1 to d
      DISK-READ(z, 1)
      if z.c_{1} == 2 * t - 1
        2-3-4-TREE-SPLIT-CHILD-H(z, 1)
      z = z.c_{1}
      // 所有子节点指针和关键字都向后挪一步
      for i = z.n downto 1
        z.key_{i + 1} = z.key_{i}
      for i = z.n + 1 downto 1  
        z.c_{i + 1} = z.c_{i}
      z.key_{1} = k
      z.c_{1} = T'.root
    T.root = T''.root
  return T

c

令节点\(x\)是关键字\(k\)所在的节点，\(v_1,v_2,\dots,v_n\)是题目中所提到的路径\(p\)，其中\(v_1=T.root,v_n=x\)。目前先考虑\(S'\)中的关键字，对于\(\forall i\in [1,n]\)，如果\(\exists j:v_i.key_{j}\le k\)，那么令\(l_i\)为满足最大条件的\(j\)，此时可以将节点\(v_i\)的键分裂成两部分：\(v_{i}.key_{1},v_{i}.key_{2},\dots,v_{i}.key_{l_i-1};v_{i}.key_{l_i}\)，并且第一部分的关键字及其相邻的子节点切割成一个新的节点，以其为根的子树作为\(T'_{j-1}\)的一部分，并且\(k'_j=v_i.key_{l_i}\)，继续朝向第\(v_{i+1}=v_i.c_{l_i+1}\)棵子树递归操作；如果\(l_i\)不存在，那么直接访问\(v_{i+1}=v_i.c_{1}\)。当到了第\(n\)层时，切割完节点后终止程序（不用再取\(k'\)）。因此对于\(\forall i\in[1,m]\)，都有\(T'_{i-1}.height\ge T_{i}'.height\)。

对于\(S''\)，其操作过程类似，对于\(\forall i\in [1,n]\)，如果\(\exists j:v_i.key_{j}\ge k\)，那么令\(r_i\)为满足条件最小的\(j\)，此时可以将节点\(v_i\)的键分裂成两部分：\(v_{i}.key_{l_i};v_{i}.key_{l_i+1},v_{i}.key_{l_i+2},\dots,v_{i}.key_{l_i}\)，第二部分的关键字及其相邻的子节点切割成一个新的节点，以其为根的子树作为\(T''_{j-1}\)的一部分，并且\(k''_j=v_i.key_{r_i}\)，继续朝向第\(v_{i+1}=v_i.c_{r_i}\)棵子树递归操作；如果\(r_i\)不存在，那么直接访问\(v_{i+1}=v_i.c_{v_i.n+1}\)，并且不做任何操作。当到了第\(n\)层时，切割完节点后终止程序（不用再取\(k'\)）。

整个过程由2-3-4-TREE-GEN-S'和2-3-4-TREE-GEN-S''给出，由于单个节点的关键字的个数上限为常数，并且它们仅仅是自顶向下找出一条通往叶子节点的路径，因此它们的时间复杂度为\(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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
2-3-4-TREE-GEN-S'(T, k)
  let t be 0-index array, K be 1-index array
  x = T.root
  while True
    DISK-READ(x)
    l = 1
    while l <= x.n and x.key_{l} < k
      l = l + 1
    // 不存在l_i的情况。
    if l == 1 and x.key_{1} > k
      x = x.c_{1}
    else
      is-end = (l <= x.n and x.key_{l} == k)
      if x.leaf and not is-end
        // 在叶节点仍然找不到关键字，那么报错。
        error "not find key: " k 
      if not is-end
        INSERT(K, k.key)
        // x.key_{l} = k，不能进入T[m]，需要去掉。
        l = l - 1
      Let T1 be new tree 
      if l == 0
        T1.root = NIL
      else
        y = ALLOCATE-NODE()
        y.leaf = x.leaf
        y.n = l
        for i = 1 to l
          y.key_{i} = x.key_{i}
        if not y.leaf
          for i = 1 to l + 1
            y.c_{i} = x.c_{i}
        T1.root = y
        DISK-WRITE(y)
      INSERT(t, T1)
      if is-end
        break
      x = x.c_{l + 1}
  return t, K', K'.size

2-3-4-TREE-GEN-S''(T, k)
  let t be 0-index array, K be 1-index array
  x = T.root
  while True
    DISK-READ(x)
    r = x.n
    while r >= 1 and x.key_{r} > k
      r = r - 1
    // 不存在r_i的情况。
    if r == n and x.key_{r} < k
      x = x.c_{x.n + 1}
    else
      is-end = (r >= 1 and x.key_{r} == k)
      if x.leaf and not is-end
        // 在叶节点仍然找不到关键字，那么报错。
        error "not find key: " k 
      if not is-end
        INSERT(K, k.key)
        // x.key_{r} = k，需要去掉。
        r = r + 1
      Let T1 be new tree 
      if r == x.n + 1
        T1.root = NIL
      else
        y = ALLOCATE-NODE()
        y.leaf = x.leaf
        y.n = x.n - r + 1
        for i = r to x.n
          y.key_{i - r + 1} = x.key_{i}
        if not y.leaf
          for i = r to x.n + 1
            y.c_{i - r + 1} = x.c_{i}
          T1.root = y
        DISK-WRITE(y)
      INSERT(t, T1)
      if is-end
        break
      x = x.c_{l + 1}
  return t, K', K'.size

d

根据题目18-2-c的结论，集合\(S'\)通过节点\(m\)被划分成了\(m+1\)块。并且\(\forall i\in[0,m], T'_i\)都是一棵2-3-4树，并且\(\forall i\in[1,m]:\forall x\in T'_{i-1},y\in T'_i,x<k'_i<y,T'_{i-1}.height\ge T'_{i-1}.height\)均成立。那么使用2-3-4-TREE-JOIN算法，从后往前依次将这些树拼接起来，即可得到一个以\(S'\)中的所有节点构成的2-3-4树。对于集合\(S''\)操作也类似。具体过程由2-3-4-TREE-SPLIT-AUX-S'和2-3-4-TREE-SPLIT-AUX-S''分别给出。这些程序使用了子程序2-3-4-TREE-JOIN来拼接。因此，只要按照从低到高进行拼接，那么就能做到时间复杂度为\(O(\lg n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2-3-4-TREE-SPLIT-AUX-S'(t', k', m)
  T' = t'[m]
  for i = m downto 1
    T' = 2-3-4-TREE-JOIN(t'[i - 1], k'[i], T')
  return T'

2-3-4-TREE-SPLIT-AUX-S''(t'', k'', m)
  T'' = t''[0]
  for i = 1 to m
    T'' = 2-3-4-TREE-JOIN(T'', k''[i], t''[i])
  return T''

2-3-4-TREE-SPLIT(T, k)
  t', k', m' = 2-3-4-TREE-GEN-S'(T, k)
  t'', k'', m'' = 2-3-4-TREE-GEN-S''(T, k)
  T' = 2-3-4-TREE-SPLIT-AUX-S'(t', k', m)
  T'' = 2-3-4-TREE-SPLIT-AUX-S''(t'', k'', m)
  return T', T''