算法导论18.2 Exercises 答案

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

18.2-1

如下是在\(t=2\)的B树中，按序插入这些字母的姿态变化过程。

  • F
graph TD
  A[F];
  • S
graph TD
  A[F S];
  • Q
graph TD
  A[F Q S];
  • K
graph TD
  A[Q];B[F K];C[S];
  A---B;A---C;
  • C
graph TD
  A[Q];B[C F K];C[S];
  A---B;A---C;
  • L
graph TD
  A[F Q];B[C];C[K L];D[S];
  A---B;A---C;A---D;
  • H
graph TD
  A[F Q];B[C];C[H K L];D[S];
  A---B;A---C;A---D;
  • T
graph TD
  A[F Q];B[C];C[H K L];D[S T];
  A---B;A---C;A---D;
  • V
graph TD
  A[F Q];B[C];C[H K L];D[S T V];
  A---B;A---C;A---D;
  • W
graph TD
  A[F Q T];B[C];C[H K L];D[S];
  E[V W]
  A---B;A---C;A---D;A---E;
  • M
graph TD
  A[Q];B[F K];C[T];D[C];
  E[H];F[L M];G[S];H[V W];
  A---B;A---C;B---D;B---E;
  B---F;C---G;C---H;
  • R
graph TD
  A[Q];B[F K];C[T];D[C];
  E[H];F[L M];G[R S];H[V W];
  A---B;A---C;B---D;B---E;
  B---F;C---G;C---H;
  • N
graph TD
  A[Q];B[F K];C[T];D[C];
  E[H];F[L M N];G[R S];H[V W];
  A---B;A---C;B---D;B---E;
  B---F;C---G;C---H;
  • P
graph TD
  A[Q];B[F K M];C[T];D[C];
  E[H];F[N P];G[R S];H[V W];
  I[L];
  A---B;A---C;B---D;B---E;
  B---I;B---F;C---G;C---H;
  • A
graph TD
  A[Q];B[F K M];C[T];D[A C];
  E[H];F[N P];G[R S];H[V W];
  I[L];
  A---B;A---C;B---D;B---E;
  B---I;B---F;C---G;C---H;
  • B
graph TD
  A[Q];B[F K M];C[T];D[A B C];
  E[H];F[N P];G[R S];H[V W];
  I[L];
  A---B;A---C;B---D;B---E;
  B---I;B---F;C---G;C---H;
  • X
graph TD
  A[Q];B[F K M];C[T];D[A B C];
  E[H];F[N P];G[R S];H[V W X];
  I[L];
  A---B;A---C;B---D;B---E;
  B---I;B---F;C---G;C---H;
  • Y
graph TD
  A[Q];B[F K M];C[T W];D[A B C];
  E[H];F[N P];G[R S];H[X Y];
  I[L];J[V];
  A---B;A---C;B---D;B---E;
  B---I;B---F;C---G;C---J;
  C---H;
  • D
graph TD
  A[K Q];B[B F];C[M];D[T W];
  E[A];F[C D];G[H];H[L];
  I[N P];J[R S];K[V];L[X Y];
  A---B;A---C;A---D;B---E;
  B---F;B---G;C---H;C---I;
  D---J;D---K;D---L;
  • Z
graph TD
  A[K Q];B[B F];C[M];D[T W];
  E[A];F[C D];G[H];H[L];
  I[N P];J[R S];K[V];L[X Y Z];
  A---B;A---C;A---D;B---E;
  B---F;B---G;C---H;C---I;
  D---J;D---K;D---L;
  • E
graph TD
  A[K Q];B[B F];C[M];D[T W];
  E[A];F[C D E];G[H];H[L];
  I[N P];J[R S];K[V];L[X Y Z];
  A---B;A---C;A---D;B---E;
  B---F;B---G;C---H;C---I;
  D---J;D---K;D---L;

18.2-2

  • 考虑算法B-TREE-SEARCH的DISK-READ。由于这个DISK-READ每次都是读取当前节点的子节点信息，因此一路向下查找并不会造成读取冗余。

  • 考虑算法B-TREE-CREATE的DISK-WRITE。树\(T\)只会被建立一次，因此这里只会写入一次节点，没有写入冗余。

  • 考虑算法B-TREE-SPLIT-CHILD第16-18行的DISK-WRITE。节点\(x\)添加了一个关键字和一个子节点指针；\(y\)节点挪去了一半的关键字和子节点指针到新节点\(z\)。也就是说，\(x,y,z\)都进行了相应的变化，需要更新，因此这里没有写入冗余。

  • 考虑B-TREE-INSERT-NONFULL的DISK-READ和DISK-WRITE。DISK-READ的分析和B-TREE-SEARCH一致，它都是只读取当前节点的某一个子节点的信息，向下查找不会造成读取冗余。DISK-WRITE只是对叶节点进行了一次写入（因为插入了一个元素），因此DISK-WRITE操作也不是冗余的。

总而言之，无论是DISK-READ还是DISK-WRITE操作，都没有冗余。

18.2-3

可以注意到，如下图这棵B树目前每一个节点都是满的，它的高度达到了最小高度\(2\)。

graph TD
  A[4 8 12];B[1 2 3];C[5 6 7];D[9 10 11];
  E[13 14 15]
  A---B;A---C;A---D;A---E;

这棵B树不可能是某一个插入操作序列所得到的一棵B树。不失一般性，假设它的根节点为\(r\)。在插入这\(15\)个关键字的最后一个关键字之前的B树\(T'\)，它只有\(2\)层，考虑两种情况：

  1. 存在某个叶子节点\(l\)不是满的，那么根节点\(r\)必定是满的。当进行这个插入操作时，先检测到根节点\(r\)是满的，那么根节点\(r\)必定需要拆分，从而导致这棵树的树高增加。

  2. 所有叶子节点都是满的，只有根节点不是满的。这种情况是不可能出现的，如果根节点非满，那这棵B树最多只有\(4\)个节点，最多存储满\(3\times3+2=11\)个关键字，不到\(15\)个。

因此哪怕只有\(14\)个关键字且高度为\(2\)的B树，按照上面的论证，插入一个关键字后，树必定会增高，因此不存在某种插入序列使得这棵B树保持最小的高度，也就是\(2\)。

\(\star\) 18.2-4

首先，每次插入操作都保证了每个节点包含至少一个关键字，因此第\(n\)次操作的节点数\(N(n)\)不超过\(n\)，因此有\(N(n)=O(n)\)。同时，每个节点最多只能包含\(3\)个关键字，因此\(N(n)\ge n/3\)，因此可以得到\(N(n)=\Omega(n)\)。最终可以得知\(N(n)=\Theta(n)\)。

更进一步的分析是，由于每次插入的关键字都比之前的大，因此插入算法B-TREE-INSERT-NONFULL只会遍历最右边的子节点。并且，每次分裂算法执行后，左边的子节点都只剩下一个元素，此后这些节点再也不会被遍历到。也就是说，只有从\(r\)到最右边的叶子节点路径上的所有节点才有可能有多个关键字。因此接下来我们只考虑这条路径上的所有节点。

可以观察得到，这条路径上有\(f(n)\)个节点，其中\(f(n)=j\)当且仅当满足\(2^{j}+j\le n+2\le 2^{j+1}+j\)。

此外，还可以得到这条路径上，倒数第\(i\)个节点的关键字个数具有一定的规律，只要路径长度开始超过\(i\)，那么从第\(2\)个值起（第\(1\)个值是特殊的，为\(1\)），其节点数是一个周期为\(2^i\)的循环节，先是\(2^{i-1}-1\)个\(1\)，再是\(2^{i-1}\)个\(2\)，然后是一个\(3\)。总而言之，这条路径上的关键字总数\(g(n)\)不超过\(3n\)。

因此\(N(n)=n-g(n)+f(n)\)，其中\(g(n)=\Theta(f(n))\)，因此\(N(n)=\Theta(n)\)。以下表的第\(n\)行第\(i\)个值表示最右路径中，插入关键字\(n\)后，倒数第\(i\)个节点的关键字个数。

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
1
2
3
2 1
3 1
2 2
3 2
2 3
3 1 1
2 2 1
3 2 1
2 3 1
3 1 2
2 2 2
3 2 2
2 3 2
3 1 3
2 2 1 1
3 2 1 1
2 3 1 1
3 1 2 1
2 2 2 1
3 2 2 1
2 3 2 1
3 1 3 1
2 2 1 2
3 2 1 2
2 3 1 2
3 1 2 2
2 2 2 2
3 2 2 2
2 3 2 2
3 1 3 2
2 2 1 3
3 2 1 1 1
2 3 1 1 1
3 1 2 1 1
2 2 2 1 1
3 2 2 1 1
2 3 2 1 1
3 1 3 1 1
2 2 1 2 1
3 2 1 2 1
2 3 1 2 1
3 1 2 2 1
2 2 2 2 1
3 2 2 2 1
2 3 2 2 1
3 1 3 2 1
2 2 1 3 1
3 2 1 1 2
2 3 1 1 2
3 1 2 1 2
2 2 2 1 2
3 2 2 1 2
2 3 2 1 2
3 1 3 1 2
2 2 1 2 2
3 2 1 2 2
2 3 1 2 2
3 1 2 2 2
2 2 2 2 2
3 2 2 2 2
2 3 2 2 2
3 1 3 2 2
2 2 1 3 2
3 2 1 1 3
2 3 1 1 1 1
3 1 2 1 1 1
2 2 2 1 1 1
3 2 2 1 1 1
2 3 2 1 1 1
3 1 3 1 1 1
2 2 1 2 1 1
3 2 1 2 1 1
2 3 1 2 1 1
3 1 2 2 1 1
2 2 2 2 1 1
3 2 2 2 1 1
2 3 2 2 1 1
3 1 3 2 1 1
2 2 1 3 1 1
3 2 1 1 2 1
2 3 1 1 2 1
3 1 2 1 2 1
2 2 2 1 2 1
3 2 2 1 2 1
2 3 2 1 2 1
3 1 3 1 2 1
2 2 1 2 2 1
3 2 1 2 2 1
2 3 1 2 2 1
3 1 2 2 2 1
2 2 2 2 2 1
3 2 2 2 2 1
2 3 2 2 2 1
3 1 3 2 2 1
2 2 1 3 2 1
3 2 1 1 3 1
2 3 1 1 1 2
3 1 2 1 1 2
2 2 2 1 1 2
3 2 2 1 1 2

18.2-5

只需要判断当且节点是不是一个叶子节点即可。如果是叶子节点，那么使用另一个最小度数\(t'\)然后再对这个叶子节点进行相同的分割操作即可。

如下是对插入算法和节点拆分算法B-TREE-SPLIT-CHILD的改写：

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
CAL-T(x)
  if x.leaf == True
    return t'
  else
    return t

B-TREE-SPLIT-CHILD'(x, i)
  y = x.c_{i}
  z = ALLOCATE-NODE()
  z.leaf = y.leaf
  z.n = CAL-T(z) - 1
  for j = 1 to CAL-T(z) - 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 = CAL-T(y) - 1
  for j = x.n + 1 downto i + 1
    x.c_{j+1} = x.c_{j}
  x.c_{j+1} = z
  for j = x.n downto i
    x.key_{j+1} = x.key_{j}
  x.key_{i} = y.key_{CAL-T(y)}
  x.n = x.n + 1
  DISK-WRITE(y)
  DISK-WRITE(z)
  DISK-WRITE(x)

B-TREE-INSERT'(T, k)
  r = T.root
  if r == 2 * CAL-T(r) - 1
    s = B-TREE-SPLIT-ROOT(T)
    B-TREE-INSERT-NONFULL(s, k)
  else B-TREE-INSERT-NONFULL(r, k)

B-TREE-INSERT-NONFULL'(x, k)
  i = x.n
  if x.leaf
    while i >= 1 and k < x.key_{i}
      x.key_{i + 1} = x.key_{i}
      i = i - 1
    x.key_{i + 1} = k
    x.n = x.n + 1
    DISK-WRITE(x)
  else
    while i >= 1 and k < x.key_{i}
      i = i - 1
    i = i + 1
    DISK-READ(x, c_{i})
    if x.c_{i}.n == 2 * CAL-T(x.c_{i}) - 1
      B-TREE-SPLIT-CHILD'(x, i)
      if k > x.key_{i}
        i = i + 1
    B-TREE-INSERT-NONFULL'(x.c_{i}, k)

18.2-6

由于单个节点中有\(O(t)\)个关键字，因此节点内部进行一次二分查找需要\(O(\lg t)\)的时间。由于整棵树的高度为\(O(\log_t n)\)，因此在B树中进行一次元素查找需要\(O(\lg t\cdot \log_t n)=O(\lg n)\)的时间，这种查找方式最终将时间复杂度中的\(t\)消去了。

18.2-7

由于进行一次查找操作需要\(h=O(\log_t{n})\)次的读取，因此花费在磁盘读取上面的时间为\(h\cdot (a+bt)=O((a+bt)\log_{t}n)\)。

令\(f(t)=(a+bt)\log_t n=\dfrac{\ln n}{\ln t}(a+bt)\)。可以求得\(f'(t)=\ln n\left(\dfrac{b}{\ln t}-\dfrac{a+bt}{t\ln^2 t}\right)\)。

令\(f'(t)=0\)，可以化简得到\(b=\dfrac{a+bt}{t\ln t}\)。

代入\(a=5,b=10\)，使用Mathematica求解这个方程，可以得到\(t\approx 3.18097\)。由于\(t\)为整数，且\(f(3)<f(4)\)，因此取\(t=3\)是一个最优值。