在之前的篇章当中我们已经了解了基于二叉搜索树的AVL树，那么接下来在本篇当中将继续来学习另一种基于二叉搜索树的树状结构——红黑树，在此和之前学习AVL树类似还是通过先了解红黑树是什么以及红黑树的结构特点，接下来在试着实现红黑树的结构以及实现红黑树插入新节点、进行节点查询的功能，相信通过本篇的学习能让你了解红黑树，一起加油把！！！
1. 红黑树的概念
在此红黑树是基于二叉搜索树进行改进的，因此红黑树的中序遍历也是有序的。
红黑树是⼀棵二叉搜索树，他的每个结点增加⼀个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何⼀条从根到叶子的路径上各个结点的颜⾊进行约束，红黑树确保没有⼀条路径会比其他路径长出2倍，因而是接近平衡的。
1.1 红黑树的规则
只有同时满足以下的几点要求时才是在红黑树：
1. 每个结点不是红色就是黑色
2. 根结点是黑色的
3. 如果⼀个结点是红色的，则它的两个孩⼦结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点。
4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点
以上的要求看起来是规律的，但是其实这几点规则之间是相互协调的，接下来我们就通过几个示例来看看这些规则是怎么使得红黑树当中的最长路径的长度不大于其他路径的两倍的。
来看以下的示例：
以上图示的二叉树当中，根节点为黑，并且不存在连续的红节点，那么接下来就是要知道二叉树当中每个路径上黑节点的个数；在此之前需要我们先找出以上的二叉树有几条路径，可能你会简单的认为以上不就是有4条路径吗？如下所示
但是其实以上求路径个数的方式是错误的，在此要一条路径的需要到空节点为止，因此以上的正确的路径应如下所示：
此时就可以看出以上的二叉树有9条路径，并且每条的路径上黑色节点的个数都是2两个，这也是满足红黑树的要求的。
以上的二叉树当中满足了以上所示的红黑树的1、2、4点规则，但是对应规则3以上的所示的二叉树的叶子节点为红时不就不满足规则了吗？
这其实在在此通常情况下我们会忽略这种情况，在《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是黑色的规则。他这⾥所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道⼀下这个概念即可。
那么在满足红黑树的规则下，就可以使得没有⼀条路径会比其他路径长出2倍，因而是接近平衡的。
以上所示的红黑树当中最长路径为3，最短的为2，这时二叉搜索树就是接近平衡的
以下的二叉搜索树也是满足以上的红黑树规则，也是红黑树
这是就可以看出红黑树当中其实是完全没有红色节点的，这是也是满足红黑树的规则的
1.2 红黑树如何保持接近平衡
在此我们就要思考在红黑树是如何确保基本平衡的，也就是在红黑树当中是如何确保最长的路径不超过最短路径的两倍的？
• 由规则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. 红黑树实现
以上我们了解了红黑树的结构特点之后接下来就来实现红黑树的代码
在此创建两个文件BRTRee.h和test.cpp，在BRTRee.h内实现红黑树的结构以及各种的功能，在test.cpp内对实现的红黑树进行测试，看是否满足我们的要求
2.1 红黑树节点实现
在实现红黑树的结构之前我们先要实现红黑树节点的结构体，在此创建一个名为colour的枚举来表示节点的颜色，创建一个名为RBTree的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;
//父节点为祖父节点的左节点时
// g
// p u
//c
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;
}
//其他情况……
}
//父节点为祖父节点的右节点时
// g
// u p
// c
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节点的左节点和右节点的两种情况分别进行分析
g
p u
c如果p是g的左，c是p的左，那么以g为旋转点进行右单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是黑色还是红色或者空都不违反规则。
g
u p
c如果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不存在或者是⿊⾊的，但是这⾥单纯的变色⽆法解决问题，需要旋转+变色。
g
p u
c如果p是g的左，c是p的右，那么先以p为旋转点进行左单旋，再以g为旋转点进行右单旋，再把c变
黑，g变红即可。c变成课这颗树新的根，这样子树黑⾊结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。
g
u p
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;
//父节点为祖父节点的左节点时
// g
// p u
//c
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
{
//当c为p的左节点时
// g
// p u
//c
if (Parent->_left == cur)
{
RotateR(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的右节点时
// g
// p u
// c
else
{
RotateL(Parent);
RotateR(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
//父节点为祖父节点的右节点时
// g
// u p
// c
else
{
Node* uncle = grandfather->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
//叔叔不存在或者为黑
else
{
//当c为p的右节点时
// g
// u p
// c
if (Parent->_right == cur)
{
RotateL(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的左节点时
// g
// u p
// c
else
{
RotateR(Parent);
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
//无论以上是否进行调整都将根结点的颜色置为黑
root->_col = BLACK;
return true;
}
void RotateR(Node* Parent)
{
Node* subL = Parent->_left;
Node* subLR = subL->_right;
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)
{
Node* subR = Parent->_right;
Node* subRL = subR->_left;
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. 规则1枚举颜⾊类型，天然实现保证了颜色不是黑色就是红色。
2. 规则2直接检查根即可
3. 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩⼦有两个，且不⼀定存在，反过来检查父亲的颜色就方便多了。
4. 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径黑色结点数量作为参考值，依次比较即可。
实现代码如下所示：
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
// 前序遍历⾛到空时，意味着⼀条路径⾛完了
//cout << blackNum << endl;
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 TestAVLTree1()
{
RBTree<int, int> t;
// 常规的测试⽤例
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试⽤例
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
t.InOrder();
//cout << t.IsBalanceTree() << endl;
cout<<t.IsBalance();
}运行以上代码输出如下所示：
这时只能是说明对以上示例的测试用例进行插入是没问题的，要更严谨的验证就需要有更多的测试用例，这时使用以上的代码进行验证 ，并且测试进行插入的效率以及查找效率
void TestAVLTree2()
{
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 (auto e : v)
{
t.Find(e);
}*/
// 随机值
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;
//父节点为祖父节点的左节点时
// g
// p u
//c
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
{
//当c为p的左节点时
// g
// p u
//c
if (Parent->_left == cur)
{
RotateR(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的右节点时
// g
// p u
// c
else
{
RotateL(Parent);
RotateR(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
//父节点为祖父节点的右节点时
// g
// u p
// c
else
{
Node* uncle = grandfather->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
//叔叔不存在或者为黑
else
{
//当c为p的右节点时
// g
// u p
// c
if (Parent->_right == cur)
{
RotateL(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的左节点时
// g
// u p
// c
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()
{
_InOrder(root);
cout << endl;
}
int Height()
{
return _Height(root);
}
int Size()
{
return _Size(root);
}
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
// 前序遍历⾛到空时，意味着⼀条路径⾛完了
//cout << blackNum << endl;
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)
{
Node* subL = Parent->_left;
Node* subLR = subL->_right;
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)
{
Node* subR = Parent->_right;
Node* subRL = subR->_left;
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 TestAVLTree1()
{
RBTree<int, int> t;
// 常规的测试⽤例
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试⽤例
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
t.InOrder();
//cout << t.IsBalanceTree() << endl;
cout<<t.IsBalance();
}
void TestAVLTree2()
{
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 (auto e : v)
{
t.Find(e);
}*/
// 随机值
for (size_t i = 0; i < N; i++)
{
t.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
}
int main()
{
//TestAVLTree1();
TestAVLTree2();
return 0;
}以上就是本篇的全部内容了，在实现了红黑树之后接下来我们就可以基于红黑树来自己实现封装set和map，未完待续……