数据结构 —— 红黑树

目录

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.xdnf.cn/news/5942.html

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

相关文章

第J9周:Inception v3算法实战与解析(pytorch版)

>- **&#x1f368; 本文为[&#x1f517;365天深度学习训练营]中的学习记录博客** >- **&#x1f356; 原作者&#xff1a;[K同学啊]** &#x1f4cc;本周任务&#xff1a;&#x1f4cc; 了解并学习InceptionV3相对与InceptionV1有哪些改进的地方 使用Inception完成天气…

什么是 AWS PrivateLink

您可以使用 Amazon VPC 定义虚拟私有云&#xff08;VPC&#xff09;&#xff0c;这是一个逻辑隔离虚拟网络。您可以在 VPC 中启动 AWS 资源。您可以允许 VPC 中的资源连接到该 VPC 外部的资源。例如&#xff0c;向 VPC 添加互联网网关以允许访问互联网&#xff0c;或添加 VPN 连…

vue2 -- el-form组件动态增减表单项及表单项验证

需求 在数据录入场景(如订单信息录入)中,可根据实际情况(如商品种类增加)动态添加表单项(如商品相关信息)。包含必填项验证和数据格式验证(如邮箱、电话格式),防止错误数据提交。 效果 代码一 <template><div>

旧衣回收小程序:提高回收效率,扩大服务范围

近年来&#xff0c;旧衣回收作为一种新兴回收模式&#xff0c;逐渐走入了大众的生活中&#xff0c;在回收市场中形成了新的商业模式&#xff0c;也为大众带来了新的创业选择。 随着社会生活的快速发展&#xff0c;人们的生活水平不断提高&#xff0c;为旧衣市场发展提供了基础…

电子电气架构 --- Trace 32(劳特巴赫)多核系统的调试

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所有人的看法和评价都是暂时的,只有自己的经历是伴随一生的,几乎所有的担忧和畏惧,都是来源于自己的想象,只有你真的去做了,才会发现有多快乐。…

使用C++和QT开发应用程序入门以及开发实例分享

目录 1、搭建开发环境&#xff08;VS2010和QT4.8.2&#xff09; 2、创建一个QT窗口 3、在QT窗口中添加子窗口 4、QT界面布局 5、QT信号&#xff08;SIGNAL&#xff09;和槽&#xff08;SLOT&#xff09; 6、最后 C软件异常排查从入门到精通系列教程&#xff08;专栏文章列…

1553B总线协议

参考地址 MIL-STD-1553B时分制指令/响应多路传输数据总线采用半双工传输方式。 1553B总线协议概述 1553B总线协议是一种军用标准&#xff0c;主要用于飞机上的设备间的信息传输。这种协议由美国军方制定&#xff0c;被广泛应用于航空、航天和军事领域的电子联网系统中。1553B…

LVI-GS:港大待开源、雷达-视觉-惯紧耦合,实时渲染

文章目录 摘要一、 介绍二、相关工作A 基于NeRF的SLAMB 基于3DGS的SLAM 三、方法A 超原语B. 3D 高斯投影C. 关键帧管理D. 基于金字塔的训练E. 高斯映射 四、实验 摘要 文章&#xff1a;github 介绍&#xff1a;介绍 3D高斯溅射&#xff08;3DGS&#xff09;在快速渲染和高保真…

2024年中国AI大模型场景应用趋势蓝皮书【附47页PPT】

目录 01 AI大模型行业应用概况 02 AI大模型行业应用现状及案例 03 AI大模型行业应用痛点及解决方案 04 AI大模型行业应用前景趋势及投资机会分析 如何学习AI大模型 &#xff1f; “最先掌握AI的人&#xff0c;将会比较晚掌握AI的人有竞争优势”。 这句话&#xff0c;放在…

基于Zynq FPGA对雷龙SD NAND的测试

一、SD NAND 特征 1.1 SD 卡简介 雷龙的 SD NAND 有很多型号&#xff0c;在测试中使用的是 CSNP4GCR01-AMW 与 CSNP32GCR01-AOW。芯片是基于 NAND FLASH 和 SD 控制器实现的 SD 卡。具有强大的坏块管理和纠错功能&#xff0c;并且在意外掉电的情况下同样能保证数据的安全。 …

Spring Boot框架下的教育导师匹配系统

第一章 绪论 1.1 选题背景 如今的信息时代&#xff0c;对信息的共享性&#xff0c;信息的流通性有着较高要求&#xff0c;尽管身边每时每刻都在产生大量信息&#xff0c;这些信息也都会在短时间内得到处理&#xff0c;并迅速传播。因为很多时候&#xff0c;管理层决策需要大量信…

鉴源实验室·加密技术在汽车系统中的应用

随着汽车技术的快速发展&#xff0c;现代汽车已经不再是简单的交通工具&#xff0c;而是融合了多种智能功能的移动终端。无论是自动驾驶、车联网&#xff08;V2X&#xff09;&#xff0c;还是车内娱乐系统&#xff0c;数据传输和存储已经成为汽车生态系统中的关键环节。然而&am…

Oracle数据库是什么?

Oracle Database&#xff0c;又名 Oracle RDBMS&#xff0c;简称 Oracle。Oracle 数据库系统是美国 Oracle 公司&#xff08;甲骨文&#xff09;提供的以分布式数据库为核心的一组软件产品&#xff0c;是目前最流行的客户/服务器&#xff08;client/server&#xff09;或B/S体系…

利用Docker Compose构建微服务架构

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 利用Docker Compose构建微服务架构 引言 Docker Compose 简介 安装 Docker Compose 创建项目结构 编写 Dockerfile 前端 Dockerf…

macOS15.1及以上系统bug:开发者证书无法打开,钥匙串访问无法打开一直出现图标后立马闪退

团队紧跟苹果最新系统发现bug:今日设备信息如下,希望能带给遇到这个问题的开发者一点帮助。 错误图如下: 点击证书文件后,先出现钥匙串访问图标,后立马闪退消失 中间试过很多方法,都是一样的表现,最后好在解决了,看网上也没有相关的帖子,这里直接写解决办法和导致原因…

牵手APP引领交友新风尚,多元匹配助力寻找心仪伴侣

第54次《中国互联网络发展状况统计报告》数据显示&#xff0c;截至2024年6月&#xff0c;我国网民规模近11亿人&#xff0c;互联网普及率达78.0%。网络平台的普及&#xff0c;在便捷生活的同时&#xff0c;也衍生出一系列全新的领域与服务生态。如今&#xff0c;线上交友作为一…

C#WPF使用CommunityToolkit.Mvvm库

C#WPF之快速理解MVVM模式 接上篇介绍MVVM&#xff0c;这里使用相关库介绍MVVM。 CommunityToolkit.Mvvm CommunityToolkit.Mvvm介绍 CommunityToolkit.Mvvm是Microsoft Community Toolkit的一部分&#xff0c;它是一个轻量级但功能强大的MVVM&#xff08;Model-View-ViewMod…

Pr 视频效果:ASC CDL

视频效果/颜色校正/ASC CDL Color Correction/ASC CDL ASC CDL ASC CDL效果通过对红、绿、蓝三个原色通道的独立调整&#xff0c;实现对图像色彩的精确控制。在此基础上&#xff0c;还可用于调整处理后图像的整体饱和度。 ◆ ◆ ◆ 效果选项说明 斜率 Slope、偏移 Offset和功…

【Linux】网络编程:应用层协议—HTTP协议(超详细)

目录 一、HTTP协议概念 HTTP协议的基本概念 HTTP的工作流程 二、认识URL URL 的基本结构 URLencode与URLdecode 三、认识HTTP协议 四、HTTP请求格式 1. 请求行&#xff08;Request Line&#xff09; 2. 请求报头&#xff08;Request Headers&#xff09; 3. 空行&a…

kelp protocol

道阻且长,行而不辍,未来可期 有很长一段时间我都在互联网到处拾金,but,东拼西凑的,总感觉不踏实,最近在老老实实的看官方文档 & 阅读白皮书 &看合约,挑拣一些重要的部分配上官方的证据,和过路公主or王子分享一下,愿我们早日追赶上公司里那些可望不可及大佬们。…