手机版 | 登陆 | 注册 | 留言 | 设首页 | 加收藏
当前位置: 网站首页 > 精彩文章 > 文章 当前位置: 精彩文章 > 文章

关于哈夫曼树的复习以及概念等零碎知识点

时间:2018-10-04    点击: 次    来源:网络    作者:佚名 - 小 + 大

首先哈弗曼树的构造是一种贪心的思想。。。然后直接上图说这个东西是怎么构造的、

这种数据结构有什么用呢,他的直接应用就是弄到哈夫曼编码上,那就先讲讲哈夫曼编码吧。

我们知道一些英文字母的使用频率是不同的,现在考虑用01串来表示每个字母,从而形成一篇英文文章。

我们希望这篇用01串形成的文章尽可能的短,来提高通讯效率。那么就要求我们对于出现频率高的字母用尽可能短的01串来表示。

于是乎就有了图片上的东西,下面介绍几个概念

1.PL:树根到树的某个节点的长度(每条边的长度为1)

2.WPL:树的所有叶子节点的带权路径长度(该节点到根节点路径长度与节点上权的乘积)之和。(注意叶子节点是指度为0的节点 度不等于深度)

上图中就可以很好的看出哈夫曼树的优势,我们详细的分析一下WPL的用处

其实我们把PL看做是每个单词所代表的01串的长度,权代表出现频率。

这样一搞wpl就看做是整篇文章的长度,显然哈夫曼短。

其实哈夫曼的贪心思想就是把出现频率高的单词用较短的01串表示。

稍微推广一下哈夫曼树的应用,对于出现频率高的一个对象的某个属性尽可能小,从而使由这个对象的属性构成的集合尽可能小,那么就可以考虑用哈夫曼树来搞。。

呵呵,关键是遇到题要能抽象出这个模型来,就nb了!

上一篇:关于满二叉树,完全二叉树的辨析

下一篇:NOIP2018初赛复习之原码,补码,反码

备案ICP编号  |   QQ:3558389921  |  地址:山东济南  |  电话:暂不提供  |  
Copyright © 2018 天人文章管理系统 版权所有,授权down1s.com使用 Powered by 55TR.COM