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

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

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

证明 ：把频率最小的两个字母称为 \(l_1\) 和 \(l_2\) 。它们必定是兄弟结点，因为 buildHuff 在构建过程的第一步就选中了它们。假设 \(l_1\) 和 \(l_2\) 不是树中最深的结点。在这种情况下，哈夫曼树必定如图 7.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 创建出具有最小外部路径长度的哈夫曼树。