6.8 赫夫曼树在线视频

同学们,大家好

我是云南大学信息学院教师孔兵

这节课我们讨论赫夫曼树

前面几节我们讨论了二叉树的定义

性质和操作

这节课我们讨论二叉树的一个应用

最优二叉树或叫赫夫曼树

首先定义几个概念

树中的路径是指树中一个结点到另一个结点之间的分支

构成这两个结点之间的路径

一般所讨论的路径都是指祖先到它的某个子孙之间的路径

比如说，分支,< B, C>,构成了A到D的路径

路径的长度，是指路径上的分支的数目

A到D的路径长度是3

树的路径长度，是指从树根到每个结点的路径长度之和

结点的带权路径长度，指的是结点到根的路径长度乘以结点的权值

例如，结点k带权值wk

结点k到根的路径长度为lk

那么，结点k的带权路径长度为wk*lk

树的带权路径长度，是指所有叶结点的带权路径长度之和

如果数中有n个叶结点，1到n

那么，树的带权路径长度WPL等于从1到n每个叶结点的带权路径长度之和

在树的带权路径长度的概念上，我们定义了最优二叉树

也叫赫夫曼树

假设有n个权值，w1到wn，试构造一棵有n个叶子结点的二叉树

每个叶子结点带权为wi

针对这样叶结点带权的二叉树

我们可以计算它的树的带权路径长度

则我们把其中带权路径长度WPL最小的二叉树

我们可以计算它的树的带权路径长度

则我们把其中带权路径长度WPL最小的二叉树

称为最优二叉树或者叫赫夫曼树

下面通过一个例子直观的来看一下

假设有4个叶子结点，a, b, c, d.它们分别带有权值

7，5，2，4。构造有这样4个叶子的二叉树

就形态上来说有很多种

图中我们给了三个例子

分别计算这三棵树的带权路径长度

它们的带权路径长度分别是36, 46和35

第3棵树就是一棵最优二叉树

我们注意到图3的带权路径长度最小，为什么呢？

我们观察发现，图3中，权值大的结点到根的路径长度小

例如，a的权值为7，路径长度1

权值小结点到根的路径长度大

例如，c的权值为2，路径长度3

图2正好相反，其带权路径长度最大

从上面的讨论可以看出，要让树的带权路径长度最小

基本的策略应该是权值大的，应该离根近一些

这样路径小，它的带权路径长度比较小

而权值小的，哪怕是路径长些

它本身权值比较小，增长的量也不大

可以直观地总结一下，一棵二叉树

要使树的带权路径长度最小

那么，权值大的结点应该离根近一些

权值小的呢，远一点也无所谓

前面介绍了最优二叉树

那么，最优二叉树有什么用呢？

下面我们用一段转换5分制的代码

作为最优二叉树应用的一个例子

假设有这样一个需求，要把1万个输入的分数转换为5分制

为了实现这个转换，可以用if-else的嵌套语句来完成

有如幻灯片上的一段代码

如果输入分数a小于60，那么转换为不及格

否则，如果小于70，转换为及格

再否则，如果小于80，转换为中等

再否则，如果小于90，转换为良好

再否则呢，转换为优良

if-else语句是两个分支的结构4

可以用如图所示的一棵判定树来描述这段代码

判定树中尖框是用来描述一个if-else语句的

比如说第1个尖框，它描述if(a<60) 这个if-else语句

a小于60，如果为真则不及格

否则，进入第二尖框

第二个尖框是描述if(a<70)这个嵌套的if-else语句

其它尖框类似，矩形框描述一个赋值语句

也就是具体的转换

因为if-else语句两个分支的特点，判定树是一棵二叉树

我们用判定树描述if-else语句

目的是为了比较直观的分析代码的执行效率

这段代码中，基本的操作是比较

我们自然可以通过执行过程中比较的次数多少

来度量其执行的效率

从图中可以看到，每个尖框中是进行1次比较

而不同分数转换需要的比较次数是不一样的

例如，要转换一个中等的分数

需要做三次的比较，就是a<60，a<70，a<80这三次

要转换一个良好的分数需要4次比较

转换一个不及格的分数只要1次比较

应该注意到，每个分数赋值的矩形框是二叉树的一个叶子

这个分数转换需要的比较次数是它的路径的长度

如中等矩形框的路径长度就是3

基于判定树，我们来分析一下代码执行的效率

一般来说

分数是呈正态分布的

看表中，不及格的占0.05，最少

及格的占0.15，中等的占0.4

最多，良好的占0.3，优良占0.1

如果这1万个输入数据满足这样的分布

我们可以基于判定树计算比较的次数

用每个分数段的人数乘该分数段转换所需的比较次数

再求和，公式见幻灯，

那么，转换1万个这样的输入数据

总共需要进行31,500次比较

如果把分数段的人数（或比例）看做叶子的权值

比较次数是路径长度的话

总的比较次数就是判定树的带权路径长度

观察计算过程，我们注意到不合理之处

就是中等和良好人数很多

转换分别需要3次和4次比较，而人数很少的不及格

转换只需要1次比较

这就引起了我们的思考

如果占比多的分数，能通过少的比较次数来进行转换

代码执行的效率应该能够提高

基于这个思想，我们重新设计了一个判定树

因为中等人数最多，首先比较是a否大于等于70小于80

如果为真则直接转换为中等

否则考虑占比第二多的良好

如果a大于等于80小于90，转换为良好

再否则考虑占比第三的及格

如果a大于等于60小于70，转换为是及格

后面再比较一次，确定不及格和优秀

当然，我们注意到这个判定树中有的比较框中是要进行两次比较的

为此，把它展开，如图中下部所示

每个比较框只有一次比较

如果基于这棵判定树进行分析

作为占比最多的中等，它的路径长度为2

它的转换需要2次比较

占比次多的良好也是需要2次比较，如不及格需要3次比较

和上一张幻灯片的方法相同

同样处理上述的1万个数据，需要的比较次数

总共是22,000次，也就是带权路径长度是22,000

上一张幻灯片的带权路径长度是31,500

减少比较次数近三分之一

我们可以说，这是一棵比上一棵更优的二叉树

实际上，它就是以5个分数段人数（或比例）为叶子权值的最优二叉树

我们可以基于这个判定树，重新写if-else嵌套语句的代码段

实现分数转换，具体怎么写，请大家思考完成

这是最优二叉树一个典型的应用

确实提高了程序执行的效率

那么，最优二叉树是怎么来的呢？

下面我们看一下最二叉树的构造

赫夫曼树的构造

第1是初始化

根据给定的n个权值w1到wn

我们先构成n棵二叉树的集合F

它有n棵二叉树T1到Tn

其中，每棵二叉树Ti中,只有一个带权为wi的根结点

其左右子树均为空

第2在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树

且置新的二叉树的根结点的权值为其

左右子树上根结点的权值之和

第3在二叉树集合F当中删除，这两棵权值最小的数

同时将新得到的二叉树加入F中

第4重复2，3两步，直到F中只含一棵树为止

这样构造的，获得的便是一棵最优二叉树

下面我们通过一个例子来看一下

假设有5个权值，2，5，6，7，9

初始化，构造F集合中的只有一个根结点的5棵二叉树

每个根带一个权值

随后，执行第2步，从这5棵二叉树中

挑选根结点的权值最小的两棵树

例中是红圈代表的2和5

按照第3步，以2和5为左右子树构造一棵新的树

新树根的权值为左右子树权值之和为7

随后，从集合F中删除2和5这两棵子树

把新生成的子树加入到F中

现在，如图1所示，F中有4棵二叉树

经过2,3两步后， F中删除2棵

增加1棵，二叉树从5棵变为4棵

重复2，3两步。挑出红圈中的6，7

因为7有两个，挑另1个7也是可以的

不会影响最优二叉树的构造

只是二叉树的形态会不同

结果如图2所示。继续重复2，3两步，挑出7，9

构造结果如图3所示

只有两棵子树，最终把这两个子树构造为一棵二叉树

如图4所示

棵树的WPL=65，这就是带权路径长度最小的二叉树-最优二叉树

5个叶子，通过4次重复2，3两步可以构造出最优二叉树

如果n个叶子的话，需要n-1次重复2，3两步

提醒大家注意，n个叶子的最优二叉树形态并不是唯一的

同学们，这节课就到这儿

我们下次课再见