[每日一学] 哈夫曼树(最优二叉树)的概念以及构造
作者:CC下载站 日期:2022-04-08 00:00:00 浏览:57 分类:涨姿势
哈夫曼树产生的背景
在实际生活和生产应用中,我们往往会遇到综合比较一系列的离散量的问题;比如说车站根据包裹的重量以及旅途的长短来确定携带行李的价格,或者我们根据一定的重量范围来给一箱铁球进行分类。这一类问题的解决思路是:
1、 根据实际需要划分出分类的标准;
2、 按一定的顺序(算法)将实际的数据归到相应的类别里。
一般情况下,我们所确定的分类标准并不能保证每一类的数据量是平均分配的;也就是说,由于每一类数据出现的概率不同,造成当采用不同的算法时所需的运算次数的不同。当然,在实际生产生活中,我们更希望得到一种最快,最简洁同时也不会产生歧义的算法。在这个背景下,哈夫曼树以及哈夫曼算法应运而生。
准备概念
森林:森林由n(n>=2)个二叉树组成,它的遍历可以归结为二叉树的遍历,即以其中一棵二叉树的根结点为森林的“根结点”,之后每一个二叉树的根结点都依次相连,由此组成了一个大的二叉树——森林向二叉树的转化。
路径和路径的长度:从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称作路径长度。
对于一个二叉树,其在第n层上的结点到根结点的路径长度为n-1。
结点的权:根据应用的需要给树的结点赋的权值。
结点的带权路径长度:从根结点到该结点的路径长度与该几点权的乘积。
树的带权路径长度(WPL):树中所有叶子的带权路径长度之和。
哈夫曼二叉树及其构造
有了以上的概念,哈夫曼二叉树的定义就变得水到渠成。所谓哈夫曼二叉树(最优二叉树),就是带权路径长度最小的二叉树(注意这里的带权路径)。
因为树的带权路径长度只与所有叶子的带权路径长度有关,所以对于一个哈夫曼树,其真正其作用的数据是存在于叶子上。
再回到问题产生的根源。我们说在现实的分类中,每一类数据出现的概率不尽相同;这些数据出现的概率可以被看做哈夫曼树中叶子的权值。为了获取最短的路径,也就是带权路径长度最短的二叉树,我们希望那些权值低的数据拥有相对较长的对根结点的路径长度。根据这一思路,我们可以从一群离散的数据中构造出一颗哈夫曼树,具体的算法如下:
- 根据给定的n个权值{w1 ,w2 ,...,wn }构造n棵二叉树的集合F={T1 ,T2 ,...,Tn },其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空。
- 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根 结点的权值为其左、右子树上根结点的权值之 和。
- 在F中删除这两棵树,同时将新得到的二叉树加入F中。
- 重复2和3,直到F中只含一棵树为止。这棵树便是最优二叉树。
例如,有权值分别为 5、10、15、20、25、40的结点,根据以上算法构造出一个哈夫曼树。
- 取这六个树中最小的两个树5、10连成一个二叉树,其权值为15;此时森林里的树变为15(5、10)、15、20、25、40。
- 取这五个树中最小的两个树(15(5、10)、15),构成一个新的二叉树30((5、10)、15);此时森立里的树变为20、25、30((5、10)、15)、40。
- 继续上述过程,得到一个新的二叉树45(20、25);此时的森林变为30((5、10)、15)、40、45(20、25)。
- 继续得到二叉树70((5、10)、15)、40);则森林里只剩下两棵树:70((5、10)、15)、40)与45(20、25)。
- 最后将这两棵二叉树合并成为一棵二叉树115(((5、10)、15)、40)、(20、25)),完成了哈夫曼树的构造。
- 计算WPL=(5+10)4+153+402+(20+25)2=275。
以上便是哈夫曼树(最优二叉树)的相关概念和构造方法。根据最后二叉树可以解决类似于文章开头提到的一些实际问题。同时还另外引申出了哈夫曼编码——即不等长编码,实现数据总长度的最优化。
猜你还喜欢
- 05-13 [摄影] 让手机秒变单反的手机拍摄好物
- 05-11 [摄影] 想挣钱的摄影师建议收藏!
- 05-11 [美食] 选址秘籍:从摆摊到开小店,大数据地图助你找到理想店铺位置
- 05-04 [知识分享] 「科普」不知道电影资源那么长一大串名字是什么意思?看完这个你就明白了!
- 04-30 [摄影] 玩转手机摄影 | 滤镜手机支架
- 04-30 [经验] 摆地摊的八大禁忌
- 04-27 [绘画] 油画棒原创作品【绽放】图文教程来咯~
- 04-17 [涨姿势] 餐饮管理故事:对不起,我订错了雅间,怎么办?(附解决方案)
- 03-29 [摄影课堂] 电光火石间的决定
- 03-29 [摄影相关] UV镜不要随便将就
- 03-29 [摄影技巧] 抗光害滤镜 | 还原城市最美夜景 城市夜空的色彩救星!
- 03-29 [设计] 无边泳池是怎么设计的?以及它的原理介绍
取消回复欢迎 你 发表评论:
- 精品推荐!
-
- 最新文章
- 热门文章
- 热评文章
[资料课程] 适合3-7岁学前幼小衔接 《22天搞定拼音》,认、读、拼、写
[课程] 衣之镖-- 《辅行诀五脏用药法要》研究 线上54讲课程视频
[课程] 12节在家也能练出性感蜜桃臀,让臀部变得圆、紧、翘
[游戏娱乐] 《灵魂石幸存者》v10g中文版
[跨境电商] TikTok中视频课程30天线上陪跑
[电影] [摩登笑探 冇面俾].1995.HDTV1080i.国语中字
[游戏娱乐] 《阿斯特赖亚》v1.1.42中文版
[游戏娱乐] 《消逝的光芒:仇恨》中文版
[电影] 非常偵探/The Private Eye Blues 1994
[摄影] 让手机秒变单反的手机拍摄好物
[资料] [大学期末救急课] 猴博士+高斯课堂+斐多课堂,全集视频合集
[云资源] 价值2万元的老男孩Python教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[云资源] 花了一千多元买的私人健身教程
[下载工具] Internet Download Manager 6.42.7 (IDM)
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[安卓软件] 酷我音乐APP_v10.7.6.4 去广告破解豪华VIP版
[即时通讯] 微信PC版WeChat 3.9.9.43 多开防撤回绿色版
[安卓软件] Solid Explorer文件管理器APP 2.8.38 破解版
[浏览器] Google Chrome v123.0.6312.59便携增强版
[云资源] 价值2万元的老男孩Python教程
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[云资源] 花了一千多元买的私人健身教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[动画] 北斗神拳(1984) [两季合集] [MKV]
[资料] 抗战阵亡将士资料+续编
[电视剧] 三体 (2024) 全8集 网飞版本 中文字幕 合集
[纪录片] 河西走廊【10集 国语 中文字幕 1080P 10.8G MP4】
[电影] 2024年喜剧片·热辣滚烫 [mp4]
[影视] 铁爪 WEB-DL版下载 2023 The Iron Claw 23.48G
- 最新评论
-
杂物房内的旧档资源不保证有效CC下载站 评论于:05-14 不能**123 评论于:05-14 我想看看mw2ddyy 评论于:04-26 好东西阿zfy123123 评论于:04-18 谢谢楼主xiaoqi 评论于:04-12 勿在线解压,勿手机解压,请在电脑上用最新款压缩软件解压!推荐360压缩或者好压CC下载站 评论于:04-10 无法解压啊,客服能不能给个解压教程ravengrey 评论于:04-10 谢谢支持!!CC下载站 评论于:03-26 很棒的资源,感谢分享云体风身 评论于:03-26 感谢分享,好东西云体风身 评论于:03-26
- 热门tag