哈夫曼树

最优二叉树 —— 哈夫曼树

路径与路径长度

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

加权路径长度

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

树的加权路径长度

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

$$\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。尝试构造三颗树如下

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

WPL$_a=7\times2+5\times2+2\times2+4\times2=36$

WPL$_b=7\times3+5\times3+2\times1+4\times2=46$

WPL$_c=7\times1+5\times2+2\times3+4\times3=35$

可以验证(也包括其他情况)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 个等级上的分布是不均匀的

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$ 只含一棵树为止,此树即是哈夫曼树

上面的例子构造哈夫曼树的具体过程如下
image-14.png

📅 更新时间:2021/10/17 Sunday 21:57

🖊️ 本文由 Alone Café 创作,如果您觉得本文让您有所收获,请随意赞赏 🥺
⚖️ 本文以 CC BY-NC-SA 4.0,即《署名-非商业性使用-相同方式共享 4.0 国际许可协议》进行许可
👨‍⚖️ 本站所发表的文章除注明转载或出处外,均为本站作者原创或翻译,转载前请务必署名并遵守上述协议
🔗 原文链接:https://alone.cafe/2020/03/哈夫曼树
📅 最后更新:2021年10月17日 Sunday 21:57

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×