#1024程序员节 | 征文#
个人主页：夜晚中的人海
文章目录
- ⭐前言
- 🚆一、红黑树的概念
- 🏠二、红黑树的规则
- 🎄三、红黑树的效率
- 🎡四、红黑树的实现
- 1. 基本框架
- 2. 插入操作
- • 变色
- • 单旋 + 变色
- • 双旋 + 变色
- 3. 查找操作
- 4. 验证操作
⭐前言
我们在前面的文章中提到了当一棵树退化成单支时导致性能和效率降低时，我们可以用AVL树来解决这一问题。但由于AVL树是一棵高度平衡的树，且每次修改树的结构时都要保证左右子树的高度差不超过1。因此如果需要一棵结构动态变化的二叉搜索树时，红黑树的作用就出来了。下面就来详细讲解一下有关红黑树的相关知识以及操作。
🚆一、红黑树的概念
红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位来表示节点的颜色，可以是红色或者黑色。红黑树确保没有一条路径会比其他路径长出2倍（通过对任何一条从根到叶子的路径上各个结点的颜色进行约束），因而是接近平衡的。
红黑树的结构示意图：
🏠二、红黑树的规则
每一棵红黑树，都需要满足以下规则：
1.每个节点不是红色就是黑色。
2.根节点是黑色的。
3.如果一个结点是红色的，则它的两个孩子结点必须是黑色的，即任意一条路径不会有连续的红色结点。
4.对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。
通过上述规则，我们思考一下红黑树是如何确保最长路径不超过最短路径的两倍的呢？
我们通过规则4可知，从根节点开始到空节点的每条路径上都有相同数量的黑色节点，因此在极端场景下，最短路径就是全是黑色节点的路径。我们假设该最短路径的长度为bh。
由规则2和3可知，任意一条路径上不会有连续的红色节点，因此在极端场景下，最长路径就是一黑一红间隔组成的。我们假设最长路径的长度为2 * bh。
综合上述规则，全黑的最短路径和一黑一红的最长路径并不是每一棵红黑树都存在的。因此我们假设一条从根到空节点的路径长度为x，则这个x的范围是在bh <= x <= 2 * bh之间的。
🎄三、红黑树的效率
1.红黑树在插入、查找和删除操作上的时间复杂度都为O(logN)。
2.与AVL树相比，其插入和删除操作上的平衡代价较低，整体性能略优于AVL树，且旋转情况少于AVL树，这使得红黑树在实际应用中更加高效和稳定。
🎡四、红黑树的实现
1. 基本框架
// 枚举值表⽰颜⾊
enum Colour
{
RED,
BLACK
};
// 默认按KV结构进行实现
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};
2. 插入操作
红黑树的插入与AVL树的插入不同，这也是区分它们俩之间的一大特点。红黑树的插入减少了旋转的次数，采用变色+旋转的调整方式，提高了插入的效率。
红黑树插入一个值的过程：
1.按照二叉搜索树的规则进行插入，插入后看是否符合红黑树的4个规则。
2.如果是空树插入，则新增节点为黑色节点。如果是非空树进行插入，则新增节点必须是红色节点。因为如果新增的是黑色节点，则违反了规则4，而规则4是很难进行维护的。
3.非空树插入后，新增节点为红色。如果父亲节点是黑色的，则没有违反任何规则，插入结束。而如果父亲节点是红色的情况下，则违反了规则3。我们通过下图来分析一下：
我们可以确定，c是红色的，p也为红色的，则g必为黑色的，这三个颜色都固定了，因此关键的变化就看u的情况了。需要根据u分为以下几种情况进行分别处理。
• 变色
当c为红，p为红，g为黑，u存在且为红时，则只需将p和u变黑，g变红，再把g当成新的c，不断往上进行更新即可。
为什么g还需要向上进行更新呢？
• 当这棵树是某棵子树时，g一定还有双亲节点，如果g的双亲节点为红色，则还需要进行向上调整。
• 当这棵树是整棵树时，g是根节点，则需要将g的颜色修改成黑色。
在这里我们只展示了一种情况，而在现实情况中我们需要处理很多种情况，因此我们只需看抽象图即可，其原理和处理方法都相似。
• 单旋 + 变色
当c为红，p为红，g为黑，u不存在或存在且为黑时，如果u不存在时，则c一定是新增节点；而如果u存在且为黑时，则c一定不是新增的，c之前是肯定是黑色的，在c的子树中进行插入，变色将c从黑色变为红色，不断更新上来的。
因此在这里我们发现，p必须变黑才能解决连续红色节点的问题，而这种情况下单纯的变色并不能解决，需要用到旋转+变色。
如果是上述图中的情况，那么我们以g为旋转点进行右单旋，再把p变黑，g变红即可。让p成为整棵树的新根，这样就可以解决连续红色节点的问题。且p并不需要往上更新，因为p的父亲节点是红色还是空都不违反规则。
如果是上述图中的情况，则与前面所讲的方法相反即可。以g为旋转点进行左单旋，再把p变黑，g变红即可。让p成为整棵树的新根。也同样不需要往上进行更新。
• 双旋 + 变色
当c为红，p为红，g为黑，u不存在或存在且为黑时，如果u不存在时，则c一定是新增节点；而如果u存在且为黑时，则c一定不是新增的，c之前是肯定是黑色的，在c的子树中进行插入，变色将c从黑色变为红色，不断更新上来的。
如果是上图这一情况，p是g的左，c是p的右时，那么则先对p为旋转的进行左单旋，再以g为节点进行右单旋，再把c变黑，g变红即可，让c成为整棵树的新根，这样就可以解决连续红色节点的问题了。
如果是上述这一情况，p是g的右，c是p的左时，那么先对p进行右单旋，再以g为旋转点进行左单旋，再把c变黑，g变红，让c成为整棵树的新根。
完整插入代码：
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);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//如果父亲节点是红色，则需要进行处理
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
// g
// p u
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上进行处理
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
3. 查找操作
按二叉搜索树的逻辑进行查找，其效率为 O(logN)
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;
}
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);
}
