算法导论18 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 4.1k 阅读时长 ≈ 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(T0)=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{ci}=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{ci}\le c$均成立。那么根据$\displaystyle{\sum{i=1}^n \widehat{ci}=\sum{i=1}^n ci+\Phi(T_n)-\Phi(T_0)}$，那么得到$\displaystyle{\sum{i=1}^n ci =\sum{i=1}^n \widehat{ci}-\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$所在的节点，$v1,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$，那么令$li$为满足最大条件的$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{li}$，继续朝向第$v{i+1}=vi.c{li+1}$棵子树递归操作；如果$l_i$不存在，那么直接访问$v{i+1}=vi.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:vi.key{j}\ge k$，那么令$ri$为满足条件最小的$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{ri}$，继续朝向第$v{i+1}=vi.c{ri}$棵子树递归操作；如果$r_i$不存在，那么直接访问$v{i+1}=vi.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''