算法导论16 Problems 答案

16-1

a

定义二进制反射格雷码序列$ak$的差分序列为$d(a_k)=\langle a{k,1}\text{ xor }a{k,0},a{k,2}\text{ xor }a{k,1}\,a{k,3}\text{ xor }a{k,2},\dots,a{k,2^k-1}\text{ xor }a_{k,2^k-2}\rangle$。也就是说，$d(a_k)$的长度为$2^k-1$。

现在证明，$\forall k\ge 1,d(a_k)$是一个对称的序列。

当$k=1$时，可以知道$d(a_1)=\langle1\rangle$。这是一个对称的序列。

当$k>1$时，按照从$a{k-1}$到$a{k}$的构造可以发现，$d(ak)$的前$2^{k-1}-1$个元素和$d(a{k-1})$完全相同，而$d(ak)$的后$2^{k-1}-1$个元素恰好是$d(a{k-1})$的逆序$\text{rev}(d(a{k-1}))$，$d(a_k)$中间那个元素的值为$2^{k-1}$。也就是说，$d(a{k})=d(a{k-1})\Vert\langle 2^{k-1}\rangle\Vert\text{rev}(d(a{k-1}))$。因此，$d(a_k)$仍然是对称的。

可以发现，$d(a_k)$的第$i$个元素表示的是最大的整数$x$使得$2^x\mid i$。那么这个程序的设计和算法INCREMENT非常类似。这个过程将由DETERMINE-FLIP给出。

// I表示这个下标二进制数组，k表示这个数组的大小。
DETERMINE-FLIP(I, k)
  i = 0
  while i < k and I[i] == 0
    i = i + 1
  return i

b

算法GEN-BINARY-REFLECTED-GRAY-CODE给出了产生一个长度为$2^k$的$k$位反射格雷码算法。这个算法的特点是在第4行执行了$2^k$次子程序INCREMENT'。按照前文的分析，这$2^k$次执行INCREMENT'的运行时间之和为$\Theta(2^k)$。如果for循环中的其它所有单次操作的时间均有常数上限，那么算法GEN-BINARY-REFLECTED-GRAY-CODE的运行时间之和为$\Theta(2^k)$。

// 假设算法INCREMENT'的过程和INCREMENT完全相同，区别在于INCREMENT'会在最后将i值返回。
GEN-BINARY-REFLECTED-GRAY-CODE(k)
  let I[0 : k], J[0 : k] be new array by 0
  m = pow(2, k)
  for s = 1 to m
    parse J as k-bit binary reflected Gray code and show it
    i = INCREMENT'(I, k)
    // 按照题目条件，这个步骤是常数花费的。
    if i < k
      J[i] ^= 1

16-2

a

直接遍历这$k$个数组，每个数组$Ai$执行一次二分查找，如果查找到了及时返回，否则继续查找下一个数组。因此在最坏情况下，每个数组都为满且进行了一次查找，因此在最坏情况下这个算法的时间复杂度为$O\displaystyle{\left(\sum{i=0}^{k-1} \lg 2^i\right)}$，即$O(k^2)=O(\lg^2n)$。

b

首先简单地将数插入到$A0$，这时只需要花费$O(1)$的代价。如果$A_0$原本就已满，那么就复制到$A_1$中，如果$A_1$也是满的，那么有序合并$A_0,A_1$，并复制到$A_2$中，以此类推，从低级别的数组转移到高级别数组。如果当前有$n=2^k-1$个元素，并且再执行一次插入操作，那么就会达到最坏情况。此时数组$A_0,A_1,A_2\dots,A{k-1}$中的所有数都需要清空，合并后放到$A_{k}$中。由于合并两个有序数组的开销是线性的，这时将会达到最坏的时间复杂度$O(2^k)$，即$O(n)$。

考虑INSERT操作的均摊代价。每次操作支付$1$美元，用于当前的插入操作，并且预支$k-1$美元，用于后续将这个元素从低级数组转移到高级数组。由于这个$n$元集合最多只有$k$个数组，并且所有元素只会从低级数组转移到高级数组，因此这些操作足以不产生任何的欠费。因此，无论是否处于最坏情况，一个INSERT操作均摊后只需要花费$O(k)$的代价，即$O(\lg n)$。

c

令$p$为最小的整数使得数组$Ap$不为空。如果所要删除的元素$x$在$A_p$，那么删除$x$，并以$O(2^p)$的时间将$A_p$剩余的元素全部转入$A_0,A_1,\dots,A{p-1}$中。否则，假设$x$在$Aq(q>p)$中，那么从$A_q$中删除元素$x$，并且从$A_p$中挑选一个元素$x$放到$q$中，以$O(2^q)$的时间使序列$A_q$有序，接下来就和之前一样，继续将$A_p$剩下的所有元素全部转入$A_0,A_1,\dots,A{p-1}$中。

因此，DELETE的单次操作的时间复杂度为$O(2^q)=O(n)$。当元素个数恰好为$2^x-1$时，轮流进行INSERT, DELETE, INSERT, DELETE, ...操作时将会达到最坏情况，每次产生$O(n)$个元素的位置变化，此时均摊分析失效。

最终，单次操作的平均运行时间为$O(n)$。

16-3

a

重构出一棵$\dfrac{1}{2}$平衡二叉树由算法REBUILD-BALANCED-TREE给出。它先将原本树$T$的中序遍历结果求出，使用$O(T.root.size)$的空间存储这个结果。然后再以这个中序遍历的结果的中点作为根节点，然后左半部分和右半部分分别进行递归。划分出中点后，左半部分和右半部分的子节点数最多相差$1$，因此是满足$\dfrac{1}{2}$平衡的条件的。

在算法REBUILD-RUN中，一个中序遍历的结果被均匀划分成两半。令$T(n)$表示用长度为$n$的序列构造出一棵$\dfrac{1}{2}$平衡的二叉树的运行时间，那么有$T(n)=2T(n/2)+1$，最终不难得出$T(n)=\Theta(n)$。

REBUILD-RUN(L, p, r)
  if p > r
    return NIL
  m = ⌊(p + r) / 2⌋
  l = REBUILD(L, p, m - 1)
  r = REBUILD(L, m + 1, r)
  L[m].left = l
  L[m].right = r
  return L[m]

REBUILD-BALANCED-TREE(T)
  // 将T的中序遍历结果存放在L中。
  generate inorder traversal list L of T
  T.root = REBUILD-RUN(L, 1, n)
  n = L.size
  return T

b

令$U(n)$表示在一棵$\alpha$平衡二叉树中进行查找的时间。根据$\alpha$平衡的定义，如果当前树的节点个数为$n$，那么它的两个子树的节点数都不超过$\alpha n$。因此有$U(n)\le U(\alpha n)+1$。由于$\alpha<1$，根据主定理，可以得到$U(n)=O(\lg n)$。

c

由于$\Delta(x)$的定义最外部有一个绝对值符号，因此$\Delta(x)\ge 0$必定成立。也就是说，$\Phi(T)\ge 0$必定成立。

如果一棵树是$T$满足$\Phi(T)=0$，那么相当于$\forall x\in T,\Delta(x)\le 1$均成立。如果一个节点的两棵子树的节点树相等，那么这个节点必定是一个$\dfrac{1}{2}$平衡节点；如果一棵子树的节点子树的节点数相差$1$，假设左子树为$x$，右子树为$x+1$，整棵树一共有$x+x+1+1=2x+2$个节点，右子树的节点数占比数仍然不超过$\dfrac{1}{2}$。因此，如果一棵二叉树$T$是一个$\dfrac{1}{2}$平衡二叉树，那么$\Phi(T)=0$。

d

不失一般性，假设子树$T$中的某个节点$x_0\in T$不满足$\alpha$平衡的情况。那么有$x_0.left.size>\alpha x_0.size$。

那么可以推出$x_0.right.size< x_0.size-\alpha x_0.size-1<(1-\alpha)x_0.size$。

在这种情况下，有$\Delta(x_0)=x_0.left.size-x_0.right.size>(2\alpha-1)x_0.size$。

不考虑$T$中的其它节点的情况，可以知道，$\displaystyle{\Phi(T)=c\sum_{x\in T:\Delta(x)\ge 2}\Delta(x)>c\Delta(x_0)=c(2\alpha-1)x_0.size}$。

如果$x.size$个单位的势能够支付重建$x.size$个节点子树的代价，那么有$\Phi(T)>x_0.size$，并且每个节点平均只会摊分了常数代价。为了保证此式成立，令$c(2\alpha-1)x_0.size>x_0.size$，最终得到$c>\dfrac{1}{2\alpha}$。

e

继续进行16-3-d的讨论。每个节点的均摊成本为常数。

由于这棵树是$\alpha$平衡的，根据题目16-3-b的结论，无论进行一次插入操作还是进行一次删除操作，都只需要$O(\lg n)$的运行时间。需要注意的是，无论是哪种操作，本质上都是在一棵树上的某个节点$x$进行操作。操作完成后，只有从根节点$T.root$到$x$这条路径之间的所有节点都需要进行$\alpha$平衡性判断，这条路径上一共有$O(\lg n)$个节点。一次操作完成后，如果有多个节点不再满足$\alpha$平衡性质，那么就选择深度最浅的那个节点$p$进行重构。这次操作导致了路径$p$到$x$中，所有的$\Delta$值都发生了改变。由于这些节点至多有$O(\lg n)$个，每个节点的均摊成本为常数，因此进行一次操作的均摊成本为$O(\lg n)$。