跳到主要内容 C++ 红黑树概念、原理及代码实现 | 极客日志
C++ 算法
C++ 红黑树概念、原理及代码实现 介绍 C++ 红黑树的概念、规则及实现。红黑树是基于二叉搜索树的自平衡结构，通过颜色约束确保路径长度差异不超过两倍。主要规则包括根节点为黑、无连续红节点、任意路径黑节点数相同。插入操作需处理变色、单旋和双旋三种情况以维持平衡。文章提供了完整的 C++ 代码实现，包含节点定义、插入、查找、旋转及验证逻辑，时间复杂度为 O(log N)。
FlinkHero 发布于 2026/3/30 更新于 2026/4/13 1. 红黑树的概念
红黑树是基于二叉搜索树进行改进的，因此红黑树的中序遍历也是有序的。
红黑树是一棵二叉搜索树，它的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。
1.1 红黑树的规则
只有同时满足以下的几点要求时才是在红黑树：
每个结点不是红色就是黑色
根结点是黑色的
如果一个结点是红色的，则它的两个孩⼦结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。
对于任意一个结点，从该结点到其所有 NULL 结点的简单路径上，均包含相同数量的黑色结点
以上的要求看起来是规律的，但是其实这几点规则之间是相互协调的，接下来我们就通过几个示例来看看这些规则是怎么使得红黑树当中的最长路径的长度不大于其他路径的两倍的。
来看以下的示例：
以上图示的二叉树当中，根节点为黑，并且不存在连续的红节点，那么接下来就是要知道二叉树当中每个路径上黑节点的个数；在此之前需要我们先找出以上的二叉树有几条路径，可能你会简单的认为以上不就是有 4 条路径吗？如下所示
但是其实以上求路径个数的方式是错误的，在此要一条路径的需要到空节点为止，因此以上的正确的路径应如下所示：
此时就可以看出以上的二叉树有 9 条路径，并且每条的路径上黑色节点的个数都是 2 个，这也是满足红黑树的要求的。
以上的二叉树当中满足了以上所示的红黑树的 1、2、4 点规则，但是对应规则 3 以上的所示的二叉树的叶子节点为红时不就不满足规则了吗？
这其实在通常情况下我们会忽略这种情况，在《算法导论》等书籍上补充了一条每个叶子结点 (NIL) 都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把 NIL 叫做外部结点。NIL 是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了 NIL 结点，所以我们知道一下这个概念即可。
那么在满足红黑树的规则下，就可以使得没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。
以上所示的红黑树当中最长路径为 3，最短的为 2，这时二叉搜索树就是接近平衡的
以下的二叉搜索树也是满足以上的红黑树规则，也是红黑树
这是就可以看出红黑树当中其实是完全没有红色节点的，这是也是满足红黑树的规则的
1.2 红黑树如何保持接近平平衡
在此我们就要思考在红黑树是如何确保基本平衡的，也就是在红黑树当中是如何确保最长的路径不超过最短路径的两倍的？
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
• 由规则 4 可知，从根到 NULL 结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就就是全是黑色结点的路径，假设最短路径长度为 bh (black height)。
• 由规则 2 和规则 3 可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为 2*bh 。
• 综合红黑树的 4 点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到 NULL 结点路径的长度为 x，那么bh <= h <= 2*bh 。
1.3 红黑树的效率 以上我们了解了红黑树的特性，以及要使得二叉搜索树为红黑树要满足什么样的要求，那么接下来就来分析在红黑树当中进行查找的效率。
假设 N 是红黑树树中结点数量，h 最短路径的长度，那么
, 由此推出
h ≈ logN ，也就是意味着红黑树增删查改最坏也就是走最长路径为 2*logN，那么时间复杂度就为
在此红黑树其实相比之前学习的 AVL 树控制平衡的方式不用，AVL 树是通过子树的控制高度差进行整体的平衡控制，而红黑树是通过 4 条规则的颜色约束间接的实现近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。在大量节点时 AVL 树的高度相比红黑树会低一些。
2. 红黑树实现 以上我们了解了红黑树的结构特点之后接下来就来实现红黑树的代码
在此创建两个文件 RBTree.h 和 test.cpp，在 RBTree.h 内实现红黑树的结构以及各种的功能，在 test.cpp 内对实现的红黑树进行测试，看是否满足我们的要求
2.1 红黑树节点实现 在实现红黑树的结构之前我们先要实现红黑树节点的结构体，在此创建一个名为 colour 的枚举来表示节点的颜色，创建一个名为 RBTreeNode 的 struct 结构体来表示红黑树的节点，实现代码如下所示：
enum colour { RED, BLACK };
template <class K , class V > struct RBTreeNode {
pair<K, V> _val;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
colour _col;
RBTreeNode (const pair<K, V>& val) :_val(val), _left(nullptr ), _right(nullptr ), _parent(nullptr ) { }
};
2.2 红黑树结构实现 在实现了红黑树节点的结构之后，接下来我们创建一个名为 RBTree 的类，在该类内实现红黑树的结构以及各种功能，接下来就先实现结构，实现的代码如下所示：
template <class K , class V > class RBTree {
typedef RBTreeNode<K, V> Node;
public :
private :
Node* root = nullptr ;
};
以上我们时使用类模板的方式来创建对应的二叉树，这样就可以使得创建的二叉树内节点的数据的类型是任意的，不过要存储在红黑树内的数据类型是需要能进行大小的比较，如果默认不支持也是需要我们自己实现的。
2.3 红黑树插入实现 以上实现了红黑树的大体结构之后接下来就来实现红黑树当中的插入功能，接下来在实现插入的代码之前先来分析在红黑树当中插入新的节点会有几种情况。
在插入新的节点之后，新形成的也是要满足红黑树的 4 条规则的。
1. 在空树当中插入节点，那么新增的节点需要是红色节点。
在非空的树当中插入新的节点，此时我们就要思考应将新的节点的颜色置为黑的还是红色？
如果我们插入的节点是红色的那么就只需要在其父节点为红色是进行调整，但是如果插入的节点为黑色的，这就会使得新产生的路径内的黑色节点数比其他的路径要多一个，这时要进行调整是很困难的，因此插入的节点应该初始化为红节点
2. 在非空树当中插入新的节点，将该节点初始化为红
在非空树内插入新节点之后接下来就要看其父节点是否为红，是的话此时的树就违背了红黑树的规则 3，就需要进行调整。调整直到没有应该红色节点的父节点为红为止。如果一开始插入的节点的父节点就为黑；那么插入完就可以停止操作
bool Insert (const pair <K, V> kv) if (root == nullptr ) {
root = new Node (kv);
root->_col = BLACK;
return true ;
}
Node* cur = root;
Node* Parent = nullptr ;
while (cur) {
if (cur->_val.first < kv.first) {
Parent = cur;
cur = cur->_right;
} else if (cur->_val.first > kv.first) {
Parent = cur;
cur = cur->_left;
} else {
return false ;
}
}
cur = new Node (kv);
if (Parent->_val.first < kv.first) {
Parent->_right = cur;
} else {
Parent->_left = cur;
}
cur->_parent = Parent;
cur->_col = RED;
root->_col = BLACK;
return true ;
}
接下来就来讲解插入的节点的父节点为红时进行调整的 3 种情况
注：接下来的讲解当中假设我们把新增结点标识为 c (cur)，c 的父亲标识为 p(parent)，p 的父亲标识为 g(grandfather)，p 的兄弟标识为 u（uncle）。
1. 情况 1：只需变色 当插入的节点的为父亲节点为红时，而且父亲的父亲的另一个节点也是红 的，也就是 c 节点的叔叔节点 u 也为红 时。因为在插入新的节点 c 之前当前的树一定是满足红黑树的规则的，那么此时 p 节点的父亲节点f 一定是为黑 ，也就是c 节点的祖父节点一定为黑 。
新插入的节点为 x，此时 c、p、u 的节点颜色情况就满足以上描述的形式。那么要让该节点变回满足红黑树的规则，就只需要将**p、u 变黑；g 变红即可。**这时调整完之后就可以使得树当中每条路径内的黑色节点的个数都相同。
以下是只进行变色情况的抽象表达，d/e/f 代表每条路径拥有hb 个黑色结点的子树 ，a/b 代表每条路径拥有 hb-1 个黑色结点的根为红的子树，hb>=0。和之前学习 AVL 树一样接下来来通过看看几种只进行变色的情况。
那么接下来就开看看 hb==0、hb==1、hb==2 的情况，其中当 hb 等于 2 时，这里组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理方式一样的，变色再继续往上处理即可，所以我们只需要看抽象图即可。
通过以上的示例就可以看出在处理只需要变色的情况时，新出现的红色节点可能是新插入的也可能是下部分的节点调整上来的，此时只需要一直进行调整直到对应的 p 为黑时就停止
以下以 p 节点分别为 g 节点的左节点和右节点的两种情况分别进行分析
bool Insert (const pair <K, V> kv) if (root == nullptr ) {
root = new Node (kv);
root->_col = BLACK;
return true ;
}
Node* cur = root;
Node* Parent = nullptr ;
while (cur) {
if (cur->_val.first < kv.first) {
Parent = cur;
cur = cur->_right;
} else if (cur->_val.first > kv.first) {
Parent = cur;
cur = cur->_left;
} else {
return false ;
}
}
cur = new Node (kv);
if (Parent->_val.first < kv.first) {
Parent->_right = cur;
} else {
Parent->_left = cur;
}
cur->_parent = Parent;
cur->_col = RED;
while (Parent && Parent->_col == RED) {
Node* grandfather = Parent->_parent;
if (grandfather->_left == Parent) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
}
else {
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
}
}
root->_col = BLACK;
return true ;
}
2. 情况 2：单旋 + 变色 以上情况 1 当中是叔叔存在且为红的情况，那么如果叔叔不存在或者是不为红又要怎么进行调整呢？
首先是 c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变色将 c 从黑色变成红色，更新上来的。
在此 p 是必须变为黑的，但是由于 u 为黑或者不存在，那么这就使得将 p 变为黑时 p 节点所在的路径的黑色节点的个数就与其他的路径不相同，那么这时就需要进行旋转来解决问题。
在此也是以 p 节点分别为 g 节点的左节点和右节点的两种情况分别进行分析
如果 p 是 g 的左，c 是 p 的左，那么以 g 为旋转点进行右单旋，再把 p 变黑，g 变红即可。p 成为这颗树新的根，这样子树黑色结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为 p 的⽗亲是黑色还是红色或者空都不违反规则。
如果 p 是 g 的右，c 是 p 的右，那么以 g 为旋转点进行左单旋，再把 p 变黑，g 变红即可。p 成为这颗树新的根，这样子树黑色结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为 p 的⽗亲是⿊⾊还是红⾊或者空都不违反规则。
3. 情况 3：双旋 + 变色 以上我们分析了单旋的情，那么接下来就来分析双旋的情况，当插入 c 之后红黑树的子树结构如下所示时只使用单旋是无法实现调整之后的树满足红黑树的规则的，在此接下来要使用到双旋 才能调整至满足要求。
c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变色将 c 从黑色变成红色，更新上来的。
在此 p 必须变黑，才能解决，连续红色结点的问题，u 不存在或者是⿊⾊的，但是这⾥单纯的变色⽆法解决问题，需要旋转 + 变色。
如果 p 是 g 的左，c 是 p 的右，那么先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，再把 c 变黑，g 变红即可。c 成为这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为 c 的⽗亲是⿊⾊还是红⾊或者空都不违反规则。
如果 p 是 g 的右，c 是 p 的左，那么先以 p 为旋转点进行右单旋，再以 g 为旋转点进行左单旋，再把 c 变黑，g 变红即可。c 成为这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为 c 的⽗亲是⿊⾊还是红⾊或者空都不违反规则。
2.4 插入完整代码 以上我们就进行插入节点的三种情况的分析，那么接下来就将以上的插入代码补充完整
bool Insert (const pair <K, V> kv) if (root == nullptr ) {
root = new Node (kv);
root->_col = BLACK;
return true ;
}
Node* cur = root;
Node* Parent = nullptr ;
while (cur) {
if (cur->_val.first < kv.first) {
Parent = cur;
cur = cur->_right;
} else if (cur->_val.first > kv.first) {
Parent = cur;
cur = cur->_left;
} else {
return false ;
}
}
cur = new Node (kv);
if (Parent->_val.first < kv.first) {
Parent->_right = cur;
} else {
Parent->_left = cur;
}
cur->_parent = Parent;
cur->_col = RED;
while (Parent && Parent->_col == RED) {
Node* grandfather = Parent->_parent;
if (grandfather->_left == Parent) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
else {
if (Parent->_left == cur) {
RotateR (grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
else {
RotateL (Parent);
RotateR (grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
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 {
if (Parent->_right == cur) {
RotateL (grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
else {
RotateR (Parent);
RotateL (grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break ;
}
}
}
root->_col = BLACK;
return true ;
}
void RotateR (Node* Parent) if (subLR != nullptr ) {
subLR->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_left = subLR;
Parent->_parent = subL;
subL->_right = Parent;
if (tmpNode != nullptr ) {
if (tmpNode->_left == Parent) {
tmpNode->_left = subL;
} else {
tmpNode->_right = subL;
}
subL->_parent = tmpNode;
} else {
root = subL;
subL->_parent = nullptr ;
}
}
void RotateL (Node* Parent) if (subRL != nullptr ) {
subRL->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_right = subRL;
Parent->_parent = subR;
subR->_left = Parent;
if (tmpNode != nullptr ) {
if (tmpNode->_left == Parent) {
tmpNode->_left = subR;
} else {
tmpNode->_right = subR;
}
subR->_parent = tmpNode;
} else {
root = subR;
subR->_parent = nullptr ;
}
}
2.4 红黑树查找 在此红黑树的查找实现和之前实现的二叉搜索树和 AVL 树类似，对你来说实现查找的代码肯定是 so easy 的，在此就不再进行讲解，直接奉上代码：
Node* Find (const K& val) {
if (root == nullptr ) {
return nullptr ;
}
Node* cur = root;
while (cur) {
if (cur->_val.first < val) {
cur = cur->_left;
} else if (cur->_val.first > val) {
cur = cur->_right;
} else {
return cur;
}
}
return nullptr ;
}
2.5 红黑树删除 在此红黑树的删除较为复杂且不是很重要，在此就不进行讲解。
2.6 红黑树验证 以上我们实现了红黑树的插入以及查找，那么接下来就来实现验证的代码
首先来分析验证的代码该如何实现：
这力获取最长路径和最短路径，检查最长路径不超过最短路径的 2 倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查 4 点规则，满足这 4 点规则，一定能保证最长路径不超过最短路径的 2 倍。
规则 1 枚举颜⾊类型，天然实现保证了颜色不是黑色就是红色。
规则 2 直接检查根即可
规则 3 前序遍历检查，遇到红色结点查孩子不太方便，因为孩⼦有两个，且不⼀定存在，反过来检查父亲的颜色就方便多了。
规则 4 前序遍历，遍历过程中用形参记录跟到当前结点的 blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径黑色结点数量作为参考值，依次比较即可。
bool Check (Node* root, int blackNum, const int refNum) if (root == nullptr ) {
if (refNum != blackNum) {
cout << "存在⿊⾊结点的数量不相等的路径" << endl;
return false ;
}
return true ;
}
if (root->_col == RED && root->_parent->_col == RED) {
cout << root->_val.first << "存在连续的红⾊结点" << endl;
return false ;
}
if (root->_col == BLACK) {
blackNum++;
}
return Check (root->_left, blackNum, refNum)&& Check (root->_right, blackNum, refNum);
}
bool IsBalance () if (root == nullptr ) return true ;
if (root->_col == RED) return false ;
int refNum = 0 ;
Node* cur = root;
while (cur) {
if (cur->_col == BLACK) {
++refNum;
}
cur = cur->_left;
}
return Check (root, 0 , refNum);
}
void TestRBTree1 () int , int > t;
int a[] = { 16 , 3 , 7 , 11 , 9 , 26 , 18 , 14 , 15 };
for (auto e : a) {
t.Insert ({ e, e });
}
t.InOrder ();
cout<<t.IsBalance ();
}
这时只能是说明对以上示例的测试用例进行插入是没问题的，要更严谨的验证就需要有更多的测试用例，这时使用以上的代码进行验证，并且测试进行插入的效率以及查找效率
void TestRBTree2 () const int N = 1000000 ;
vector<int > v;
v.reserve (N);
srand (time (0 ));
for (size_t i = 0 ; i < N; i++) {
v.push_back (rand () + i);
}
size_t begin2 = clock ();
RBTree<int , int > t;
for (auto e : v) {
t.Insert (make_pair (e, e));
}
size_t end2 = clock ();
cout << t.IsBalance () << endl;
cout << "Insert:" << end2 - begin2 << endl;
cout << "Height:" << t.Height () << endl;
cout << "Size:" << t.Size () << endl;
size_t begin1 = clock ();
for (size_t i = 0 ; i < N; i++) {
t.Find ((rand () + i));
}
size_t end1 = clock ();
cout << "Find:" << end1 - begin1 << endl;
}
将 vs 的调整为 release 模式之后，通过输出的结果就可以看出我们实现的红黑树的插入代码是没问题的，并且实现的红黑树的插入效率以及查找效率都是很高的，效率基本和 AVL 树不相上下。
2.7 完整代码
RBTree.c #pragma once
#include <iostream>
using namespace std;
enum colour { RED, BLACK };
template <class K , class V > struct RBTreeNode {
pair<K, V> _val;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
colour _col;
RBTreeNode (const pair<K, V>& val) :_val(val), _left(nullptr ), _right(nullptr ), _parent(nullptr ) { }
};
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* cur = root;
Node* Parent = nullptr ;
while (cur) {
if (cur->_val.first < kv.first) {
Parent = cur;
cur = cur->_right;
} else if (cur->_val.first > kv.first) {
Parent = cur;
cur = cur->_left;
} else {
return false ;
}
}
cur = new Node (kv);
if (Parent->_val.first < kv.first) {
Parent->_right = cur;
} else {
Parent->_left = cur;
}
cur->_parent = Parent;
cur->_col = RED;
while (Parent && Parent->_col == RED) {
Node* grandfather = Parent->_parent;
if (grandfather->_left == Parent) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
else {
if (Parent->_left == cur) {
RotateR (grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
else {
RotateL (Parent);
RotateR (grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
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 {
if (Parent->_right == cur) {
RotateL (grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
else {
RotateR (Parent);
RotateL (grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break ;
}
}
}
root->_col = BLACK;
return true ;
}
Node* Find (const K& val) {
if (root == nullptr ) {
return nullptr ;
}
Node* cur = root;
while (cur) {
if (cur->_val.first < val) {
cur = cur->_left;
} else if (cur->_val.first > val) {
cur = cur->_right;
} else {
return cur;
}
}
return nullptr ;
}
void InOrder () int Height () return _Height(root);
}
int Size () return _Size(root);
}
bool Check (Node* root, int blackNum, const int refNum) if (root == nullptr ) {
if (refNum != blackNum) {
cout << "存在⿊⾊结点的数量不相等的路径" << endl;
return false ;
}
return true ;
}
if (root->_col == RED && root->_parent->_col == RED) {
cout << root->_val.first << "存在连续的红⾊结点" << endl;
return false ;
}
if (root->_col == BLACK) {
blackNum++;
}
return Check (root->_left, blackNum, refNum)&& Check (root->_right, blackNum, refNum);
}
bool IsBalance () if (root == nullptr ) return true ;
if (root->_col == RED) return false ;
int refNum = 0 ;
Node* cur = root;
while (cur) {
if (cur->_col == BLACK) {
++refNum;
}
cur = cur->_left;
}
return Check (root, 0 , refNum);
}
private :
Node* root = nullptr ;
void RotateR (Node* Parent) if (subLR != nullptr ) {
subLR->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_left = subLR;
Parent->_parent = subL;
subL->_right = Parent;
if (tmpNode != nullptr ) {
if (tmpNode->_left == Parent) {
tmpNode->_left = subL;
} else {
tmpNode->_right = subL;
}
subL->_parent = tmpNode;
} else {
root = subL;
subL->_parent = nullptr ;
}
}
void RotateL (Node* Parent) if (subRL != nullptr ) {
subRL->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_right = subRL;
Parent->_parent = subR;
subR->_left = Parent;
if (tmpNode != nullptr ) {
if (tmpNode->_left == Parent) {
tmpNode->_left = subR;
} else {
tmpNode->_right = subR;
}
subR->_parent = tmpNode;
} else {
root = subR;
subR->_parent = nullptr ;
}
}
void _InOrder(Node* cur) {
if (cur == nullptr ) {
return ;
}
_InOrder(cur->_left);
cout << cur->_val.first << ":" <<cur->_val.second<<endl;
_InOrder(cur->_right);
}
int _Height(Node* cur) {
if (cur == nullptr ) {
return 0 ;
}
int Left = _Height(cur->_left);
int Right = _Height(cur->_right);
return Left > Right ? Left + 1 : Right + 1 ;
}
int _Size(Node* cur) {
if (cur == nullptr ) {
return 0 ;
}
return 1 + _Size(cur->_left) + _Size(cur->_right);
}
};
test.cpp #include <iostream>
#include <vector>
#include "BRTree.h"
using namespace std;
void TestRBTree1 () int , int > t;
int a[] = { 16 , 3 , 7 , 11 , 9 , 26 , 18 , 14 , 15 };
for (auto e : a) {
t.Insert ({ e, e });
}
t.InOrder ();
cout<<t.IsBalance ();
}
void TestRBTree2 () const int N = 1000000 ;
vector<int > v;
v.reserve (N);
srand (time (0 ));
for (size_t i = 0 ; i < N; i++) {
v.push_back (rand () + i);
}
size_t begin2 = clock ();
RBTree<int , int > t;
for (auto e : v) {
t.Insert (make_pair (e, e));
}
size_t end2 = clock ();
cout << t.IsBalance () << endl;
cout << "Insert:" << end2 - begin2 << endl;
cout << "Height:" << t.Height () << endl;
cout << "Size:" << t.Size () << endl;
size_t begin1 = clock ();
for (size_t i = 0 ; i < N; i++) {
t.Find ((rand () + i));
}
size_t end1 = clock ();
cout << "Find:" << end1 - begin1 << endl;
}
int main () TestRBTree2 ();
return 0 ;
}
以上就是本篇的全部内容了，在实现了红黑树之后接下来我们就可以基于红黑树来自己实现封装 set 和 map。
