深入探索：C++红黑树原理与实现
文章目录
一、红黑树的概念
红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色，通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。
二、红黑树的规则
- 每个
结点不是红色就是黑色 根节点是黑色的- 如果一个节点是
红色的，则它的两个孩子结点是黑色的 - 对于每个结点，从该结点到其所有后代叶结点的简单
路径上，均包含相同数目的黑色结点 - 每个
叶子结点都是黑色的(此处的叶子结点指的是空结点):
规则解释：
- 什么是路径？对于上图来说，一共有11条路径，根到空节点算一条路径。
- 红色结点的孩子必须是黑色结点，也就是说任何路径没有连续的红色节点。
- 每条路径上黑色节点的数量相等
- 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点说明:《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道一下这个概念即可。
- 为什么说只要满足了上述所有规则，就能保证红黑树其最长路径中节点个数不会超过最短路径节点个数的两倍？
只要满足了上述规则，最短的路径将会是全是黑色，最长的路径将是一红一黑红黑相间：
由规则4可知，从根到NULL结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就就是全是黑色结点的路径，假设最短路径长度为bh(black height)。
由规则2和规则3可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是黑一红间隔组成，那么最长路径的长度为2*bh。
综合红黑树的4点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL结点路径的长度为x，那么bh<=h<=2*bh。
三、红黑树与AVL树性能对比
性能差异总结：
- AVL树:
- 严格平衡（高度差不超过1）。
- 高度较低，查找效率更高。
- 插入和删除操作由于需要频繁调整平衡，开销较大。
- 红黑树:
- 平衡条件较宽松（最长路径不超过最短路径的2倍）。
- 高度比AVL树稍高，查找效率略低。
- 插入和删除操作调整较少，性能更优。
表格总结：
| 树种类 | 平衡条件 | 高度（1000个值） | 高度（10亿个值） | 查找效率 | 插入/删除效率 |
|---|---|---|---|---|---|
| AVL树 | 高度差不超过1 | (log N = 10) | (log N = 30) | 更高 | 较低 |
| 红黑树 | 最长路径 ≤ 最短路径的2倍 | (2log N = 20) | (2log N = 60) | 略低 | 更高 |
四、红黑树框架的搭建
#pragmaonce#include<iostream>usingnamespace std;enumColour{ RED, BLACK };template<classK,classV>structRBTreeNode{ 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),_col(RED){}};template<classK,classV>classRBTree{typedef RBTreeNode<K, V> Node;public:private: Node* _root =nullptr;};五、红黑树的插入逻辑
1. 大体框架
首先，插入逻辑的答题思路是和前面我们所学的AVL树的插入主体框架是大体相同的，代码如下：
boolInsert(const pair<K, V>& kv){// 树为空，直接插入然后返回if(_root ==nullptr){ _root =newNode(kv);returntrue;} Node* cur = _root; Node* parent =nullptr;while(cur){// 小于往左走if(kv.first < cur->_kv.first){ parent = cur; cur = cur->_left;}elseif(kv.first > cur->_kv.first)// 大于往右走{ parent = cur; cur = cur->_right;}else{returnfalse;}} cur =newNode(kv);// 链接if(cur->_kv.first < parent->_kv.first){ parent->_left = cur;}else{ parent->_right = cur;} cur->_parent = parent;returntrue;}2. 初始颜色的设置
首先迎来我们第一个问题，新插入结点初始的颜色要设置成什么呢?
如果是根节点，答案很明确，根节点的颜色是黑色！
// 树为空，直接插入然后返回if(_root ==nullptr){ _root =newNode(kv);// 根节点必须是黑色 _root->_col = BLACK;returntrue;}那么对于其他结点呢？
是插入红色，还是插入黑色？
这里面就涉及到两个相冲的规则：
如果我们选择插入黑色，那么就会违背规则4，那么画出的图是这样的：
就会造成所有路径黑色结点出现问题，就要更改所有路径的风险，因此我们不选择这种方案。
如果选择插入红色结点，就会违背规则3，画出的图是这样的：
如果插入到红色节点后，则只牵扯到当前路径，很容易进行调整。因此我们新插入的结点默认为红色！！！
所以对于其他颜色，我们调节的代码为：
cur =newNode(kv);// 其他结点初始颜色为红色 cur->_col = RED;3. 颜色的调整
1）通过具体的情况对颜色调整进行框架认识
对于颜色的调整，我们可以总结为三种情况：
情况一：uncle存在，且为红色：
解决方式：parent与uncle变黑，grandfather变红，继续向上调整。
情况二：uncle不存在
解决方式：旋转 + 变色
情况三：uncle存在且为黑色
解决方式：旋转 + 变色
我们上一种情况继续插入，就会变成这种情况：
2）通过抽象图对颜色调整加深理解
情况一：uncle存在且uncle为红色
代码解析：
// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定// 用while循环是因为我们要不断的向上调整while(parent && parent->_col == RED){// 首先我们要找到grandfather Node* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif(parent == grandfather->_left){// 说明uncle在右边 Node* uncle = grandfather->_right;// uncle存在且为红if(uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色 parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;// 继续向上调整 cur = grandfather; parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else// uncle不存在 或 uncle存在且为黑色{// ...}}// 这里保证根为黑色 _root->_col = BLACK;情况二：uncle不存在或uncle存在且uncle为黑色
因为这里牵扯到旋转，所以我们需要知道旋转的逻辑，这个J桑之前做过专题讲解过，不会的小伙伴可以戳这里~🥰🥰🥰
下面我们在这里再放以下旋转的代码~
唯一的区别就是，这里不需要平衡因子。
// 左单旋voidRotateL(Node* parent){ Node* cur = parent->_right; Node* curleft = cur->_left;// 重新链接 parent->_right = curleft;if(curleft)// 如果curleft存在{ curleft->_parent = parent;} cur->_left = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(ppnode ==nullptr){ _root = cur; cur->_parent =nullptr;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}// 右单旋voidRotateR(Node* parent){ Node* cur = parent->_left; Node* curright = cur->_right; parent->_left = curright;if(curright){ curright->_parent = parent;} cur->_right = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(ppnode ==nullptr){ cur->_parent =nullptr; _root = cur;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}代码解析：
else// uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋if(cur == parent->_left){// g// p// cRotateR(grandfather);// 调整颜色 parent->_col = BLACK; grandfather->_col = RED;}else// 左右双旋{// g// p// cRotateL(parent);RotateR(grandfather);// 调整颜色 cur->_col = BLACK; grandfather->_col = RED;}// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出break;}六、红黑树是否构建正确的检查
以下的这段代码的核心目标是检查红黑树是否构建正确，主要基于红黑树的规则进行验证。代码的设计分为两个关键部分：计算基准值和递归验证规则。
代码解析
// 检查是否构建正确boolCheckColour(Node* root,int blacknum,int benchmark){if(root ==nullptr){if(blacknum != benchmark)returnfalse;returntrue;}if(root->_col == BLACK){++blacknum;}if(root->_col == RED && root->_parent && root->_parent->_col == RED){ cout << root->_kv.first <<"出现连续红色节点"<< endl;returnfalse;}returnCheckColour(root->_left, blacknum, benchmark)&&CheckColour(root->_right, blacknum, benchmark);}boolIsBalance(){returnIsBalance(_root);}boolIsBalance(Node* root){if(root ==nullptr)returntrue;if(root->_col != BLACK){returnfalse;}// 基准值int benchmark =0; Node* cur = _root;while(cur){if(cur->_col == BLACK)++benchmark; cur = cur->_left;}returnCheckColour(root,0, benchmark);}- 基准值的计算
在红黑树中，所有从根节点到叶节点的路径上，必须经过相同数量的黑色节点。为此，代码首先沿着树的左侧路径计算路径上黑色节点的数量，作为基准值benchmark。这是验证红黑树平衡性的关键步骤。 - 递归验证红黑树规则
接下来通过递归函数CheckColour，对红黑树的所有节点进行逐一验证，确保其符合以下规则： - 每个节点是红色或黑色。
- 红色节点的子节点必须是黑色（即不能出现连续的红色节点）。
- 从任一节点到其所有后代的每条路径包含相同数量的黑色节点。
整体逻辑描述
- 首先调用
IsBalance()，对整棵树进行平衡性检查。- 先判断根节点是否为黑色，这是红黑树的基本要求。
- 沿着左侧路径，计算从根节点到最左叶节点的黑色节点总数，作为基准值。
- 然后进入递归检查函数
CheckColour()：- 如果当前节点为空（即到达叶节点），检查该路径累计的黑色节点数量是否与基准值一致。
- 对每个非空节点，检查其颜色是否满足规则：红色节点不能有红色父节点。
- 累计当前路径上的黑色节点数，并递归检查左右子树。
- 最终通过递归结果判断整棵树是否满足红黑树性质。
- 如果发现不符合的地方（如连续红色节点或黑色节点数不一致），会提前返回
false并结束验证。
我们运行的时候给10000000个随机值，看看会不会调用成功。
#include"RBTree_1.h"#include<vector>intmain(){constint N =10000000; vector<int> v; v.reserve(N);srand(time(0));for(size_t i =0; i < N; i++){ v.push_back(i);} RBTree<int,int> rbt;for(auto e : v){ rbt.Insert(make_pair(e, e));} cout << rbt.IsBalance()<< endl;return0;}运行结果如下：
说明我们的红黑树构建成功啦~
七、红黑树总体代码总结
#pragmaonce#include<iostream>usingnamespace std;enumColour{ RED, BLACK };template<classK,classV>structRBTreeNode{ 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),_col(RED){}};template<classK,classV>classRBTree{typedef RBTreeNode<K, V> Node;public:boolInsert(const pair<K, V>& kv){// 树为空，直接插入然后返回if(_root ==nullptr){ _root =newNode(kv);// 根节点必须是黑色 _root->_col = BLACK;returntrue;} Node* cur = _root; Node* parent =nullptr;while(cur){// 小于往左走if(kv.first < cur->_kv.first){ parent = cur; cur = cur->_left;}elseif(kv.first > cur->_kv.first)// 大于往右走{ parent = cur; cur = cur->_right;}else{returnfalse;}} cur =newNode(kv);// 其他结点初始颜色为红色 cur->_col = RED;// 链接if(cur->_kv.first < parent->_kv.first){ parent->_left = cur;}else{ parent->_right = cur;} cur->_parent = parent;// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定// 用while循环是因为我们要不断的向上调整while(parent && parent->_col == RED){// 首先我们要找到grandfather Node* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif(parent == grandfather->_left){// 说明uncle在右边 Node* uncle = grandfather->_right;// uncle存在且为红if(uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色 parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;// 继续向上调整 cur = grandfather; parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else// uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋if(cur == parent->_left){// g// p// cRotateR(grandfather);// 调整颜色 parent->_col = BLACK; grandfather->_col = RED;}else// 左右双旋{// g// p// cRotateL(parent);RotateR(grandfather);// 调整颜色 cur->_col = BLACK; grandfather->_col = RED;}// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出break;}}else//(parent == grandfather->_right) // 如果parent是grandfather->_right{// 说明uncle在左边 Node* uncle = grandfather->_left;// uncle存在且为红if(uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色 parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;// 继续向上调整 cur = grandfather; parent = cur->_parent;}else// uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 左单旋if(cur == parent->_right){// g// p// cRotateL(grandfather);// 调整颜色 parent->_col = BLACK; grandfather->_col = RED;}else// 右左双旋{// g// p// cRotateR(parent);RotateL(grandfather);// 调整颜色 cur->_col = BLACK; grandfather->_col = RED;}break;}}}// 这里保证根为黑色 _root->_col = BLACK;returntrue;}// 左单旋voidRotateL(Node* parent){ Node* cur = parent->_right; Node* curleft = cur->_left;// 重新链接 parent->_right = curleft;if(curleft)// 如果curleft存在{ curleft->_parent = parent;} cur->_left = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(ppnode ==nullptr){ _root = cur; cur->_parent =nullptr;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}// 右单旋voidRotateR(Node* parent){ Node* cur = parent->_left; Node* curright = cur->_right; parent->_left = curright;if(curright){ curright->_parent = parent;} cur->_right = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(ppnode ==nullptr){ cur->_parent =nullptr; _root = cur;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}// 检查是否构建正确boolCheckColour(Node* root,int blacknum,int benchmark){if(root ==nullptr){if(blacknum != benchmark)returnfalse;returntrue;}if(root->_col == BLACK){++blacknum;}if(root->_col == RED && root->_parent && root->_parent->_col == RED){ cout << root->_kv.first <<"出现连续红色节点"<< endl;returnfalse;}returnCheckColour(root->_left, blacknum, benchmark)&&CheckColour(root->_right, blacknum, benchmark);}boolIsBalance(){returnIsBalance(_root);}boolIsBalance(Node* root){if(root ==nullptr)returntrue;if(root->_col != BLACK){returnfalse;}// 基准值int benchmark =0; Node* cur = _root;while(cur){if(cur->_col == BLACK)++benchmark; cur = cur->_left;}returnCheckColour(root,0, benchmark);}private: Node* _root =nullptr;};结语
那么到这里就结束啦，创作不易，如果对各位大佬有帮助的话，麻烦给一个一键三连吧~谢谢各位大佬🥰🥰🥰
