c++红黑树

c++红黑树

1. 红黑树的概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

在这里插入图片描述

2. 红黑树的性质

  1. 每个结点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的

  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点

极端情况:

最短路径:全黑

最长路径:一黑一红到底

  1. 每个叶子结点都是黑色的(叶子结点是NULL结点)

  2. 红黑树的高度接近2logN

    AVL树的高度接近logN,所以红黑树的搜索效率比AVL树要差一点,但是几乎可以忽略不计。但是AVL的相对低高度,是通过频繁的旋转得到的。

3. 红黑树的定义

在定义红黑树的代码时,为了增加代码的可读性,可以用枚举类型把黑色和红色从数字转换成字母。在插入结点的时候,如果直接插入黑色结点会使红黑树的结构变得不可控,所以在插入结点的时候是默认插入红色结点,所以在初始化结点的时候,直接把结点的颜色设定成红色

//颜色
enum color
{RED,BLACK
};//红黑树节点的定义
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;color _col;//构造函数RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

4. 红黑树的插入

红黑树在插入的时候会涉及到结点的变色和旋转,是红黑树结构最核心的内容。

红黑树的插入可以分两种情况讨论,为了方便描述,以插入的结点的视角:

p:表示父结点

g:表示爷结点

u:表示叔结点

cur:表示当前的操作结点(因为会涉及变色的向上更新)

4.1 u存在,且p、u为红

cur为插入的结点,此时cur、p、u均为红色结点,因为规则规定不能有两个相连的红色结点,所以需要对p结点和u进行变色,同时g结点也需要变成红色。

在这里插入图片描述

g结点变色后,还需要分两种情况

1. g结点还有父结点:

如果g结点还有父结点,那么需要把cur结点变成g结点,重复变色的操作,直到满足不变色的条件

在这里插入图片描述

2. g结点就是根结点:

如果g结点就是根结点,那么需要把g结点从红色变回黑色

在这里插入图片描述

4.2 p为红,u为黑或不存在

4.2.1 叔结点存在且为黑

具体操作为:

(p在g的左子树,cur是p的左孩子)

1.将p结点右旋(我的右变成你的左,你变成我的右)

2.p变黑,g变红

在这里插入图片描述

在这里插入图片描述

相反,如果p在g的右子树,cur是p的右孩子。那么对p进行左旋,变色操作相同。因为,整个变色和旋转的操作都没有对u进行操作,所以u存不存在都不会影响。

出现p、u异色或p存在、u不存在的情况分析:

注意:如果u存在,cur不一定是插入的结点,cur可以是插入后向上更新的结点。对于情况一,cur可能是插入的结点也可能不是。但对于第二种情况,cur只有可能是向上更新的结点,也就是说,树的情况应该是这样:

在这里插入图片描述

注意,这种情况不但违反了不能有连续两个红色结点的规则,还违反了最短路径不能超过最长路径的规则。所以这种情况需要进行旋转操作,因为旋转的目的就是为了降低整个树的高度。

而当u不存在时,cur则一定是插入的结点:

在这里插入图片描述

注意,这里不仅违反了不能有两个连续红色结点的规则,因为如果只对p变色,整颗树就违反了最长路径和最短路径的黑色结点数量相等的规则(g没有右子树,可以看作最短路径只有g一个结点),所以需要进行旋转操作让整棵树的高度降低。

4.3 需要双旋的情况二

第三种情况和第二种情况基本相同,但g、p、cur形成了一个<>的形状

举形状为<的为例:

1.先对cur进行左旋

2.再对cur进行右旋

3.g变红,cur变黑

在这里插入图片描述

在这里插入图片描述

如果是>形状的情况,那么需要反过来对cur先右旋再左旋,变色操作相同,g变红,cur变黑。

因为整个过程没有对u进行操作,所以u存在和不存在都没有影响

注意情况三和情况二的不同:

  1. 情况三需要双旋

  2. 结点最终位置不同

  3. 变色操作的对象不同

5. 红黑树的删除

红黑树删除结点可以分为两个步骤:

1.按二叉搜索树删除

2.调整为红黑树结构

5.1 二叉搜索树的删除

二叉搜索树删除可以分为三种情况

1.删除的是叶子结点:

叶子结点直接删,删除叶子结点对二叉搜索树的结构没有影响

2.删除的结点有一个孩子:

有一个孩子的结点的删除,只需要让被删除的结点的孩子代替它的位置即可

3.删除的结点有两个孩子:

中序遍历的下一个结点代替被删除结点的位置

5.2 调整红黑树

5.2.1 被删除的是红色结点

删除红色结点不会破会红黑树的结构,所以对红色结点的删除不需要调整结构
在这里插入图片描述

如果是叶子结点,可以直接删除,无需调整操作

在这里插入图片描述

如果被删除的不是叶子节点,那么这个结点的前驱与它的父结点向上更新值,直到找到本来要删除的结点,然后再把前驱结点删除

5.2.2 被删除的是黑色结点

黑色结点大体可以分成三种情况讨论,被删除结点为D,它的右孩子是subR,它的右孩子的右孩子是subRR

1.D是黑色,subR是红色,subRR是黑色 :

因为没有对subRR进行操作,所以subRR在这种情况下也可以是空

在这里插入图片描述

操作:

1.按二叉搜索树删除

2.把subR改成黑色

2. D是黑色,subR是黑色,subRR是红色:

在这里插入图片描述

操作:

  1. 按二叉搜索树删除
  2. 把subR改成红色

3.D是黑色,subR是黑色,SubRR是黑色:

先看删除D结点会造成的情况:

在这里插入图片描述

删除D结点发现,无法通过简单的变色来调整红黑树的结构

那么此时就需要到subR的层面旋转结点,可以将情况分为四种:其中两种互为镜像,所以这里分析非镜像的两种情况:

此处原本的subR更改标记为cur,它的父结点为p(注意这里p是删除D结点后的结点),它的兄弟结点为b。为了避免结点过多导致图像复杂,简化的图像会有多个标记落在空结点上。

1.cur为p的右孩子,b为黑:

在这种情况中,还需要细分为四个小情况:

在这里插入图片描述

它们对应的解决办法为:

在这里插入图片描述

2.cur为p的右孩子,b为红:

对于这种情况,需要把他转换成上面的情况再进行操作:

在这里插入图片描述

在这里插入图片描述

6. 红黑树的检查

bool Check(Node* cur){if (cur == nullptr)return true;if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}return Check(cur->_left)&& Check(cur->_right);}

黑树的检查

bool Check(Node* cur){if (cur == nullptr)return true;if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}return Check(cur->_left)&& Check(cur->_right);}

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

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

相关文章

Qt消息机制和事件

Qt消息机制和事件 Qt消息机制和事件--2 事件 事件&#xff08;event&#xff09;是由系统或者 Qt 本身在不同的时刻发出的。当用户按下鼠标、敲下键盘&#xff0c;或者是窗口需要重新绘制的时候&#xff0c;都会发出一个相应的事件。一些事件在对用户操作做出响应时发出&…

基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现

基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言…

【Java程序设计】【C00415】基于(JavaWeb)Springboot的家教管理系统(含论文)

基于&#xff08;JavaWeb&#xff09;Springboot的家教管理系统&#xff08;含论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;已经做了六年的毕业设计程序开发&#xff0c;开发过上千…

07、Lua 流程控制

Lua 流程控制 Lua 流程控制控制结构语句 Lua 流程控制 Lua编程语言流程控制语句通过程序设定一个或多个条件语句来设定。在条件为 true 时执行指定程序代码&#xff0c;在条件为 false 时执行其他指定代码。 以下是典型的流程控制流程图&#xff1a; 控制结构的条件表达式结…

VLAN详解

文章目录 VLANWhat-VLAN是什么When-VLAN是什么时候出现的Why-为什么需要VLANHow-VLAN是如何工作预备知识VLAN通信简述流程相同的VLAN间通信不同的VLAN间通信 VLAN的访问链接VLAN tagVLAN的接口类型和VLAN 标签的处理机制Access接口Trunk接口Hybrid接口 接口对比区别 VLAN间路由…

幻兽帕鲁服务器价格表_阿里云/腾讯云/京东云/华为云报价大全

2024年全网最全的幻兽帕鲁服务器租用价格表&#xff0c;阿里云幻兽帕鲁游戏服务器26元1个月、腾讯云32元一个月、京东云26元一个月、华为云24元1个月&#xff0c;阿腾云atengyun.com整理最新幻兽帕鲁专用4核16G、8核16G、8核32G游戏服务器租用价格表大全&#xff1a; 阿里云幻…

文献阅读笔记(Transformer)

文献阅读笔记&#xff08;Transformer&#xff09; 摘要Abstract1、文献阅读1.1 文献题目1.2 文献摘要1.3 研究背景1.4 模型架构1.4.1 Encoder-Decoder1.4.2 注意力机制1.4.3 多头注意力1.4.4 Position-wise Feed-Forward Networks1.4.5 Embeddings and Softmax1.4.6 Positiona…

使用Docker搭建YesPlayMusic网易云音乐播放器并发布至公网访问

目录 ⛳️推荐 1. 安装Docker 2. 本地安装部署YesPlayMusic 3. 部署公有云YesPlayMusic播放器 3.1 安装cpolar内网穿透 3.2 固定YesPlayMusic公网地址 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一…

PyQT5学习--新建窗体模板

目录 1 Dialog 2 Main Window 3 Widget Dialog 模板&#xff0c;基于 QDialog 类的窗体&#xff0c;具有一般对话框的特性&#xff0c;如可以模态显示、具有返回值等。 Main Window 模板&#xff0c;基于 QMainWindow 类的窗体&#xff0c;具有主窗口的特性&#xff0c;窗口…

Freemarker环境搭建快速入门

Freemarker环境搭建&快速入门 测试工程搭建快速入门Freemarker指令语法基础语法种类集合指令&#xff08;List和Map&#xff09;if指令运算符空置处理内建函数 输出静态化文件 测试工程搭建 创建一个freemarker-demo 的测试工程专门用于freemarker的功能测试与模板的测试。…

【数据结构】顺序表的实现——静态分配

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;数据结构 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…

图片标注编辑平台搭建系列教程(3)——画布拖拽、缩放实现

简介 标注平台很关键的一点&#xff0c;对于整个图片为底图的画布&#xff0c;需要支持缩放、拖拽&#xff0c;并且无论画布位置在哪里&#xff0c;大小如何&#xff0c;所有绘制的点、线、面的坐标都是相对于图片左上角的&#xff0c;并且&#xff0c;拖拽、缩放&#xff0c;…

linux之进程

一、背景 冯.诺依曼体系结构 输入设备键盘、鼠标、摄像头、话筒、磁盘、网卡...输出设备显示器、声卡、磁盘、网卡...CPU运算器、控制器存储器一般就是内存 数据在计算机的体系结构进行流动&#xff0c;流动过程中&#xff0c;进行数据的加工处理&#xff0c;从一个设备到另一…

Qt 多线程QThread的四种形式

重点&#xff1a; 1.互斥量&#xff1a;QMutex配套使用&#xff0c;lock(),unlock(),如果一个线程准备读取另一个线程数据时候采用tryLock()去锁定互斥量&#xff0c;保证数据完整性。 QMutexLocker简化版的QMutex,在范围区域内使用。 QMutex mutex QMutexLocker locker(&…

【unity】如何汉化unity编译器

在【unity】如何汉化unity Hub这篇文章中&#xff0c;我们已经完成了unity Hub的汉化&#xff0c;现在让我们对unity Hub安装的编译器也进行下汉化处理。 第一步&#xff1a;在unity Hub软件左侧栏目中点击安装&#xff0c;选择需要汉化的编译器&#xff0c;再点击设置图片按钮…

Dubbo启动流程

Java面试题 Dubbo启动流程 1.服务提供者将服务实例化后注册到注册中心。 2.服务消费者向注册中心订阅所需的服务。 3.注册中心将服务提供者注册的服务地址推送给服务消费者&#xff0c;同时基于长链接推送变更。 4.服务消费者通过代理对象&#xff08;Proxy&#xff09;发起远…

Java毕业设计-基于springboot开发的休闲娱乐代理售票系统-毕业论文+答辩PPT(附源代码+演示视频)

文章目录 前言一、毕设成果演示&#xff08;源代码在文末&#xff09;二、毕设摘要展示1、开发说明2、需求分析3、系统功能结构 三、系统实现展示1、系统功能模块2、后台登录2.1管理员功能2.2用户功能 四、毕设内容和源代码获取总结 Java毕业设计-基于springboot开发的休闲娱乐…

腾讯云优惠券领取及使用常见问题解答

随着云计算的普及&#xff0c;腾讯云作为国内领先的云计算服务提供商&#xff0c;为越来越多的企业和个人提供了丰富的云产品和服务。为了帮助用户更好地了解和使用腾讯云优惠券&#xff0c;本文将为大家解答关于腾讯云优惠券领取及使用的常见问题。 一、腾讯云优惠券概述 腾讯…

利用互斥锁解决缓存击穿问题

2.9 利用互斥锁解决缓存击穿问题 核心思路&#xff1a;相较于原来从缓存中查询不到数据后直接查询数据库而言&#xff0c;现在的方案是 进行查询之后&#xff0c;如果从缓存没有查询到数据&#xff0c;则进行互斥锁的获取&#xff0c;获取互斥锁后&#xff0c;判断是否获得到了…

包子凑数(蓝桥杯,闫氏DP分析法)

题目描述&#xff1a; 小明几乎每天早晨都会在一家包子铺吃早餐。 他发现这家包子铺有 N 种蒸笼&#xff0c;其中第 i 种蒸笼恰好能放 Ai 个包子。 每种蒸笼都有非常多笼&#xff0c;可以认为是无限笼。 每当有顾客想买 X 个包子&#xff0c;卖包子的大叔就会迅速选出若干笼…