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

C++:红黑树

红黑树的概念

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

 红黑树的性质

⭐1.每个节点不是红色就是黑色。

⭐2.根节点是黑色的。

⭐3.如果一个节点是红色的,则它的两个孩子结点是黑色的。也就意味着,红黑树没有连续的红色节点。

⭐4.对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。也就是说每条路径都有相同数量的黑色节点。

⭐5.每个叶子结点都是黑色的(此处的叶子结点指的是空结点。

从性质上分析红黑树的近似平衡

一颗红黑树最短的路径是这条路径全黑。最长是一红一黑相间路径。

对于近似平衡来说:

①最优情况就是左右平衡,此时每条路径都是全黑或者是一红一黑相间,形成满二叉树。

②差的情况就是左右越不平衡,情况就越差。比如左子树全黑,而右子树是一黑一红相间。假设左子树全黑的路径长度位h = logN,因为红黑树要求每条路径的黑色节点的数量是相同的,而右子树是一红一黑相间的,那就说明右子树的长度是左子树的两倍h = 2*logN,这是最差的情况了,再差点就不是红黑树了。

红黑树节点的定义

红黑树节点的定义,跟AVL树的区别就是红黑树不需要平衡因子,而加入了颜色红跟黑。在定义当中,构造函数初始化列表对颜色_col默认初始化为红色是因为权衡了上面所述红黑树性质中的性质3和性质4。

性质3是说明了红黑树没有连续的红色节点,性质4说明的是每条路径都有相同数量的黑色节点。我们在定义节点的时候,需要给节点的颜色初始化,要么是红色,要么是黑色。

如果我们选择了黑色,那么在插入新节点之前,我们是往红黑树插入的嘛,本身就是红黑树,再插入一个黑色节点的话,那么必定会破坏掉红黑树的规则,是一定被破坏掉的,那么就一定需要对这颗红黑树进行调整。

如果我们选择红色,那么有可能会破坏掉红黑树的规则,也可能不会造成破坏。因为新增的节点的父节点是黑色的,那么就不会造成影响,而父节点是红色的话,那就需要调整。

因此,综上所述,默认初始化为红色是比较好的选择。

//使用枚举
enum Colour
{RED,BLACK,
};template<class K,class V>
struct RBTreeNode
{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)  //跟AVL树一样,使用parent节点是为了旋转,_col(RED)  //默认是红色{}
};

红黑色的插入操作

红黑树是在二叉搜索树的基础上加入了平衡限制条件的树,因此红黑树的插入分为两步:

第一步:按照二叉搜索树的规则插入新节点。

第二步:检测新节点插入后,红黑树的性质是否造到破坏。

判断依据:因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:

本文约定好:cur为当前节点,p(parent)为父节点,g(grandther)为祖父节点,u(uncle)为叔叔节点。

①cur为红,p为红,g为黑,u存在且为红

这种情况是插入的节点cur是红色的(默认),cur的双亲节点和叔叔节点是红色的,祖先节点是黑色的。因为不能连续存在红色节点,那么就需要把颜色调整一下即可,不需要旋转。

调整的方法为:将p节点和u节点的颜色改成黑色,同时为了防止g不是一棵单独的树,先把它变成红色,再进行判断,如果是单独的树,那么就把g的颜色变回黑色,如果是一棵子树,那么就往上继续调整。

②cur为红,p为红,g为黑,u不存在/u存在且为黑

这种情况下是需要旋转+变色的。因为当cur为红色,p为红色,g为黑色,而u的情况是:

如果u不存在,cur肯定是新增的节点,因为在新增之前,p和g组成的树是一棵红黑树,在cur新增之后,不符合红黑树的性质。

这种情况下光凭变色是解决不了问题的,因为u为空说明有一条路径只有根节点,而另一条路径上会存在连续红,只凭变色,无论怎么变,都会导致各路径的黑色节点数量不相同,所以需要先根据p和cur的位置来决定旋转的方向而旋转,再变色。

如果u存在,则u是黑色,并且cur原本的颜色一定是黑色的,而现在cur的颜色是红色,那就肯定是第一种情况调整后,导致了现在的cur的颜色变了

这种情况下就跟u不存在的情况一样,采用旋转+变色来解决问题。此时,u存在不存在已经没什么关系了(单独是看构造红黑树的情况来说)。

③cur为红,p为红,g为黑,u不存在/u存在且为黑

这种情况的颜色是跟情况二的一样,区别就是节点的位置不一样。

这种情况是跟第二中情况差不多,就是多了一步旋转,先左旋再右旋,或者先右旋再左旋。

整体代码如下:

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;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//创建完二叉搜索树//开始创建红黑树,使用颜色来判断是否需要调整//循环往上走,循环条件:当走到的parent不为空,并且parent是红色的//即我们列举是三种情况,parent都是红的,就需要重新调整//如果parent是黑色的,那就不需要了。直接就是一棵红黑树,不进入循环while (parent && parent->_col == RED){//保存祖先节点,即g节点Node* grandfther = parent->_parent;//判断父节点是在祖先节点的哪边if (parent == grandfther->_left){//父节点在左边,那么叔叔节点就在右边Node* uncle = grandfther->_right;//情况一:uncle存在且为红。改变颜色即可if (uncle && uncle->_col == RED){//变色。parent->_col = uncle->_col = BLACK;grandfther->_col = RED;//往上走cur = grandfther;parent = cur->_parent;}else  //uncle不存在 或者 存在但是黑色{//情况二  p是g的左孩子,cur是p的左孩子,以g为轴右单旋if (cur == parent->_left){//右单旋RotateR(grandfther);//变色  右单旋后,parent为根节点,变黑色。cur和g节点为红色parent->_col = BLACK;grandfther->_col = RED;}else  //情况三  p是g的左孩子,cur是p的右孩子.{//先以p为轴左旋转RotateL(parent);//变成情况二,再以g为轴右单旋RotateR(grandfther);//变色  cur变成根节点,为黑色。p和g是红色cur->_col = BLACK;grandfther->_col = RED;}break;}}else  //parent是在grandfther的右边{//叔叔节点就在祖先节点的左边Node* uncle = grandfther->_left;//情况一:uncle存在且为红。改变颜色即可if (uncle && uncle->_col == RED){//变色。parent->_col = uncle->_col = BLACK;grandfther->_col = RED;//往上走cur = grandfther;parent = cur->_parent;}else  //uncle不存在 或者 存在但是黑色{//情况二  p是g的右孩子,cur是p的右孩子。if (cur == parent->_right){//左单旋RotateL(grandfther);//变色  右单旋后,parent为根节点,变黑色。cur和g节点为红色parent->_col = BLACK;grandfther->_col = RED;}else  //情况三  p是g的右孩子,cur是p的左孩子.{//先以p为轴右旋转RotateR(parent);//变成情况二,再以g为轴左单旋RotateL(grandfther);//变色  cur变成根节点,为黑色。p和g是红色cur->_col = BLACK;grandfther->_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* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else  {if (ppNode->_left == parent) {ppNode->_left = subL;}else                        {ppNode->_right = subL;}subL->_parent = ppNode;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;	parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left = parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}private:Node* _root = nullptr;
};

旋转请看:AVL树这篇文章有详细解析。红黑树的旋转直接复用AVL树的旋转的代码即可。

红黑树与AVL树的对比

⭐相同点:红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(log_2 N)。

⭐不同点:红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言降低了插入和旋转的次数。而AVL树是高度平衡的二叉搜索树,旋转的次数比红黑树的要频繁。

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

也就是因为红黑树在修改操作方面的性能比AVL树好,因此红黑树都用在了C++的STL库(map/set、mutil_map/mutil_set),Java库、Linux内核等等地方。
 

相关文章:

C++:红黑树

红黑树的概念 红黑树是一棵二叉搜索树&#xff0c;但是红黑树通过增加一个存储位表示结点的颜色RED或BLACK。通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出2倍&#xff0c;因而是接近平衡的。 红黑树的性质 ⭐…...

每天一道算法题の中缀表达式

中缀表达式&#xff08;、-、*、/&#xff09; &#xff1a;中缀表达式是指操作符位于操作数之间的数学表达式。例如&#xff0c;在中缀表达式"2 3"中&#xff0c;操作符""位于操作数"2"和"3"之间。现给定一个中缀表达式&#xff0c…...

Dar语法基础-泛型

泛型 如果查看基本数组类型 List 的 API 文档&#xff0c;您会发现该类型实际上是 List<E>。 <…> 表示法将 List 标记为泛型&#xff08;或参数化&#xff09;类型——具有正式类型参数的类型。 按照惯例&#xff0c;大多数类型变量的名称都是单字母的&#xff0…...

rt-thread------串口(一)配置

系列文章目录 rt-thread 之 fal移植 rt-thread 之 生成工程模板 文章目录系列文章目录前言一、串口的配置step1&#xff1a;通过串口名字找到串口句柄step2&#xff1a;配置串口参数step3&#xff1a;设置串口接收回调函数step4&#xff1a;打开串口设备前言 UART&#xff08…...

Android - 自动系统签名

一、系统签名 以下是两类应用开发场景&#xff1a; 普通应用开发&#xff1a;使用公司自定义 keystore 进行签名&#xff0c;如&#xff1a;微信、支付宝系统应用开发&#xff1a;使用 AOSP 系统签名或厂商自定义 keystore 进行签名&#xff0c;如&#xff1a;设置、录音 系…...

SSH 服务详解 (八)-- vscode 通过 SSH 远程连接 linux 服务器

vscode 通过 SSH 远程连接 linux 服务器 SSH服务详解(一)–Linux SSH 服务器与客户端的安装与启动 SSH服务详解(二)–使用私钥登录 SSH 服务器(免密登录) SSH 服务详解 (三)-- 使用 SSH 代理 SSH 服务详解 (四)-- 本地调用远程主机的命令 SSH 服务详解 (五)-- 远程文件拷贝…...

【PTA Advanced】1060 Are They Equal(C++)

目录 题目 Input Specification: Output Specification: Sample Input 1: Sample Output 1: Sample Input 2: Sample Output 2: 思路 C 知识点UP 代码 题目 If a machine can save only 3 significant digits, the float numbers 12300 and 12358.9 are considered …...

仿真与测试:通过Signal Builder模块生成输入信号

本文研究通过Signal Builder模块生成输入信号的方法。 文章目录1 生成输入信号2 仿真过程2.1 搭建被测模型2.2 搭建Signal Builder输入模块2.3 配置仿真log及仿真3 总结1 生成输入信号 在汽车的电控软件开发中&#xff0c;经常会在Simulink模型内部进行单元测试。单元测试的本…...

云计算培训靠谱吗?

怎么算靠谱的培训呢&#xff1f; 举个例子&#xff1a; 我想参加云计算培训找个工作&#xff0c;机构满足了我的要求&#xff0c;有工作了&#xff0c;但是不是做云计算相关的。 小强也参加了云计算培训&#xff0c;想学好云计算成为技术大牛&#xff0c;最后专业学得普普通…...

力扣SQL刷题10

目录标题618. 学生地理信息报告--完全不会的新题型1097. 游戏玩法分析 V - 重难点1127. 用户购买平台--难且不会618. 学生地理信息报告–完全不会的新题型 max()函数的功效&#xff1a;&#xff08;‘jack’, null, null&#xff09;中得出‘jack’&#xff0c;&#xff08;nul…...

31 岁生日快乐,Linux!

Linux 迎来了 31 岁生日&#xff0c;所以和我一起庆祝 Linux 的 31 岁生日吧&#xff0c;喝上一杯好香槟和一个美味的蛋糕&#xff01;虽然有些人不承认 8 月 25 日是 Linux 的生日&#xff0c;但我知道。1991 年 8 月 25 日&#xff0c;21 岁的芬兰学生 Linus Benedict Torval…...

分布式ID生成方案

文章目录前言一、分布式ID需要满足的条件二、分布式ID生成方式基于UUID数据库自增数据库集群数据库号段模式redis ID生成基于雪花算法&#xff08;Snowflake&#xff09;模式百度&#xff08;uid-generator&#xff09;美团&#xff08;Leaf&#xff09;滴滴&#xff08;Tinyid…...

合宙Air103|fbd数据库| fskv - 替代fdb库|LuatOS-SOC接口|官方demo|学习(16):类redis的fbd数据库及fskv库

基础资料 基于Air103开发板&#xff1a;&#x1f697; Air103 - LuatOS 文档 上手&#xff1a;开发上手 - LuatOS 文档 探讨重点 对官方社区库接口类redis的fbd数据库及fskv库的调用及示例进行复现及分析&#xff0c;了解两库的基本原理及操作方法。 软件及工具版本 Luat…...

【论文精读】Deep Residual Learning for Image Recognition

1 Degradation Problem&#x1f4a6; 深度卷积神经网络在图像分类方面取得了一系列突破。深度网络自然地将低/中/高级特征和分类器以端到端的多层方式集成在一起&#xff0c;特征的“层次”可以通过堆叠层数(深度)来丰富。最近的研究揭示了网络深度是至关重要的&#xff0c;在具…...

Lesson2:基础语法、输出输入

一、基础语法 1、行结构 一个Python程序可分为许多逻辑行&#xff0c;一般来说&#xff1a;一个语句就是一行代码&#xff0c;不会跨越多行。 """比如下面的Python程序&#xff0c;一共有3个逻辑行&#xff0c;每一行都通过print()输出一个结果。""…...

android 9.0去掉前置摄像头闪光灯功能

1.1概述 在9.0的系统rom定制化开发中,在系统中camera2也是非常重要的一部分功能,在很多场合会用到camera2拍照视频,等等功能, 但是在使用过程中发现系统camera2在使用的时候,在前置摄像头进行拍照的时候,会出现闪光灯的情况,对于产品来说,者就是一个大问题,所以产品要求…...

静态分析工具Cppcheck在Windows上的使用

之前在https://blog.csdn.net/fengbingchun/article/details/8887843 介绍过Cppcheck&#xff0c;那时还是1.x版本&#xff0c;现在已到2.x版本&#xff0c;这里再总结下。 Cppcheck是一个用于C/C代码的静态分析工具&#xff0c;源码地址为https://github.com/danmar/cppcheck …...

用一年时间脱胎换骨

生活习惯篇早睡早起11点30之前必须睡觉按时吃饭特别是早餐控糖&#xff0c;少吃甜食早起刷牙后&#xff0c;喝一杯温水保持身材&#xff0c;养成运动健身的习惯养成持续写作的习惯记录选题&#xff0c;金句&#xff0c;素材断舍离&#xff0c;定期整理&#xff0c;把不用的东西…...

全景拼接python旗舰版

前言在这个项目中&#xff0c;您将构建一个管道&#xff0c;将几幅图像拼接成一个全景图。您还将捕获一组您自己的图像来报告最终的结果。步骤1 特征检测与描述本项目的第一步是对序列中的每幅图像分别进行特征检测。回想一下我们在这个类中介绍过的一些特征探测器&#xff1a;…...

(C语言)常见的字符串与内存操作函数

问&#xff1a;1. Solve the problems&#xff1a;我想用三种方法求字符串的长度怎么办&#xff1f;2. strlen处理的字符串中有什么时需要注意&#xff1a;什么只记为什么&#xff1f;当什么不起什么作用时&#xff0c;什么不计算在内&#xff0c;编译器会把什么&#xff0c;什…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...