算法导论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))$。