算法导论 B.5 Exercises 答案

B.5-1

自由树和以 $x$ 为根的有根树如下：

以 $x$ 为根的有序树如下：

以 $x$ 为根的二叉树如下：

B.5-2

由于存在 $v_0\in V,\mathrm{\forall }v\in V$，$v_0$ 到 $v$ 都存在路径。因此 $G$ 的无向图版本 $G^{\prime }$ 是一个连通图。

考虑使用反证法证明这是一棵树。假设 $G^{\prime }$ 中存在一个环 $⟨u_0,u_1,\dots ,u_i,u_{i+1},\dots ,u_k⟩$，其中 $u_0=u_k=u,u\in V$。

那么，由于 $G$ 是 DAG，从 $v_0$ 到 $u$ 将有一条路径。那么同样的，从 $v_0$ 到 $v_i,v_{i+1}$ 都有各自的路径。

如图，虚线箭头 $u\to v$ 表示这 $u$ 从 $v$ 有路径可达，实线箭头则意味着有一条有向边从 $u$ 到 $v$。

由于无向图 $G^{\prime }$ 存在环，考虑为边 $(u_i,u_{i+1})$ 标记上箭头。可见，如果标记的是 $u_{i+1}\to u_i$，那么从 $u$ 到 $u_i$ 存在两条有向路径 $⟨v_0,\dots ,u,u_1,\dots ,u_i⟩$ 和 $⟨v_0,\dots ,u,u_{k-1},\dots ,u_{i+1},u_i⟩$，违反了路径中的唯一性；反之亦然。

因此，这个连通图 $G$ 不应该存在环，因此 $G$ 是一棵树。

B.5-3

假设 $F(T)$ 是二叉树 $T$ 中的 $2$ 度节点数，$G(T)$ 是二叉树 $T$ 的叶子节点数。那么问题转化成证明对于所有二叉树 $T$，都有 $F(T)=G(T)-1$。

考虑只有一个节点的树 $O$，那么 $F(O)=0,G(O)=1,F(O)=G(O)-1$ 成立。

以下分别按照两种情况归纳：

1

由上图构造出来的树中，左子树 $L$ 或者右子树 $R$ 为空。不失一般性，假设非空的是 $L$。那么新构造的树 $T$ 中，多了一个 $1$ 度节点 $v_0$。此时 $F(T)=F(L),G(T)=G(L)$，仍有 $F(T)=G(T)-1$。

2

新构造出来的树中，左子树 $L$ 或者右子树 $R$ 都非空。那么有 $F(L)=G(L)-1,F(R)=G(R)-1$。那么新构造的树 $T$ 中，多了一个 $2$ 度节点 $v_0$。那么 $F(T)=F(L)+F(R)+1,G(T)=G(L)+G(R)$。

那么有：

$F(T)=F(L)+F(R)+1=G(L)-1+G(R)-1+1=G(L)+G(R)-1=G(T)-1$。

因此原结论成立。

假设 $I(T)$ 是满二叉树 $T$ 的内部节点数，$J(T)$ 是满二叉树 $T$ 的叶子节点数。那么问题转化成证明对于所有满二叉树 $T$，都有 $I(T)=J(T)-1$。

考虑只有一个节点的树 $O$（可以发现这是满二叉树）。那么 $I(O)=0,J(O)=1,I(O)=J(O)-1$ 成立。

如果 $L,R$ 都是满二叉树，那么如图构造的树 $T$ 一定也是满二叉树。

目前已经满足 $I(L)=J(L)-1,I(R)=J(R)-1$，考虑 $I(T)$ 和 $J(T)$ 的关系。

不难发现，$v_0$ 是 $T$ 的内部节点，因此 $I(T)=I(L)+I(R)+1$。而叶子节点数直接相加即可，因此有 $J(T)=J(L)+J(R)$。

那么有：

$I(T)=I(L)+I(R)+1=J(L)-1+J(R)-1+1=J(L)+J(R)-1=J(T)-1$。

因此原结论成立。

B.5-4

本题将使用数学归纳法进行证明。假设构造出的 $k$ 个叶节点的满二叉树为 $T(k)$。

当 $k=1$ 时，不难发现只有 $1$ 个节点的树为满二叉树 $T(1)$，此时恰有一个叶节点。

当 $k>1$ 时，假设从 $1\sim k-1$ 个叶节点的满二叉树都能构造出，考虑题目 8.5-3 中的图。令 $L=T(1),R=T(k-1)$，那么节点 $v_0$ 的度数为 $2$，因此不是叶子节点。由 $v_0,L,R$ 新构造出的树恰好维持着满二叉树的性质，并且有 $1+(k-1)=k$ 个叶子节点。这颗新构造出来的满二叉树即为 $T(k)$。

B.5-5

令 $h(n)$ 为有 $n$ 个节点的二叉树的高度的下界。也就是说，目标是证明 $h(n)\ge \lfloor \lg n\rfloor$。

可以发现对于 $n>1$，$h(n)\ge h(n-1)$ 必定成立。因为节点数越多，数的深度的下界肯定越高。

当树只有 $n=1,2$ 个节点时，树的高度为恰好为 $\lg n$，原结论成立。

假设对于 $\mathrm{\forall }i,1\le i\le n$，原结论均成立。考虑 $n+1$ 个节点时的树。

当 $n+1$ 不是 $2$ 次幂时，有 $\lfloor \lg n\rfloor =\lfloor \lg (n+1)\rfloor$。那么 $h(n+1)\ge h(n)\ge \lfloor \lg n\rfloor =\lfloor \lg (n+1)\rfloor$。证明结束。

否则，假设左子树有 $k$ 个节点，那么右子树有 $(n+1)-1-k=n-k$ 个节点。

那么按照题目 8.5-3 中的图，可以得到，$\mathrm{\forall }1\le k<n,h(n+1)\ge max(h(k),h(n-k))+1$ 成立。即：

$$h(n+1)\ge \underset{k=1}{\overset{n-1}{min}}\{max(h(k),h(n-k))+1\}$$

那么当 $k=(n+1)/2$ 时，上面的最小值能够取到。因此有 $h(n+1)\ge h((n+1)/2)+1\ge \lfloor \lg (n+1)-1\rfloor +1\ge \lfloor \lg (n+1)\rfloor$。原结论成立，证明结束。

$\star$ B.5-6

本题将使用数学归纳法进行证明。

假设 $I(T)$ 是满二叉树 $T$ 的内部节点数，$J(T)$ 是满二叉树 $T$ 的叶子节点数，$i(T)$ 为树的内部路径，$e(T)$ 为树的外部路径。那么原结论化为，证明对于所有的满二叉树 $T$，都有 $i(T)-e(T)=2I(T)$。

考虑只有一个节点的树 $O$（可以发现这是满二叉树）。有 $i(O)=e(O)=I(O)=0$，因此 $i(O)-e(O)=2I(O)$ 成立。

如题目 8.5-3 中的图所示，如果 $L,R$ 都是满二叉树，那么构造的树 $T$ 一定也是满二叉树。注意到，当 $T$ 如此被构造后，原来属于子树 $L,R$ 中所有节点的深度都增加了 $1$。并且都满足 $i(L)-e(L)=2I(L),i(R)-e(R)=2I(R)$。

那么根据 $i$ 的定义可以写出 $i(T)=i(L)+i(R)+I(L)+I(R)$。注意后面两项产生的原因是：由于 $T$ 构造出来后，左子树的 $I(L)$ 个内部节点和右子树的 $I(R)$ 个节点深度都增加了 $1$。

类似的，根据 $e$ 的定义，可以写出 $e(T)=e(L)+e(R)+J(L)+J(R)$。

那么有：

$\begin{array}{rl}i(T)-e(T)& =e(L)-i(L)+e(R)-i(R)+J(L)-I(L)+J(R)-I(R)\\ & =(e(L)-i(L))+(e(R)-i(R))+(J(L)-I(L))+(J(R)-I(R))\\ & =2I(L)+2I(R)+1+1& (A)\\ & =2(I(L)+2I(R)+1)\\ & =2I(T)& (B)\end{array}$

变换 $(A)$ 使用了题目 8.5-3 中的结论：$J(T)-I(T)=1$。对于变换 $(B)$，由于 $v_0$ 是 $T$ 的内部节点，因此 $I(T)=I(L)+I(R)+1$。

原结论成立。

$\star$ B.5-7

本题将使用数学归纳法进行证明。

为方便描述，令 $l(T)$ 表示树 $T$ 中的所有叶节点。那么本题的目标则是证明 ${\displaystyle \sum _{x\in l(T)}w(x)\le 1}$。

考虑一棵空树 $E$，没有叶节点。因此 ${\displaystyle \sum _{x\in l(E)}w(x)=0\le 1}$，原结论成立。

考虑一棵只有一个节点的树 $O$，恰好有一个叶节点。因此 ${\displaystyle \sum _{x\in l(O)}w(x)=1\le 1}$，原结论成立。

如题目 8.5-3 中的图所示，假设子树 $L,R$ 都满足 ${\displaystyle \sum _{x\in l(L)}w(x)\le 1,\sum _{x\in l(R)}w(x)\le 1}$。注意到，新构造出来的树 $T$ 中，原来属于子树 $L,R$ 中所有节点的深度都增加了 $1$。这意味着，对于 $L,R$ 中所有的叶子节点，其新权值为旧权值的 ${\displaystyle \frac{2^{-(d+1)}}{2^{-d}}}={\displaystyle \frac{1}{2}}$。

那么根据刚刚的假设，可以得到 ${\displaystyle \sum _{x\in l(L)}w(x)+\sum _{x\in l(R)}w(x)\le 2}$

因此，有 ${\displaystyle \sum _{x\in l(T)}w(x)={\displaystyle \frac{1}{2}}(\sum _{x\in l(L)}w(x)+\sum _{x\in l(L)}w(x))\le {\displaystyle \frac{1}{2}}\cdot 2=1}$

原结论成立。

$\star$ B.5-8

本题将使用反证法进行证明。

假设这棵树为 $T$。由于叶节点数量超过 $2$。因此根据 8.5-3 的结论，这棵树必定存在一个内部节点 $r$。考虑使用 $r$ 节点定根，使 $T$ 成为一棵有根树。

令 $S(u)$ 表示以 $u$ 为根的子树中，叶节点的个数。那么按照题意有 $S(r)=L$。

假设不存在任何节点 $u\in V$，使得 ${\displaystyle \frac{L}{3}}\le S(u)\le {\displaystyle \frac{2L}{3}}$ 成立。也就是说，对于所有节点 $u$，要么 $S(u)<{\displaystyle \frac{L}{3}}$，要么 $S(u)>{\displaystyle \frac{2L}{3}}$。

考虑构造树 $T$ 中一条从根节点到某个叶子的路径 $⟨v_0,v_1,v_2,\dots ,v_d⟩$，其中 $v_0=r,v_d$ 是某个叶子，即 $S(v_d)=1$。对于 $0\le i<d$，构造方式如下：

• 如果 $v_i$ 有两个子节点，设其为 $l_i,r_i$。如果 $S(l_i)\ge S(r_i)$，那么 $v_{i+1}=l_i$，否则 $v_{i+1}=r_i$。
• 如果 $v_i$ 有一个子节点，那么 $v_{i+1}$ 是 $v_i$ 的那个唯一一个子节点。

那么按照这个构造方式，$\mathrm{\forall }0\le i<d,{\displaystyle \frac{S(v_{i+1})}{S(v_i)}}\ge {\displaystyle \frac{1}{2}}$ 都成立。因此序列 $\{S(v_i)\}$ 是一个不递减序列。

考虑自顶向下遍历这条路径。如果当前节点 $v_i$ 满足 ${\displaystyle \frac{L}{3}}\le S(v_i)\le {\displaystyle \frac{2L}{3}}$，那么 $v_i$ 为所求节点，证明结束。否则，如果存在某个 $j,0<j<d$，使得 $S(v_j)>{\displaystyle \frac{2L}{3}},S(v_{j+1})<{\displaystyle \frac{L}{3}}$ 成立，那么得到 ${\displaystyle \frac{S(v_{j+1})}{S(v_j)}}<{\displaystyle \frac{1}{2}}$，与构造的 $\{S(v_i)\}$ 序列的性质矛盾。

因此原结论成立。