思考题17-1
a) 对数组中每个数逆序花费 Θ(k)，一个有 n 个数，总时间就是 O(nk)。
BIT_REVERSAL (A) For I = 1 to n do B [I] =A[revk(I)]b) 和书上的二进制计数器递增相似。
BIT-REVERSED-INCREMENT (A) I = A.length A[I] = A[I] + 1 if(A[I] == 1) return I = I - 1 while I ≥ 0 and A[I] = 1 do A[I] = 0 I = I – 1 if I ≥ 0 A[I] = 1类似于书上的分析知可以在 O(n) 时间完成。
c) 由于BIT-REVERSED-INCREMENT独立于位运算。因此还是在 O(n) 时间完成。
思考题17-2
a) SERACH可以在每个已排序的数组上执行搜索操作，由于每个数组都已排序，用二分法搜索其中的某个数组花费 O(lgm)，其中 m 是这个数组的大小。搜索不成功的时间是 Θ(lgm)。最坏的情况下是所有数组都是满的，然后执行搜索不成功，总耗时： T(n)=Θ(lg2k−1+lg2k−2+...+lg21+lg20)=Θ(k−1+k−2+...+1+0)=Θ(k(k−1)/2)=Θ(⌈lg(n+1)⌉⌈lg(n+1)−1⌉/2)=Θ(lg2n) 因此最坏情况是 Θ(lg2n)。
b) 建一个新的大小为 1 的排序数组，里面存放要被插入的元素，若 A0 空，则用新数组替换 A0。否则合并这两个数组成一个大小为 2 的排序数组，若 A1 空，则用合并的数组替换 A1，否则和 A1 和并成大小为 4 的排序数组，就这样一直下去。 分析最坏运行时间，假设合并两个大小为 m 的数组花费 2m 时间，若数组 A0,..,Ak−2 都是满的，则： T(n)=2(20+21+...+2k−2)=2k−2=Θ(n)。 但是用聚合算法分析摊还时间时，从空数组插入 n 次，r 表示二进制中 [nk−1,nk−2...n0] 的最右为 0 的下标，花费：∑j=0r−12⋅2j=O(2r)。此外，r=0 花费一半时间，r=1 用四分之一时间…对每个 r 最多有 ⌈n/2r⌉ 次插入。所以有：O(∑r=0⌈lg(n+1)⌉(⌈n/2r⌉)2r)=O(nlgn)。即摊还代价每次操作时间是 O(lgn)。
c) DELETE(x)操作如下： 1.找到最小的 j 满足有 2j 个元素的数组 Aj 是满的，设 y 是 Aj 的最后一个元素； 2.设 x 在数组 Ai 中，从 Ai 中移除 x，然后将 y 放入 Ai 中，并把 y 放在 Ai 的正确位置； 3.对 Aj 进行下述操作（剩下 2j−1 个元素）：第一个元素放到数组 A0 中，接下来的 2 个元素到数组 A1 中，再接下来的 4 个元素到数组 A2…标记 Aj 为空。 DELETE(x)操作在最坏情况下的代价是 Θ(n)。
思考题17-3
a) 首先排序以 x 为根的子树中是元素。对二叉搜索树排序时间是线性的。假设排序后的是 s1,s2,...sk，选取 s⌊k/2⌋ 做根，将剩下的元素分为两半，然后递归建树；
b) 令 f(n) 表示在一颗有 n 个结点的 α 平衡二叉树中执行一次搜索的时间，则 f(n)≤f(αn)+O(1)，最后有 f(n)∈O(log1/αn)=O(lgn)；
c) 对 1/2 平衡树中的每个结点 x 有： x.left.size+x.right.size+1=x.sizex.left.size≤x.size/2x.right.size≤x.size/2 因此 |x.left.size−x.right.size|≤1，所以 Δ(x)=0。即 1/2 平衡树的势为 0；
d) 假设在结点 x 处会重建，则在重建之前 x 就已经不平衡了，重建之前的势能是: Δ(x)=|x.left.size−x.right.size|≥α⋅x.size−(x.size−α⋅x.size)=(2α−1)x.size。 在重建之后，以 x 为根的子树的势能是 0，势能至少减少了 Δ(x)。为了弥补这一部分代价，满足 c⋅Δ(x)≥x.size 即可。由于Φ(Tx)≥c⋅Δ(x)， 意味着 c(2α−1)≥1；
e) 令 c^i 表示在一颗 n 个结点的 α 平衡树中插入或删除一个结点的摊还时间，若操作不引起树的重建，则 c^i=ci+Φ(Di)−Φ(Di−1)，有 b) 知 ci∈O(lgn)。相似的，树的最大高度是 O(lgn)，插入或删除树中的结点 v 将会改变从结点 x 到 v 的路径上的所有结点的 Δ(x)，因此： Φ(Di)−Φ(Di−1)≤c⋅O(lgn)∈O(lgn)。 若操作引起树的重建，令 ci=c′i+c′′i，其中 c′i,c′′i 分别表示删除后插入和重建的代价。设Di 表示插入或删除后的状态。ci^=c′i+c′′i+[Φ(Di)−Φ(D′i)]+[Φ(D′i)−Φ(Di−1)]，类似于前面有：Φ(D′i)−Φ(Di−1)≤O(lgn)。Φ(D′i) 是重建之前的势能，Φ(Di) 是删除之后的势能，Φ(D′i)−Φ(Di) 是重建之后减少的势能，由 d) 得 c′′i≤Φ(D′i)−Φ(Di)。最后有：ci^≤O(lgn)。
思考题17-4
a) RB-INSERT操作，考虑这种情况，根黑色，根的孩子是红色，根的孩子的孩子是黑色，根孩子的孩子的孩子是红色…当插入一个红色结点作为某个红色结点的孩子时，在情况 1（见十三章）的RB-INSERT-FIXUP操作会有 lg(n+1)/2 次。即 Ω(lgn) 次颜色修改。 对于RB-DELETE，考虑全黑的情况，如果叶结点被删除，则双黑的结点会一直向上到根，即每层的结点颜色都改变，Ω(lgn) 次颜色修改；
b) 除了RB-INSERT-FIXUP的情况 1 和RB-DELETE-FIXUP的情况 2，其余都会终止；
c) RB-INSERT-FIXUP的情况 1 减少了一个红色结点，由图 13.5所示，结点 z 的父节点和叔结点都会从红变黑， z 的祖父从黑变红，因此得证；
d) RB-INSERT的 1-16 行导致一个结点的插入和一个单位的势能增加，非终止情况下的RB-INSERT-FIXUP导致 3 次颜色改变，并减少 1 个势能。终止的情况会有一次旋转但不改变势能；
e) RB-INSERT的 1-16 行的结构性变化和势变化，以及终止性的RB-INSERT-FIXUP都是 O(1)，非终止性的RB-INSERT-FIXUP是 O(lgn)。但是通过摊还分析知RB-INSERT的结构性变化是 O(1)；
f) 由图 13.5，RB-INSERT-FIXUP的情况 1 改变了下面几个地方： 1) 把一个有两个红结点孩子的黑结点变成红色，势能-2； 2) 把带有一个黑孩子结点的红结点变成黑色，势能不变； 3) 对没有红孩子的红结点变成黑色，势能变 1。 总的势能是 -1，支付了结构性变化，因此情况 1 中的结构性变化的摊还分析是 0。终止情况下的RB-INSERT-FIXUP导致 O(1) 的结构性变化，所以最后总的结构性变化的摊还分析是 O(1)。
g) 根据图13.7，RB-DELETE-FIXUP的情况 2 改变了下面几个地方： 1) 把一个没有红孩子结点的黑结点变成红色，势能 -1； 2) 若 B 是红色，则丢失黑色的孩子，势能不变； 3) 若 B 是黑色，从没有红孩子结点到有红孩子结点，势能变 -1 总的变化为 -1 或 -2，无论哪种情况，一个单位的势能变化用于支付结构性变化，因此在情况 2 下的摊还分析的结构性变化至多为 0。终止情况下有 O(1) 变化，因此最后总的结构性变化的摊还分析是 O(1)。
h) 由上面分析知每次操作摊还分析是 O(1)，所以在一颗空的红黑树上进行 m 次RB-INSERT和RB-DELETE操作的最坏情况是 O(m)。
思考题17-5
略
