最后更新: 2025-01-22 09:58 ● 参与者查看: 11 次纠错分享参与项目词条搜索

霍夫曼算法

霍夫曼算法 设 $n$ 个权 $w_1, w_2, \cdots, w_n, w_1 \leqslant w_2 \leqslant \cdots \leqslant w_n$ 。
首先构造 $n$ 棵树的集合 $F=\left\{T_1, T_2, \cdots, T_n\right\}$ ，其中每棵二分树 $T_i$ 中只有一个带权为 $w_i$ 的根顶点，其左右子树为空。然后在 $F$ 中选取两个带最小权 $w_1$ 和 $w_2$ 的顶点作为树叶，构造一棵二分树，且新二分树的根顶点的权值为其左右子树是根顶点权值之和。于是得到 $n-1$ 棵树，它的根分别带权 $w_1+w_2, \cdots, w_n$ ，（此时 $w_1+w_2 \leqslant w_3$ 不一定成立）。再在 $n-1$ 棵树中找出两棵根带权最小的树，合并为一棵新的二分树，使得这两棵树分别是它的左，右子树，新的二分树的根带的权为原两棵树根带的权之和，每一步选择两棵根带权最小的树合并为一棵二分树，重复这一过程直到只有一棵二分树为止。该树即为霍夫曼树。

例10．3 求带权为 $1,1,2,3,4,5$ 的最优树。
解题过程由图 10.7 给出，$W(T)=38$ 。
 ![图片](/uploads/2025-01/9d2a7a.jpg)
 
 下面证明霍夫曼算法的正确性。
定理 10.13 霍夫曼算法得到的带权 $w_1, w_2, \cdots, w_n$ 的二分树是最优树。
证明：用归纳法证明。对于有两个权 $w_1, w_2$ ，则根带权 $w_1+w_2$ 的二分树是最优树。
假设对于有 $n-1$ 个权，用霍夫曼算法求出的二分树是带这 $n-1$ 个权的最优树。
现考察有 $n$ 个权的情况，设 $w_1 \leqslant w_2 \leqslant \cdots \leqslant w_n$ 。设 $T$ 是用霍夫曼算法得到的二分树，它的权记为 $W(T)$ 。设 $T_1$ 是带权 $w_1, w_2, \cdots, w_n$ 的一棵最优树，权为 $W\left(T_1\right)$ 。则要证明 $W(T)=W\left(T_1\right)$ 。

在最优树 $T_1$ 中，存在离根最远的分枝点 $v_0$ ，它的儿子 $v_a$ 和 $v_b$ 都是树叶，如果它的权为 $w_a, w_b$而不是 $w_1$ 和 $w_2$ ，就把这两片带权的树叶与带权 $w_1, w_2$ 的树叶交换。交换以后，因为 $v_a$ 和 $v_b$ 是具有最大长度的树叶，而 $w_1, w_2$ 是最小的两个权，所以不会增加树的权，所得到的二分树还是最优树，记为 $T_2, W\left(T_2\right)=W\left(T_1\right)$ 。将 $T_2$ 中 $w_1$ 和 $w_2$ 及其父亲构成的子树用带权 $w_1+w_2$ 的树叶代替，得到一棵带权 $w_1+w_2, w_3, \cdots, w_n$ 的二分树 $T_2{ }^{\prime}$ ，因为 $T_2$ 是最优树，而且 $W\left(T_2\right)=W\left(T_2{ }^{\prime}\right)+w_1+w_2$ 。因此 $T_2$＇是带权 $w_1+w_2, w_3, \cdots, w_n$ 的一棵最优树。

用霍夫曼算法求 $w_1+w_2, w_3, \cdots, w_n$ 的树，由归纳假设，得最优树 $T^{\prime}$ ，再用两片带权 $w_1$ 和 $w_2$ 的树叶及其带权的 $w_1+w_2$ 父亲的二分树回代 $T$＇中的树叶 $w_1+w_2$ ，得到用霍夫曼算法求得的树 $T$ ，显然 $W(T)=W\left(T^{\prime}\right)+w_1+w_2$ 。

由于 $T^{\prime}$ 和 $T_2{ }^{\prime}$ 都是最优树，所以 $W\left(T^{\prime}\right)=W\left(T_2{ }^{\prime}\right)$ 。则有 $W(T)=W\left(T^{\prime}\right)+w_1+w_2=W\left(T_2{ }^{\prime}\right)+w_1+w_2=$ $W\left(T_2\right)=W\left(T_1\right)$ 。因此 $T$ 是一棵带权 $w_1, w_2, \cdots, w_n$ 的最优树。

上一篇：最优树

下一篇：连通度与块

本文对您是否有用？有用 (0) 无用 (0)