C++ | 红黑树
前言
本篇博客讲解c++中数据结构红黑树，看这篇博客之前请先去看：
C++ | AVL树_c++ avl树能有重复节点吗-CSDN博客
💓 个人主页：普通young man-CSDN博客
⏩ 文章专栏：C++_普通young man的博客-CSDN博客
⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
————————————————
红黑树的概念
红黑树是一种特殊的二叉搜索树，其每个节点包含一个额外的存储位来表示该节点的颜色，颜色可以是红色或黑色。通过施加特定的颜色约束规则于从根到任意叶子节点的所有路径上，红黑树保证了没有一条路径会比其他路径长出两倍以上，从而保持树的整体平衡性。
与AVL树相比，两者都是自平衡二叉搜索树，但它们在实现平衡的方式和效率上有所不同：
- 红黑树：通过对插入或删除操作后的树结构进行重新着色和旋转操作来维持一种宽松的平衡状态。它确保任何路径上的黑色节点数量相同，并且不允许连续两个红色节点出现。
- AVL树：对每个节点都维护一个平衡因子（左右子树高度差），并通过旋转操作严格保持这棵树的高度尽可能低，即绝对平衡。
红黑树的规则
节点颜色：每个节点要么是红色，要么是黑色。
根节点颜色：根节点必须是黑色。
红色节点的子节点：如果一个节点是红色，则它的两个子节点都必须是黑色。换句话说，任意路径上不会出现连续的红色节点。
黑色深度一致：对于树中的任意一个节点，从该节点到其可达的任何叶子节点（即NULL或哨兵节点）的所有简单路径上，黑色节点的数量（称为黑色深度）必须相同。
了解：
《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是⿊⾊的规则。他这⾥所指的叶⼦结点 不是传统的意义上的叶⼦结点，⽽是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了 ⽅便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道 ⼀下这个概念即可。
实际编程实现中，这些NIL节点通常被隐式处理或者直接忽略，特别是在高级编程语言中，因为它们通常不显式地表示这些空节点。
结合上面概念，看下方图片：
观看图片的时候看一下这个，避免大家去看平衡因子，可能会觉得是咋保持平衡的，其实就是这个颜色规则来保持平衡
红黑树的效率
如何确保最长路径不超过最短路径的二倍？
这个问题其实就被红黑树的规则给抹杀了，我们可以看一个图：
会发现每条路径的黑节点是相同的，这个我们可以参考红黑树的第四条规则，所以极端场景下，最短路径 就就是全是黑色结点的路径，假设最短路径长度为bh(black height)，由规则2和规则3可知，任意⼀条路径不会有连续的红色结点，所以极端场景下，最长的路径就是⼀黑⼀红间隔组成，那么最长路径的长度为2*bh。
综合红黑树的4点规则而言，理论上的全⿊最短路径和⼀黑⼀红的最长路径并不是在每棵红黑树都 存在的。假设任意⼀条从根到NULL结点路径的长度为x，那么bh<=h<=2*bh
两种特殊情况：
全是最短路径：
全是最长路径：
通过这些我们就可以看出红黑树的效率：
在红黑树中，假设 N为树中节点的数量,为从根节点到叶节点的最短路径长度。根据红黑树的性质，我们可以得出以下关系：
2^{h - 1} <= N < 2^{2h - 1}
通过对上述不等式进行推导，可以得出 h = logN 。这意味着在红黑树中，增删查改操作在最坏情况下，即沿着最长路径进行操作时，其时间复杂度为 O(log N) 。因为最长路径长度与最短路径长度 h相关，大致为 2h ，所以时间复杂度为 O(2\log N)，简化后仍为 O(log N) 。
相较于AVL树，红黑树的定义和规则更为抽象。AVL树通过直接控制节点高度差来维持平衡，较为直观。而红黑树则是借助四条颜色约束规则，间接实现了树的近似平衡。尽管二者在效率上处于同一量级，但在插入相同数量节点的情况下，由于红黑树对平衡的控制相对宽松，其旋转次数会更少。
红黑树实现
红黑树的结构
// 枚举值表⽰颜⾊
enum Colour
{
RED,
BLACK
};
// 这⾥我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
// 这⾥更新控制平衡也要加⼊parent指针
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;
};红黑树的插入
插入是这棵树的主要核心，因为如果你插入错误就不是红黑树
红黑树插入节点规则及处理流程
在红黑树中插入一个新节点时，需要遵循特定的规则，并根据不同情况进行相应处理，具体步骤如下：
步骤 1：确定新增节点的初始颜色
- 空树插入：若红黑树为空，将新增节点的颜色设置为黑色。这是因为空树插入黑色节点不会违反红黑树的任何规则。
- 非空树插入：若红黑树非空，将新增节点的颜色设置为红色。这是为了避免破坏红黑树的规则 4（从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点），因为插入黑色节点很可能会破坏此规则，且该规则相对较难维护。
步骤 2：检查插入后是否违反规则
插入节点后，需要检查是否违反红黑树的规则，主要关注规则 3（每个红色节点的两个子节点都是黑色，即从每个叶子到根的所有路径上不能有两个连续的红色节点）。根据父节点的颜色，分以下两种情况处理：
情况 1：父节点为黑色
若父节点为黑色，插入红色节点后没有违反红黑树的任何规则，插入操作结束。
情况 2：父节点为红色
若父节点为红色，插入红色节点后违反了规则 3。由于红黑树的性质，此时祖父节点（父节点的父节点）必定为黑色（因为不能有两个连续的红色节点）。接下来，需要根据叔叔节点（父节点的兄弟节点）的颜色进行进一步的分类处理：
- 关键颜色固定：此时新增节点
c为红色，父节点p为红色，祖父节点g为黑色，这三个节点的颜色是固定的，处理的关键在于叔叔节点u的颜色情况。 - 根据叔叔节点
u分类处理：后续需要根据叔叔节点u的颜色分为几种不同情况分别进行旋转和颜色调整操作，以恢复红黑树的性质。具体的分类及处理方式将根据叔叔节点u是红色还是黑色，以及节点的相对位置（如左子树或右子树）来确定。
红黑树插入调整：情况1 - 变色
当在红黑树中插入新节点
c后，若出现c为红色、其父节点p为红色、祖父节点g为黑色，且叔叔节点u存在且为红色的情况，可按以下方式处理：处理步骤
- 颜色调整：将
p和u的颜色变为黑色，g的颜色变为红色。- 持续更新：把
g当作新的c，继续向上进行更新操作。原理分析
由于
p和u原本为红色，g为黑色，将p和u变为黑色后，g左子树路径和右子树路径各自增加了一个黑色节点。接着把g变为红色，相当于保持了以g为根的子树中每条路径上黑色节点的数量不变。同时，这一操作解决了c和p连续为红色节点的问题，避免违反红黑树 “不能有两个连续红色节点” 的规则。
d/e/f代表每条路径拥有hb个⿊⾊结点的⼦树，a/b代表每 条路径拥有hb-1个⿊⾊结点的根为红的⼦树，hb>=0
在分析过程中，分别展示了
hb == 0、hb == 1和hb == 2的具体情况组合。当hb等于 2 时，组合情况多达上百亿种。这些具体样例的作用是辅助我们理解问题，实际上，无论情况数量有多少、情况本身多么复杂，处理方式都是一致的，即进行变色操作后继续向上处理。因此，我们只需关注抽象图来把握整体处理逻辑即可。
红黑树插入调整：情况2 - 单旋(AVL树)+变色
当在红黑树中插入新节点
c后，若c为红色、其父节点p为红色、祖父节点g为黑色，且叔叔节点u存在且为红色时：节点情况分析
- 若
u不存在，c一定是新增节点。- 若
u存在且为黑，c一定不是新增节点，c之前为黑色，是在c的子树中插入新节点后，经过类似情况 1 的变色处理，c从黑色变为红色更新上来的。处理必要性
为解决
p和c连续红色节点的问题，p必须变为黑色。又因为u不存在或者为黑色，单纯变色无法解决问题，需要结合旋转和变色操作。
p是g的右子节点，c是p的右子节点(左单旋)
- 操作步骤：以
g为旋转点进行左单旋，然后将p变为黑色，g变为红色。- 操作效果：旋转和变色后，
p成为这棵子树新的根节点。这保证了子树中黑色节点的数量不变，消除了连续的红色节点。并且，无论p的父节点是黑色、红色还是为空，都不会违反红黑树规则，无需再往上更新。g p / \ / \ u p --> g c \ c
p是g的左子节点，c是p的左子节点(右单旋)
- 操作步骤：以
g为旋转点进行右单旋，然后将p变为黑色，g变为红色。- 操作效果：旋转和变色后，
p成为这棵子树新的根节点。既保证了子树中黑色节点的数量不变，又避免了连续的红色节点。而且，不管p的父节点状态如何，都不会违反红黑树规则，无需再往上更新。g p / \ / \ p u --> c g / c
红黑树插入调整：情况1 - 双旋(AVL树)+变色
当在红黑树中插入节点后，出现
c为红色、其父节点p为红色、祖父节点g为黑色，且叔叔节点u不存在或者u存在但为黑色的情况，具体分析与处理如下：节点情况分析
u不存在：此时c必定是新增节点。u存在且为黑：c并非新增节点，此前c为黑色。是在c的子树中插入节点后，经过类似情况 1（叔叔节点为红色时的变色处理）的操作，c从黑色变为红色并更新上来。处理必要性分析
为解决
p和c连续红色节点违反红黑树规则的问题，p必须变为黑色。由于u不存在或者为黑色，单纯的变色操作无法恢复红黑树性质，需要结合旋转与变色操作。情况一：
p是g的左子节点，c是p的右子节点
- 操作步骤：
- 以
p为旋转点进行左单旋。- 接着以
g为旋转点进行右单旋。- 将
c变为黑色，g变为红色。- 操作效果：操作完成后，
c成为该子树新的根节点。这样既保证了子树中各路径上黑色节点数量不变，又消除了连续的红色节点。而且，无论c的父节点状态（黑色、红色或为空）如何，都不会违反红黑树规则，无需再向上更新。g g c / \ / \ / \ p u --> c u --> p g \ / / \ c p p u情况二：
p是g的右子节点，c是p的左子节点
- 操作步骤：
- 以
p为旋转点进行右单旋。- 再以
g为旋转点进行左单旋。- 将
c变为黑色，g变为红色。- 操作效果：操作结束后，
c成为子树新的根节点。同样保证了子树黑色节点数量不变，避免了连续红色节点的出现。并且，不管c的父节点状态怎样，都不违反红黑树规则，无需继续向上处理。g g c / \ / \ / \ u p --> u c --> g p / \ / \ c p u p
红黑树的插入代码实现
//红黑树
template<class K, class T>
class Red_BlackTree
{
typedef Red_BlackTree_Node<T> Node;
public:
//插入
//插入
bool insert(const T& kv) {
//判空:如果是空根节点就是黑色
if (_root == nullptr)
{
_root = new Node(kv);
_root->_cr = _black;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
//不为空就插入红色
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
{
return false;
}
}
cur = new Node(kv);
cur->_cr = _red;
//链接节点
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else if (parent->_kv.first < kv.first) {
parent->_right = cur;
}
//判断三插链当中的_parent指向
cur->_parent = parent;
//parent是红色插入说明出现连续的红(违反规则)
while (parent && parent->_cr == _red)
{
Node* grandfather = parent->_parent;
//parent 如果是left
if (parent == grandfather->_left)
{
// g
// p u
//uncle存在且为红
Node* uncle = grandfather->_right;
if (uncle && uncle->_cr == _red) {
uncle->_cr = _black;
parent->_cr = _black;
grandfather->_cr = _red;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在或为黑
else
{
if (parent->_left == cur) {
Rotati_r(grandfather);
parent->_cr = _black;
grandfather->_cr = _red;
}
else
{
Rotati_LR(grandfather);
cur->_cr = _black;
grandfather->_cr = _red;
}
break;
}
}
else
{
// g
// u p
Node* uncle = grandfather->_left;
//uncle存在且为红
if (uncle && uncle->_cr == _red) {
uncle->_cr = _black;
parent->_cr = _black;
grandfather->_cr = _red;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在或为黑
else
{
if (parent->_right == cur) {
Rotati_l(grandfather);
parent->_cr = _black;
grandfather->_cr = _red;
}
else
{
Rotati_RL(grandfather);
cur->_cr = _black;
grandfather->_cr = _red;
}
break;
}
}
}
//更新到最后不管_root是不是红都设置为黑
_root->_cr = _black;
return true;
}
//右旋转
void Rotati_r(Node* parent) {
Node* subL = parent->_left;
Node* sublr = subL->_right;
//旋转
parent->_left = sublr;
//判断是否是空,为空不能链接避免野指针
if (sublr)
sublr->_parent = parent;
//存储parent节点方便后续链接
Node* Pparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
//判断是否是root或则是局部旋转方便链接上下节点
if (parent == _root) {
_root = subL;
subL->_parent = nullptr;
}
else {
if (Pparent->_left == parent) {
Pparent->_left = subL;
}
else if (Pparent->_right == parent)
{
Pparent->_right = subL;
}
subL->_parent = Pparent;
}
}
//左旋转
void Rotati_l(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
//左右旋
void Rotati_LR(Node* parent) {
Rotati_l(parent->_left);
Rotati_r(parent);
}
//右左旋
void Rotati_RL(Node* parent) {
Rotati_r(parent->_right);
Rotati_l(parent);
}
private:
Node* _root = nullptr;
};红黑树的查找
直接看代码吧，这个已经非常简单了，按⼆叉搜索树逻辑实现即可，搜索效率为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;
}红黑树的验证
在红黑树中，判断其是否符合要求时，直接获取最长路径和最短路径并检查最长路径是否不超过最短路径的 2 倍这种方式不可行。因为即便满足该条件，红黑树仍可能在颜色方面不满足规则，虽然当前可能看似正常，但后续继续插入节点时仍会出现问题。所以，应该检查红黑树的四条基本规则，只要满足这四条规则，就能确保最长路径不超过最短路径的 2 倍。以下是对四条规则检查方法的具体说明：
规则 1：节点颜色类型检查
此x。由于在代码实现中通常会枚举颜色类型，因此在定义节点颜色时就天然保证了该规则的实现，无需额外的检查操作。
规则 2：根节点颜色检查
规则规定根节点必须是黑色。检查时，直接查看红黑树的根节点颜色是否为黑色即可。
规则 3：红色节点子节点颜色检查
规则要求每个红色节点的两个子节点都是黑色。采用前序遍历的方式进行检查，若正向检查红色节点的孩子节点会不太方便，因为孩子节点有两个且不一定都存在。所以，反过来检查每个节点（除根节点外）的父节点颜色更为便捷。若当前节点为红色，而其父节点也为红色，则违反了该规则。
规则 4：各路径黑色节点数量检查
规则要求从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。同样使用前序遍历，在遍历过程中，利用形参记录从根节点到当前节点的黑色节点数量
blackNum。当前序遍历遇到黑色节点时，blackNum加 1。当遍历到空节点时，就得到了一条路径上的黑色节点数量。选取任意一条路径的黑色节点数量作为参考值，依次与其他路径的黑色节点数量进行比较，若存在不同，则违反该规则。
// 递归检查红黑树是否满足规则 3（不存在连续红色节点）和规则 4（每条路径上黑色节点数量相同） // root: 当前递归检查的子树的根节点 // blackNum: 从根节点到当前节点路径上的黑色节点数量 // refNum: 作为参考的一条路径上的黑色节点数量 bool Check(Node* root, int blackNum, const int refNum) { // 当前节点为空，说明已经遍历完一条路径 if (root == nullptr) { // 前序遍历⾛到空时，意味着⼀条路径⾛完了 // 比较当前路径的黑色节点数量和参考值 if (refNum != blackNum) { // 若不相等，输出提示信息，说明存在黑色节点数量不相等的路径 cout << "存在⿊⾊结点的数量不相等的路径" << endl; return false; } // 若相等，说明当前路径满足规则 4 return true; } // 检查规则 3，即是否存在连续的红色节点 // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了 // 若当前节点为红色且其父节点也为红色，违反规则 3 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; // 规则 2：根节点必须为黑色，若根节点为红色，不满足红黑树规则 if (_root->_col == RED) return false; // 计算参考值，即从根节点到其最左子节点路径上的黑色节点数量 // 参考值 int refNum = 0; Node* cur = _root; // 沿着左子树向下遍历 while (cur) { // 若当前节点为黑色，参考值加 1 if (cur->_col == BLACK) { ++refNum; } cur = cur->_left; } // 调用 Check 函数开始递归检查整棵树 return Check(_root, 0, refNum); }递归展开图：
