C++分析红黑树

目录

红黑树介绍

红黑树的性质与平衡控制关系

红黑树节点的插入

情况1:不需要调整

情况2:uncle节点为红色

情况3:uncle节点为黑色

总结与代码实现

红黑树的删除(待实现)

红黑树的效率


红黑树介绍

红黑树是第二种平衡二叉搜索树,为了解决普通二叉搜索树的效率问题,红黑树在控制平衡时选择近似平衡而不是AVL树的绝对平衡,每一个节点都会存储一个表示颜色的属性,包括红色和黑色,通过对颜色的控制,红黑树可以保证没有一条路径会比其他路径的长度长出两倍

红黑树的性质

  1. 根节点一定是黑色
  2. 一条简单路径下不会出现连续的红色节点,如果父亲节点为红色,则其孩子节点一定为黑色,如果父亲节点为黑色,则没有限制
  3. 对于每个节点来说,从该节点开始到其后代所有节点的简单路径上均包含相同数量的黑色节点
  4. (了解)每个空叶子结点都是黑色的

在上图中,NIL表示空叶子节点,以NIL作为结束条件,一共有11条路径,需要注意不是以叶子节点为结束条件(即不是7条路径)

满足上面的四个性质,红黑树就可以保证其相对平衡的条件:红黑树可以保证最长路径会比最短路径的长度长出两倍。

最短路径:节点颜色为全黑的路径,此时黑色节点的个数即为路径的长度
最长路径:节点颜色为红色和黑色交替出现的路径

红黑树的性质与平衡控制关系

因为黑色节点的个数可以决定一条路径的长度,假设黑色节点的个数为h,则最短路径的长度也为h,满足第二条规则时,红色节点的个数不会超过黑色节点(1个或者h个),从而最长路径的最大长度为2h,因为红色节点是在黑色节点出现后才会出现。

如果按照下图的插入方式导致红色节点连续出现:

违反了规则二,此时最短路径的长度的两倍会小于最长路径的长度,从而打破了红黑树的平衡。

如果插入的27为黑色节点,则最长路径的长度增加,并且黑色节点的个数也增加,违反了规则三,此时对于其他路径来说也需要增加一个黑色节点。

所以为了维持平衡,不可以插入黑色节点,此时最长路径的长度刚好为2h,如下图所示:

综上所述,在满足第二条规则和第三条规则下可以保证红黑树的最长路径始终不会超过最短路径的2倍

红黑树节点的插入

根据红黑树的性质可以看出红黑树如何控制高度近似平衡,但是如果插入了节点,可能会破坏原有的平衡,此时需要通过重新填色或者旋转调整使红黑树重新达到平衡

在前面的分析中可以得知,如果插入的节点是黑色节点,可能会导致每一条路径都需要多一个黑色节点,为了更加方便处理,规定插入的节点是红色节点

情况1:不需要调整

如果插入的节点是红色节点,并且其父亲节点是黑色节点,此时不需要进行任何处理,当父亲节点是黑色节点时,保证了规则三没有违背,因为黑色节点的个数决定了高度,插入前如果保证原树是红黑树,那么高度一定满足红黑树的近似平衡,并且此时插入红色节点也不会违背规则二,如下图的一种情况所示:

情况2:uncle节点为红色

如果cur的节点是红色,并且其父亲节点(假设为parent)是红色节点,此时说明父亲的兄弟节点(假设为uncle)也一定为红色,因为插入前一定是红黑树(插入前不是红黑树那么插入前就已经出现了不平衡,需要进行调整),当父亲节点时红色,说明父亲节点所在的路径缺少黑色节点,违反了规则三。父亲节点的父亲节点(假设为grandfather)也一定为黑色,如果为红色则违反了第二条规则所以插入前的状态应该为:

cur节点可能为新增的红色节点,也可能为上一次调整变为的红色节点

  1. 假设a、b、c、d和e为黑色节点个数为0的红黑树,此时cur为新插入节点如下图所示:

因为出现了连续的红色节点,为了恢复红黑树的平衡,此时需要进行调整,因为uncle节点为红色,为了保证每条路径上都有一个黑色节点并且保证没有连续的红色节点出现,将parent节点的颜色改为黑色,将uncle节点的颜色改为黑色,将grandfather节点改为红色(如果grandfather节点为根节点则再处理为黑色),处理完后,cur = grandfather继续向上调整直到遇到根节点:

对于 uncle为红色的情况来说,不需要考虑插入位置在 parent左或者右、 parentgrandfather的左或者右已经 unclegrandfather的左或者右,因为不论是哪种情况,本质都是将 uncleparent变为黑色增加两边路径的黑色节点使其满足规则二和规则三
  1. 假设a、b、c、d和e为黑色节点个数大于0,此时cur为上一次调整变成的红色节点,如下图所示:

对于当前情况来说,只有cur位置的节点是红色,其余几棵子树已经通过调整变成了符合规则的红黑树,所以也可以归类为上面的情形,处理方式与上面相同

情况3:uncle节点为黑色

uncle节点为黑色时一共有两种情况:

  1. uncle节点不存在
  2. uncle节点存在且为黑

因为红黑树规定下空节点是黑色的,所以uncle节点不存在与存在且为黑可以视为一种情况,下面主要以uncle节点不存在进行分析,对于uncle节点存在且为黑的情况给出一种分析,剩下与uncle节点不存在的情况类似

下面分析中, uncle节点不存在时将不展示 NIL节点

cur节点在parent的右子树并且parentgrandfather的右子树时,并且uncle不存在时,此时需要进行左单旋,将parent的颜色更新为黑色,grandfather的颜色更新为红色,因为如果仅仅是将parent变成黑色,则依旧不满足规则三,其余路径还是少一个黑色节点,通过左单旋使得当前子树的根节点变为黑色时可以使当前根节点出发的所有路径都至少有一个黑色节点,如下图所示:

cur节点在parent的左子树并且parentgrandfather的左子树时,此时需要进行右单旋,将parent的颜色更新为黑色,grandfather的颜色更新为红色,原因类比左单旋,过程如下图所示:

cur节点在parent的右子树并且parentgrandfather的左子树时,此时需要进行右左双旋,将cur的颜色更新为黑色,将grandfather的颜色更新为红色,过程如下:

cur节点在parent的左子树并且parentgrandfather的右子树时,此时需要进行左右双旋,将cur的颜色更新为黑色,将grandfather的颜色更新为红色,过程如下:

如果uncle节点本身存在,那么经过uncle节点的路径下方的两个子树为红色,而parent插入节点前至少会有一个黑色节点,如下图所示:

此时在parent的右侧插入一个cur节点(本身就是红色节点cur节点也是如此)如下:

此时如果只是对parent节点的颜色进行改变,则会出现parent所在路径比uncle所在路径多一个黑色节点,所以为了解决这个问题,单单改变颜色无法解决,当curparent的右边时,只需要一次左单旋即可,而curparent的左边时,需要先进行右旋再进行左旋,以右左双旋为例,如下图所示:

对于其他两种情况也是一样的道理,此处不再赘述

总结与代码实现

红黑树的插入过程一共有三种情况:

  1. 当插入节点的父亲节点为黑色时,直接插入节点即可,不需要进行任何调整
  2. 当uncle节点为红色时,cur节点的parent节点和uncle节点均变为黑色,将所在子树的根节点变为红色,如果子树的根节点为整棵树的根节点,则再处理为黑色
  3. 当uncle节点为黑色(包括空节点的黑色和存在且为黑色节点)时,需要进行旋转
    1. parentcur节点是同方向时,进行一次旋转(左旋或者右旋),将parent节点变为黑色,将grandfather节点变为红色,此时因为parent是本棵子树的根,所以更新完后当前子树也是一棵红黑树,颜色是黑色不需要再进行调整
    2. parentcur节点不是同方向时,进行两次旋转(先左后右或者先右后左),再将cur节点变为黑色,grandfather节点变为红色,更新完后当前子树也是一棵红黑树,并且因为cur的颜色是黑色不需要再进行调整

代码实现:

// 树插入
bool insertNode(const pair<T, V>& kv)
{// 判断key是否已经存在if (findNode(kv.first)){// 已经存在时插入失败return false;}// 判断根节点是否为空,为空则作为第一个节点if (_root == nullptr){_root = new node(kv);return true;}// 根节点不为空时接着遍历插入node* cur = _root;// 定义父亲节点记录父亲的位置node* parent = _root;while (cur){if (kv.first > cur->_kv.first){// 大于根节点数据,插入在右子树,走到左子树的空位置parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){// 小于根节点数据,插入在左子树,走到右子树的空位置parent = cur;cur = cur->_left;}}// 创建node节点// 创建节点可以使用新节点,但是要使cur走到新节点的位置,便于下面判断新节点的平衡因子,再通过cur判断祖先节点的平衡因子cur = new node(kv);// parent为叶子节点,链接新节点if (parent->_kv.first < kv.first){// 如果是右子树,则插入在右子树parent->_right = cur;}else{// 否则插入在左子树parent->_left = cur;}// 链接父亲cur->_parent = parent;// 插入节点颜色为红色cur->_col = Red;// 存在父亲且当父亲节点为红色时需要判断是否更新while (parent && parent->_parent && parent->_col == Red){node* grandfather = parent->_parent;if (grandfather->_right == parent){node* uncle = grandfather->_left;if (uncle && uncle->_col == Red){// 叔叔存在且为红uncle->_col = parent->_col = Black;grandfather->_col = Red;cur = grandfather;parent = cur->_parent;}else{// cur在parent的右孩子if (cur == parent->_right){// 右右->左单旋rotateLeft(grandfather);// 改变颜色grandfather->_col = Red;parent->_col = Black;}else{// 右左->右左双旋rotateRight(parent);rotateLeft(grandfather);cur->_col = Black;grandfather->_col = Red;}// 旋转结束后不需要再向上更新break;}}else{node* uncle = grandfather->_right;if (uncle && uncle->_col == Red){// 叔叔存在且为红uncle->_col = parent->_col = Black;grandfather->_col = Red;// 继续向上更新cur = grandfather;parent = cur->_parent;}else{if(cur == parent->_left){// 叔叔不存在// 左左->右单旋rotateRight(grandfather);// 改变颜色grandfather->_col = Red;parent->_col = Black;}else{// 左右->左右双旋rotateLeft(parent);rotateRight(grandfather);// 改变颜色grandfather->_col = Red;cur->_col = Black;}// 旋转结束后不需要再向上更新break;}}}// 根节点为黑色_root->_col = Black;return true;
}

红黑树的删除(待实现)

红黑树的效率

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(),红黑树不追

求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,

所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红

黑树更多

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

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

相关文章

提前批测开三面,已OC!

大家好&#xff0c;我是洋子 近期百度提前批已经开始有一段时间了&#xff0c;甚至已经有不少 25 届的同学 oc 了&#xff0c;这里分享一位已经顺利 oc 百度提前批测开岗位同学的三轮面试面经 整个三轮技术面试总体难度不高&#xff0c;但考察知识广度比较广&#xff0c;如果…

SQL注入:MySQL元数据库,外网实战手工SQL注入

MySQL元数据库 MySQL的元数据库是一组特殊的数据库&#xff0c;用于存储MySQL服务器的元数据信息&#xff0c;在sql注入中较为常用为以下两种元数据库&#xff1a; information_schema&#xff1a;这个数据库包含了MySQL服务器上所有其他数据库的元数据信息。例如数据库名、表…

AI人工智能为企业带来的优势及应用例子

自2022年知名大型语言模型及其他 AI 产品面世至今&#xff0c;无论商界、政府以至社会各界都逐渐关注人工智能的发展&#xff0c;并纷纷引入 AI 技术&#xff0c;全球正式踏入人工智能的新纪元。根据 Statista 一份有关全球人工智能软件的数据研究&#xff0c;至2025年预测各国…

Pytorch基础模型,数据加载,优化算法

目录 一.nn.Module 二.优化器类 三.损失函数 四.在GPU上运行代码 五.常见的优化算法 1.梯度下降算法 2.动量法&#xff1a; 3.AdaGrad 4.RMSProp 六.Pytorch中的数据加载 1.数据集类 2.迭代数据集 2.Pytorch自带的数据集 一.nn.Module nn.Modul是torch.nn提供的一个…

趋动科技荣登「AIGC赋能金融创新引领者TOP20」

2023年11月28日&#xff0c;“极新AIGC行业峰会”在北京召开&#xff0c;峰会以“AI落地”为指引&#xff0c;探究AI实践与产业化。 从制造业到金融服务业&#xff0c;从医疗保健到交通运输&#xff0c;从文化娱乐到消费零售&#xff0c;智能客服、数字人直播、智能巡检机器人&…

vue前端项目--路由vue-router

1. 路由介绍 我们可以总结一下从早期网站开发到现代单页应用(SPA)的发展过程及其关键概念&#xff1a; 早期的服务器端渲染 (SSR): 早期的网站开发中&#xff0c;服务器负责生成完整的 HTML 页面&#xff0c;并将其发送给客户端展示。 每个 URL 对应一个特定的控制器(Control…

基于CUDA12.1+CUDNN8.9+PYTORCH2.3.1,实现自定义数据集训练

目录 0 结果预览 1 核心点 2 参考链接 0 结果预览 1 核心点 yolo命令行CL需要将虚拟环境的yolo程序加入系统路径。 遇到conda install 失效问题&#xff0c;重建新的虚拟环境&#xff0c;再进行安装。 whl可以下载好后再安装。 pip install F:\tool\ai\torch-2.3.1cu…

leetcode日记(64)最小覆盖子串

很复杂的题目&#xff0c;无论是思路还是实践都很难… 思路还是看了答案&#xff08;&#xff1f;&#xff09;设定两个指针“框”出一串字符串&#xff0c;初始两个指针都指在s的零位&#xff0c;先移动下指针&#xff0c;直到使框出的字符串中包含t中所有字符串&#xff0c;…

JDK17安装与配置

为了学习spring boot3.x&#xff0c;首先确保本地安装了17以上的jdk版本。 安装版本&#xff1a;jdk-17.0.10_windows-x64_bin.exe 傻瓜式安装&#xff0c;步骤省略&#xff0c;这里设置的安装位置&#xff1a;D:\Programs\Java\jdk-17 JAVA_HOME环境变量配置&#xff1a; #…

容器七层负载均衡解决方案——IngressNGINX

一、概述 当我们使用 K8S 对容器进行编排时&#xff0c;基于负载均衡和高可用方面考虑&#xff0c;且设计上 Pod 易失态&#xff0c;不能直接使用 PodIP 作为外部访问的方式。因此&#xff0c;K8S 官方提供了一些负载均衡的解决方案。这其中有四层和七层两种&#xff0c;本文主…

养猫必看!热销猫罐头有哪些?2024年推荐这4款口碑很好的主食罐

开猫咖3年啦&#xff0c;店里有加菲&#xff0c;美短&#xff0c;布偶&#xff0c;暹罗&#xff0c;都是我一手带大的。店铺开在高校附近&#xff0c;顾客以学生为主&#xff0c;也有很多养猫人士会到店里来&#xff0c;和我交流选粮经验。很多养猫人都在喂主食罐头&#xff0c…

FreeRTOS基础入门——FreeRTOS的任务基础知识(四)

个人名片&#xff1a; &#x1f393;作者简介&#xff1a;嵌入式领域优质创作者&#x1f310;个人主页&#xff1a;妄北y &#x1f4de;个人QQ&#xff1a;2061314755 &#x1f48c;个人邮箱&#xff1a;[mailto:2061314755qq.com] &#x1f4f1;个人微信&#xff1a;Vir2025WB…

Leetcode每日刷题之字符串相加(C++)

在学习的同时也不要忘记适当练习&#xff0c;本题字符串相加主要在于字符串类型与整数类型的转化&#xff0c;要将字符串类型转化为整数类型计算后转化为字符串类型输出即可。 思路解析 根据题中给出的信息&#xff0c;我们不可以使用库函数计算大整数&#xff0c;也不能直接将…

做空日经指数的策略与时机

一、市场背景分析 在全球股市的剧烈波动中&#xff0c;日本股市的表现尤为引人关注。日经225指数在经历一轮暴跌后&#xff0c;又出现了大幅反弹&#xff0c;这种剧烈的波动为投资者提供了做空日经指数的机会。近期&#xff0c;日本股市受到日元汇率波动、日本央行货币政策以及…

C++中的string的介绍(从string到STL)

C中的string的介绍 文章目录 C中的string的介绍1. 从string到STL2. string 的构造函数3. string 的iterator&#xff08;迭代器&#xff09;4. string 中的元素访问5. string 中容量相关6. string 中的插入删除7. string 中的查找8. string 的剩余函数 1. 从string到STL 严格来…

【轻松拿捏】Java是如何实现跨平台性的?

Java是如何实现跨平台性的&#xff1f; 一、Java 的跨平台性主要通过以下几个核心机制实现&#xff1a; 二、具体实现 三、示例 四、JVM 工作示意图 五、总结 &#x1f388;边走、边悟&#x1f388;迟早会好 一、Java 的跨平台性主要通过以下几个核心机制实现&#xff…

CICD流水线

一、CICD流水线简介 CICD概念 CI/CD流水线是现代软件开发的一个核心概念&#xff0c;它涉及自动化和管理软件从开发到部署的整个生命周期 概念定义 具体有三点&#xff1a;持续集成、持续交付、持续部署 流水线组成为&#xff1a;代码提交、测试、构建、部署、结果通知 二…

PHP最新可用获取QQ昵称API接口源码_非第三方

PHP最新可用获取QQ昵称API接口源码&#xff0c;运行环境为php7-8都可以&#xff0c;内容为直接调用QQ空间接口 在需要展示QQ昵称处&#xff0c;直接调用以下函数就可以。 例如&#xff1a;get_qq_nick(123456)就会直接输出123456的qq号昵称。 API源码下载&#xff1a;QQ昵称AP…

第R2周:LSTM-火灾温度预测:一文搞懂LSTM(长短期记忆网络)

一文搞懂LSTM&#xff08;长短期记忆网络&#xff09; 一句话介绍LSTM&#xff0c;它是RNN的进阶版&#xff0c;如果说RNN的最大限度是理解一句话&#xff0c;那么LSTM的最大限度则是理解一段话&#xff0c;详细介绍如下&#xff1a; LSTM&#xff0c;全称为长短期记忆网络(Lo…

python-鼠标绘画线条程序

闲来无聊简单编写了一个绘图小程序。 主要思路 主要是基于Python中的内置模块turtle编写的&#xff0c;简单扩展了一下&#xff0c;通过绑定事件能够达到鼠标绘制、删除、存储已经绘制图案的线条这几个功能。 路径结构 -draw- define.py- main.py- myturtle.py使用 点住鼠…