当前位置: 首页 > 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…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

Spring AOP代理对象生成原理

代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】&#xff0c;这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。

2024 年&#xff0c;高端封装市场规模为 80 亿美元&#xff0c;预计到 2030 年将超过 280 亿美元&#xff0c;2024-2030 年复合年增长率为 23%。 细分到各个终端市场&#xff0c;最大的高端性能封装市场是“电信和基础设施”&#xff0c;2024 年该市场创造了超过 67% 的收入。…...