6.6.1最优二叉树(赫夫曼树)
发布日期:2021-06-30 10:49:23
浏览次数:2
分类:技术文章
本文共 584 字,大约阅读时间需要 1 分钟。
首先我们来看一个伪代码。这个是代表成绩的等级。
然后我们知道,每一次高考,学生的成绩分布应该接近某个比例,现在我们假如分别规律如下:
为此可以作出下面的这个树。
我们发现,概率分布主要是在70-79,80-89之间,如果有很多数据要比较,那么就要从60分开始比较,然后,分布最多的确是70-79,80-89的人,所以我们可以把树话成这样
现在先介绍几个概念:
路径长度:从树中一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目叫路径长度。
树的路径长度:根结点到每个结点的路径长度和。
WPL(weight path length):树中所有叶子结点的带权路径之和。
比如上面那两个图,我们把他权重标号。如下图所示(为了方便,我们扩大10倍,避免小数点)
现在来看看WPL
WPL1=5*3+15*3+40*2+30*2+10*2=220
WPL2=5*1+15*+40*3+30*4+10*4=315。
现在给出一个概念:带权路径长度WPL最小的二叉树叫最优二叉树或赫夫曼树。
下面给出最优二叉树或赫夫曼树的画法。
规则如下:
1.在森林中选出两颗根结点的权值最小的二叉树。
2.合并两颗,增加一个新结点作为新二叉树的根,全职为左右孩子的权重之和。
3.再从未选中的结点中选择,小的放左边,大的放右边,然后重复,一直到结点没有了为止。
如下图所示:
转载地址:https://it1995.blog.csdn.net/article/details/56279372 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月29日 14时22分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【工具使用】pycharm中用带参数的命令行进行断点Debug
2019-04-30
【工具使用】pycharm逐步调试
2019-04-30
【深度学习笔记】PyTorch的torch.cat()函数
2019-04-30
【深度学习笔记】查看动态的GPU使用情况、CUDA版本
2019-04-30
【工具使用】GPU的各项参数说明
2019-04-30
【深度学习笔记】example-based超分的定义
2019-04-30
【python学习笔记】Python os.getcwd() 方法:获取当前路径
2019-04-30
【python学习笔记】几个常见的OS函数
2019-04-30
【python学习笔记】字典的打印
2019-04-30
【python3学习笔记】有序字典OderedDict
2019-04-30
【python3学习笔记】os.path.relpath(path[, start])
2019-04-30
【python3学习笔记】os.chdir(path)用法
2019-04-30
【python3学习笔记】assert 关键字
2019-04-30
【python3学习笔记】函数参数前单星号(*)和双星号(**)的区别
2019-04-30
【python3学习笔记】斜杠和双斜杠运算符的区别
2019-04-30
【深度学习笔记】用torch.nn.Sequential()搭建神经网络模型
2019-04-30