红黑树(RBTree)

文章目录

  • 红黑树的概念
  • 红黑树的性质
  • 红黑树结点定义
  • 红黑树的插入
  • 红黑树的验证
  • 参考源码

除了AVL树，红黑树也是被广泛使用的平衡二叉树。两者都解决了二叉搜索树的平衡问题。
关于AVL树，之前博客有介绍： AVL树

红黑树的概念

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

比如下图就是一棵红黑树
image.png

红黑树的性质

所谓红黑树，不仅仅是一个二叉搜索树，还要必须满足以下规则：

  1. 每个节点不是黑色就是红色
  2. 根节点是黑色
  3. 如果节点为红色，则它的两个孩子结点是黑色的。(不能出现连续的红色)
  4. 任意节点到NULL(树尾端)的任何路径，所包含黑色节点的个数必须相同。
  5. 每个叶子结点都是黑色的（此处的叶子结点指定是空结点）。

对于第四点规则：任意节点到NULL(树尾端)的任何路径，所包含黑色节点的个数必须相同。

比如上图从根节点到任意NULL节点，所包含的黑色节点都是3个。
根据红黑树的性质可以得出一颗红黑树的最短路径全部是由黑色结点构成

image.png
而最长路径是一黑一红结点构成的路径(因为要满足红黑第4点性质)

image.png
所以对于一颗红黑树来说，最长路径不会超过最短路径的二倍

红黑树结点定义

结点直接定义为K,V模型，

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 _color; //使用枚举值定义结点的颜色RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(RED){}
};

这里再结点定义的时候，默认颜色初始化为红色。也就是说，当插入一个新节点时，默认是红色的。这是为什么？

  • 如果新插入结点是黑色的，那么一定会破坏规则4，插入新结点的这条路径黑色结点个数就会比其他路径多一个。这时就需要对红黑树进行调整。
  • 如果插入结点是红色的，如果父结点是红色的，就会出现连续红色结点破坏了规则3。但如果父结点是黑色的，插入后就仍然满足红黑树的性质，无需进行调整。

所以在构造结点的时候默认初始化为红色更为合理。

红黑树的插入

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

  • 按照二叉树的规则插入新节点
bool insert(const pair<K,V>& kv)
{//空树直接做为根结点if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}//确定插入的位置Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;//键值冗余不允许插入}}// 进行链接cur = new Node(kv);if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;return true;
}
  • 检测新节点插入后，红黑树的性质是否遭到破坏
    因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连 在一起的红色节点，此时需要对红黑树分情况来讨论:
    约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

1. 情况一：cur为红，p为红，g为黑，u存在且为红
cur新节点肯定为红，p也只能为红，p如果为黑无需处理。cur和p都为红，g只能为黑。如果此时g为红说明插入前就不是红黑树。 只用看u节点是否存在和其颜色(对应的是三种情况)。 如果u存在且为红

比如对下图插入新节点-1(其中c、d、e是任意一种包含一个黑色节点的红黑子树)

image.png
插入新节点cur后，违反了红黑树的性质3。出现了相同的红色节点。并且其叔叔节点u是红色，就需要对其进行颜色调整。
将p节点和u节点变为黑色，再将g节点变为红色。如下图：

image.png
此时g节点的父结点是红色，仍然破坏性质3，出现了连续的红色节点。(如果g节点的父结点是黑色的，就无需处理)还需要继续向上调整。

让g节点当做cur，继续向上调整。根据u节点的情况进行调整。下图u节点正好是红色，对应得是情况1，如果出现其他情况，分别对应得是下面分析得情况2和情况3进行处理。

image.png
注意： 插入在0或2的左右，处理情况都是一样的。因为u节点都是红色。只需进行颜色调整即可。

当新插入节数的叔叔存在且为数色的时候，解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

2. 情况二: cur为红，p为红，g为黑，u存在且为黑

当u存在时且为黑，这种情况一定是由情况1继续向上调整造成的因为cur新节点肯定为红，p也只能为红，p如果为黑无需处理。cur和p都为红，g只能为黑。如果此时u存在且为黑只能说明插入前就不是一棵红黑树。
image.png
当出现u存在且为黑的情况，一定是由情况一继续向上调整造成的，并且cur之前是黑色的(只用cur是黑色的才能说明其是红黑树)，cur子树经过情况1调整之后由黑色变为了红色。
比如下面这种情况。
对下面这棵红黑树插入新节点5(插入再7或者10 的 左或右对应的都是情况1，这里以7的左为例)
image.png
插入新节点，引发情况1，进行颜色调整，如下。

image.png
此时cur为红，p为红，g为黑，u存在且为黑。需要对其进行旋转处理。
p是g的左，cur是p的左，进行右单旋处理。如下：

image.png
右单旋结束后，还需要对其进行颜色调整。p变黑，g变红即可。如下：

image.png
相反，如果u存在且为黑。p是g的右子树，cur是g的右子树，则需要进行左单旋+变色处理。(插入再16或19 的左或右对应的都是这种情况)
image.png

当情况1调整完后，p是g的左子树，cur是p的右子树时，这种情况就需要左右双旋处理了
比如下面这种情况：
对下面这课红黑树插入新节点
image.png
对应的是情况1，进行变色调整

image.png
颜色调整完之后此时，p是g的左子树，cur是p的右子树时，这种情况就需要左右双旋处理了(先左旋，再右旋)
以p为轴点进行左单旋(不用变色)
image.png
再以g为轴点进行右单旋

image.png
最后，将cur变黑，g变红即可

image.png
相反，如果u存在且为黑，且p是g的右子树，cur是p的左子树时，这种情况就需要右左双旋处理了。
比如下面红黑树插入新节点36之后，引发情况1进行变色。
此时 p是g的右子树，cur是p的左子树时，先以p为轴点进行右单旋，再以g为轴点左单旋，最后也是将cur变黑，g变红即可。
image.png

总结：
当u存在且为黑时，这种情况一定是由情况一引发的。当情况一进行颜色调整完之后，对应的四种情况分别是：

  • p是g的右子树，cur是p的右子树。左单旋 + p变黑，g变红
  • p是g的左子树，cur是p的左子树。右单旋 + p变黑，g变红
  • p是g的右子树，cur是p的左子树。右左双旋 + cur变黑，g变红。
  • p是g的左子树，cur是p的右子树。左右双旋 + cur变黑，g变红。

3. 情况三: cur为红，p为红，g为黑，u不存在

当u不存在时对应的是下面这种情况。cur一定是新插入节点，因为cur如果不是新节点，则cur和p节点一定有一个是黑色的(性质3)。cur和p有一个为黑时，不满足性质4，只能说明cur就是新插入节点。

image.png

cur是新插入节点，对应的也是四种情况。

  • 当u不存在，p是g的左子树，cur是p的左子树。 右单旋 + p变黑，g变红。

image.png

  • 当u不存在，p是g的右子树，cur是p的右子树。 左单旋 + p变黑，g变红。

image.png

  • 当u不存在，p是g的左子树，cur是p的右子树。 左右双旋 + cur变黑，g变红。

image.png

  • 当u不存在，p是g的右子树，cur是p的左子树。 右左双旋 + cur变黑，g变红。

image.png
代码实现(左旋和右旋的代码和AVL树的一样)

bool insert(const pair<K,V>& kv)
{//空树直接做为根结点if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}//1、 确定插入的位置Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;//键值冗余不允许插入}}//2、进行链接cur = new Node(kv);if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//3、若插入结点的父结点是红色的，则需要对红黑树进行调整while (parent != nullptr && parent->_color == RED){Node* grandfahter = parent->_parent; //parent为红色，grandfahter一定存在if (grandfahter->_left == parent) //parent是grandfather左孩子的情况{Node* uncle = grandfahter->_right;//uncle若存在，一定是其右孩子if (uncle != nullptr && uncle->_color == RED)//情况一：u存在且为红{//颜色调整parent->_color = BLACK;uncle->_color = BLACK;grandfahter->_color = RED;//继续向上调整cur = grandfahter;parent = cur->_parent;}else //情况2+3(u不存在/u存在且为黑){//cur是parent的左/*    g*   p    u* c*/if (cur == parent->_left){//右旋RotateR(grandfahter);//更新颜色parent->_color = BLACK;grandfahter->_color = RED;}else//cur是parent的右{/*    g*   p    u*     c*///左右双旋(先以p为旋点左旋，在以g为旋点右旋)RotateL(parent);RotateR(grandfahter);// cur变黑，g变红cur->_color = BLACK;grandfahter->_color = RED;}break;}}else //parent是grandfather的右孩子{Node* uncle = grandfahter->_left; //uncle若存在一定是其左孩子if (uncle != nullptr && uncle->_color == RED)//u存在且为红{//颜色调整parent->_color = BLACK;uncle->_color = BLACK;grandfahter->_color = RED;//继续向上调整cur = grandfahter;parent = cur->_parent;}else//u不存在/u存在为黑{//cur是parent的右/*   g*  u   p *		 c*/if (cur == parent->_right){//左旋RotateL(grandfahter);parent->_color = BLACK;grandfahter->_color = RED;}else{//cur是parent的左/*   g*  u   p*	 c*///右左双旋(先以p为轴点右旋，再以g为轴点左旋)RotateR(parent);RotateL(grandfahter);// cur变黑，g变红cur->_color = BLACK;grandfahter->_color = RED;}break;}}}//根节点一定为黑_root->_color = BLACK;return true;
}
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parent_parent = parent->_parent;//让subRL结点作为parent结点的右子树 更新完之后处理subRL_parent;parent->_right = subRL;if (subRL != nullptr){subRL->_parent = parent;}//让parnet做为subR的左子树 更新完之后处理parent的_parentsubR->_left = parent;parent->_parent = subR;//subR做为这颗最小不平衡子树的根节点if (parent_parent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subR;}else{parent_parent->_right = subR;}subR->_parent = parent_parent;}
}void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parent_parent = parent->_parent;//让subLR节点做为parent节点的左子树 更新完之后处理subLR的_parent;parent->_left = subLR;if (subLR != nullptr){subLR->_parent = parent;}//让parent节点做为subL的右子树 更新完之后处理parent的_parentsubL->_right = parent;parent->_parent = subL;//让这颗最小不平衡子树的parent节点做为subL的右子树if (parent_parent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subL;}else{parent_parent->_right = subL;}subL->_parent = parent_parent;}
}

红黑树的验证

红黑树的检测分为两步：

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
void Inorder()
{_Inorder(_root);
}
void _Inorder(Node* root)
{if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << ' ';_Inorder(root->_right);
}
  1. 检测其是否满足红黑树的性质
  • 检查根节点是否是黑色
  • 检查每条路径的黑色节点个数是否相等
  • 检查是否出现连续的红色节点
bool IsRBtree()
{//根节点是红色肯定不是红黑树if (_root->_color == RED){cout << "根节点是红色" << endl;return false;}//红黑树每条路径的黑色节点个数都相等，给定一个基准值进行判断每条路径的黑色节点个树是否相等int reference_value = 0;Node* cur = _root;while (cur != nullptr){if (cur->_color == BLACK){reference_value++;}cur = cur->_left;}//检查每条路径的黑色节点个数是否相等，并检查是否出现连续的红色节点return _Check(_root, 0, reference_value);
}
bool _Check(Node* root, int blacknum, int reference_value)
{if (root == nullptr){if (reference_value != blacknum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}else{//cout << "黑色节点个数相等" << endl;return true;}}if (root->_color == BLACK){blacknum++;}if (root->_color == RED && root->_parent != nullptr && root->_parent->_color == RED)//root节点的父结点为红色则出现连续的红色节点{cout << "出现连续的红色节点" << endl;return false;}return _Check(root->_left, blacknum, reference_value)&& _Check(root->_right, blacknum, reference_value)；
}

参考源码

  • gitee 红黑树
  • 菜鸟一枚，写的不好的地方请各位大佬多多包涵，手下留情。

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

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

相关文章

【c++】vector用法详解

【c++】vector用法详解

vector用法详解 vector定义vector容器的构造函数vector容器内元素的访问1.通过下标 [ ]来访问2.通过迭代器来访问3.通过范围for来访问 vector常用函数的用法解析1.size()2.clear()3.capacity()4.reserve()5.resize()6.shrink_to_fit()7.pop_back()8.push_back()9.erase()10.in…
阅读更多...
使用潜在向量进行检测、屏蔽和重建以进行遮挡的面部表情识别

使用潜在向量进行检测、屏蔽和重建以进行遮挡的面部表情识别

Latent-OFER: Detect, Mask, and Reconstruct with Latent Vectors for Occluded Facial Expression Recognition 一、创新点 &#xff08;1&#xff09;提出了一种与表情相关的特征提取器&#xff0c;它使用空间注意力为特定的面部特征分配更高的权重&#xff0c;从而使我们能…
阅读更多...
【Linux】统信服务器操作系统V20 1060a-AMD64 Vmware安装

【Linux】统信服务器操作系统V20 1060a-AMD64 Vmware安装

目录 ​编辑 一、概述 1.1 简介 1.2 产品特性 1.3 镜像下载 二、虚拟机安装 一、概述 1.1 简介 官网&#xff1a;统信软件 – 打造操作系统创新生态 统信服务器操作系统V20是统信操作系统&#xff08;UOS&#xff09;产品家族中面向服务器端运行环境的&#xff0c;是一款…
阅读更多...
Python 轻量级定时任务调度：APScheduler

Python 轻量级定时任务调度：APScheduler

简述 APscheduler (Advanced Python Scheduler)&#xff0c;作用为按指定的时间规则执行指定的作业。提供了基于日期date、固定时间间隔interval 、以及类似于Linux上的定时任务crontab类型的定时任务。该框架不仅可以添加、删除定时任务&#xff0c;还可以将任务存储到数据库…
阅读更多...
【Docker】WSL(Windows Subsystem for Linux)常见命令解释说明以及简单使用

【Docker】WSL(Windows Subsystem for Linux)常见命令解释说明以及简单使用

欢迎来到《小5讲堂》&#xff0c;大家好&#xff0c;我是全栈小5。 这是《Docker容器》序列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对…
阅读更多...
使用gcc/g++查看C语言预处理，编译，汇编，连接，以及动静态库的区分

使用gcc/g++查看C语言预处理，编译，汇编，连接，以及动静态库的区分

文章目录 使用gcc/ggcc如何完成编译后生成可执行文件&#xff1f;预处理(进行宏替换)编译&#xff08;生成汇编&#xff09;汇编&#xff08;生成机器可识别代码&#xff09;连接&#xff08;生成可执行文件或库文件&#xff09;最后记忆小技巧 在这里涉及到一个重要的概念&…
阅读更多...
Pandas.DataFrame.cumsum() 累积和 详解 含代码 含测试数据集 随Pandas版本持续更新

Pandas.DataFrame.cumsum() 累积和 详解 含代码 含测试数据集 随Pandas版本持续更新

关于Pandas版本&#xff1a; 本文基于 pandas2.2.0 编写。 关于本文内容更新&#xff1a; 随着pandas的stable版本更迭&#xff0c;本文持续更新&#xff0c;不断完善补充。 传送门&#xff1a; Pandas API参考目录 传送门&#xff1a; Pandas 版本更新及新特性 传送门&…
阅读更多...
备份RK35XX 设备的ubuntu根文件系统的方法

备份RK35XX 设备的ubuntu根文件系统的方法

简介 我们使用 RK35XX 提供的SDK包制作了一个完整的 ubuntu 镜像，烧录到设备中，会在设备中安装很多我们需要的软件，运行的一些自己写的脚本和业务程序，当我们有很多台设备时，不可能每台都一个个去安装，此时我们就需要一个工具来备份当前设备的根文件系统，然后再放到 SD…
阅读更多...
智能决策的艺术：探索商业分析的最佳工具和方法

智能决策的艺术：探索商业分析的最佳工具和方法

文章目录 一、引言二、商业分析思维概述三、数据分析在商业实践中的应用四、如何培养商业分析思维与实践能力五、结论《商业分析思维与实践&#xff1a;用数据分析解决商业问题》亮点内容简介作者简介目录获取方式 一、引言 随着大数据时代的来临&#xff0c;商业分析思维与实…
阅读更多...
C语言指针的几种用途

C语言指针的几种用途

先看题目&#xff0c;写一个fun函数&#xff0c;统计一个字符串中某个字符出现的次数&#xff0c;以及这个字符第一次出现的位置。 看起来很简单&#xff0c;似乎几行就可以搞定&#xff0c;但是写出来之后&#xff0c;才发现代码怎么这么长&#xff01;程序里多处使用了指针&…
阅读更多...
Elasticsearch(ES) 简述请求操作索引下文档 增删查改操作

Elasticsearch(ES) 简述请求操作索引下文档 增删查改操作

上文 Elasticsearch(ES) 创建带有分词器规则的索引 带着大家创建了一个带有分词功能的索引 老规矩 我们启动一下ES服务 本文 我们就来说说 关于文档的操作 我们先来添加一个文档 就像数据库加一条数据一样 这里 并不需要指定什么表结构和数据结构 它的文档结构是无模式的 添…
阅读更多...
PyTorch 2.2 中文官方教程（十七）

PyTorch 2.2 中文官方教程（十七）

&#xff08;Beta&#xff09;使用缩放点积注意力&#xff08;SDPA&#xff09;实现高性能 Transformer 原文&#xff1a;pytorch.org/tutorials/intermediate/scaled_dot_product_attention_tutorial.html 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 注意 点击这…
阅读更多...
从领域外到领域内：LLM在Text-to-SQL任务中的演进之路

从领域外到领域内：LLM在Text-to-SQL任务中的演进之路

导语 本文介绍了ODIS框架&#xff0c;这是一种新颖的Text-to-SQL方法&#xff0c;它结合了领域外示例和合成生成的领域内示例&#xff0c;以提升大型语言模型在In-context Learning中的性能。 标题&#xff1a;Selective Demonstrations for Cross-domain Text-to-SQL会议&am…
阅读更多...
Jenkins任意文件读取漏洞(CVE-2024-23897)复现

Jenkins任意文件读取漏洞(CVE-2024-23897)复现

Jenkins 有一个内置的命令行界面CLI&#xff0c;在处理 CLI 命令时Jenkins 使用args4j 库解析 Jenkins 控制器上的命令参数和选项。此命令解析器具有一个功能&#xff0c;可以将参数中后跟文件路径的字符替换为文件内容 ( expandAtFiles)。具有Overall/Read权限的攻击者可以读取…
阅读更多...
成都爱尔林江院长解读儿童青少年为什么一定要进行医学验光配镜

成都爱尔林江院长解读儿童青少年为什么一定要进行医学验光配镜

根据国家卫健委数据显示&#xff1a;我国青少年儿童总体近视率为52.7%、高度近视人口超3000万。近视学生中,有10%为高度近视,且占比随年级升高而增长。 近视孩子之多&#xff0c;孩子视力发展备受关注。戴镜进行近视防控十分必要&#xff0c;且眼镜不可随意验配&#xff01; 成…
阅读更多...
PAT-Apat甲级题1007(python和c++实现)

PAT-Apat甲级题1007(python和c++实现)

PTA | 1007 Maximum Subsequence Sum 1007 Maximum Subsequence Sum 作者 CHEN, Yue 单位 浙江大学 Given a sequence of K integers { N1​, N2​, ..., NK​ }. A continuous subsequence is defined to be { Ni​, Ni1​, ..., Nj​ } where 1≤i≤j≤K. The Maximum Su…
阅读更多...
论文阅读-MapReduce

论文阅读-MapReduce

论文名称&#xff1a;MapReduce: Simplified Data Processing on Large Clusters 翻译的效果不是很好&#xff0c;有空再看一遍&#xff0c;参照一下别人翻译的。 MapReduce:Simplified Data Processing on Large Clusters 中文翻译版(转) - 阿洒 - 博客园 (cnblogs.com) 概…
阅读更多...
仰暮计划|“如果你想看到世界上最完美的笑容，你就要多一点儿时间跟老人在一起，老人笑了，你就看到了。”

仰暮计划|“如果你想看到世界上最完美的笑容，你就要多一点儿时间跟老人在一起，老人笑了，你就看到了。”

敬老从心开始&#xff0c;助老从我做起 时值假期&#xff0c;我们有了时间&#xff0c;决定好好践行孝亲敬老的传统美德。会计学院红心使者敬老院访问团在7月6日上午在河南省郑州市新郑市“华信老年公寓”进行实践活动。 一早来到敬老院&#xff0c;老人们都已经开始择菜&…
阅读更多...
某赛通电子文档安全管理系统 PolicyAjax SQL注入漏洞复现

某赛通电子文档安全管理系统 PolicyAjax SQL注入漏洞复现

0x01 产品简介 某赛通电子文档安全管理系统（简称：CDG）是一款电子文档安全加密软件，该系统利用驱动层透明加密技术，通过对电子文档的加密保护，防止内部员工泄密和外部人员非法窃取企业核心重要数据资产，对电子文档进行全生命周期防护，系统具有透明加密、主动加密、智能…
阅读更多...
Redis核心技术与实战【学习笔记】 - 19.Pika：基于SSD实现大容量“Redis”

Redis核心技术与实战【学习笔记】 - 19.Pika：基于SSD实现大容量“Redis”

前言 随着业务数据的增加&#xff08;比如电商业务中&#xff0c;随着用户规模和商品数量的增加&#xff09;&#xff0c;就需要 Redis 能保存更多的数据。你可能会想到使用 Redis 切片集群&#xff0c;把数据分散保存到不同的实例上。但是这样做的话&#xff0c;如果要保存的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023