当前位置: 首页 > news >正文

从零开始的C++(十九)

红黑树:

一种接近平衡的二叉树,平衡程度低于搜索二叉树。

特点:

1.根节点为黑

2.黑色结点的子结点可以是红色结点或黑色结点。

3.红色结点的子结点只能是黑色结点。

4.每个结点到其所有叶子结点的路径的黑色结点个数相同。

5.指向空的结点,指向空的那一侧视为指向黑色结点(指向nullptr的黑色结点,用于明确路径)

6.由于上述规则,使得红黑树任意结点的左右子树高度差不超过二倍(最小是全黑,最大是红黑相交,又由于黑色结点个数需要一致,因此高度不会超过二倍)。

模拟实现红黑树:

1.红黑树的插入:

	// 注意:为了简单起见,本次实现红黑树不存储重复性元素bool Insert(const T& data){if (_pHead == nullptr){Node* cur = new Node(data);_pHead = cur;_pHead->_color = black;return true;}//有根节点的时候Node* cur = new Node(data);Node* news = _pHead;Node* parent = nullptr;//查找插入位置while (news != nullptr){if (news->_data < data){   parent = news;news = news->_pRight;}else if (news->_data > data){ parent = news;news = news->_pLeft;}else{return false;}}//确定插入位置是parent的左还是右if (parent->_data < data){parent->_pRight = cur;cur->_pParent = parent;}else{parent->_pLeft = cur;cur->_pParent = parent;}//开始向上判断//若父节点为黑则可以正常插入,无任何影响//父节点为红才进入,若父节点为空则cur指向根结点同样退出while (parent&&parent->_color==red){   Node* grandparent = parent->_pParent;//parent为红则一定有父节点if(grandparent->_color==black){//得到uncleNode* uncle = nullptr;if (parent->_data < grandparent->_data){uncle = grandparent->_pRight;}else{uncle = grandparent->_pLeft;}//判断uncle情况if (uncle && uncle->_color == red){  //UNCLE存在且是红parent->_color = uncle->_color = black;grandparent->_color = red;cur = grandparent;parent = cur->_pParent;}else{//uncle为黑或者uncle为空if (cur == parent->_pLeft&& parent == grandparent->_pLeft){//右旋RotateR(grandparent);//更新颜色parent->_color = black;grandparent->_color = red;}else if (cur == parent->_pRight&& parent == grandparent->_pRight){//左旋RotateL(grandparent);//更新颜色parent->_color = black;grandparent->_color = red;}//更新后当前子树的根节点为黑,无需向上继续判断,因此parent->_color可以直接使得退出循环else if(cur == parent->_pRight&& parent == grandparent->_pLeft){//先左旋parent再右旋grandparentRotateL(parent);RotateR(grandparent);cur->_color = black;grandparent->_color = red;break;}else{RotateR(parent);RotateL(grandparent);cur->_color = black;grandparent->_color = red;break;}}}else{	 //此时grandparent和parent颜色均是红,报错cout << parent->_data<<"出现连续红结点" << endl;assert(false);}}_pHead->_color = black;}// 左单旋void RotateL(Node* pParent){Node* parent = pParent;Node* pr = parent->_pRight;Node* prl = pr->_pLeft;//记录父节点Node* pp = parent->_pParent;//更新指针parent->_pRight = prl;if (prl)//判断prl是否存在prl->_pParent = parent;pr->_pLeft = parent;parent->_pParent = pr;if (pp == nullptr){//若parent是根节点_pHead = pr;pr->_pParent = nullptr;}else{   //父节点连接if (pp->_data < parent->_data){pp->_pRight = pr;pr->_pParent = pp;}else{pp->_pLeft = pr;pr->_pParent = pp;}}}// 右单旋void RotateR(Node* pParent){Node* parent = pParent;Node* pl = parent->_pLeft;Node* plr = pl->_pRight;//记录父节点Node* pp = parent->_pParent;//更新指针parent->_pLeft = plr;if (plr)//判断prl是否存在plr->_pParent = parent;pl->_pRight = parent;parent->_pParent = pl;if (pp == nullptr){//若parent是根节点_pHead = pl;pl->_pParent = nullptr;}else{   //父节点连接if (pp->_data < parent->_data){pp->_pRight = pl;pl->_pParent = pp;}else{pp->_pLeft = pl;pl->_pParent = pp;}}}

插入一个结点,初始时插入结点为红(若为黑则会导致其祖先结点每条路径黑色结点的个数改变,修改十分麻烦)。若此时父节点为黑,则无需进行任何其余操作。

若父节点为红,此时会出现连续红色结点的情况,不符合红黑树的定义,因此需要修改。

修改主要分以下几种情况:

1.

此时叔叔结点存在且为红色。

修改方式是将父节点和叔叔结点改成黑色,祖先结点改成红色,然后将祖先结点视为新插入结点继续向上判断。此时父节点和叔叔结点改成黑色,不会受其子节点颜色的影响,且对于祖先结点的父节点,每条路径的黑色结点的个数没有变化,因此仍符合红黑树。

2.

此时叔叔结点为黑色结点或者不存在(不存在的情况,根据红黑树规则指向空的结点,指向空的那一侧视为指向黑色结点,因此也可以看做叔叔结点为黑色结点)。此时需要进行旋转来修改这棵子树。若祖先结点和父节点以及新插入结点都在同一侧(比如父节点是祖先结点左子树,新插入结点是父节点的左子树),则只需要对祖先结点进行一次旋转,旋转完成后将父节点改成黑色,祖先结点改成红色即可。若不在同一侧,则需要先对父节点进行一次旋转,再对祖先结点进行一次旋转,旋转完成后新插入结点的颜色为黑,祖先结点颜色为红。

在同一侧的旋转一次。


不在同一侧,旋转两次。

相关文章:

从零开始的C++(十九)

红黑树&#xff1a; 一种接近平衡的二叉树&#xff0c;平衡程度低于搜索二叉树。 特点&#xff1a; 1.根节点为黑 2.黑色结点的子结点可以是红色结点或黑色结点。 3.红色结点的子结点只能是黑色结点。 4.每个结点到其所有叶子结点的路径的黑色结点个数相同。 5.指向空的…...

opencv-使用 Haar 分类器进行面部检测

Haar 分类器是一种用于对象检测的方法&#xff0c;最常见的应用之一是面部检测。Haar 分类器基于Haar-like 特征&#xff0c;这些特征可以通过计算图像中的积分图来高效地计算。 在OpenCV中&#xff0c;Haar 分类器被广泛用于面部检测。以下是一个简单的使用OpenCV进行面部检测…...

C++纯虚函数和抽象类 制作饮品案例(涉及知识点:继承,多态,实例化继承抽象类的子类,多文件实现项目)

一.纯虚函数的由来 在多态中&#xff0c;通常父类中虚函数的实现是毫无意义的&#xff0c;主要都是调用子类重写的内容。例如&#xff1a; #include<iostream>using namespace std;class AbstractCalculator { public:int m_Num1;int m_Num2;virtual int getResult(){r…...

什么是网关和链路追踪,以及怎么使用?

在云计算中&#xff0c;网关和链路追踪也是非常重要的。云服务提供商通常会提供网关和链路追踪等相关服务来帮助用户管理和优化云计算网络。 云计算中的网关通常包括以下几种&#xff1a; 虚拟网络网关&#xff1a;用于将云中不同虚拟网络之间相互连接&#xff0c;实现云内不同…...

git 文件被莫名其妙的或略且无论如何都查不到哪个.gitignore文件忽略的

先说解决办法&#xff1a;git check-ignore -v [文件路径] 这个命令会返回一个忽略规则&#xff0c;以及该规则在哪个文件中定义的&#xff0c;该规则使得指定的文件被忽略。 1.遇到的问题 同项目组&#xff0c;其他同学都可以正常的提交.meta文件&#xff0c;我的提交就出现以…...

nova组件简介

目录 组件关系图 controller节点 openstack-nova-api.service: openstack-nova-conductor.service: openstack-nova-consoleauth.service: openstack-nova-novncproxy.service: openstack-nova-scheduler.service: openstack-nova-conductor.service详解 作用和功能&…...

【Vue】响应式与数据劫持

Vue.js 是一个渐进式的 JavaScript 框架&#xff0c;其中最重要的一个特性就是响应式&#xff08;Reactivity&#xff09;。Vue 借助数据劫持&#xff08;Data Observation&#xff09;技术实现了对数据的响应式更新&#xff0c;当数据发生变化时&#xff0c;它会自动重新渲染视…...

Modbus RTU转Profinet网关连接PLC与变频器通讯在机床上应用案例

背景&#xff1a;以前在机床加工车间里&#xff0c;工人们忙碌地操作着各种机床设备。为了使整个生产过程更加高效、流畅&#xff0c;进行智能化改造。 方案&#xff1a;在机床上&#xff0c;PLC通过Modbus RTU转Profinet网关连接变频器进行通讯&#xff1a;PLC作为整个生产线…...

Autoware 整体架构

Autoware 整体架构 测试...

【maven】手动指定jar推送

说明 为了推送第三方的jar&#xff0c;有时需要指定对应的jar推送到私有仓库。 示例 mvn deploy:deploy-file --settings /home/xxx/.m2/settings.xml -DgroupIdgroupId的值 -DartifactIdartifactId的值 -Dversionjar包的版本号 -Dpackagingjar -Dfilejar的路径 -Durlhttp:/…...

算法---定长子串中元音的最大数目

题目 给你字符串 s 和整数 k 。 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为&#xff08;a, e, i, o, u&#xff09;。 示例 1&#xff1a; 输入&#xff1a;s “abciiidef”, k 3 输出&#xff1a;3 解释&#xff1a;…...

美国汽车零部件巨头 AutoZone 遭遇网络攻击

Security Affairs 网站披露&#xff0c;美国汽车配件零售商巨头 AutoZone 称其成为了 Clop MOVEit 文件传输网络攻击的受害者&#xff0c;导致大量数据泄露。 AutoZone 是美国最大的汽车零配件售后市场经销商之一&#xff0c;在美国、墨西哥、波多黎各、巴西和美属维尔京群岛经…...

WPF面试题入门篇

入门篇[2] 1. 谈谈什么是WPF&#xff1f; WPF&#xff08;Windows Presentation Foundation&#xff09;是微软公司开发的一种用于创建Windows应用程序的用户界面框架。它是.NET Framework的一部分&#xff0c;提供了一种基于XAML&#xff08;可扩展应用程序标记语言&#xf…...

opencv-ORB检测

ORB&#xff08;Oriented FAST and Rotated BRIEF&#xff09;是一种图像特征检测和描述算法&#xff0c;结合了 FAST 关键点检测器和 BRIEF 描述子的优点。ORB 算法具有良好的性能&#xff0c;特别适用于实时应用&#xff0c;如目标追踪、相机定位等。 以下是 ORB 算法的一般…...

please upgrade numpy version to >=1.20

升级 upgrade numpy_升级numpy-CSDN博客 pip install numpy --upgrade 没有pip conda install numpy --upgrade 会报错 conda list numpy来查看numpy版本 似乎这个numpy要看numpy-base这个 似乎没有pip...

关于进制的转化

二进制转十进制&#xff1a; &#x1f530; 方法一&#xff1a;二进制转十进制&#xff0c;用各数的码位与位权的乘积之和&#xff0c;说白了就是用从右到左的每个数去乘以2的幂次方&#xff08;最右边是0&#xff09;&#xff0c;然后就所有的数相加。 补充&#xff1a;位权是…...

JVM 之 字节码指令

目录 一. 前言 二. 指令集 2.1. 支持的数据类型 2.2. 指令分类 三. 指令手册 3.1. 操作数栈 3.2. 运算与转换 3.3. 条件转移 3.4. 类与数组 3.5. 调度与返回加 finally 3.6. 指令手册汇总 3.7. 示例 一. 前言 字节码指令集的特点是数据量短小精干&#xff0c;便于传…...

阿里云跨账号建立局域网

最近有活动&#xff0c;和好友一并薅了下阿里云的羊毛。琢磨着两台机器组一个局域网&#xff0c;于是有了这个需求&#xff0c;把步骤记录一下&#xff1a; 假设两台机器叫A和B&#xff0c;我们开始进行建立和组网 1. 建立ECS 把A机器公共环境装好&#xff0c;然后使用《实例与…...

【OpenSTL】方便好用的时空预测开源库

OpenSTL&#xff1a;方便好用的时空预测开源库 时空预测学习是一种学习范式&#xff0c;它使得模型能够通过在无监督的情况下从给定的过去帧预测未来帧&#xff0c;从而学习空间和时间的模式。尽管近年来取得了显著的进展&#xff0c;但由于不同的设置、复杂的实现和难以复现性…...

【Unity】IBeginDragHandler、IDragHandler 和 IEndDragHandler 介绍

IBeginDragHandler、IDragHandler 和 IEndDragHandler 介绍 IBeginDragHandler、IDragHandler 和 IEndDragHandler 是 Unity 引擎中的三个接口&#xff0c;用于处理 UI 元素的拖放事件。这些接口通常结合使用&#xff0c;构成了 Unity 引擎的拖放事件系统。 IBeginDragHandler…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...