1. 红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 红色(Red) 或 黑色(Black)。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
红黑树通过对每个节点颜色的限制，从而使得整棵树的最长路径不超过最短路径的两倍（这里说的是整棵树），虽然红黑树达不到像AVL树那样绝对平衡，但却可以达到接近平衡。
2. 红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
这里我们需要注意的是：最后一点说到了此处的叶子节点不是指我们平时的普通叶子节点，而是指空节点(下图种的NIL节点)，其实最后一条性质并不会影响第四条性质，因为不计算叶子节点，树中所有的路径中的黑色节点都会减一，对第四点没有任何影响。
那么为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
其实这是因为红黑树中会存在两个特殊的路径，最短路径和最长路径，当一条路径中仅有黑色节点时这条路径是最短路径，当一条路径中黑色节点和红色节点相交排列时为最长路径。当满足以上性质时，红黑树的最长路径刚好是最短路径的两倍。
3. 红黑树节点的定义
红黑树的节点和AVL树很相似，都需要实现三叉链（左孩子、右孩子和父亲），但不同的是红黑树节点中不需要定义控制平衡因子的变量。但是红黑树在定义节点之前需要定义一个枚举类型来控制节点的颜色。然后在节点定义的结构体中定义一个枚举类型的变量来控制每个节点的颜色。
enum Colour {
RED,
BLACK,
};
template <class K,class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;//枚举红黑树的颜色
RBTreeNode(const pair<K,V> &kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{}
};
在构造函数中我们默认给每个节点的颜色初始化为红色，这是因为：
我们在初始化节点的颜色时，必然会违反性质3和性质4中的一条，如果我们定义的是黑色节点，那么根据性质4的要求，每新增一个黑色节点都必须调整整棵红黑树，保证每一条路径上的黑色节点数目都相同。如果我们定义的是红色节点，根据性质3，我们只需要保证它的孩子节点是黑色就可以了。所以
为了降低每次插入节点后对红黑树的调整，我们首相初始化时将节点初始化为红色。
当然了，如果新增的节点是根节点，我们只需要将节点的颜色改为黑色即可。当新增节的父节点颜色是红色时，我们需要对该路径上的节点颜色进行进一步的调整。当新增节点的父节点颜色为黑色时，此时我们不需要做任何事情。
4. 红黑树的插入
红黑树的插入操作，前面的部分和普通的二叉搜索树没什么区别。唯一需要注意的是，当我们插入的节点是根节点时，我们需要将该节点的颜色修改为黑色，因为红黑树根节点的颜色只能是黑色。
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 (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_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;//链接父节点
return true;
}
当我们新增一个节点时，需要先判断一下该节点的父节点的颜色。如果该节点的父节点的颜色是黑色，不违反红黑树的性质，所以不需要进行任何调整。
如果该节点父节点的颜色是红色，此时出现了连续的红节点，不满足红黑树的性质，所以我们需要根据不同的情况来进行调整，使整棵树依然是一棵红黑树。
红黑树的调整分为两种情况：仅变色 和 旋转 + 变色
💕 情况一：仅变色
💕 情况二：旋转 + 变色
4.1 调整一：叔叔存在且为红
当。cur为红，p为红，g为黑，u==(这里的u指的是叔叔节点)==存在且为红。解决方式为：将p和u改为黑，g改为红，然后把g当作cur，继续向上调整。
根据上面的调整，调整完成后。当g是根节点时，我们仅仅将根节点变为黑色就可以了。但是，如果g不是根节点时，我们并不知道g的父节点的情况，所以我们需要将g作为新增节点继续向上调整。
下面我们来看一下具象图的情况分类和调整方式：
💕 a/b/c/d/e都是空，cur为新增
💕 当子树高度h==1时
所以，只要叔叔存在且为红，那么无论如何插入的节点的父亲在祖父节点的左边还是右边。都统一将叔叔节点和父亲节点变黑，将祖父节点变红，然后再继续向上调整。
4.2 调整二：叔叔不存在/叔叔存在且为黑
当叔叔不存在或者叔叔存在且为红时，他们的调整方式都是相同的。都是先旋转、再变色。当然了旋转也分为了不同的情况，可能是单旋也可能需要双旋
单旋情况：
💕 a/b/c/d/e都是空，cur为新增，uncle不存在时
当叔叔不存在时，cur一定是新增节点，这时我们需要进行的操作是：旋转 + 变色，先将以g为轴点进行左旋，再将p改为黑色，g改为红色。
💕 uncle存在且为黑时
如图所示的情况，新增的节点的uncle存在且为红色，所以是上面调整一的情况，当变色并向上调整一次后，遇到了uncle存在且为黑的情况，此时我们再进行先旋转、后变色。
双旋情况：
💕 a/b/c/d/e都是空，cur为新增，uncle不存在时
💕 uncle存在且为黑时
红黑树的旋转 – 和 AVL 树一样，红黑树会根据父节点位置的不同和插入节点位置的不同选择不同的旋转方式来进行调整，旋转一共分为四类：
- 右单旋 – 父节点在祖父节点的左侧，cur 在父节点的左侧；
- 左单旋 – 父节点在祖父节点的右侧，cur 在父节点的右侧；
- 左右双旋 – 父节点在祖父节点的左侧，cur 在父节点的右侧；
- 右左双旋 – 父节点在祖父节点的右侧，cur 在父节点的左侧。
需要注意的是，和 情况1 – 叔叔存在且为红 不同，由于这里我们将祖父节点的颜色改为黑色 (旋转后子树的根节点为祖父节点)，所以不用考虑祖父的父节点为红色从而违反性质4的问题，即这里我们不需要继续向上调整。
4.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 (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_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 (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)// 情况1：u存在且为红，变色处理，并继续往上处理
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else // 情况2 + 3：u不存在/u存在且为黑 --- 旋转 + 变色
{
// g
// p u
// c
if (cur == parent->_left)
{
//右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
//先对parent节点进行左单旋，在对grandfather进行右单旋
RotateL(parent);
RotateR(grandfather);
//调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // (grandfather->_right == parent)
{
// u存在且为红，变色处理，并继续往上处理
// g
// u p
// c
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
// g
// u p
// c
if (cur == parent->_left)
{
RotateR(parent);
RotateL(grandfather);
//调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
5. 红黑树的验证
红黑树的检测分为两步：
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 检测其是否满足红黑树的性质
💕 验证是否满足二叉搜索树
//验证中序遍历是否有序
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
💕 验证是否满足红黑树的性质
//判断是否为红黑树
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根节点颜色是红色的" << endl;
return false;
}
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
benchmark++;
cur = cur->_left;
}
//判断是否有连续红色节点
return _Check(_root, 0, benchmark);
}
bool _Check(Node* root, int blackNum, int benchmark)
{
if (root == nullptr)
{
if (blackNum != benchmark)
{
cout << "某条路径黑色节点的数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
blackNum++;
if (root->_col == RED
&& root->_parent
&& root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}
return _Check(root->_left, blackNum, benchmark)
&& _Check(root->_right, blackNum, benchmark);
}
6. 红黑树与 AVL 树的比较
红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，但由于红黑树不追求绝对平衡，只需要保证最长路径不超过最短路径的2倍，所以在某些极端情况下红黑树的查询效率相较于 AVL 树要低一点点；例如当树左子树全部为黑色节点，右子树全部为一黑一红交替时，红黑树的高度差不多是 AVL 树的两倍，但是此时红黑树的查询效率仍然属于 O(logN) 这个量级；
不过也正是由于红黑树不要求左右子树绝对平衡，所以红黑树相较于 AVL 树在插入和删除时的旋转次数要少一些，所以在经常进行增删的结构中红黑树的性能比 AVL 树更优，而且红黑树实现比较简单，所以在实际业务中一般都使用红黑树，而不使用 AVL 树。
7. 红黑树的整体代码实现
//枚举类型，枚举红黑树的颜色红色和黑色
enum Colour {
RED,
BLACK,
};
//创建红黑树的节点
template <class K,class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;//枚举红黑树的颜色
RBTreeNode(const pair<K,V> &kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{}
};
//创建红黑树
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//析构
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
//查询
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_kv.first)
cur = cur->_right;
else if (key < cur->_kv.first)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
//插入
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 (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_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 (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)// 情况1：u存在且为红，变色处理，并继续往上处理
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else // 情况2 + 3：u不存在/u存在且为黑 --- 旋转 + 变色
{
// g
// p u
// c
if (cur == parent->_left)
{
//右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
//先对parent节点进行左单旋，在对grandfather进行右单旋
RotateL(parent);
RotateR(grandfather);
//调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // (grandfather->_right == parent)
{
// u存在且为红，变色处理，并继续往上处理
// g
// u p
// c
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
// g
// u p
// c
if (cur == parent->_left)
{
RotateR(parent);
RotateL(grandfather);
//调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
//判断是否为红黑树
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根节点颜色是红色的" << endl;
return false;
}
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
benchmark++;
cur = cur->_left;
}
//判断是否有连续红色节点
return _Check(_root, 0, benchmark);
}
int Height()
{
return _Height(_root);
}
private:
//红黑树的高度计算
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHight = _Height(root->_left);
int rightHight = _Height(root->_right);
return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}
bool _Check(Node* root, int blackNum, int benchmark)
{
if (root == nullptr)
{
if (blackNum != benchmark)
{
cout << "某条路径黑色节点的数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
blackNum++;
if (root->_col == RED
&& root->_parent
&& root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}
return _Check(root->_left, blackNum, benchmark)
&& _Check(root->_right, blackNum, benchmark);
}
void _Destroy(Node* root)
{
if (root == nullptr)
return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
//这里我们需要注意一下，subRL有可能为空
if (subRL)
subRL->_parent = parent;
Node* ppnode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
//判断父节点是否为_root节点
if (parent == _root) {
_root = subR;
_root->_parent = nullptr;
}
else {
if (parent == ppnode->_left)
ppnode->_left = subR;
else
ppnode->_right = subR;
subR->_parent = ppnode;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//保存parent节点的_parent节点
Node* ppnode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
//判断parent节点是否为_root节点
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == ppnode->_left)
ppnode->_left = subL;
else
ppnode->_right = subL;
subL->_parent = ppnode;
}
}
private:
Node* _root = nullptr;
};
void Test_RBTree1()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 16, 3, 7, 11, 9, 26, 18, 14, 15 };
RBTree<int, int> t1;
for (auto e : a)
{
t1.Insert(make_pair(e, e));
cout << t1.IsBalance() << endl;
}
t1.InOrder();
cout << t1.IsBalance() << endl;
}
void Test_RBTree2()
{
srand(time(0));
const size_t N = 5000000;
RBTree<int, int> t;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand() + i;
t.Insert(make_pair(x, x));
}
cout <<"红黑树是否平衡: " <<t.IsBalance() << endl;
cout <<"红黑树的高度为: " << t.Height() << endl;
}
