Alone Cáfe
There is no limit to learning.
阿龙咖啡
哈夫曼树

最优二叉树 —— 哈夫曼树

路径与路径长度

  • 路径:从树中一个节点到另一个节点的分支构成这两个节点之间的路径
  • 路径长度:路径上的分支数目
  • 树的路径长度:从树根到每一个节点的路径长度之和

加权路径长度

若考虑节点的权值情况,可以拓宽路径长度的概念。节点的加权路径长度可以定义为路径长度与节点上权值的乘积

树的加权路径长度

树的加权路径长度为树中所有叶子节点的加权路径长度之和

\textit{WPL}=\sum_{k=1}^n(\omega_k \times l_k)

哈夫曼树

设有 n 个权值 ( \omega_1, \omega_2, … , \omega_n ) ,可以构造一棵有 n 个叶子节点的二叉树,其中加权路径长度 WPL 最小的二叉树称作最优二叉树哈夫曼树

例:有 4 个叶子节点 a、b、c、d ,分别带有权值 7、5、2、4 。尝试构造三颗树如下

https://yenyu.cn/wp-content/uploads/2020/03/image-12.png

这些树的 WPL(加权路径长度)分别是

\textit{WPL}_a=7\times2+5\times2+2\times2+4\times2=36
\textit{WPL}_b=7\times3+5\times3+2\times1+4\times2=46
\textit{WPL}_c=7\times1+5\times2+2\times3+4\times3=35

可以验证(也包括其他情况),\textit{WPL}_c 最小,树 c 即是哈夫曼树

应用:最佳判定算法

例如,编制一个将百分制转换为五级分制的程序,一般做法如下

if (score < 60) level = "bad";
else if (score < 70) level = "pass";
    else if (score < 80) level = "general";
        else if (score < 90) level = "good";
            else level = "excellent";

实际生活中,学生的成绩在 5 个等级上的分布是不均匀的

https://yenyu.cn/wp-content/uploads/2020/03/image-13.png

可以看出,80% 的概率需要进行 3 次以及 3 次以上的比较才能得出结果,所以此程序在概率上可以进行优化

可以使用 \text{5, 15, 40, 30, 10} 为权值构造一棵有 5 个叶子节点的哈夫曼树

哈夫曼算法:构造哈夫曼树

  1. 根据给定的 n 个权值 \{ \omega_1, \omega_2, … , \omega_n \} 构成 n 棵二叉树的集合 F = \{ T_1, T_2, … , T_n \} ,其中每棵二叉树 T_i 中只有一个带权的为 \omega_i 的根节点(左右子树皆为空)
  2. F选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树,置新的二叉树的根节点的权值为其左右子树上跟节点的权值之和
  3. F删除这两棵树,并将合成得到的二叉树加入集合 F
  4. 重复第 2、3 步,直到 F 只含一棵树为止,此树即是哈夫曼树

上面的例子构造哈夫曼树的具体过程如下

https://yenyu.cn/wp-content/uploads/2020/03/image-14.png

赞赏
知识共享许可协议本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。欢迎转载、使用、重新发布,但务必保留文章署名。

发表评论

textsms
account_circle
email

阿龙咖啡

哈夫曼树
最优二叉树 —— 哈夫曼树 路径与路径长度 路径:从树中一个节点到另一个节点的分支构成这两个节点之间的路径路径长度:路径上的分支数目树的路径长度:从树根到每一个节点的路径长度…
扫描二维码继续阅读
2020-03-24