最后更新: 2025-01-22 09:58 查看: 79 次纠错评论(0) 课件开VIP

霍夫曼算法

霍夫曼算法 设 $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$ 的最优树。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：最优树

下一篇：连通度与块

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