算法导论19.4 Exercises 答案
19.4-1
正如MAKE-SET操作的第2行所示，一个节点的\(rank\)属性会被初始化为\(0\)。
当节点\(x\)是其所在的树的根时，按照定义，有\(x=x.p\)，因此有\(x.rank=x.p.rank\)。原来的不等式成立。
当节点\(x\)不是其所在的子树的根时，那么有\(x\neq x.p\)，令\(y=x.p\)。不难发现，\(y\)是有两种途经得到的：调用LINK，根节点\(x\)被链接到根节点\(y\)下；或者是调用FIND后，经过路径压缩得到\(x.p=y\)。
首先讨论第1种情况。可见，在LINK操作中，必定有\(x.rank\le
y.rank\)（否则，LINK操作之后不会有\(x.p=y\)）。如果在LINK操作执行前，有\(x.rank<y.rank\)，那么执行之后不会改变两个节点的\(rank\)属性；如果有\(x.rank=y.rank\)，那么按照\(y.rank\)的值会提升\(1\)，从而保证操作结束仍然满足\(x.rank<y.rank\)。
对于第2种情况，在对\(x\)执行FIND操作前，有一条从\(x\)到\(y\)的路径\(v_1,v_2,\dots,v_k\)，其中\(v_1=x,v_k=y\)，根据第1种情况的结论，有\(v_1.rank<v_2.rank<\dots<v_k.rank\)，因此\(v_1.rank<v_2.rank\)，路径压缩完成后，有\(x.rank<y.rank\)，原结论仍然成立。
因此，由于\(x.p\neq x\)，小于号是严格成立的。
\(rank\)的变化只发生在LINK操作中。当\(x\neq x.p\)时，\(x\)不是其所在子树的根，因此\(x\)从此不会作为LINK的参数，即\(x.rank\)不会再变化。此外，根据LINK代码的第5行可知，\(rank\)属性不会下降，因为它只会在某次满足if条件的操作中对其进行加\(1\)。
19.4-2
考虑使用归纳法来进行证明这个结论。
当\(n=1\)时，无需进行任何UNION操作，也就是说，最大\(rank\)属性有\(\lfloor\lg
1\rfloor=0\)，因此原结论成立。
当\(n>1\)时，假设对于\(k=1,2,\dots,n-1\)，\(rank\)属性的最大值均为\(\lfloor\lg k\rfloor\)。那么考虑\(k=n\)时的情况，假设现在有两棵非空的子树，大小分别为\(a,b\)（满足\(a+b=n\)，不失一般性，假设\(1\le a\le b<n\)），那么考虑如下两种情况：
两棵树的最大\(rank\)属性\(\lfloor\lg a\rfloor\)和\(\lfloor\lg b\rfloor\)满足\(\lfloor\lg a\rfloor\neq\lfloor\lg b\rfloor\)。那么对这两棵树进行
LINK操作时，第4行代码判断必定为FALSE，最终合并后的树的\(rank\)属性为\(\lfloor\lg b\rfloor\le \lfloor\lg n\rfloor\)，原结论成立。\(\lfloor\lg a\rfloor\)和\(\lfloor\lg b\rfloor\)满足\(\lfloor\lg a\rfloor=\lfloor\lg b\rfloor\)。那么对这两棵树进行
LINK操作时，第4行代码判断必定为TRUE，最终合并后的树的\(rank\)属性为\(\lfloor\lg a\rfloor+1\)。由于\(1\le a\le b<n\)，这意味着\(a\le n/2\)，因此有\(\lfloor\lg a\rfloor+1\le\lfloor1+\lg (n/2)\rfloor=\lfloor\lg n\rfloor\)。因此原结论成立。
最终，原结论得证。
19.4-3
根据题目19.4-3可知，\(rank\)属性的最大值为\(\lfloor\lg n\rfloor\)。为了保证从\(0\)到\(m\)中的所有整数都被正确表示，需要\(\lceil\lg(m+1)\rceil\)比特才能正确表示。因此最终答案为\(\lceil\lg(\lfloor\lg n\rfloor+1)\rceil\)。
19.4-4
假设一个长度为\(m(m\ge
n)\)的操作序列中，包含了\(n\)次MAKE-SET操作，\(a(a<n)\)次UNION操作，其余为FIND-SET操作。每一次MAKE-SET操作仅仅是将节点信息初始化，花费\(O(1)\)的时间。每一次UNION操作可以分解成两次FIND-SET和一次\(O(1)\)时间的LINK操作。最终，这个长度为\(m\)的序列可以视为是\(a+n\)次的\(O(1)\)操作和\(m-n-a+2a=m-n+a<m\)次FIND-SET操作。由于整棵树的深度最多为\(\lfloor\lg n\rfloor\)，因此这\(m\)次的时间开销为\(m\cdot O(\lg n)+2n\cdot O(1)=O(m\lg
n)\)。
19.4-5
不正确。考虑从\(x\)起的向根方向的三个节点\(x,y,z\)，并且有\(x.rank=1,y.rank=4,z.rank=5\)。那么可以得知，\(A_2(1)=7>4,A_1(1)=3\le 4\)，因此有\(\text{level}(x)=1\)同时可以得知\(A_1(4)=9>5,A_0(4)=5\)，因此有\(\text{level}(y)=0\)。
也就是说，\(\text{level}\)值并非是自底向上单调递增的，因此原结论错误。
19.4-6
对于一次FIND-SET操作，假设除去递归调用所消耗的时间，其单次调用所产生的开销最多为常数\(c\)。那么令\(\phi_q'(x)=c\cdot\phi_q(x),\Phi_q'=c\cdot\Phi_q\)，引理19.8和推论19.9,
19.10和19.14的推理使用\(\phi'_q\)，都需要对它们的系数都要乘上\(c\)。
对于19.14的最后一步推理，对这\(s\)个节点的实际花费为\(\displaystyle{\sum_{i=1}^s w_i\le
cs}\)。此外，由于其至少有\(s-(\alpha(n)+2)\)的势\(\phi'_q\)至少下降了\(c\)（因为当初\(\phi_q\)至少下降了\(1\)），因此这次的FIND-SET操作的均摊开销为：
\(\begin{aligned} \sum_{i=1}^s\widehat{w_i}&=\sum_{i=1}^sw_i+\Delta\Phi'_q\\ &\le cs+\Delta\Phi'_q\\ &\le cs-c\cdot(s-\alpha(n)+2)\\ &=c\cdot\alpha(n)-2c\\ &\le c\cdot\alpha(n) \end{aligned}\)
由于\(c\)为常数，因此这次FIND-SET操作的均摊开销为\(O(\alpha(n))\)。
\(\star\) 19.4-7
按照定义，有\(\alpha'(n)=\alpha(\lg(n+1))\)。
如果\(\alpha'(n)\le 3\)，那么意味着\(\alpha(\lg(n+1))\le 3\)，根据\(\alpha\)的范围定义，可以得出\(\lg(n+1)\le 2047\)，也就是\(n\le 2^{2047}-1\)，这已经远远超过了我们所需要的实际值范围。因此对于\(n\)的所有实际值，均有\(\alpha'(n)\le 3\)。
接下来证明这\(m\)个操作序列的时间复杂度可以达到\(O(m\alpha'(n))\)。我们可以进一步证明：\(\text{level}(x)<\alpha'(n)\)，这是因为：
\(\begin{aligned} A_{\alpha'(n)}(x.rank)&\ge A_{\alpha'(n)}(1)\\ &\ge \lg(n+1)\\ &> \lfloor\lg n\rfloor\\ &\ge x.p.rank&\qquad(A) \end{aligned}\)
其中步骤\((A)\)是根据题目19.4-2得出的。因此有\(\text{level}(x)<\alpha'(n)\)。
此外，对于等式19.7，我们构造出类似的势函数\(\phi_q'(x)\)：
\(\phi'_q(x)= \left \{\begin{aligned} &\alpha'(n)\cdot x.rank & & \text{if } x\text{ is a root or }x.rank=0 \\ &(\alpha'(n)-\text{level}(x))\cdot x.rank-\text{iter}(x)& & \text{if } x\text{ is not a root and }x.rank>1 \\\end{aligned}\right.\)
那么，引理19.8相当于是证明\(0\le \phi'_q(x)\le \alpha'(n)\cdot x.rank\)，证明过程和原版完全一致，由此可以因此类似的推论19.9：对于一个非根节点\(x\)并且\(x.rank>1\)，有\(\phi_q'(x)<\alpha'(n)\cdot x.rank\)。引理19.10, 19.11, 19.12, 19.13的证明过程和原版一致，最终得到这\(m\)个操作序列的总时间复杂度为\(O(m\alpha'(n))\)。