20.1. 哈夫曼编码最优性的证明¶

哈夫曼树的构建是 贪心算法 的一个例子。 每一步，算法都做出"贪心"决策，合并权值最小的两棵子树。 这使算法很简单，但它能得到期望的结果吗？ 本节最后将证明， 哈夫曼树确实能为给定字母集合给出最高效的排布。 该证明需要下面的引理。

引理 ： 对于由函数 buildHuff 构建的、至少包含两个字母的任意哈夫曼树， 频率最小的两个字母存储在兄弟结点中， 其深度至少与树中任何其他叶结点一样深。

证明 ： 把频率最小的两个字母称为 \(l_1\) 和 \(l_2\) 。 它们必定是兄弟结点，因为 buildHuff 在构建过程的第一步就选中了它们。 假设 \(l_1\) 和 \(l_2\) 不是树中最深的结点。 在这种情况下，哈夫曼树必定如图 12.20.1 所示， 或者与之有效地对称。 要出现这种情形， \(l_1\) 和 \(l_2\) 的父结点 （标记为 \(V\) ）的权值必须大于 标记为 \(X\) 的结点。 否则，函数 buildHuff 会选择结点 \(V\) 而不是结点 \(X\) 作为结点 \(U\) 的子结点。 然而这是不可能的，因为 \(l_1\) 和 \(l_2\) 是频率最小的字母。

下面是证明。

定理 ： 函数 buildHuff 为给定字母集合构建出 具有最小外部路径权值的哈夫曼树。

证明 ： 证明是对字母个数 \(n\) 进行归纳。

• 基本情况 ：对于 \(n = 2\) ，哈夫曼树必然具有最小外部路径权值，因为只可能有两棵树，它们两个叶结点的加权路径长度相同。

• 归纳假设 ：假设任何由 buildHuff 创建的、包含 \(n-1\) 个叶结点的树都具有最小外部路径长度。

• 归纳步骤 ：给定一棵由 buildHuff 构建的、含 \(n\) 个叶结点的哈夫曼树 \(\mathbf{T}\) （ \(n \geq 2\) ），假设 \(w_1 \leq w_2 \leq ... \leq w_n\) ，其中 \(w_1\) 到 \(w_n\) 是各字母的权值。把频率为 \(w_1\) 和 \(w_2\) 的字母的父结点称为 \(V\) 。由引理可知，包含频率为 \(w_1\) 和 \(w_2\) 的字母的叶结点与 \(\mathbf{T}\) 中任何结点一样深。如果树中还有任何其他叶结点更深，我们就可以把它们与 \(w_1\) 或 \(w_2\) 交换，从而减小其加权路径长度。但引理告诉我们不存在这样的更深结点。把与 \(\mathbf{T}\) 完全相同、只是把结点 \(V\) 替换为权值为 \(w_1 + w_2\) 的叶结点 \(V'\) 的哈夫曼树称为 \(\mathbf{T}'\) 。由归纳假设， \(\mathbf{T}'\) 具有最小外部路径长度。把子结点放回 \(V'\) 就恢复了树 \(\mathbf{T}\) ，它必定也具有最小外部路径长度。

因此，由数学归纳法，函数 buildHuff 创建出具有最小外部路径长度的哈夫曼树。