数据结构——红黑树详解

一、红黑树的定义

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能）

 红黑树的性质：

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

2. 根节点是黑色的。

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的。

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

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

为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

由性质4可知，红黑树的根节点到其叶子结点的所有路径上黑色节点的个数相同，那么一条路径上如果没有红色节点，则该路径为最短路径。

由性质3可知，红黑树的红色节点不连续，那么在一条路径上间隔插入红色节点，则该路径为最长路径。

得出结论：最短路径为全黑色节点，最长路径为一黑一红节点。所以，最长路径中节点个数不会超过最短路径节点个数的两倍。最短路径和最长路径可能在一颗红黑树上并不存在，如上图中就不存在最短路径。

二、红黑树的基本操作实现

红黑树同样是二叉查找树的演变，因此红黑树和AVL树一样，查找、遍历操作基本和二叉查找树一样。而红黑树的插入和删除操作与AVL树相比，需要对节点的颜色进行调整，也使用了旋转操作。

红黑树节点定义:

enum Colour {//枚举类型，定义红黑树颜色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;Colour _col;RBTreeNode(const pair<k, v>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

红黑树节点的结构与AVL树节点类似，这里用节点的颜色来替换平衡因子。

2.1 红黑树的插入操作

插入中需要用到的节点概念：

  • parent：父亲节点
  • uncle：叔叔节点（ parent 的兄弟节点）
  • grand：祖父节点（ parent 的父节点）

红黑树的节点有颜色之分，那么新插入节点的颜色是红色还是黑色呢？

当插入节点的颜色是黑色，新节点所在路径上的黑色节点个数+1。要保持每条路径上黑色节点个数相同，需要对其他路径一一调整，这样操作是非常繁琐的。

当插入节点的颜色是红色，所有路径上的黑色节点个数均不变。当新节点的父亲是黑色时，插入新节点，依然符合红黑树性质，无需调整。当新节点的父亲是红色时，进行调整。

得出结论：新插入节点默认颜色为红色。

2.1.1 叔叔节点(uncle)存在且为红

新插入节点cur的父亲为黑，插入后依然符合红黑树性质，无需调整。新插入节点cur的父亲为红，并且爷爷节点(grandparent)为黑（红黑树的红色节点不连续），叔叔节点(uncle)存在且为红。

此时对该子树进行操作，将parent节点变为黑色，grandparent节点变为红色，这样就能保证该子树中每条路径中黑色节点相同，并且没有连续的红色节点。然后更新cur、parent节点，parent = cur->_parent，cur=grandparent，沿插入路径向上调整，直到该树中没有连续的红节点。如下图所示：

2.1.2 叔叔节点(uncle)不存在或存在且为黑

新插入节点cur的父亲为红，并且爷爷节点(grandparent)为黑（红黑树的红色节点不连续），叔叔节点(uncle)不存在或存在且为黑。

在插入cur节点前，该树各路径上黑色节点个数已经不同，不满足红黑树的性质。说明cur节点不是新插入的节点，且cur以前是黑色节点，经过第一种情况的颜色调整后，cur节点变为红色。此时需要旋转操作，并更改颜色。这里不对旋转做详细叙述，参考数据结构——AVL树详解-CSDN博客。

右单旋：当parent节点时grandparent节点的右孩子，且cur节点是parent节点的右孩子

旋转后将grandparent节点变为红色，parent变为黑色。

右单旋：当parent节点时grandparent节点的左孩子，且cur节点是parent节点的左孩子

旋转后将grandparent节点变为红色，parent变为黑色。

左右双旋：当parent节点时grandparent节点的左孩子，且cur节点是parent节点的右孩子

旋转后将grandparent节点变为红色，cur变为黑色。 

右左双旋：当parent节点时grandparent节点的右孩子，且cur节点是parent节点的左孩子

旋转后将grandparent节点变为红色，cur变为黑色。  

插入代码实现具体实现如下：

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位置插入红色节点if (parent->_kv.first < kv.first) {//连接cur节点到红黑树parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//1：当叔叔存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else{//2：叔叔不存在或者存在且为黑，由第一种情况调整而来//旋转＋变色if (cur == parent->_left){//     g//   p    u// c//此时路径上黑色节点不相同，且有连续的红色节点，不满足最长路径是最短路径的两倍RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//     g//   p    u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//      g//   u     p//       cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

三、红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质：根节点是否为黑色，各路径黑色节点个数是否相同，红色节点是否连续出现。

bool IsBalance(){if (_root && _root->_col == RED)return false;int refBlackNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refBlackNum++;cur = cur->_left;}return Check(_root, 0, refBlackNum);}

先判断根节点，根节点为空或者根节点为红色，直接返回false。按照中序遍历，找到最左路径，遇到黑色节点refBlackNum++,最后得到最左路径的黑色节点个数。调用Check函数，传入根节点和refBlackNum。

bool Check(Node* cur, int blackNum, int refBlackNum){//传blackNum，每次走到黑色节点++，为nullptr回到上一层调用走右子树，此时blackNum还是上一层的值if (cur == nullptr) {if (refBlackNum != blackNum) {cout << "黑色节点的数量不相等" << endl;return false;}return true;}if (cur->_col == RED && cur->_parent->_col == RED) {cout << "存在连续的红色节点" << endl;return false;}if (cur->_col == BLACK)++blackNum;return Check(cur->_left, blackNum, refBlackNum) && Check(cur->_right, blackNum, refBlackNum);
}

当cur==nullptr,说明当前路径已走完，判断这条路径黑色节点个数blackNum是否和refBlackNum（标准值）是否相等。不为空时，判断当前节点是否为红色，如果cur为红色，再判断其父亲是否为红色（&&避免判断根节点的parent）。如果是黑色节点，blackNum++，最后递归左子树与右子树。blackNum为传值，每次遇到黑色节点++，为nullptr回到上一层调用遍历右子树，此时blackNum还是上一层的值。

四、红黑树的模拟实现

#define  _CRT_SECURE_NO_WARNINGS
#pragma once
#include<vector>
#include<iostream>
#include<time.h>
using namespace std;enum Colour {//枚举类型，红黑树颜色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;Colour _col;RBTreeNode(const pair<k, v>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};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位置插入红色节点if (parent->_kv.first < kv.first) {//连接cur节点到红黑树parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//1：当叔叔存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else{//2：叔叔不存在或者存在且为黑，由第一种情况调整而来//旋转＋变色if (cur == parent->_left){//     g//   p    u// c//此时路径上黑色节点不相同，且有连续的红色节点，不满足最长路径是最短路径的两倍RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//     g//   p    u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//      g//   u     p//       cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent)//左单旋{++rotateSize;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) {subRL->_parent = parent;}subR->_left = parent;Node* ppnode = parent->_parent;//记录parent的父节点parent->_parent = subR;if (parent == _root)//考虑parent是该树的根节点{_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent)//右单旋{++rotateSize;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) {subLR->_parent = parent;}subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}int GetRotateSize(){return rotateSize;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int Height(){return _Height(_root);}Node* Find(const k& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}bool IsBalance(){if (_root && _root->_col == RED)return false;int refBlackNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refBlackNum++;cur = cur->_left;}return Check(_root, 0, refBlackNum);}bool Check(Node* cur, int blackNum, int refBlackNum){//传blackNum，每次走到黑色节点++，为nullptr回到上一层调用走右子树，此时blackNum还是上一层的值if (cur == nullptr) {if (refBlackNum != blackNum) {cout << "黑色节点的数量不相等" << endl;return false;}return true;}if (cur->_col == RED && cur->_parent->_col == RED) {cout << "存在连续的红色节点" << endl;return false;}if (cur->_col == BLACK)++blackNum;return Check(cur->_left, blackNum, refBlackNum) && Check(cur->_right, blackNum, refBlackNum);
}private:Node* _root = nullptr;int rotateSize = 0;};

五、红黑树和AVL树的比较

  1. AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异。
  2. 红黑树的插入删除比AVL树更便于控制操作。
  3. 红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）。

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

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

相关文章

数据库加载驱动问题（java.lang.ClassNotFoundException: com.mysql.cj.jdbc.Driver）

数据库加载驱动问题（java.lang.ClassNotFoundException: com.mysql.cj.jdbc.Driver）

java.lang.ClassNotFoundException: com.mysql.cj.jdbc.Driver 遇到此问题&#xff0c;首先检查IDEA外部库中是否有mysql数据库驱动。如下所示&#xff1a; 如果发现外部库中存有mysql数据库驱动&#xff0c;需要在数据库配置文件中查看是否设置有时区mysql8.0以上版本需要设…
阅读更多...
【机器学习】机器学习创建算法第3篇：K-近邻算法,学习目标【附代码文档】

【机器学习】机器学习创建算法第3篇：K-近邻算法,学习目标【附代码文档】

机器学习&#xff08;算法篇&#xff09;完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;机器学习算法课程定位、目标&#xff0c;K-近邻算法定位,目标,学习目标,1 什么是K-近邻算法,1 Scikit-learn工具介绍,2 K-近邻算法API。K-近邻算法&#xff0c;1.4 …
阅读更多...
rhce复习2

rhce复习2

HTTPS协议 https简介 超文本传输协议HTTP协议被用于在Web浏览器和网站服务器之间传递信息。HTTP协议以明文方式发送内容&#xff0c;不提供任何方式的数据加密&#xff0c;如果攻击者截取了Web浏览器和网站服务器之间的传输报文&#xff0c;就可以直接读懂其中的信息&#xf…
阅读更多...
Canal1.1.5整Springboot在MQ模式和TCP模式监听mysql

Canal1.1.5整Springboot在MQ模式和TCP模式监听mysql

canal本实验使用的是1.1.5&#xff0c;自行决定版本&#xff1a;[https://github.com/alibaba/canal/releases] canal 涉及的几个角色 canal-admin&#xff1a;canal 后台管理系统&#xff0c;管理 canal 服务canal-deployer&#xff1a;即canal-server&#xff08;客户端&…
阅读更多...
某眼实时票房接口获取

某眼实时票房接口获取

某眼实时票房接口获取 前言解决方案1.找到veri.js2.找到signKey所在位置3.分析它所处的这个函数的内容4.index参数的获取5.signKey参数的获取运行结果关键代码另一种思路票房接口:https://piaofang.maoyan.com/dashboard-ajax https://piaofang.maoyan.com/dashboard 实时票房…
阅读更多...
Meta 推出Ego-Exo4D：一个研究视频学习和多模态感知的基础数据集

Meta 推出Ego-Exo4D：一个研究视频学习和多模态感知的基础数据集

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
安全架构设计理论与实践相关知识总结

安全架构设计理论与实践相关知识总结

一、安全架构概述 常见信息威胁介绍&#xff1a; 1. 信息泄露&#xff1a;信息被泄露或透露给某个非授权实体 2. 破坏信息完整性&#xff1a;数据被非授权地进行增删改查货破坏而受到损失 3. 拒绝服务&#xff1a;对信息会其他资源的合法访问被无条件的组织 4. 非法使用&#x…
阅读更多...
IDE/VS2015和VS2017帮助文档MSDN安装和使用

IDE/VS2015和VS2017帮助文档MSDN安装和使用

文章目录 概述VS2015MSDN离线安装离线MSDN的下载离线MSDN安装 MSDN使用方法从VS内F1启动直接启动帮助程序跳转到了Qt的帮助网页 VS2017在线安装MSDN有些函数在本地MSDN没有帮助&#xff1f;切换中英文在线帮助文档 概述 本文主要介绍了VS集成开发环境中&#xff0c;帮助文档MS…
阅读更多...
hibernate session接口

hibernate session接口

hibernate session接口 Session接口是hibernate向应用程序提供的操纵数据库的最主要的接口&#xff0c;提供了保存、更新、删除和加载Java对象的方法。 session具有一个缓存&#xff0c;位于缓存中的对象成为持久化对象&#xff0c;和数据库中的相关记录对应。session能够在某些…
阅读更多...
【御控物联】JavaScript JSON结构转换（17）：数组To对象——键值互换属性重组

【御控物联】JavaScript JSON结构转换（17）：数组To对象——键值互换属性重组

文章目录 一、JSON结构转换是什么&#xff1f;二、核心构件之转换映射三、案例之《JSON数组 To JSON对象》四、代码实现五、在线转换工具六、技术资料 一、JSON结构转换是什么&#xff1f; JSON结构转换指的是将一个JSON对象或JSON数组按照一定规则进行重组、筛选、映射或转换…
阅读更多...
MES可视化管理，提高制造业工厂管理水平

MES可视化管理，提高制造业工厂管理水平

在制造业中&#xff0c;生产过程的可视化管理对于提高生产效率、降低成本以及提升决策的准确性和及时性至关重要。MES系统作为制造执行过程中的核心管理工具&#xff0c;为实现生产过程的可视化管理提供了有力支持。 生产车间应用MES生产管理系统之后&#xff0c;能通过电子屏幕…
阅读更多...
异地文件如何共享访问？

异地文件如何共享访问？

异地文件共享访问是一种让不同地区的用户能够快速、安全地共享文件的解决方案。人们越来越需要在不同地点之间共享文件和数据。由于复杂的网络环境和安全性的问题&#xff0c;实现异地文件共享一直是一个挑战。 为了解决这个问题&#xff0c;许多公司和组织研发了各种异地文件共…
阅读更多...
集成电路企业tapeout，如何保证机台数据准确、完整、高效地采集？

集成电路企业tapeout，如何保证机台数据准确、完整、高效地采集？

Tapeout即流片&#xff0c;集成电路行业中将CDS最终版电路图提交给半导体制造厂商进行物理生产的过程。在芯片设计与制造的流程中&#xff0c;Tapeout是非常重要的阶段&#xff0c;包括了布局&#xff08;Layout&#xff09;、连线&#xff08;Routing&#xff09;、分析&#…
阅读更多...
基于SSM的“汽车销售分析与管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SSM的“汽车销售分析与管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SSM的“汽车销售分析与管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SSM 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能结构图 销售经理系统首页图 客户管理图 车辆…
阅读更多...
数据采集工具如何使用呢？那么设置数据采集的方法又是什么呢？

数据采集工具如何使用呢？那么设置数据采集的方法又是什么呢？

数据采集工具将能够非常有效地解决面临的各种问题。这款工具被设计成一种自动化数据采集工具&#xff0c;特别适用于对日志文件数据的采集。一旦完成设置&#xff0c;该工具将在后台实时进行数据采集&#xff0c;并自动对收集到的数据进行清洗&#xff0c;以确保最终保存到的数…
阅读更多...
Redis简介、常用命令

Redis简介、常用命令

目录 一、关系数据库​​与非关系数据库​​ 1.1. 关系型数据库 1.2 非关系型数据库 1.3.关系数据库与非关系型数据库区别 1.3.1. 数据存储方式不同 1.3.2. 扩展方式不同 1.3.3.对事务性的支持不同 1.4.非关系型数据库产生背景 二、Redis 2.1.Redis简介 2.2.Redis的…
阅读更多...
CentOS 7 下离线安装RabbitMQ教程

CentOS 7 下离线安装RabbitMQ教程

CentOS 7 下安装RabbitMQ教程一、做准备&#xff08;VMWare 虚拟机上的 CentOS 7 镜像 上安装的&#xff09; &#xff08;1&#xff09;准备RabbitMQ的安装包&#xff08;rabbitmq-server-3.8.5-1.el7.noarch&#xff09;下载地址mq https://github.com/rabbitmq/rabbitmq-se…
阅读更多...
【OpenCV-颜色空间】

【OpenCV-颜色空间】

OpenCV-颜色空间 ■ RGB■ BGR■ HSV■ HSL■ HUE■ YUV ■ RGB ■ BGR BGR 就是RGB R和B调换位置。 OpenCV 默认使用BGR ■ HSV ■ HSL ■ HUE ■ YUV
阅读更多...
实验四 微信小程序智能手机互联网程序设计（微信程序方向）实验报告

实验四 微信小程序智能手机互联网程序设计（微信程序方向）实验报告

请编写一个用户登录界面&#xff0c;提示输入用户名和密码进行登录&#xff1b; 代码 index.wxml <view class"user"> <form bindreset""> <view>用户名&#xff1a;</view><input type"text"name""/>…
阅读更多...
【面试八股总结】传输控制协议TCP（三）

【面试八股总结】传输控制协议TCP（三）

参考资料 &#xff1a;小林Coding、阿秀、代码随想录 一、TCP拥塞控制⭐ 1. 慢启动 – Slow Start 慢启动是指TCP连接刚建立&#xff0c;一点一点地提速&#xff0c;试探一下网络的承受能力&#xff0c;以免直接扰乱了网络通道的秩序。 慢启动算法&#xff1a; 初始拥塞窗口…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023