红黑树
概念
红⿊树是⼀棵⼆叉搜索树。它的每个结点增加⼀个存储位来表示结点的颜⾊，可以是红色或者黑色（并不会出现第三种颜色）。
通过对结点颜色特别的规则进行约束，红黑树确保没有任何⼀条路径会比其他路径长出2倍，即保证最长路径（一黑一红）<= 最短路径*2（全黑），因此红黑树是接近平衡的。
规则
1，每个结点不是红色就是黑色。
2，根结点是黑色的。
3，如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点。
4，对于任意⼀个结点，从该结点到其所有空结点（NULL）的简单路径上，均包含相同数量的黑色结点。
5，最长路径（一黑一红）<= 最短路径*2（全黑）。
说明：《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是黑色的规则。他这⾥所指的叶⼦结点 不是传统的意义上的叶⼦结点，⽽是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了 ⽅便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道 ⼀下这个概念即可
实现
结点
// 枚举值表⽰颜⾊
enum Colour
{
RED,
BLACK
};
// 这⾥我们默认按key_value结构实现
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
//这⾥更新控制平衡也要加⼊parent指针
RBTreeNode<K, V>* _parent;
Colour _col;
//构造
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(BLACK)
{
}
};
插入
首先实现最简单的插入操作。
1，首先判断是否是空树，因为空树也是红黑树。如果是空树，创建新节点，颜色是黑色（根节点必须是黑色），返回即可。
2，查找我们数据应该插入的位置，查找规则和二叉搜索树一样。比当前结点大，再去和右孩子的结点比较；比当前结点小，再去和左孩子的结点比较；即大就向右走，小就向左走，直到找到空，执行插入操作。
3，不是空树，创建新增结点，默认颜色是红色。为什么不给黑色，仔细分析红黑树的规则发现：如果新增结点是黑色的话，那么就可能会破坏其他简单路径上黑色结点数量，造成简单路径黑色结点的数量不相等。所以默认是红色结点，这样更方便。
那是否可以将全部结点都设置为黑色呢？按照红黑树的规则来看，逻辑上没有问题，但是这样的红黑树就失去了原本意义，全部都是黑色结点和二叉搜索树没有区别，而且还浪费了存储颜色的额外空间。
4，最简单的情况是，新节点的父亲结点是黑色，则插入成功后就结束。
但是如果父亲结点是红色，那么插入新节点后就需要进行变色处理，原因是红黑树不会存在连续的红色结点，变色处理稍微麻烦，放到后边位置详细说明。
参考代码：
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);
return true;
}
//记录cur的父结点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//新增结点，初始给红色
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
return true;
}
private:
Node* _root = nullptr;
};
变色
前面分析过，如果新节点的父亲结点存在且为红色，那么需要对祖先结点进行变色。
但是变色依旧有多种情况，需要分别讨论。
为了方便使用缩写展示：g代表grandfather，p代表parent，u代表uncle，c代表cur即新结点。
1，
- 父亲结点存在且为红色
- 此时的父亲结点是爷爷结点的左孩子
- 叔叔结点存在并且为红色
此时经过分析得到，我们需要对父亲结点进行变色处理，以下是参考过程：
将父亲和叔叔结点颜色变黑，爷爷结点颜色变红
注意：为了防止此处将根结点也变为红色，所以在最后一处_root->_col = RED
如果此时符合红黑树的规则，那么即可结束，反之向上更新结点，直到结束。
//更新结点位置，向上更新
cur = grandfather;
parent = cur->_parent;
2，
- 父亲结点存在且为红色
- 此时的父亲结点是爷爷结点的左孩子
- 叔叔结点不存在或者存在且为黑色
此时需要进行变色+旋转处理。
但是旋转时又有所差异：如果cur是parent的左孩子（如下图），需要以grandfather为旋转点进行右单旋；
如果cur是parent的右孩子（如下图），需要先以parent为旋转点左单旋，再以grandfather为旋转点进行右单旋的左右双旋，最后要记得将旋转后的cur改为黑色，grandfather改为红色。
3，
父亲结点存在且为红色
此时的父亲结点是爷爷结点的右孩子
叔叔结点存在且为红色
与情况1类似不再赘述。
4，
父亲结点存在且为红色
此时的父亲结点是爷爷结点的右孩子
叔叔结点不存在或者存在且为黑色
与情况2类似不再赘述。
变色参考代码：
//变色处理
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
// g
//p u
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//叔叔结点存在，并且为红色
if (uncle && uncle->_col == RED)
{
//将父亲和叔叔结点颜色变黑，爷爷结点颜色变红
//为了防止此处将根结点也变为红色，所以在最后一处_root->_col = RED
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//更新结点位置，向上更新
cur = grandfather;
parent = cur->_parent;
}
//叔叔结点不存在，或者存在并且为黑色
//变色+旋转
else
{
// g
// p u
//c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
//cur == parent->_right
else
{
// g
// p u
// c
//双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
// g
// u p
//parent == grandfather->_right
else
{
Node* uncle = grandfather->_left;
//叔叔结点存在，并且为红色
if (uncle && uncle->_col == RED)
{
//将父亲和叔叔结点颜色变黑，爷爷结点颜色变红
//为了防止此处将根结点也变为红色，所以在最后一处_root->_col = RED
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//更新结点位置，向上更新
cur = grandfather;
parent = cur->_parent;
}
//叔叔结点不存在，或者存在并且为黑色
//变色+旋转
else
{
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
//cur == parent->_left
else
{
// g
// p u
// c
//双旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
查找
查找很简单，与二叉搜索树的查找规则一样。
即要查找的cur结点的值大于根结点就向右走，比当前结点小就向左走，直到查找到或者走到空为止。
查找参考代码
//查找
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;
}
遍历
因为红黑树是二叉搜索树，所以使用中序遍历即可。
//中序遍历
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
红黑树检查
对红黑树检查时，可以从红黑树的规则入手。
1，每个结点不是红色就是黑色。
2，根结点是黑色的。
3，如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红色结点。
4，对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点。
对于规则1，我们在实现时，使用的就是红色和黑色的枚举，不可能出现其他颜色。
对于规则2，也很好判断，加一句判断语句即可。
对于规则3，前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲的颜⾊就⽅便多了。
对于规则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->_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);
}
完整代码
https://gitee.com/any10/c_plus_plus/blob/master/2025c%2B%2B/RBTree_5_5/RBTree.h