目录
1.预备知识
红黑树本质是二叉搜索树的变形，所以需要了解一下二叉搜索树的知识：
还需要了解旋转的知识，在AVL树中我讲解过旋转的知识，这一讲我不会讲太多关于旋转如何改变指针指向的知识，需要的可以去看这篇博客：
2.红黑树的概念
红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。
2.1红黑树的规则
（1） 每个结点不是红⾊就是⿊⾊；
（2） 根结点是⿊⾊的；
（3） 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点；
（4） 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点。
以上四条规则非常重要，一定要了解它们才能为后面的红黑树的实现做铺垫！
以下就是一个标准的红黑树：
2.2红黑树如何确保最长路径不超过最短路径的两倍的？
（1）由规则4可知，从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就就是全是⿊⾊结点的路径，假设最短路径⻓度为bh；
（2）由规则2和规则3可知，任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀⿊⼀红间隔组成，那么最⻓路径的⻓度为2*bh。
（3）综合红⿊树的4点规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= x <= 2*bh。
2.3红黑树的效率
假设N是红⿊树树中结点数量，h最短路径的⻓度，那么2^h-1 <= N <2^(2*h)-1，由此推出h=logN,也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径 2 ∗ logN ，那么时间复杂度还是O(logN)。
此外红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。
3.红黑树实现的初步代码
首先我们需要枚举出结点的类型，所以需要用到C语言学到的枚举：
//枚举结点的颜色
enum Color
{
Red,
Black
};其次我们还需要定义红黑树结点的结构，建议写成key-value类型的结构，因为我们实现红黑树后面就要手动实现map和set的，我们就需要定义两个模板参数的类，除了Color表示结点的颜色以外，还需要有left表示左孩子，right表示右孩子，parent表示父亲，此外由于是key-value结构，所以要用到键值对的知识所以要借助pair对象进行初始化，用来存储key和value：
//RBTree结点的定义
template<class K,class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
Color _col;
//构造函数就行初始化
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{ }
};至于这个红黑树本身就很简单定义出来了：
//RBTree的定义
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//进行各种操作
private:
Node* _root = nullptr;
};4.红黑树的插入（最重要且最难）
4.1大概过程
（1）按照二叉搜索树规则进行插入，插⼊后我们只需要观察是否符合红⿊树的4条规则；
（2）如果是空树插⼊，新增结点是⿊⾊结点；
（3）如果是非空树插入，那么我们先把新增结点置为红色，因为如果是⾮空树插⼊，新增⿊⾊结点就破坏了规则4，规则4是很难维护的；
（4）⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是⿊⾊的，则没有违反任何规则，插⼊结束；
（5）⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是红⾊的，则违反规则3。假设我们把新增结点标识为c (cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为g(grandfather)，p的兄弟标识为u（uncle）。进⼀步分析，c是红⾊，p为红，g必为⿊，这三个颜⾊都固定了，关键的变化看u的情况。
此外当遇到第（5）种情况的uncle不存在或uncle存在且为黑时，不用继续往上更新了，因为：
旋转和变色操作后，子树的黑高度保持不变（即从子树到任何叶子节点（这里的叶子结点指的是空结点）的路径上黑色节点数量相同）（即一定满足规则4）。且由于子树根变为黑色，它不会与它的父节点形成连续的红色节点（即使父节点是红色）（即一定是满足规则3的）。
我们主要处理的是第5种情况，但是现在我们需要先把前四种情况的代码先写出来。
4.2初步代码
其中的while循环继续条件是parent存在且parent->_col==Red这是由于一般情况下是不会导致规则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->_kv.first > kv.first)
{
//往左递归
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
//往右递归
parent = cur;
cur = cur->_right;
}
else
{
//红黑树不支持插入相等的键
//所以返回false
return false;
}
}
//现在已经找到该插入的位置了，且此时cur=nullptr
//建立cur与parent之间的联系
cur = new Node(kv);
cur->_parent = parent;
if (parent->_kv.first > kv.first)
{
//cur为parent的左孩子
parent->_left = cur;
}
else
{
//cur为parent的右孩子
parent->_right = cur;
}
//确定该结点的实际颜色
cur->_col = Red;
//只有parent存在且parent->_col==Red才继续循环
while (parent && parent->_col == Red)
{
//之后代码写的地方
}
return true;
}4.3变色
插入结点之前：
当我们插入28时有：
或是插入23：
或者是插入21：
或是插入26：
这种情况就是c为红，p为红，能推出g为黑，若此时u存在且为红，不用管c是b的左孩子还是b的右孩子，不用管p是g的左孩子还是g的右孩子，都可以处理成只变色的情况，这些情况可以分别变成这些颜色：
（1）插入28后，变色：
（2）插入23变色：
（3）插入21变色：
（4）插入26变色：
也就是说明u存在且为红色，那么就要把p和u变为黑色，g变成红色即可。
但是我们注意要分情况讨论，因为后期还要判断更多情况，此外，这种情况会导致该子树的根结点为红色，可能会导致该红黑树不满足规则3，所以要继续往上更新（且此时要直接跳到grandfather这个结点（我们只要判断某个红色结点的父亲是不是满足规则）），所以在while循环改成：
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
}
else
{
Node* uncle = grandfather->_left;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
}
}4.4单旋+变色
c为红，p为红，g为黑，若u不存在，则是这种：
这个时候我们就需要单旋+变色，首先旋转成这样（右单旋）：
然后再变色，g变成红色，p变成黑色：
这就相当于我们在AVL树所学的右单旋。
如果是u不存在且p为g的右孩子且c为p的右孩子，即：
这个时候我们先进行左单旋：
然后把p变成黑色，g变成红色即可：
若u存在且为黑色，第一种情况下变成这样：
第二种情况则变成这样：
也就是说u不管是不存在还是存在且为黑，只要满足g、p、c都在一条线上就都适用于旋转+变色的情况，也就是说if(grandfather->_left==parent && parent->_left== cur)和if(grandfather-> _right == parent && parent->_right == cur)都是这样的处理方式，只是第一种是进行右单旋，第二种是进行左单旋而已，所以在Insert函数中的while循环中改成：
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
//u不存在或u存在且为黑
else
{
if (parent->_left == cur)
{
//即以下类型
//右单旋+变色
// g(黑)
// p(红) u(不存在或为黑)
//c(红)
//是以grandfather为旋转轴进行的右单旋
//所以参数不要传错了
RotateR(grandfather);
//旋转结果
// p(黑)
// c(红) g(红)
// u(不存在或为黑)
//改变颜色
parent->_col = Black;
grandfather->_col = Red;
}
//子树的根结点为黑色，已经不用继续往上判断
break;
}
}
else
{
Node* uncle = grandfather->_left;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
//u不存在或u存在且为黑
else
{
if (parent->_right == cur)
{
//即为这种类型
// g(黑)
//u(不存在或为黑) p(红)
// c(红)
//以grandfather为旋转轴的左单旋
RotateL(grandfather);
//旋转后变成这样
// p(黑)
// g(红) c(红)
//u(不存在或为黑)
parent->_col = Black;
grandfather->_col = Red;
}
break;
}
}以下是左旋操作和右旋操作的具体代码（在RBTree类里面补全），里面指针的指向的改变看不懂的需要结合AVL树的博客进行理解：
//右单旋
void RotateR(Node* parent)
{
//防止传入空指针
assert(parent != nullptr);
Node* subL = parent->_left;
//如果是右旋，是必须有左孩子的
//所以要再检查subL是否为nullptr
assert(subL != nullptr);
Node* subLR = subL->_right;
//g的左孩子变成p的右孩子
parent->_left = subLR;
//p的右孩子变成g
subL->_right = parent;
//改变每个孩子的父母指向
//h可能为0（即b和c可能不存在）
//所以要先判断一下
//p的右孩子存在
if (subLR)
{
//p的右孩子的父亲变成g
subLR->_parent = parent;
}
//其次还可能parent->_parent==nullptr
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
subL->_parent = nullptr;
//并把_root置为subL;
_root = subL;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
//左单旋
void RotateL(Node* parent)
{
//防止传入空指针，导致空指针的解引用
assert(parent != nullptr);
Node* subR = parent->_right;
//左旋必须有parent->_right，如果parent没有右孩子就会导致出错
assert(subR != nullptr);
Node* subRL = subR->_left;
//先改变孩子的指向
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
//我们先存储起来parent->_parent，不然很容易绕晕
Node* parentParent = parent->_parent;
parent->_parent = subR;
//如果parentPrent不存在即parent==_root时
if (parent == _root)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}4.5双旋+变色
满足双旋的也就是不满足这些情况的其他情况：u不存在或u存在且为黑时，并且如果p为g的左孩子且c为p的右孩子，或者当p为g的右孩子且c为p的左孩子时满足这种情况
第一种情况如下：
先对以p为根结点的左旋，变成这样：
再以g为根结点进行右旋，变成这样：
最后再进行变色，我们经过观察发现：如果把c变成黑色，g变成红色，就满足规则4了，所以：
那么会有人有疑问，如果c不是新增结点，而是一棵子树的根结点怎么办，其实这种情况我们已经在AVL树中进行处理过了，如果我们真的要把所有情况列举出来，那么p还可能有左孩子，也有可能没有，我可以告诉你的一点最后的结果就是：c的右孩子作为g的左孩子，c的左孩子作为p的右孩子去了，不懂的建议去看AVL树中的左右双旋的演示，AVL树中就是处理了类似的情况，红黑树在本质上是比AVL树简单了一些，只要你学会了AVL树的旋转，看这个红黑树就简单很多了。
第二种情况为：
这种情况下就相当于我们在AVL树进行的右左双旋，其中c是可能有孩子的，不过有孩子的话，那么右双旋和左双旋已经帮我们把二者指针的指向改变了，所以就没必要我们手动去改变指针的指向了。回到正题，这个可以先以p为根结点进行右旋操作：
然后再以g为根结点的左旋操作：
最后进行变色操作，通过观察我们可以把p变成黑色，g变成红色即满足规则4：
为了简化代码的操作，我这里就直接在while循环中进行添加了，while循环改成：
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
//u不存在或u存在且为黑
else
{
if (parent->_left == cur)
{
//即以下类型
//右单旋+变色
// g(黑)
// p(红) u(不存在或为黑)
//c(红)
//是以grandfather为旋转轴进行的右单旋
//所以参数不要传错了
RotateR(grandfather);
//旋转结果
// p(黑)
// c(红) g(红)
// u(不存在或为黑)
//改变颜色
parent->_col = Black;
grandfather->_col = Red;
}
else
{
//即以下类型
// g
// / \
//p (红) u(不存在或为黑)
// \
// c(红)
//先进行左旋操作
RotateL(parent);
//再进行右旋操作
RotateR(grandfather);
//要求变成：
// c(黑)
// / \
// p(红) g(红)
// \
// u(不存在或为黑)
//进行变色
cur->_col = Black;
grandfather->_col = Red;
}
//子树的根结点为黑色，已经不用继续往上判断
break;
}
}
else
{
Node* uncle = grandfather->_left;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
//u不存在或u存在且为黑
else
{
if (parent->_right == cur)
{
//即为这种类型
// g(黑)
//u(不存在或为黑) p(红)
// c(红)
//以grandfather为旋转轴的左单旋
RotateL(grandfather);
//旋转后变成这样
// p(黑)
// g(红) c(红)
//u(不存在或为黑)
parent->_col = Black;
grandfather->_col = Red;
}
else
{
//即为这种类型
// g(黑)
// / \
//u(不存在或为黑) p(红)
// /
// c(红)
//先进行右旋操作
RotateR(parent);
//再进行左旋操作
RotateL(grandfather);
//要求变成这样
// c(黑)
// / \
// g(红) p(红)
// /
//u(不存在或为黑)
//进行变色
grandfather->_col = Red;
cur->_col = Black;
}
break;
}
}4.6红黑树的插入代码汇总和问题解答
红黑树的插入还有一个最重要的点要注意：
我们一直在关注规则3和4，没有关注规则2：根结点是⿊⾊的。而我们结束循环无非就两种情况：遍历到根结点导致parent不存在，parent->_col==Black，而我们如果遇到第一种情况，那么就是单纯的变色的情况导致的（u存在且为红色），而这种情况的grandfather->_col会变成红色，也就是说_root->_col为红色了，所以最终我们要加一句代码：_root->_col=Black;
所以最终红黑树插入的代码为：
//红黑树的插入
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->_kv.first > kv.first)
{
//往左递归
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
//往右递归
parent = cur;
cur = cur->_right;
}
else
{
//红黑树不支持插入相等的键
//所以返回false
return false;
}
}
//现在已经找到该插入的位置了，且此时cur=nullptr
//建立cur与parent之间的联系
cur = new Node(kv);
cur->_parent = parent;
if (parent->_kv.first > kv.first)
{
//cur为parent的左孩子
parent->_left = cur;
}
else
{
//cur为parent的右孩子
parent->_right = cur;
}
//确定该结点的实际颜色
cur->_col = Red;
//只有parent存在且parent->_col==Red才继续循环
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
//u不存在或u存在且为黑
else
{
if (parent->_left == cur)
{
//即以下类型
//右单旋+变色
// g(黑)
// p(红) u(不存在或为黑)
//c(红)
//是以grandfather为旋转轴进行的右单旋
//所以参数不要传错了
RotateR(grandfather);
//旋转结果
// p(黑)
// c(红) g(红)
// u(不存在或为黑)
//改变颜色
parent->_col = Black;
grandfather->_col = Red;
}
else
{
//即以下类型
// g(黑)
// / \
//p (红) u(不存在或为黑)
// \
// c(红)
//先进行左旋操作
RotateL(parent);
//再进行右旋操作
RotateR(grandfather);
//要求变成：
// c(黑)
// / \
// p(红) g(红)
// \
// u(不存在或为黑)
//进行变色
cur->_col = Black;
grandfather->_col = Red;
}
//子树的根结点为黑色，已经不用继续往上判断
break;
}
}
else
{
Node* uncle = grandfather->_left;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
//u不存在或u存在且为黑
else
{
if (parent->_right == cur)
{
//即为这种类型
// g(黑)
//u(不存在或为黑) p(红)
// c(红)
//以grandfather为旋转轴的左单旋
RotateL(grandfather);
//旋转后变成这样
// p(黑)
// g(红) c(红)
//u(不存在或为黑)
parent->_col = Black;
grandfather->_col = Red;
}
else
{
//即为这种类型
// g(黑)
// / \
//u(不存在或为黑) p(红)
// /
// c(红)
//先进行右旋操作
RotateR(parent);
//再进行左旋操作
RotateL(grandfather);
//要求变成这样
// c(黑)
// / \
// g(红) p(红)
// /
//u(不存在或为黑)
//进行变色
grandfather->_col = Red;
cur->_col = Black;
}
break;
}
}
}
//要注意规则2
_root->_col = Black;
return true;
}可能有些人会觉得如果grandfather是nullptr的怎么办？
理论上不需要额外增加 assert 检查 grandfather 是否有效，因为红黑树的性质已经保证了 grandfather 的存在性：
根节点必须是黑色。
红色节点的子节点必须是黑色（不能有连续的红色节点）
在while (parent && parent->_col == Red) 循环中：
parent 是红色 ⇒ 它的父节点 grandfather 必须存在（否则 parent 就是根节点，但根节点不能是红色）。因此，grandfather = parent->_parent 不会为 nullptr，无需额外检查。
不过还是建议各位加上assert(grandfather!=nullptr)，但是逻辑上这个语句是不会触发的。
5.红黑树的查找
红黑树的查找和AVL树差不多，就是如果搜索的数比该结点大就往该结点的右子树走，如果搜索的数比该结点小就往该结点的左子树走，所以代码为：
//红黑树的查找
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 nullptr;
}6.红黑树的验证
如果获取最长路径和最短路径去检验是否最长路径不超过最短路径的两倍这种方式是不可行的，先不说你能不能找到，关键是如果满足也不一定是红黑树啊。所以我们需要去检查四条规则：
（1）规则1枚举颜⾊类型，天然实现保证了颜⾊不是⿊⾊就是红⾊；
（2）规则2直接检查根即可；
（3）规则3前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲的颜⾊就⽅便多了，即如果遇到红色结点就检查父亲是不是红色，如果父亲是红色就返回false；
（4）规则4前序遍历，遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可。
要完成这个操作，我们需要先把第二个操作放到一个总函数里面，第4个操作先计算出一个最左路径的黑色结点个数，最后调用递归函数即可，所以我们可以这样写：
//红黑树的验证
//前序递归遍历
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->_kv.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 InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
7.测试代码
用两个测试函数进行测试：
//测试函数1
void TestRBTree1()
{
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.IsBalance() << endl;
}
//测试函数2
void TestRBTree2()
{
const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
RBTree<int, int> t;
for (size_t i = 0; i < v.size(); ++i)
{
t.Insert(make_pair(v[i], v[i]));
}
cout << t.IsBalance() << endl;
}头文件包含以下（VS编译器）：
#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include<vector>
#include<iostream>
using namespace std;8.代码汇总
#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include<vector>
#include<iostream>
using namespace std;
//枚举结点的颜色
enum Color
{
Red,
Black
};
//RBTree结点的定义
template<class K,class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
Color _col;
//构造函数就行初始化
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{ }
};
//RBTree的定义
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//右单旋
void RotateR(Node* parent)
{
//防止传入空指针
assert(parent != nullptr);
Node* subL = parent->_left;
//如果是右旋，是必须有左孩子的
//所以要再检查subL是否为nullptr
assert(subL != nullptr);
Node* subLR = subL->_right;
//g的左孩子变成p的右孩子
parent->_left = subLR;
//p的右孩子变成g
subL->_right = parent;
//改变每个孩子的父母指向
//h可能为0（即b和c可能不存在）
//所以要先判断一下
//p的右孩子存在
if (subLR)
{
//p的右孩子的父亲变成g
subLR->_parent = parent;
}
//其次还可能parent->_parent==nullptr
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
subL->_parent = nullptr;
//并把_root置为subL;
_root = subL;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
//左单旋
void RotateL(Node* parent)
{
//防止传入空指针，导致空指针的解引用
assert(parent != nullptr);
Node* subR = parent->_right;
//左旋必须有parent->_right，如果parent没有右孩子就会导致出错
assert(subR != nullptr);
Node* subRL = subR->_left;
//先改变孩子的指向
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
//我们先存储起来parent->_parent，不然很容易绕晕
Node* parentParent = parent->_parent;
parent->_parent = subR;
//如果parentPrent不存在即parent==_root时
if (parent == _root)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
//红黑树的插入
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->_kv.first > kv.first)
{
//往左递归
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
//往右递归
parent = cur;
cur = cur->_right;
}
else
{
//红黑树不支持插入相等的键
//所以返回false
return false;
}
}
//现在已经找到该插入的位置了，且此时cur=nullptr
//建立cur与parent之间的联系
cur = new Node(kv);
cur->_parent = parent;
if (parent->_kv.first > kv.first)
{
//cur为parent的左孩子
parent->_left = cur;
}
else
{
//cur为parent的右孩子
parent->_right = cur;
}
//确定该结点的实际颜色
cur->_col = Red;
//只有parent存在且parent->_col==Red才继续循环
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
//u不存在或u存在且为黑
else
{
if (parent->_left == cur)
{
//即以下类型
//右单旋+变色
// g(黑)
// p(红) u(不存在或为黑)
//c(红)
//是以grandfather为旋转轴进行的右单旋
//所以参数不要传错了
RotateR(grandfather);
//旋转结果
// p(黑)
// c(红) g(红)
// u(不存在或为黑)
//改变颜色
parent->_col = Black;
grandfather->_col = Red;
}
else
{
//即以下类型
// g
// / \
//p (红) u(不存在或为黑)
// \
// c(红)
//先进行左旋操作
RotateL(parent);
//再进行右旋操作
RotateR(grandfather);
//要求变成：
// c(黑)
// / \
// p(红) g(红)
// \
// u(不存在或为黑)
//进行变色
cur->_col = Black;
grandfather->_col = Red;
}
//子树的根结点为黑色，已经不用继续往上判断
break;
}
}
else
{
Node* uncle = grandfather->_left;
//u存在且为红
//只变色
if (uncle && uncle->_col == Red)
{
uncle->_col = parent->_col = Black;
grandfather->_col = Red;
//这个时候由于此子树的根结点还是红色的（要判断是否满足规则3）
//这时候直接令cur=grandfather，因为其他结点已经处理完毕了
cur = grandfather;
parent = cur->_parent;
}
//u不存在或u存在且为黑
else
{
if (parent->_right == cur)
{
//即为这种类型
// g(黑)
//u(不存在或为黑) p(红)
// c(红)
//以grandfather为旋转轴的左单旋
RotateL(grandfather);
//旋转后变成这样
// p(黑)
// g(红) c(红)
//u(不存在或为黑)
parent->_col = Black;
grandfather->_col = Red;
}
else
{
//即为这种类型
// g(黑)
// / \
//u(不存在或为黑) p(红)
// /
// c(红)
//先进行右旋操作
RotateR(parent);
//再进行左旋操作
RotateL(grandfather);
//要求变成这样
// c(黑)
// / \
// g(红) p(红)
// /
//u(不存在或为黑)
//进行变色
grandfather->_col = Red;
cur->_col = Black;
}
break;
}
}
}
//要注意规则2
_root->_col = Black;
return true;
}
//红黑树的查找
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 nullptr;
}
//红黑树的验证
//前序递归遍历
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->_kv.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 InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
//测试函数1
void TestRBTree1()
{
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.IsBalance() << endl;
}
//测试函数2
void TestRBTree2()
{
const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
RBTree<int, int> t;
for (size_t i = 0; i < v.size(); ++i)
{
t.Insert(make_pair(v[i], v[i]));
}
cout << t.IsBalance() << endl;
}一般情况下，用第一个测试函数的运行结果为：
第二个测试函数运行时间较久，最终正确的运行结果为：
建议各位每个写完每个函数都测试一下，建议画图理解设计出对应的旋转的例子，否则后面排查出错误比较麻烦。
9.红黑树的删除的思路讲解
红黑树的删除在面试中考得确实不多，所以在这里讲解一下思路，感兴趣的可以自己去实现一下：
（1）先用Find函数找到位置并删除；
（2）如果被删除的位置没有左右孩子就结束；
（3）如果被删除的位置只有左子树（a），如果被删除的位置是其父亲的左孩子，则其父亲的左孩子变成被a；如果被删除的位置是其父亲的右孩子，则其父亲的右孩子变成a。如果a的根结点是红色的，则观察是否违反规则3，如果不违反就结束，如果违反，则根据所学知识进行旋转和变色的操作；
（4）如果被删除的位置只有左子树（b），如果被删除的位置是其父亲的左孩子，则其父亲的左孩子变成被b；如果被删除的位置是其父亲的右孩子，则其父亲的右孩子变成b。如果b的根结点是红色的，则观察是否违反规则3，如果不违反就结束，如果违反，则根据所学知识进行旋转和变色的操作；
（5）如果被删除的位置有有左孩子和右孩子，则需要从左子树的最右结点或右子树的最左结点进行替换，替换后，观察该位置的结点颜色，如果该位置的结点颜色是红色就没问题，如果该位置的结点颜色是黑色，就需要进行变色+旋转的操作；
（6）如果遍历到根结点后就结束。
其中（3）和（4）以及（5）这三种情况都可能涉及到变色和旋转的情况，建议各位如果想了解如何进行删除的话就去搜索其他资料。
10.总结
红黑树算是一个比AVL树更抽象的一个概念，虽然说红黑树还涉及到变色的问题，不过这和平衡因子比起来差不多，红黑树是一个比较高级的数据结构了，学好红黑树对后面的面试也有很大的帮助，看似红黑树代码确实有点多了，但是只要你理解了AVL树旋转的逻辑，其实红黑树难度确实也不是很高，如果实在是没看懂就多画图来理解一下旋转+变色。
红黑树在后面的用红黑树实现map和set的封装也是一个比较重要的一个铺垫，后面的map和set的封装的讲解可能要到下周星期三左右了，后面内容难度未知，不过要学习C++就要面对这些难题，至少，你现在已经学会很多了。
好了，这讲就到这里，下讲也是一个比较重要（不知道难不难）的章节：C++进阶-用红黑树封装实现map和set，喜欢的可以一键三连哦，下讲再见！
