《征服数据结构》哈夫曼树(Huffman Tree)

摘要:

1,哈夫曼树的介绍

2,哈夫曼树的构造

3,哈夫曼树带权路径长度计算

4,哈夫曼树的编码

5,哈夫曼树的解码

1,哈夫曼树的介绍

哈夫曼树(Huffman Tree)也叫霍夫曼树,或者赫夫曼树,又称为最优树,是因为它是一种带权路径长度最短的二叉树。在学习哈夫曼树之前我们先来了解一些和哈夫曼树相关的概念:

路径:从任一个节点往下到达其它节点之间的通路。

路径长度:路径中线段的个数。

节点的权:节点的值。

节点的带权路径长度:从根节点到该节点之间的路径长度与该节点权的乘积。

树的带权路径长度:所有叶子节点的带权路径长度之和。

在讲解哈夫曼树之前我们来看这样一个问题,假如老师根据学生的成绩给学生进行评级,有下面几个等级:

String level(int score) {if (score < 60) return "不及格";else if (score < 70) return "及格";else if (score < 80) return "中等";else if (score < 90) return "良好";else return "优秀";
}

上面的分支语句整理出来像一棵二叉树,如下图所示:

2548ba48c1016b2933e05fc5320f7d4e.png

假如同学的成绩分布如下:

90分以上:10%
80到90分:35%
70到80分:45%
60到70分:8%
60分以下:2%

可以看到60分以下的只有2%,但我们每次都是先判断是否小于60,很明显大多数情况下都不小于60,也就是无效的判断。

为了减少判断次数,最有效的判断方式就是占比越高的离根节点越近。可以看到分数在70到80分的占到45%,80到90分的占到35%,这两个加起来占了80%,这种情况下可以像下图中这样查询。

9a1580f2bce1d12f940443667f63ccf7.png

假如把这里的百分比看作叶子节点的权值,用它构造一棵二叉树,这棵二叉树可以有多种,其中带权路径长度最小的就是最优树,也是哈夫曼树。

哈夫曼树就是给定 n 个权值作为叶子节点,构造一棵二叉树,并且该树的带权路径长度达到最小。

树的带权路径长度 WPL(Weighted Path Length of Tree) 记为 WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) ,其中 W 表示节点的权值, L 表示从根节点到该节点的路径长度。

要想让树的带权路径长度最小,权值越大的节点离根节点越近。如下图所示,是用权值为 9,3,2,8 分别构造的两棵树,很明显左边树的带权路径长度比右边树的带权路径长度要小。

061eab16e0b4bcba2182630968363c23.png

2,哈夫曼树的构造

哈夫曼树构造的原则是权值越大离根节点越近,使用的是贪心算法,步骤如下:

1. 用给定的 n 个权值创建 n 棵只有一个节点的树,把它们添加到集合 S 中。

2. 每次从集合 S 中取出两个权值最小的树,让它们组成一棵新的二叉树,新树的权值为它的两棵子树的权值之和,然后把这棵新的树添加到集合 S 中。

3. 重复步骤 2 ,直到集合中只有一棵树为止,这棵树就是哈夫曼树。

e18dbc9dad8bd6c7abeb09ca24e40c3a.png

1567d647f025a7d19ed9815c40ca68ea.png

如上图所示,因为每次都是选择两棵子树合并成一棵,所以哈夫曼树只有度为 0 和 2 的节点,没有度为 1 的节点,也就是说哈夫曼树中每个节点要么没有子节点,要么有两个子节点,不可能只有一个子节点。

在二叉树中,度为 2 的节点贡献两条边,度为 1 的节点贡献一条边,度为 0 的节点不贡献任何边。在二叉树中除了根节点外,每一个节点都有一个父节点指向它,所以在任何二叉树中节点的数量等于边的数量加 1 。

假如哈夫曼树中,度为 0 (叶子节点)的节点有 n 个,度为 2 的节点有 m 个,我们可以得出边的数量是 2m ,总的节点是 m+n,根据 m+n=2m+1,可以得出 m=n-1,总的节点数就是 2n-1,所以我们可以得出一棵有 n 个叶子节点的哈夫曼树总共有 2n-1 个节点。

每次从集合中取出权值最小的两棵树,这里的集合我们可以使用最小堆,来看下代码。

Java 代码:

// 哈夫曼树的节点类。
public class HNode {// 节点对应的字符,只有叶子节点有,在编码和解码的时候会用到。private Character ch;private int weight;// 权值。private HNode left;// 左子树。private HNode right;// 右子树。private int deep;// 路径长度,也是节点的深度。public HNode(int weight) {this.weight = weight;}public HNode(HNode left, HNode right, int weight) {this.left = left;this.right = right;this.weight = weight;}
}// 构建哈夫曼树
public HNode createTree(int[] nums) {// 优先队列,这里使用最小堆PriorityQueue<HNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));// 用数字创建只有一个节点的树并全部添加到堆中。for (int num : nums)pq.offer(new HNode(num));while (pq.size() > 1) {// 大于 1 就合并。HNode left = pq.poll();// 出队。HNode right = pq.poll();// 两棵子树合并成一棵。HNode parent = new HNode(left, right, left.weight + right.weight);// 把合并之后的子树添加到队列中。pq.add(parent);}return pq.poll();// 最后一个就是构造成的哈夫曼树。
}

C++ 代码:

struct HNode {// 哈夫曼树的节点类。// 节点对应的字符,只有叶子节点有,在编码和解码的时候会用到。char ch;int weight = 0;// 权值。HNode *left = nullptr;// 左子树。HNode *right = nullptr;// 右子树。int deep = 0;// 路径长度,也是节点的深度。HNode(int weight) : weight(weight) {}HNode(HNode *left, HNode *right, int weight) : left(left), right(right), weight(weight) {}
};// 构建哈夫曼树
HNode *createTree(vector<int> &nums) {auto cmp = [](HNode *a, HNode *b) { return a->weight > b->weight; };// 优先队列,这里使用最小堆priority_queue<HNode *, vector<HNode *>, decltype(cmp)> pq(cmp);// 创建节点并全部添加到堆中。for (int num: nums)pq.push(new HNode(num));while (pq.size() > 1) {// 大于 1 就合并。HNode *left = pq.top();pq.pop();// 出队。HNode *right = pq.top();pq.pop();// 出队。// 两棵子树合并成一棵。auto *parent = new HNode(left, right, left->weight + right->weight);// 把合并之后的子树添加到队列中。pq.push(parent);}return pq.top();// 最后一个就是构造成的哈夫曼树。
}

3,哈夫曼树带权路径长度计算

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1548699.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

学校周赛(1)

A - Short Sort 题目&#xff1a; 思路&#xff1a; 本条题目只允许改一处地方&#xff0c;只有三个字母&#xff0c;我们可以直接枚举所有移动过的结果&#xff0c;同时使用哈希去记录其值&#xff0c;对于每一个输入我们都寻找是否有这个值记录&#xff0c;有则输出YES否则…

微深节能 环形运动机械定位控制系统 格雷母线

微深节能的环形运动机械定位控制系统中的格雷母线&#xff0c;是一种高精度、无磨损的非接触式位置检测系统&#xff0c;特别适用于环形运动机械的定位控制。该系统主要由格雷母线、天线箱、电气柜等关键部件组成&#xff0c;其核心在于格雷母线这一特殊的编码线。 格雷母线概述…

JAVA一站式台球学习平台多端畅享助教教练系统小程序源码

​一站式台球学习平台 —— 多端畅享助教教练系统 &#x1f31f;【开篇&#xff1a;解锁台球新境界】&#x1f31f; 你是否厌倦了传统台球学习的枯燥与局限&#xff1f;想要随时随地&#xff0c;都能享受专业级的台球指导吗&#xff1f;今天&#xff0c;就让我为你揭秘一款颠覆…

JITWatch安装使用方法

JITWatch 版本1.4.2 JDK 版本 11以上 1.下载JITWatch&#xff1a; https://github.com/AdoptOpenJDK/jitwatch/releases/download/1.4.2/jitwatch-ui-1.4.2-shaded-win.jar 2.启动 bat脚本执行&#xff1a;通过启动jar包方式启动JITWatch echo off start cmd /c "ti…

SpringBoot+Activiti7工作流入门实例

目录 文章目录 目录准备Activiti建模工具1、BPMN-js在线设计器1.1 安装1.2 使用说明1.3运行截图 2、IDEA安装Activiti Designer插件2.1安装插件2.2 设置编码格式防止中文乱码2.3 截图 简单工作流入门实例1. 新建Spring Boot工程2. 引入Activiti相关依赖添加版本属性指定仓库添加…

探索分布式IO模块的介质冗余:赋能工业自动化的稳健之心

在日新月异的工业自动化领域&#xff0c;每一个细微环节的稳定性都直接关系到生产线的效率与安全。随着智能制造的深入发展&#xff0c;分布式IO&#xff08;Input/Output&#xff09;模块作为连接现场设备与控制系统的关键桥梁&#xff0c;其重要性日益凸显。我们自主研发的带…

RAG+llamaindex+DSW实操

本文纯干货,不做任何原理性讲解,适合于有一定基础的伙伴进行实践,本次文章将分为以下几个部分来介绍: 环境搭建LlamaIndex 使用本地知识库准备基本原理: 1. 环境搭建 1.1 配置基础环境 创建虚拟环境,环境名称可以自行取,我的是"llamaindex" conda create -n ll…

「iOS」——KVC

iOS学习 前言KVC模式KVC设值KVC取值KVC使用keyPathKVC处理异常处理不存在的key处理nil异常 KVC处理字典KVC高阶消息传递 总结 前言 对KVC模式的简单学习和总结。 KVC模式 KVC&#xff08;Key-Value Coding&#xff0c;键值编码&#xff09;是一种通过字符串来访问对象属性的机…

双端之Nginx+Php结合PostgreSQL搭建Wordpress

第一台虚拟机:安装 Nginx 更新系统包列表: sudo apt update安装 Nginx及php扩展: sudo apt install nginx php-fpm php-pgsql php-mysqli -y启动 Nginx 服务: sudo systemctl start nginx检查 Nginx 是否正常运行: xdg-open http://localhost注意:终端命令打开网址 …

腾讯云SDK产品功能

本文主要介绍音视频终端 SDK&#xff08;腾讯云视立方&#xff09;的核心功能。 直播推流 音视频终端 SDK&#xff08;腾讯云视立方&#xff09;为终端直播场景提供强大的 RTMP、RTC 推流能力&#xff0c;配合云直播&#xff08;CSS&#xff09;全球布局的2000节点&#xff0…

数据结构及基本算法

目录 第一章 概论 第一节 引言 第二节 基本概念和常用术语 第三节 算法的描述与分析 第二章 线性表 第一节 线性表定义和基本运算个 一、线性表的逻辑定义 二、线性表的基本运算 第二节 线性表的顺序存储和基本运算的实现 一、线性表的顺序存储 二、顺序表上基本运算…

【网络安全】-访问控制-burp(1~6)

文章目录 前言   1.Lab: Unprotected admin functionality  2.Lab: Unprotected admin functionality with unpredictable URL   3.Lab: User role controlled by request parameter   4.Lab:User role can be modified in user profile  5.Lab: User ID controlled by…

山海优选电商平台卷轴模式订单系统核心架构解析

山海优选卷轴模式的订单核心源码是涉及订单处理、支付、搜索、状态管理等关键功能的代码部分。由于直接提供完整的源代码可能涉及版权和隐私保护问题&#xff0c;我将基于参考文章中的信息&#xff0c;概述该模式订单核心源码的主要结构和功能点。 一、订单核心源码概述 在山海…

C语言线程

线程 多个进程中通过轮流使用CPU来完成自己的任务&#xff0c;如果多个进程的操作都一模一样那么CPU的开销就会很大&#xff0c;因为进程的地址都是私有的&#xff0c;如果CPU对相同的操作只执行一次&#xff0c;后面再遇到直接去获取即可&#xff0c;这样大大降低了CPU的开销…

【AI战略思考5】工欲善其事,必先利其器。我的利器是什么?

目录 导言1.不要忽视时间本身复利的巨大威力2.只赚自己认知以内的钱&#xff0c;只把握自己能力以内的机会3.多做有难度的事来激发自己的潜力和提升自己4.学会抵制诱惑5.减少冗余思考和冗余操作 导言 工欲善其事&#xff0c;必先利其器。我的利器是什么&#xff1f; 虽然我中考…

【C++拓展(四)】秋招建议与心得

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:C从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学习C   &#x1f51d;&#x1f51d; C拓展 1. 前言2. 今年秋招形势到底如何?3. 学历…

Proteus如何添加数码管

1、打开安装好的Proteus&#xff0c;点击上方菜单栏中的“库”&#xff0c;再选择“从库选取零件”&#xff0c;或者在左侧元件列表中单击鼠标右键&#xff0c;再点击右键菜单中的“从库中挑选”选项。 2、之后在元器件库中&#xff0c;点击类别中的“Optoelectronics”&#…

景联文科技精准数据标注:优化智能标注平台,打造智能未来

景联文科技是一家致力于为人工智能提供全面数据标注解决方案的专业公司。 拥有一支由经验丰富的数据标注师和垂直领域专家组成的团队&#xff0c;确保数据标注的质量和专业性。 自建平台功能一站式服务平台&#xff0c;提供从数据上传、标注、审核到导出的一站式服务&#xff0…

熔断降级 请求合并 请求缓存 线程池隔离 信号量隔离 openfeign整合Hystrix

〇、Hystrix的解决策略和预防措施&#xff1a; 熔断降级是解决远程调用已经出现问题的解决方案。 请求合并 请求缓存 线程池隔离 信号量隔离都是预防性措施 使用Hystrix启动类上需要添加注解开启注解支持&#xff1a; EnableHystrixEnableCircuitBreaker 测试Hystrix需要的依赖…

DAY81服务攻防-开发框架安全SpringBootStruts2LaravelThinkPHPCVE 复现

知识点&#xff1a; 1、PHP-框架安全-Thinkphp&Laravel 2、J2EE-框架安全-SpringBoot&Struts2 常见语言开发框架&#xff1a; PHP&#xff1a;Thinkphp Laravel YII CodeIgniter CakePHP Zend等 JAVA&#xff1a;Spring MyBatis Hibernate Struts2 Springboot等 P…