数据结构 —— 红黑树

目录

1. 初识红黑树

1.1 红黑树的概念

 1.2 红⿊树的规则

1.3 红黑树如何确保最长路径不超过最短路径的2倍

1.4 红黑树的效率:O(logN)

2. 红黑树的实现 

2.1 红黑树的基础结构框架

2.2 红黑树的插⼊

2.2.1 情况1:变色

2.2.2 情况2:单旋+变色

2.2.3 情况3:双旋+变色  

2.3 验证一棵树是否为红黑树

2.4 代码汇总



1. 初识红黑树

1.1 红黑树的概念

红⿊树是⼀棵⼆叉搜索树,他的每个结点增加⼀个存储位来表⽰结点的颜⾊,可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束,红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍,因⽽是接近平衡的


 1.2 红⿊树的规则

1. 每个结点不是红⾊就是⿊⾊

     
2. 根结点是⿊⾊的

   
3. 如果⼀个结点是红⾊的,则它的两个孩⼦结点必须是⿊⾊的,也就是说任意⼀条路径不会有连续的红⾊结点

     
4. 对于任意⼀个结点,从该结点到其所有NULL结点的简单路径上,均包含相同数量的⿊⾊结点
   

 


1.3 红黑树如何确保最长路径不超过最短路径的2倍

1. 由规则4可知,从根到NULL结点的每条路径都有相同数量的⿊⾊结点,所以极端场景下,最短路径就就是全是⿊⾊结点的路径,假设最短路径⻓度为hb

  

hb:从某个节点出发(不包含该节点)到达一个叶子节点的任意一条简单路径上黑色节点的个数

    
2. 由规则2和规则3可知,任意⼀条路径不会有连续的红⾊结点,所以极端场景下,最⻓的路径就是⼀⿊⼀红间隔组成,那么最⻓路径的⻓度为2*bh

     
3. 综合红⿊树的4点规则⽽⾔,理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x,那么bh <= h <= 2*bh


1.4 红黑树的效率:O(logN)

红⿊树的表达相对AVL树要抽象⼀些,AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜 ⾊约束,间接的实现了近似平衡,他们效率都是同⼀档次,但是相对⽽⾔,插⼊相同数量的结点,红⿊树的旋转次数是更少的,因为他对平衡的控制没那么严格


2. 红黑树的实现 

2.1 红黑树的基础结构框架

#pragma once
//定义一个枚举
enum Colour
{//枚举里面定义颜色RED,BLACK
};//默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{//这⾥更新控制平衡也要加⼊parent指针pair<K, V> _kv;//也要实现成三叉链RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:
private:Node* _root = nullptr;
};

2.2 红黑树的插⼊

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊,插⼊后我们只需要观察是否符合红⿊树的4条规则

    

2. 如果是空树插⼊,新增结点是⿊⾊结点。如果是⾮空树插⼊,新增结点必须是红⾊结点,因为⾮空树插⼊,新增⿊⾊结点就破坏了规则4,规则4是很难维护的

     

3. ⾮空树插⼊后,新增结点必须红⾊结点,如果⽗亲结点是⿊⾊的,则没有违反任何规则,插⼊结束

     

4. ⾮空树插⼊后,新增结点必须红⾊结点,如果⽗亲结点是红⾊的,则违反规则3。进⼀步分析,c是红⾊,p为红,g必为⿊,这三个颜⾊都固定了,关键的变化看u的情况,需要根据u分为以下⼏种 情况分别处理

    

说明:下图中假设我们把新增结点标识为c(cur),c的⽗亲标识为p(parent),p的⽗亲标识为 g(grandfather),p的兄弟标识为u(uncle)


2.2.1 情况1:变色

新增结点标识为c(cur),c的⽗亲标识为p(parent),p的⽗亲标识为 g(grandfather),p的兄弟标识为u(uncle)

c为红,p为红,g为⿊,u存在且为红,则将p和u变⿊,g变红,再在把g当做新的c,继续往上更新

    
分析:因为p和u都是红⾊,g是⿊⾊,把p和u变⿊,左边⼦树路径各增加⼀个⿊⾊结点,g再变红,相当于保持g所在⼦树的⿊⾊结点的数量不变,同时解决了c和p连续红⾊结点的问题,需要继续往上更新因为,g是红⾊

   

如果g的⽗亲还是红⾊,那么就还需要继续处理;如果g的⽗亲是⿊⾊,则处理结束了;如果g就是整棵树的根,再把g变回⿊⾊

   

 情况1只变⾊,不旋转。所以⽆论c是p的左还是右,p是g的左还是右,都是上⾯的变⾊处理⽅式


2.2.2 情况2:单旋+变色

c为红,p为红,g为⿊,u不存在或者u存在且为⿊,u不存在,则c⼀定是新增结点

    

u存在且为⿊,则c⼀定不是新增,c之前是⿊⾊的,是在c的⼦树中插⼊,符合情况1,变⾊将c从⿊⾊变成红⾊,更新上来的

分析:p必须变⿊,才能解决,连续红⾊结点的问题,u不存在或者是⿊⾊的,这⾥单纯的变⾊⽆法解决问题,需要旋转+变⾊

如果p是g的左,c是p的左,那么以g为旋转点进⾏右单旋,再把p变⿊,g变红即可。p变成课这颗树新的根,这样⼦树⿊⾊结点的数量不变,没有连续的红⾊结点了,且不需要往上更新,因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则

 

如果p是g的右,c是p的右,那么以g为旋转点进⾏左单旋,再把p变⿊,g变红即可。p变成课这颗树新的根,这样⼦树⿊⾊结点的数量不变,没有连续的红⾊结点了,且不需要往上更新,因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则


2.2.3 情况3:双旋+变色  

c为红,p为红,g为⿊,u不存在或者u存在且为⿊,u不存在,则c⼀定是新增结点

    

u存在且为⿊,则c⼀定不是新增,c之前是⿊⾊的,是在c的⼦树中插⼊,符合情况1,变⾊将c从⿊⾊变成红⾊,更新上来的

分析:p必须变⿊,才能解决,连续红⾊结点的问题,u不存在或者是⿊⾊的,这⾥单纯的变⾊⽆法解决问题,需要旋转+变⾊

如果p是g的左,c是p的右,那么先以p为旋转点进⾏左单旋,再以g为旋转点进⾏右单旋,再把c变⿊,g变红即可。c变成课这颗树新的根,这样⼦树⿊⾊结点的数量不变,没有连续的红⾊结点了,且不需要往上更新,因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则

如果p是g的右,c是p的左,那么先以p为旋转点进⾏右单旋,再以g为旋转点进⾏左单旋,再把c变⿊,g变红即可。c变成课这颗树新的根,这样⼦树⿊⾊结点的数量不变,没有连续的红⾊结点了,且不需要往上更新,因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则 


2.3 验证一棵树是否为红黑树

规则1:枚举颜⾊类型,天然实现保证了颜⾊不是⿊⾊就是红⾊

   

规则2:直接检查根即可

   

规则3:前序遍历检查,遇到红⾊结点查孩⼦不太⽅便,因为孩⼦有两个,且不⼀定存在,反过来检 查⽗亲的颜⾊就⽅便多了

    

规则4:前序遍历,遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量),前序遍历遇到 ⿊⾊结点就++blackNum,⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值,依次⽐较即可 

bool Check(Node* root, int blacknum, const int retnum)
{if (root == nullptr){if (blacknum != retnum){cout << "有路径的黑色节点个数与其他路径不相同" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, blacknum, retnum)&& Check(root->_right, blacknum, retnum);
}
bool IsBalance()
{if (_root == nullptr){return true;}if (_root->_col == BLACK){return false;}int retnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){retnum++;}cur = cur->_left;}return Check(_root, 0, retnum);
}

2.4 代码汇总

#pragma once
#pragma once
//定义一个枚举
enum Colour
{//枚举里面定义颜色RED,BLACK
};//默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{//这⾥更新控制平衡也要加⼊parent指针pair<K, V> _kv;//也要实现成三叉链RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;//颜色RBTreeNode(const pair<K, V>& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://按二叉搜索树规则进行插入bool Insert(const pair<K, V>& kv){//如果是空树插入第一个节点if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点为黑色return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//如果非空的树插入一个节点,那么插入红色cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}// 链接父亲cur->_parent = parent;// 父亲存在并且也是红色,当出现连续的红色节点时while (parent && parent->_col == RED){//找到爷爷节点Node* grandfather = parent->_parent;//再根据叔叔节点来判断父亲节点的情况if (parent == grandfather->_left){//	 g//p		u// //说明u在g的右边Node* uncle = grandfather->_right;//如果u存在并且u的颜色为红色if (uncle && uncle->_col == RED){//将u和p的颜色改为黑色,g的颜色改为红色uncle->_col = parent->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;//p寻找g的p节点}else{if (cur == parent->_left){//     g//   p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p    u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//   g// u   pNode* uncle = grandfather->_left;// 叔叔存在且为红,-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在,或者存在且为黑{// 情况二:叔叔不存在或者存在且为黑// 旋转+变色//   g// u   p//       cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//保证根节点一定是黑色的_root->_col = BLACK;return true;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}private:Node* _root = nullptr;
};

完结撒花~

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

丹摩征文活动|AIGC实践-基于丹摩算力和CogVideoX-2b实现文生视频

一、CogVideoX简介 CogVideoX 是由智谱AI开源的新一代视频生成模型&#xff0c;属于大型语言模型在多模态应用中的重要突破。CogVideoX-2b 版本在参数规模和推理速度上进行了优化&#xff0c;支持视频从文本描述生成&#xff0c;并进一步提升了视频的分辨率和流畅度。相比于上…

麦当劳自助点餐机——实现

餐厅自助点餐优点 1. 降低服务成本&#xff1a; - 减少了对服务员数量的需求&#xff0c;降低了人力成本。 - 减轻了服务员的工作负担&#xff0c;使其能够更专注于提供优质的服务&#xff0c;如解决顾客的特殊需求和处理复杂问题。 2. 提升点餐效率和准确性&#xf…

Linux【基础篇】T

如何安装Linux操作系统&#xff1f; 1.直接把笔记本的Windows干掉&#xff0c;单独安装Linux系统&#xff08;初学者对于Linux使用还是比较苦难&#xff09;。 2.可以安装双系统&#xff08;开机也是命令行&#xff09;&#xff0c;电脑配置要高。 3.可以安装虚拟机。 --如果…

Linux操作系统之软件安装与包管理器工具

一、实验目的 1、掌握常用的软件包管理器RPM、YUM的使用&#xff1b; 2、掌握内网YUM源的配置方法。 二、实验环境 1台PC、VMware虚拟机、2个CentOS7操作系统 三、实验步骤及内容 1、使用RPM软件包管理器安装软件 (1)从阿里云https://mirrors.aliyun.com/下载CentOS7操作…

贯穿式学习MySQL

注&#xff1a;MySQL版本众多&#xff0c;本次讲述的内容以MySQL8.0.34版本为准 范式化设计 范式具体是用来干嘛的&#xff1f; 我们在设计关系数据库时&#xff0c;要遵从不同的规范要求&#xff0c;设计出合理的关系型数据库&#xff0c;这些不同的规范要求被称为不同的范式…

web——[SUCTF 2019]EasySQL1——堆叠注入

这个题主要是讲述了堆叠注入的用法&#xff0c;来复现一下 什么是堆叠注入 堆叠注入&#xff1a;将多条SQL语句放在一起&#xff0c;并用分号;隔开。 1.查看数据库的名称 查看数据库名称 1;show databases; 发现有名称为ctftraining的数据库 2.对表进行查询 1;show tabl…

「Mac畅玩鸿蒙与硬件31」UI互动应用篇8 - 自定义评分星级组件

本篇将带你实现一个自定义评分星级组件&#xff0c;用户可以通过点击星星进行评分&#xff0c;并实时显示评分结果。为了让界面更具吸引力&#xff0c;我们还将添加一只小猫图片作为评分的背景装饰。 关键词 UI互动应用评分系统自定义星级组件状态管理用户交互 一、功能说明 …

发布 VectorTraits v3.0(支持 X86架构的Avx512系列指令集,支持 Wasm架构及PackedSimd指令集等)

文章目录 支持 X86架构的Avx512系列指令集支持Avx512时的输出信息 支持 Wasm架构及PackedSimd指令集支持PackedSimd时的输出信息VectorTraits.Benchmarks.Wasm 使用说明 新增了向量方法支持 .NET 8.0 新增的向量方法提供交织与解交织的向量方法YGroup3Unzip的范例代码 提供重新…

分布式数据库中间件mycat

MyCat MyCat是一个开源的分布式数据库系统&#xff0c;它实现了MySQL协议&#xff0c;可以作为数据库代理使用。 MyCat(中间件)的核心功能是分库分表&#xff0c;即将一个大表水平分割为多个小表&#xff0c;存储在后端的MySQL服务器或其他数据库中。 它不仅支持MySQL&#xff…

操作系统学习笔记-3.2虚拟内存

文章目录 虚拟内存请求分页管理方式页面置换算法最佳置换算法工作原理OPT 算法的示例最佳置换算法的优点和缺点 先进先出置换算法最近最久未使用时钟置换算法时钟置换算法的工作原理&#xff1a;算法的步骤&#xff1a; 改进型时钟置换算法改进型时钟置换算法的特点&#xff1a…

【计网】物理层学习笔记

【计网】物理层 物理层概述 物理层要实现的功能 在各种传输媒体上传输比特0和1&#xff0c;进而为上面的数据链路层提供透明传输比特流的作用。 物理层接口特性 物理层之下的传输媒体 传输媒体是计网设备之间的物理通路&#xff0c;也称为传输介质。 传输媒体并不包含在…

python机器人Agent编程——实现一个本地大模型和爬虫结合的手机号归属地天气查询Agent

目录 一、前言二、准备工作三、Agent结构四、python模块实现4.1 实现手机号归属地查询工具4.2实现天气查询工具4.3定义创建Agent主体4.4创建聊天界面 五、小结PS.扩展阅读ps1.六自由度机器人相关文章资源ps2.四轴机器相关文章资源ps3.移动小车相关文章资源ps3.wifi小车控制相关…

Spring MVC(一)

1. Spring MVC是什么&#xff1f; 搞清楚Spring MVC之前先搞清楚MVC是什么&#xff1f;MVC是一种架构设计模式&#xff0c;也就是一种思想&#xff0c;M是Model&#xff0c;V是View&#xff0c;C是Controller。他们之间的关系举一个例子来介绍。比如去饭店吃饭&#xff0c;一进…

文件操作:Xml转Excel

1 添加依赖 Spire.Xls.jar <dependency><groupId>e-iceblue</groupId><artifactId>spire.xls</artifactId><version>5.3.3</version></dependency>2 代码使用 package cctd.controller;import com.spire.xls.FileFormat; im…

C语言中的 printf( ) 与 scanf( )

时隔多日&#xff0c;小编我又回来咯小编相信之前的博客能够给大家带来不少的收获。在我们之前的文章中&#xff0c;许多代码块的例子都用到了printf( ) 与 scanf( )这两个函数&#xff0c;大家都知道他们需要声明头文件之后才能使用&#xff0c;那这两个函数是什么呢&#xff…

Yocto 项目下通过网络更新内核、设备树及模块

Yocto 项目下通过网络更新内核、设备树及模块 前言 在 Yocto 项目的开发过程中&#xff0c;特别是在进行 BSP&#xff08;Board Support Package&#xff09;开发时&#xff0c;经常需要调整特定软件包的版本&#xff0c;修改内核、设备树以及内核模块。然而&#xff0c;每次…

算法每日双题精讲——双指针(移动零,复写零)

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; 别再犹豫了&#xff01;快来订阅我们的算法每日双题精讲专栏&#xff0c;一起踏上算法学习的精彩之旅吧&#xff01;&#x1f4aa;…

数据库的使用02:SQLServer的连接字符串、备份、还原、SQL监视相关设置

目录 一、连接字符串 【本地连接字符串】 【远程连接字符串】 二、备份 三、还原 &#xff08;1&#xff09;还原数据库-bak、btn文件 &#xff08;2&#xff09;附加数据库mdf文件 四、SQL监视器的使用 一、连接字符串 【本地连接字符串】 server DESKTOP-FTH2P3S; Da…

使用SearXNG-搭建个人搜索引擎(附国内可用Docker镜像源)

介绍 SearXNG是聚合了七十多种搜索服务的开源搜索工具。我们可以匿名浏览页面&#xff0c;不会被记录和追踪。作为开发者&#xff0c;SearXNG也提供了清晰的API接口以及完整的开发文档。 部署 我们可以很方便地使用Docker和Docker compose部署SearXNG。下面给出Docker部署Se…

【笔记】LLC电路工作频点选择 2-2 开关管与滤波压力

LLC谐振变换器稳态工作波形分析 - 知乎&#xff0c;上面这篇文的结论相较MPS那篇文章的结论更严格。我们分析一下它的频点选择为什么会更窄&#xff1a; 1. LLC电路模型 电流滞后的特性就是电路呈感性注意这里也是开关管ZVS开通。 2.工作循环的波形 iLm的波形&#xff0c;最终…