算法导论12.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

12.2-1

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

a

$\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}$

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

b

$\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}$

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

c

$\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}$

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

d

$\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}$

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

e

$\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}$

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

12.2-2

1
2
3
4
5
6
7
8
9
10
11
12
13
TREE-MINIMUM(x)
  if x == NIL
    return -1
  else if x.left != NIL
    return TREE-MINIMUM(x.left)
  else return x

TREE-MAXIMUM(x)
  if x == NIL
    return 0
  else if x.right != NIL
    return TREE-MAXIMUM(x.right)
  else return x

12.2-3

1
2
3
4
5
6
7
8
9
TREE-PREDECESSOR(x)
  if x.left != NIL
    return TREE-MAXIMUM(x.left)
  else
    y = x.p
    while y != NIL and x == y.left
      x = y
      y = y.p
    return y

12.2-4

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

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

12.2-5

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

12.2-6

第一步是证明$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$的路径中。

12.2-7

此处通过证明二叉搜索树$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)$。

12.2-8

令$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<p,P_r$上的所有节点的左子树的节点$v$ 都满足$p< v< y$。也就是说，这些节点恰好构成了集合$S$。因此，集合$S$中的节点可以看成是由一系列二叉搜索子树通过一条链串成。根据题目12.2-7的结论，遍历这一系列子树的运行时间之和为$O(k)$。

因此这个算法的总时间复杂度为$O(h+k)$。

12.2-9

简化题意后，对于叶节点$x$，其父节点$y$要么是$x$的前驱，要么是$x$的后继。

  • 当$x$是$y$的左子节点时，有$x< y$。由于$x$没有右子树，因此$\nexists v\in T,x< v < y$成立，因此$y$是$x$的后继。

  • 当$x$是$y$的右子节点时，有$y< x$。由于$x$没有左子树，因此$\nexists v\in T,y< v < x$成立，因此$y$是$x$的前驱。

故原结论成立。