5.树与二叉树的应用

哈夫曼树和哈夫曼编码

定义

从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度

树中所有叶结点的带权路径长度之和称为该树的带权路径长度,记作

$$WPL=\sum_{i=1}^nw_{i}l_{i}$$

在含有几个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树

例子

image.png

(a) WPL= 7×2+5×2+2×2+4×2=36
(b) WPL= 4×2+7×3+5×3+2×1=46
(c) WPL= 7×1+5×2+2×3+4×3=35

哈夫曼树的构造

给定$n$个权值分别为$w_{1},w_{2},\dots,w_{n}$,的结点,构造哈夫曼树的算法描述如下:

1. 将这几个结点分别作为$n$棵仅含一个结点的二叉树,构成森林$F$
2. 构造一个新结点,从$F$中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和
3. 从$F$中删除刚才选出的两棵树,同时将新得到的树加入F中
4. 重复步骤2和3,直至$F$中只剩下一棵树为止

从上述构造过程中可以看出哈夫曼树具有如下特点:

1. 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大
2. 构造过程中共新建了$n-1$ 个结点^[1] (双分支结点),因此哈夫曼树的结点总数为$2n-1$
3. 每次构造都选择$2$棵树作为新结点的孩子,因此哈夫曼树中不存在度为1的结点

提示

结论:若度为$m$的哈夫曼树中，叶结点个数为$n$，则非叶结点的个数为$\lceil(n-1)/(m-1)\rceil$
证明:

例如,权值{7,5,2,4}的哈夫曼树的构造过程如图 5.19 所示

image.png

哈夫曼编码

• 在数据通信中,若对每个字符用相等长度的二进制位表示,称这种编码方式为固定长度编码
• 若允许对不同字符用不等长的二进制位表示,则这种编码方式称为可变长度编码
• 若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码

提示

可变长度编码比固定长度编码要好得多,其特点是对频率高的宇符赋以短编码,而对频率较低的宇符则赋以较长一些的编码,从而可以使宇符的平均编码长度减短,起到压缩数据的效果。

我们可将字符的编码解释为从根至该字符的路径上边标记的序列,其中:

• 边标记为0 表示“转向左孩子”
• 标记为1 表示“转向右孩子”

image.png

这棵哈夫曼树的WFL为

$$WPL=1×45+3×(13+12+16)+4×(5+9)=224$$

此处的 WPL 可视为最终编码得到二进制编码的长度,共 224 位。若采用了位固定长度编码,则得到的二进制编码长度为300位,因此哈夫曼编码共压缩了 25%的数据。

利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

并查集

通常用树 (森林)的双亲表示作为并查集的存储结构,每个子集合以一棵树表示。所有表示子集合的树,构成表示全集合的森林,存放在双亲表示数组内。通常用数组元素的下标代表元素名,用根结点的下标代表子集合名,根结点的双亲结点为负数。

image.png

union的优化

采用小树并大树的原则^[2]，构造的树高不超过$\left\lfloor \log_{2} n \right\rfloor+1$

---

1. 也可按照二叉树的性质，$n_0=n2+1$，故$n_2=n-1$ ↩︎

2. 具体实现就是在双亲表示的数组内，不在用-1表示根节点，假设树的结点数为n，用-n表示根节点 ↩︎