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

【C++】红黑树万字详解（一文彻底搞懂红黑树的底层逻辑）

news 2024/10/24 21:00:35

目录

00.引入

01.红黑树的性质

02.红黑树的定义

03.红黑树的插入

1.按照二叉搜索树的规则插入新节点

2.检测新节点插入后，是否满足红黑树的性质

1.uncle节点存在且为红色

2.uncle节点不存在

3.uncle节点存在且为黑色

 04.验证红黑树

00.引入

和AVL树一样，红黑树也是一种自平衡的二叉搜索树。AVL树通过平衡因子调整子树的高度，确保树的高度差在 -1 到 1 之间。而红黑树通过在每个节点上增加一个存储位表示节点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有任何一条路径会是其他路径的两倍以上长，因而接近平衡。

01.红黑树的性质

红黑树具有以下几种性质，这些性质确保了树的平衡性和高效性：

1.节点颜色：每个节点要么是红色，要么是黑色。

2.根节点颜色：根节点始终是黑色。

3.红色节点限制：没有两个红色节点可以相连。

4.黑色节点数量：从任何节点到其每个叶子节点的所以路径包含相同数量的黑色节点。

5.叶子节点：所有的叶子节点（此处都表示为NULL节点）都是黑色。

其实还有一条潜规则：每一个新插入的节点初始都为红色。

为什么以上性质就可以保证最长路径的节点个数不会超过最短路径节点个数的两倍？

通过性质1/2/5可知，在判断性质4时（计算路径上黑色节点的数量），不需要考虑头节点以及叶子节点，只需要考虑中间节点即可，再根据性质3，可以列举以下几种情况：

1.中间没有黑色节点：

路径： 黑->黑，黑->红->黑。

2.中间只有1个黑色节点：

路径： 黑->黑->黑，黑->红->黑->黑，黑->黑->红->黑，黑->红->黑->红->黑

3.中间有2个黑色节点：

路径： 黑->黑->黑->黑，黑->红->黑->黑->黑，黑->黑->红->黑->黑，黑->黑->黑->红->黑

            。。。黑->红->黑->红->黑->红->黑

可以看出，最短路径就是全黑的；最长路径是黑、红相间的。因而我们可以找到规律：

假设中间有n个黑色节点：

最短路径：n+2（中间节点加上首尾）

最长路径：n+(n+1)+2=2n+3（中间有n个黑色节点最多可以有n+1个红色节点）

所以最长路径（2n+3）永远比最短路径的2倍（2n+4）小1。

02.红黑树的定义

红黑树的底层结构在代码实现中使用节点结构体和数来表示。节点结构体 保存每个节点的数据、指向左右子节点、父节点的指针、以及平衡因子；树类管理插入、删除等操作。

// 节点的颜色
enum Color { RED, BLACK };// 红黑树节点的定义
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data = T(), Color color = RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNode<T>* _pLeft; // 节点的左孩子RBTreeNode<T>* _pRight; // 节点的右孩子RBTreeNode<T>* _pParent; // 节点的双亲T _data; // 节点的值域Color _color; // 节点的颜色
};

在节点的定义中，我们将节点默认颜色给成红色，这是因为如果定义成黑色的话，根据性质4，每一次插入节点都需要重新调整树，而定义成红色，就只需要在父节点也为红色时进行调整，一定程度上保证了插入的效率。

03.红黑树的插入

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

1.按照二叉搜索树的规则插入新节点

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false// 注意：为了简单起见，本次实现红黑树不存储重复性元素bool Insert(const T& data){if (!_pRoot) // 根节点为空直接插入{_pRoot = new Node(data);_pRoot->_color = BLACK; // 设置根节点为黑色return true;}Node* pParent = nullptr;Node* pCur = _pRoot;while (pCur){pParent = pCur;if (data == pCur->_data) // 元素重复，不进行插入return false;else if (data > pCur->_data) // 大于向右走pCur = pCur->_pRight;else // 小于向左走pCur = pCur->_pLeft;}pCur = new Node(data);// 更新父节点的子节点指针if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;pCur->_pParent = pParent;return true;}

二叉搜索树的插入过程不在赘述，详细可跳转这篇博客【C++】二叉搜索树。

2.检测新节点插入后，是否满足红黑树的性质

因为新插入节点默认为红色，因此如果双亲节点是黑色，则满足性质，不需要调整；如果双亲节点为红色，违反了性质3，需要进行调整，调整过程需要进行分类讨论：

第一种情况：

我们调整红黑树的底层逻辑是通过改变某些节点的颜色，使整棵树符合性质，看下面这棵树：

cur表示新插入节点，parent为父节点，grandpa为父节点的父节点，uncle为grandpa的另一个节点

（下面用c，p，g，u分别表示cur，parent，grandpa，uncle）

此时c和p是连续的红色节点。破坏了性质3，那么我直接把p的颜色改成黑色，性质3被修复，但同时又破坏了性质4，于是我把u的颜色也改成黑色，这样以g为根节点的这棵树确实被修复了。

但要注意，如果g不是根节点呢

此时性质4还是被破坏了，为此，把g的颜色改成红色

这样就完成了修复。但如果是下面这种情况呢

g的双亲也为红色，此时需要继续向上调整。。

所以我们得到了第一种情况：

1.uncle节点存在且为红色

a.祖父节点为根 或 祖父的双亲为黑色

只需要修改u和p的颜色即可

b.祖父节点不为根 且 祖父的双亲为红色

此时需要进一步向上调整

将cur的位置换到grandpa，p、u、g一并转换，此时u一定存在，如果u不存在，则违反了性质4

第二种情况：

2.uncle节点不存在

1.单旋的情况

学习过AVL树可以知道，对于这样的一棵树我们需要通过旋转的方法调整高度，关于旋转的原理，可以调整这篇博客【C++】AVL树

旋转完成之后，我们需要调整颜色，此时p成为了这棵树的根节点，为了满足条件4，我们把p颜色改成黑，g颜色改成红：

这是左单旋的情况，右单旋同理

2.双旋的情况

双旋分为 右左 与 左右 两种情况，右左即p是g的右孩子，c是p的左孩子。右左情况下我们需要对p进行右单旋，在对g进行左单旋，最后调整c和g的颜色，过程如下：

左右的情况同理

3.uncle节点存在且为黑色

a.单旋的情况

此时cur一定不是新插入节点，这种情况就是1.b向上调整的后续了，此时依旧要用到旋转操作，和情况2同理：

b.双旋的情况

由此看来，情况2和情况3其实可以合并。

下面给出插入以及旋转的完整代码：

template<class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:RBTree(){_pRoot = nullptr;}// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false// 注意：为了简单起见，本次实现红黑树不存储重复性元素bool Insert(const T& data){if (!_pRoot) // 根节点为空直接插入{_pRoot = new Node(data);_pRoot->_color = BLACK; // 设置根节点为黑色return true;}Node* pParent = nullptr;Node* pCur = _pRoot;while (pCur){pParent = pCur;if (data == pCur->_data) // 元素重复，不进行插入return false;else if (data > pCur->_data) // 大于向右走pCur = pCur->_pRight;else // 小于向左走pCur = pCur->_pLeft;}pCur = new Node(data);// 更新父节点的子节点指针if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;pCur->_pParent = pParent;while (pParent && pParent->_color == RED){Node* pGrandpa = pParent->_pParent;if (!pGrandpa)pParent->_color = BLACK;else {if (pParent == pGrandpa->_pRight) {Node* pUncle = pGrandpa->_pLeft;// uncle存在且为红if (pUncle && pUncle->_color == RED){pUncle->_color = pParent->_color = BLACK;pGrandpa->_color = RED;// 继续向上调整pCur = pGrandpa;pParent = pCur->_pParent;}// uncle不存在或者uncle为黑else{// 右右的情况if (pCur == pParent->_pRight){RotateL(pGrandpa);pParent->_color = BLACK;pGrandpa->_color = RED;}// 右左的情况else{RotateR(pParent);RotateL(pGrandpa);pCur->_color = BLACK;pGrandpa->_color = RED;}break;}}else // pParent = pGrandpa->_pLeft{Node* pUncle = pGrandpa->_pRight;// uncle存在且为红if (pUncle && pUncle->_color == RED){pUncle->_color = pParent->_color = BLACK;pGrandpa->_color = RED;// 继续向上调整pCur = pGrandpa;pParent = pCur->_pParent;}// uncle不存在或者uncle为黑else{// 左左的情况if (pCur == pParent->_pLeft){RotateR(pGrandpa);pParent->_color = BLACK;pGrandpa->_color = RED;}// 左右的情况else{RotateL(pParent);RotateR(pGrandpa);pCur->_color = BLACK;pGrandpa->_color = RED;}break;}}}}_pRoot->_color = BLACK;return true;}private:// 左单旋void RotateL(Node* pParent){Node* pCur = pParent->_pRight;pParent->_pRight = pCur->_pLeft; // cur的左孩子作为parent的右孩子if (pCur->_pLeft)pCur->_pLeft->_pParent = pParent;if (pParent->_pParent) // parent不是根节点{pCur->_pParent = pParent->_pParent;if (pParent->_pParent->_pLeft == pParent)pParent->_pParent->_pLeft = pCur;elsepParent->_pParent->_pRight = pCur;}else // parent是根节点{_pRoot = pCur;pCur->_pParent = nullptr;}pParent->_pParent = pCur;pCur->_pLeft = pParent;}// 右单旋void RotateR(Node* pParent){Node* pCur = pParent->_pLeft;pParent->_pLeft = pCur->_pRight; // cur的右孩子作为parent的左孩子if (pCur->_pRight)pCur->_pRight->_pParent = pParent;if (pParent->_pParent) // parent不是根节点{pCur->_pParent = pParent->_pParent;if (pParent->_pParent->_pLeft == pParent)pParent->_pParent->_pLeft = pCur;elsepParent->_pParent->_pRight = pCur;}else // parent是根节点{_pRoot = pCur;pCur->_pParent = nullptr;}pParent->_pParent = pCur;pCur->_pRight = pParent;}private:Node* _pRoot;
};

 04.验证红黑树

检验上述代码，就得从红黑树的5条性质入手，性质1、5不需要验证，性质2也很容易验证，实际上我们主要验证的是性质3（没有连续的红色节点）以及性质4（每条路径上黑色节点数量一致）

对于性质4，我们可以先记录某一条路径（这里选取最左叶节点这条路径）的黑色节点数量，再遍历每一条路径，只要有一条路径上的黑色节点数量与前者不一样，就返回false，这里选择用递归的方式遍历红黑树。

对于性质3，我们需要再遍历的过程中，碰到红色节点，就验证一下双亲的颜色，如果也为红，则违反性质，返回false

完整代码如下：

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){if (!_pRoot)return true;if (RED == _pRoot->_color)return false;Node* pCur = _pRoot;size_t blackcount = 0;while (pCur){if (BLACK == pCur->_color)++blackcount;pCur = pCur->_pLeft;}return _IsValidRBTRee(_pRoot, blackcount, 0);}bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {if (!pRoot) {// 如果到达叶子节点，检查黑色节点数量return pathBlack == blackCount;}// 检查当前节点的颜色if (pRoot->_color == RED) {// 如果是红色，检查父节点是否也是红色if (pRoot->_pParent && pRoot->_pParent->_color == RED) {return false; // 违反红黑树性质}}// 更新路径上的黑色节点数量if (pRoot->_color == BLACK) {pathBlack++;}// 递归检查左子树和右子树return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack) &&_IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);}

最后我们用一万组包含10个1~100随机数的数组验证红黑树：

#include<iostream>
using namespace std;
#include"My_RBTree.h"
#include<vector>bool test1()
{srand(time(0));  // 初始化随机种子// 生成10000组随机向量for (int i = 0; i < 10000; ++i) {RBTree<int> BT;vector<int> nums;// 每组随机生成10个整数（范围为 1 到 100）for (int j = 0; j < 10; ++j) {nums.push_back(rand() % 100 + 1);}// 将每个整数插入 B 树中for (const int& num : nums) {BT.Insert(num);}// 检查 B 树if (!BT.IsValidRBTRee()) {cout << "树不平衡，测试失败！\n";for (auto it : nums){cout << it << ", ";}cout << endl;return 1;}}cout << "所有10000组随机树均平衡，测试通过！\n";
}int main()
{test1();return 0;
}

运行结果：

验证通过！

附上完整代码：

//My_RBTree.h
#pragma once
// 节点的颜色
enum Color { RED, BLACK };// 红黑树节点的定义
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data = T(), Color color = RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNode<T>* _pLeft; // 节点的左孩子RBTreeNode<T>* _pRight; // 节点的右孩子RBTreeNode<T>* _pParent; // 节点的双亲T _data; // 节点的值域Color _color; // 节点的颜色
};template<class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:RBTree(){_pRoot = nullptr;}// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false// 注意：为了简单起见，本次实现红黑树不存储重复性元素bool Insert(const T& data){if (!_pRoot) // 根节点为空直接插入{_pRoot = new Node(data);_pRoot->_color = BLACK; // 设置根节点为黑色return true;}Node* pParent = nullptr;Node* pCur = _pRoot;while (pCur){pParent = pCur;if (data == pCur->_data) // 元素重复，不进行插入return false;else if (data > pCur->_data) // 大于向右走pCur = pCur->_pRight;else // 小于向左走pCur = pCur->_pLeft;}pCur = new Node(data);// 更新父节点的子节点指针if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;pCur->_pParent = pParent;while (pParent && pParent->_color == RED){Node* pGrandpa = pParent->_pParent;if (!pGrandpa)pParent->_color = BLACK;else {if (pParent == pGrandpa->_pRight) {Node* pUncle = pGrandpa->_pLeft;// uncle存在且为红if (pUncle && pUncle->_color == RED){pUncle->_color = pParent->_color = BLACK;pGrandpa->_color = RED;// 继续向上调整pCur = pGrandpa;pParent = pCur->_pParent;}// uncle不存在或者uncle为黑else{// 右右的情况if (pCur == pParent->_pRight){RotateL(pGrandpa);pParent->_color = BLACK;pGrandpa->_color = RED;}// 右左的情况else{RotateR(pParent);RotateL(pGrandpa);pCur->_color = BLACK;pGrandpa->_color = RED;}break;}}else // pParent = pGrandpa->_pLeft{Node* pUncle = pGrandpa->_pRight;// uncle存在且为红if (pUncle && pUncle->_color == RED){pUncle->_color = pParent->_color = BLACK;pGrandpa->_color = RED;// 继续向上调整pCur = pGrandpa;pParent = pCur->_pParent;}// uncle不存在或者uncle为黑else{// 左左的情况if (pCur == pParent->_pLeft){RotateR(pGrandpa);pParent->_color = BLACK;pGrandpa->_color = RED;}// 左右的情况else{RotateL(pParent);RotateR(pGrandpa);pCur->_color = BLACK;pGrandpa->_color = RED;}break;}}}}_pRoot->_color = BLACK;return true;}// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptrNode* Find(const T& data){Node* pCur = _pRoot;while (pCur){if (data == pCur->_data)return pCur;if (data > pCur->_data)pCur = pCur->_pRight;elsepCur = pCur->_pLeft;}return nullptr;}// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){if (!_pRoot)return true;if (RED == _pRoot->_color)return false;Node* pCur = _pRoot;size_t blackcount = 0;while (pCur){if (BLACK == pCur->_color)++blackcount;pCur = pCur->_pLeft;}return _IsValidRBTRee(_pRoot, blackcount, 0);}private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {if (!pRoot) {// 如果到达叶子节点，检查黑色节点数量return pathBlack == blackCount;}// 检查当前节点的颜色if (pRoot->_color == RED) {// 如果是红色，检查父节点是否也是红色if (pRoot->_pParent && pRoot->_pParent->_color == RED) {return false; // 违反红黑树性质}}// 更新路径上的黑色节点数量if (pRoot->_color == BLACK) {pathBlack++;}// 递归检查左子树和右子树return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack) &&_IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);}// 左单旋void RotateL(Node* pParent){Node* pCur = pParent->_pRight;pParent->_pRight = pCur->_pLeft; // cur的左孩子作为parent的右孩子if (pCur->_pLeft)pCur->_pLeft->_pParent = pParent;if (pParent->_pParent) // parent不是根节点{pCur->_pParent = pParent->_pParent;if (pParent->_pParent->_pLeft == pParent)pParent->_pParent->_pLeft = pCur;elsepParent->_pParent->_pRight = pCur;}else // parent是根节点{_pRoot = pCur;pCur->_pParent = nullptr;}pParent->_pParent = pCur;pCur->_pLeft = pParent;}// 右单旋void RotateR(Node* pParent){Node* pCur = pParent->_pLeft;pParent->_pLeft = pCur->_pRight; // cur的右孩子作为parent的左孩子if (pCur->_pRight)pCur->_pRight->_pParent = pParent;if (pParent->_pParent) // parent不是根节点{pCur->_pParent = pParent->_pParent;if (pParent->_pParent->_pLeft == pParent)pParent->_pParent->_pLeft = pCur;elsepParent->_pParent->_pRight = pCur;}else // parent是根节点{_pRoot = pCur;pCur->_pParent = nullptr;}pParent->_pParent = pCur;pCur->_pRight = pParent;}private:Node* _pRoot;
};

//test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>using namespace std;#include"My_RBTree.h"#include<vector>bool test1(){srand(time(0));  // 初始化随机种子// 生成10000组随机向量for (int i = 0; i < 10000; ++i) {RBTree<int> BT;vector<int> nums;// 每组随机生成10个整数（范围为 1 到 100）for (int j = 0; j < 10; ++j) {nums.push_back(rand() % 100 + 1);}// 将每个整数插入 B 树中for (const int& num : nums) {BT.Insert(num);}// 检查 B 树if (!BT.IsValidRBTRee()) {cout << "树不平衡，测试失败！\n";for (auto it : nums){cout << it << ", ";}cout << endl;return 1;}}cout << "所有10000组随机树均平衡，测试通过！\n";}void test2(){RBTree<int> BT1;vector<int> v1 = { 70,25,97,18,51,85 };for (auto it : v1){BT1.Insert(it);}cout << BT1.IsValidRBTRee() << endl;}int main(){test1();return 0;}

以上就是红黑树的详解与模拟实现过程，欢迎在评论区留言，码文不易，觉得这篇博客对你有帮助的，可以点赞收藏关注支持一波~😉


http://www.mrgr.cn/news/57848.html

相关文章：

  • Flutter问题记录 - 布局中莫名其妙的白线/缝隙
  • 线上问题排查-频繁GC
  • Android中的多进程通信方式
  • 基于PHP的茶叶商城系统
  • Linux常用指令操作
  • 前端开发：Vue中数据绑定原理
  • “面试造火箭，工作拧螺丝”，程序员月薪多少？
  • 医院信息化与智能化系统(7)
  • Word中Normal.dotm样式模板文件
  • Docker 下备份恢复oracle
  • 【Jenkins】解决在Jenkins Agent节点容器内无法访问物理机的docker和docker compose的问题
  • 专业级Facebook直播工具推荐：提升你的直播体验
  • 婚纱相册必须去摄影店吗？其实自己会拍照就能实现，性价比更高
  • 跟着工作簿学 Tableau（38）：解锁 20 种 KPI 可视化模板（上篇）
  • 操作系统学习笔记2.3互斥
  • 《软件估算之原始功能点：精准度量软件规模的关键》
  • Apache Flink 2.0-preview released
  • “2024，我想和 TDengine 谈谈”征文活动获奖名单揭晓！
  • C语言指针，结构体
  • 西南大学的计算机怎么样?
  • 【读书笔记·VLSI电路设计方法解密】问题22：芯片封装有哪些挑战
  • 逻辑回归（Logistic Regression）详解
  • mac-chrome提示您的连接不是私密连接
  • Nginx可视化管理平台nginxWebUI（1）【保姆级部署方式】
  • scrapy案例——读书网列表页和详情页的爬取
  • 2024 年求职不易，有没有什么效率高的求职方法？