算法导论12.2 Exercises 答案

随着遍历过程的进行，潜在的最大值和最小值区间逐渐减小。如果某个序列中的值不在这个区间里，那么这个检查序列是非法的。

\(\begin{aligned} 2&\in[1,1000]\\ 252&\in[3,1000]\\ 401&\in[253,1000]\\ 330&\in[253,400]\\ 398&\in[331,400]\\ 344&\in[331,397]\\ 363&\in[345,397] \end{aligned}\)

因此本题是一个合法的检查序列。

\(\begin{aligned} 924&\in[1,1000]\\ 220&\in[1,923]\\ 911&\in[221,923]\\ 244&\in[211,910]\\ 898&\in[245,910]\\ 258&\in[245,897]\\ 362&\in[259,897]\\ 363&\in[364,897] \end{aligned}\)

因此本题是一个合法的检查序列。

\(\begin{aligned} 925&\in[1,1000]\\ 202&\in[1,924]\\ 911&\in[203,924]\\ 240&\in[203,910]\\ 912&\not\in[241,910]\\ \end{aligned}\)

因此本题不是一个合法的检查序列。

\(\begin{aligned} 2&\in[1,1000]\\ 399&\in[3,1000]\\ 387&\in[3,398]\\ 219&\in[3,386]\\ 266&\in[220,386]\\ 382&\in[267,386]\\ 381&\in[267,381]\\ 278&\in[237,380]\\ 363&\in[279,380] \end{aligned}\)

因此本题是一个合法的检查序列。

\(\begin{aligned} 935&\in[1,1000]\\ 278&\in[1,934]\\ 347&\in[279,934]\\ 621&\in[348,934]\\ 299&\not\in[348,620]\\ \end{aligned}\)

因此本题不是一个合法的检查序列。

如图所示，路径为\(\{1,2,4\}\)，那么有\(A=\{3\},B=\{1,2,4\},C=\varnothing\)。

令\(a=3,b=1,a\in A,b\in B\)，但是\(a>b\)。故原结论不成立。

如果一个节点\(p\)有两个子节点，那么按照算法TREE-SUCCESSOR的第二行，\(p\)的后继节点是其右子树的最小节点\(t\)。如果这个最小节点具有左子节点\(t.left\)，\(p\)的后继节点将是\(t.left\)，因为\(t.left\)的键比\(t\)还小，因此\(t\)必定没有左子节点。可以通过类似的证明，知道\(p\)的前驱节点是其左子树的最大节点\(u\)，并且\(u\)没有右子节点。

第一步是证明\(x\)的后继节点\(y\)是\(x\)的祖先。假设\(x\)不是\(y\)的祖先，令\(z\)是\(x,y\)的最近公共祖先。根据二叉搜索树的性质，\(x< z< y\)必定成立，因为\(x\)在\(z\)的左子树中，\(y\)在\(z\)的右子树中。\(z\)比\(y\)小，仍依旧比\(x\)大，因此\(y\)不可能是\(x\)的后继节点。因此\(y\)是\(x\)的祖先节点。

第二步是证明原题目的结论。考虑从根节点\(r\)到\(x\)的路径\(P\)。如果节点\(q\)和其右子节点\(q.right\)都在\(P\)上，那么\(x\)在\(q\)的右子树中，有\(q< x\)，因此\(q\)不可能是\(x\)的后继节点。对于路径上任意两个节点\(p,q\)，并且\(p.left,q.left\)都在\(P\)上，并且\(p\)的深度大于\(q\)的深度，那么有\(x< p< q\)，因为\(p\)在\(q\)的左子树中，\(x\)在\(p\)的左子树中，\(q\)不可能是\(x\)的后继。

最终，如果\(x\)没有右子节点，那么其后继节点是最深的节点\(p\)，满足\(p,p.left\)都在从\(r\)到\(x\)的路径中。

此处通过证明二叉搜索树\(T\)中的每一条边最多只需要遍历\(2\)次，总共最多需要遍历\(2n-2\)条边，从而得知这个算法的时间复杂度为\(O(n)\)。

对于任意一个非根节点\(x,x.p\)和\(x\)之间都会有一条边\(e\)。假设\(x\)子树的最小值为\(m\)，最大值为\(M\)，那么两次遍历到边\(e\)的情况分别是：\(m\)的前驱求取它的后继，\(M\)求取它的后继。因为\(m\)的前驱小于\(x\)，因此从\(m\)的前驱遍历到\(M\)必须经过边\(e\)；类似的，\(r\)的后继大于\(x\)，从\(M\)求取它的后继必须经过边\(e\)。最终每条边最多只经过\(2\)次。

由于输入的树规模为\(n\)，因此时间复杂度为\(\Omega(n)\)，最终时间复杂度为\(\Theta(n)\)。

令\(y\)是\(x\)的第\(k\)个后继，考虑从\(x\)到\(z\)的路径为\(P\)。令\(z\)是\(x,y\)的最近公共祖先，那么\(z\in P\)。由于树的高度为\(h\)，因此路径\(P\)的长度最长只有\(2h\)，因此遍历这一条路径至少需要\(O(h)\)的时间。

令节点集合\(S\)为\(x\)的第\(\{1,2,\dots,k\}\)个后继，包括\(x\)本身。令路径\(P_l\)为从\(x\)到\(z.left\)的所有节点，令路径\(P_r\)为从\(z.right\)到\(y\)的所有子节点。

根据二叉搜索树的定义，\(P_l\)上的所有节点的右子树的节点\(u\)都满足\(x< u