一、红黑树概念
1.1 什么是红黑树
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，也就是最长路径不超过最短路径的2倍，因而是接近平衡的。
2.1 红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个结点是红色的，则他的两个孩子是黑色的，及不存在两个连续的红色结点
- 对于每个叶子结点，从该结点到其所有后代叶结点的简单路径，均包含相同数目的黑色节点
- 每个叶子结点都是黑色的（此处的叶子节点指的是空节点）
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？
【解释】：由于红黑树要保证每条路径的黑色结点个数相同，且不能存在连续的两个红色结点，所以最短路径就是全黑，最长路径是一黑一红交替，这样红黑树的最长路径的极限也只能为最短路径的两倍
二、红黑树的实现
2.1 红黑树结点的定义
enum Color
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode
{
RBTreeNode(const pair<K,V>& kv)
:_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)
{}
struct RBTreeNode* _left;
struct RBTreeNode* _right;
struct RBTreeNode* _parent;
pair<K, V> _kv;
Color _col;
};思考：在结点的定义中，为什么要将结点的默认颜色给成红色的？
【解释】：若将结点的颜色默认为黑色，由于要求每条路径的黑色结点个数相同，如果新插入一个结点，就会破坏这个性质，影响比较大，如果将结点的颜色默认为红色，那么最多也就会出现两个连续的红色结点，只会影响一条路径，只需要进行调整即可，影响比较小
2.2 红黑树的插入
1. 按照二叉搜索树的规则将结点插入到红黑树中
2. 检测插入结点后，红黑树的性质是否遭到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点（因为cur与p一定为红色，g一定为黑色，我们只需要对u进行讨论）
- 情况一：cur为红，p为红，g为黑，u存在且为红（假设uncle在g的右边）
注意：此时看到的树可能是一颗完整的树，也可能是一颗子树
解决方法：
由于出现了连续的两个红色结点，我们只能将p变为黑色，因为如果cur为新增结点，将其变为黑色会破坏性质4，而将p变为黑色，会导致g的左右子树黑色节点不同，所以需要将u也变为黑色，而g有可能只是一颗子树，为了保证与其他路径的黑色节点个数相同，还需要将g变为红色，如果g为根节点的话，再将其变为黑色即可。
- 情况二：cur为红色，p为红色，g为黑色，u不存在或者u存在且为黑色（假设u在g的右边）
说明：u的情况存在两种
1.uncle不存在，那么cur一定是新增的那个结点，因为如果不是新增结点，那么cur和p至少有一个应该为黑色，不然就违反性质3了
2.uncle存在且为黑色，那么cur原来的颜色一定为黑色，现在看到cur的颜色为红色是因为cur子树在调整过程中将cur变为了红色
【解决办法】：
- 如果cur为p的左孩子
将p变黑，g变红，以g作为父亲结点右单旋
- 如果cur为p的右孩子
将cur变黑，g变红，先以p为父亲节点左单旋，在以g为父亲节右单旋
ps：uncle为g左边原理同上，对于旋转不清楚的可以参考数据结构--AVL树
2.3 代码实现
bool Insert(const pair<K,V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
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);
if (parent->_kv.first>kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else //uncle不存在或者uncle存在且为黑
{
if (cur == parent->_left)
{
// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
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 //uncle不存在或者uncle存在且为黑
{
if (cur == parent->_right)
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}三、红黑树的验证
红黑树的检测分为两步：
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质
bool IsBalance()
{
if (_root->_col == RED)
return false;
Node* cur = _root;
int RefNum = 0; //作为路径黑色结点个数的参考
while (cur)
{
if (cur->_col == BLACK)
RefNum++;
cur = cur->_left;
}
return _IsBalance(_root,RefNum,0);
}
bool _IsBalance(Node* root,int RefNum,int num)
{
if (root == nullptr)
{
//验证每条路径的黑色节点个数是否相同
if (num != RefNum)
{
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)
num++;
return _IsBalance(root->_left, RefNum, num) && _IsBalance(root->_right, RefNum, num);
}