第23课-C++-红黑树的插入与旋转
🌇前言
红黑树是一种自平衡的二叉搜索树，因其出色的性能，广泛应用于实际中。Linux 内核中的 CFS 调度器便是一个使用红黑树的例子，这足以说明它的重要性。红黑树的实现通过红黑两种颜色的控制来维持平衡，并在必要时使用旋转操作来降低树的高度，使之保持平衡。
🏙️正文
1. 认识红黑树
红黑树最初由德国慕尼黑大学的 Rudolf Bayer 教授于1978年发明，后来由 Leo J. Guibas 和 Robert Sedgewick 修改为我们今天所熟悉的红黑树。红黑树在二叉搜索树的基础上，增加了颜色属性，通过一些规则降低树的高度。
与 AVL 树的严格平衡策略不同，红黑树仅在需要时进行旋转，从而减少了旋转操作的开销。虽然 AVL 树在极端情况下可能比红黑树快一倍，但红黑树在插入、删除、修改操作中性能更优。
1.1、红黑树的定义
红黑树 也是 三叉链 结构，不过它没有 平衡因子，取而代之的是 颜色。
红黑树节点的定义
// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _color(color)
{}
RBTreeNode<ValueType>* _pLeft; // 节点的左孩子
RBTreeNode<ValueType>* _pRight; // 节点的右孩子
RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给
出该字段)
ValueType _data; // 节点的值域
Color _color; // 节点的颜色
}注意： 定义新节点时，颜色可以为 红 也可以为 黑，推荐为 红色，具体原因后面解释。
1.2 红黑树的性质
红黑树有以下五条性质：
- 每个节点不是红色就是黑色。
- 根节点是黑色的。
- 如果一个节点是红色，那么它的两个子节点必须是黑色（不能有连续的红节点）。
- 从任一节点到其所有后代的叶子节点的路径中，都包含相同数量的黑色节点。
- 每个叶子节点都是黑色的空节点。
1.3 红黑树的特点
红黑树在插入节点时，默认将新节点颜色设为红色。这种设计简化了调整，因为红色新节点仅在特定条件下会触发旋转调整。
红黑树的路径特点如下：
- 最长路径：红黑相间
- 最短路径：全是黑节点
红黑树在极端情况下最长路径为最短路径的两倍，但这种情况很少见。因此在实际应用中，红黑树的查询性能与 AVL 树差异不大，而在涉及旋转的操作中，红黑树优势明显。
2. 红黑树的插入操作
2.1、抽象图
在演示 红黑树 的插入操作时，也需要借助 抽象图，此时的 抽象图 不再代表高度，而是代表 黑色节点 的数量。
2.2、插入流程
红黑树 的插入流程也和 二叉搜索树 基本一致，先找到合适的位置，然后插入新节点，当节点插入后，需要对颜色进行判断，看看是否需要进行调整
插入流程： 判断根是否为空，如果为空，则进行第一次插入，成功后返回 true 找到合适的位置进行插入，如果待插入的值比当前节点值大，则往 右 路走，如果比当前节点值小，则往 左 路走 判断父节点与新节点的大小关系，根据情况判断链接至 左边 还是 右边 根据颜色，判断是否需要进行 染色、旋转 调整高度 整体流程如下（不包括染色调整的具体实现）
bool Insert(const std::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->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
//判断是否需要 染色、旋转
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent; //祖父节点
//……
}
return true;
}
红黑树 如何调整取决于 叔叔，即父亲的兄弟节点 。并且如果父亲为黑，直接插入就行了，不必调整 如果父亲为红并且叔叔也为红，可以只通过染色解决当前问题，然后向上走，继续判断是否需要调整，如果父亲为红并且叔叔为黑或者叔叔不存在，此时需要 旋转 + 染色，根据当前节点与父亲的位置关系，选择 单旋 或 双旋，值得一提的是旋转 + 染色 后，不必再向上判断，可以直接结束调整 关于旋转的具体实现，这里不再展开叙述，可以复用 AVL 中的旋转代码，并且最后不需要调整平衡因子 《C++【AVL树】》 注意：红黑树的调整可以分为 右半区 和 左半区 两个方向（根据 grandfather 与 parent 的位置关系而定），每个方向中都包含三种情况：单纯染色、单旋+染色、双旋+染色，逐一讲解费时费力，并且两个大方向的代码重复度极高，因此 下面的旋转操作基于 右半区 左半区 的操作和 右半区 基本没啥区别，可以去完整代码中求证。
2.3、单纯染色
如果父亲为黑色，则不需要调整，不讨论这种情况，下面三种情况基本要求都是：父亲为红
当新节点插入后，如果 叔叔 节点也为 红色，那么可以通过将 祖父 节点的黑色素下放给 父亲和叔叔，祖父节点 变为 红色，这样调整仍可确保 每条路径中的黑色节点数目相同
单次染色还不够，需要从 grandfather 处继续向上判断是否需要 调整，单纯染色后，向上判断可能会变成其他情况，这是不确定的，具体情况具体分析
单纯染色 的操作如下：
注意：c 表示当前节点，p 表示父亲节点，u 表示叔叔节点，g 表示祖父节点
修正： 动图中语句修正为 “父亲为红，叔叔也为红，直接染色即可” 当 单次染色 结束后，更新 cur 至 grandfather 的位置，并同步更新 parent，继续判断是需要进行 单纯染色、单旋 + 染色 还是 双旋 + 染色 本质：将公共的黑色下放给两个孩子。
代码：
//在右半区操作
Node* uncle = grandfather->_left; //叔叔节点
if (uncle && uncle->_col == RED)
{
//染色、向上更新即可
grandfather->_col = RED;
parent->_col = uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else
{
//此时需要 旋转 + 染色
//……
}
叔叔 存在且为 红 很好处理，难搞的是 叔叔 不存在或 叔叔 为 黑，需要借助 旋转 降低高度
注意： 此时的五个抽象图，都代表同一个具象图；如果 parent 为空，证明 cur 为根节点，此时需要把根节点置为 黑色，在返回 true 前统一设置即可。
2.4、左单旋 + 染色
单旋：右右、左左，此时在 右半区，所以当 叔叔 不存在或者为 黑色 且节点位于 父亲 的 右边 时，可以通过 左单旋 降低高度
如果在左半区，节点位于父亲的左边时，则使用 右单旋 降低高度
在高度降低后，需要使用 染色 确保符合 红黑树 的性质
旋转 思想很巧妙，在 旋转 + 染色 后，可以跳出循环，结束调整
左旋转 + 染色 的操作如下：
注意：c 表示当前节点，p 表示父亲节点，u 表示叔叔节点，g 表示祖父节点
显然，旋转 + 染色 后，parent 是一定会被修改为 黑色 的，所以不必再往上判断调整，因为现在已经很符合性质了（即使 parent 的父亲是 红色，也不会出现连续的 红色节点）
本质：将 parent 的左孩子托付给 grandfather 后，parent 往上提，并保证不违背性质。
//在右半区操作
Node* uncle = grandfather->_left; //叔叔节点
if (uncle && uncle->_col == RED)
{
//染色、向上更新即可
//……
}
else
{
//此时需要 旋转 + 染色
if (parent->_right == cur)
{
//右右，左单旋 ---> parent 被提上去了
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
cur->_col = RED;
}
else
{
//右左，右左双旋 ---> cur 被提上去了
//……
}
//旋转后，保持平衡，可以结束调整
break;
}
注意： 这种情况多半是由 单纯染色 转变而来的，所以不同区域的抽象图有不同的情况，必须确保能符合红黑树的性质。
2.5、右左双旋 + 染色
双旋：右左、左右，此时在 右半区，所以当 叔叔 不存在或者为 黑色 且节点位于 父亲 的 左边 时，可以通过 右左双旋 降低高度
如果在左半区，节点位于父亲的右边时，则使用 左右双旋 降低高度
在高度降低后，需要使用 染色 确保符合 红黑树 的性质
旋转 思想很巧妙，在 旋转 + 染色 后，可以跳出循环，结束调整
右左双旋 + 染色 的操作如下：
注意：c 表示当前节点，p 表示父亲节点，u 表示叔叔节点，g 表示祖父节点
双旋 其实就是两个不同的 单旋，不过对象不同而已，先 右旋转 parent，再 左旋转 grandfather 就是 右左双旋
本质：将 cur 的右孩子托付给 parent，左孩子托付给 grandfather 后，把 cur 往上提即可，并保证不违背 红黑树 的性质
红黑树的检验主要是为了确保在插入或删除节点后，红黑树的性质依旧得到了满足。我们可以通过以下几个方面来验证红黑树的合法性：
4.红黑树的性质回顾
为了检验红黑树的合法性，需要检查以下五条性质是否都被满足：
- 每个节点不是红色就是黑色。
- 根节点是黑色。
- 如果一个节点是红色，那么它的两个子节点必须是黑色（即不能有连续的红色节点）。
- 从任一节点到其所有后代叶子节点的路径上，必须包含相同数量的黑色节点。
- 每个叶子节点的
nullptr视为黑色。
检验步骤
我们可以通过编写检查函数，递归地验证红黑树的合法性。
1. 验证根节点是否为黑色
红黑树的根节点必须是黑色的。如果根节点不是黑色，就说明红黑树不合法。这是一个简单的检查。
if (_root->_col != BLACK)
{
std::cerr << "根节点不是黑色，违反红黑树性质二" << std::endl;
return false;
}
2. 检查是否出现连续的红色节点
如果一个节点是红色，那么它的子节点必须是黑色。因此，当遍历树时，可以检查每个红色节点的子节点是否都是黑色。如果出现连续的红色节点，则树不合法。
bool CheckRedNodeRule(Node* node)
{
if (node == nullptr)
return true;
if (node->_col == RED)
{
// 如果当前节点是红色，检查左右子节点
if ((node->_left && node->_left->_col == RED) ||
(node->_right && node->_right->_col == RED))
{
std::cerr << "出现连续的红色节点，违反红黑树性质三" << std::endl;
return false;
}
}
// 递归检查左右子树
return CheckRedNodeRule(node->_left) && CheckRedNodeRule(node->_right);
}
3. 验证从根节点到每个叶子节点路径的黑色节点数量是否一致
每一条路径从根节点到叶子节点所包含的黑色节点数量必须一致。这个数量可以称为基准黑色节点数。
首先，从根节点到最左边叶子节点的路径中统计黑色节点数量作为基准值。然后，递归检查其他路径是否符合这个基准值。
// 计算左侧路径上的黑色节点数量作为基准
int GetBlackHeight(Node* node)
{
int blackCount = 0;
while (node != nullptr)
{
if (node->_col == BLACK)
blackCount++;
node = node->_left;
}
return blackCount;
}
// 检查每条路径的黑色节点数是否一致
bool CheckBlackHeight(Node* node, int blackCount, int benchMark)
{
if (node == nullptr)
{
// 到达叶子节点，检查是否等于基准值
return blackCount == benchMark;
}
if (node->_col == BLACK)
blackCount++;
return CheckBlackHeight(node->_left, blackCount, benchMark) &&
CheckBlackHeight(node->_right, blackCount, benchMark);
}
4. 汇总检验
结合以上的检查点，我们可以编写一个 IsRBTree() 函数，逐步验证红黑树的合法性
// 计算左侧路径上的黑色节点数量作为基准
int GetBlackHeight(Node* node)
{
int blackCount = 0;
while (node != nullptr)
{
if (node->_col == BLACK)
blackCount++;
node = node->_left;
}
return blackCount;
}
// 检查每条路径的黑色节点数是否一致
bool CheckBlackHeight(Node* node, int blackCount, int benchMark)
{
if (node == nullptr)
{
// 到达叶子节点，检查是否等于基准值
return blackCount == benchMark;
}
if (node->_col == BLACK)
blackCount++;
return CheckBlackHeight(node->_left, blackCount, benchMark) &&
CheckBlackHeight(node->_right, blackCount, benchMark);
}
5.调试和验证
当代码中的某些操作可能会破坏红黑树的性质时，可以调用 IsRBTree() 来验证整个树的合法性，输出不满足性质的详细信息。这些检查帮助确保红黑树操作在每次插入、删除或其他变动后仍符合红黑树的要求。
5. AVL和红黑树的性能比较
AVL树和红黑树是两种经典的自平衡二叉搜索树，它们在不同应用场景中有各自的优势和劣势。下面从几个方面对它们的性能进行对比，包括平衡机制、插入/删除性能、查询性能和实际应用场景。
1. 平衡机制对比
- AVL树：AVL树严格保持高度平衡，每个节点的左右子树高度差（称为平衡因子）最多为1。为了维持这种严格的平衡，AVL树在插入或删除节点时，几乎每次都需要进行旋转操作以确保平衡。
- 红黑树：红黑树通过颜色标记（红和黑）以及特定的旋转规则来维持大致的平衡，它的平衡策略相对宽松。红黑树允许路径长度差达到2倍，因此在插入和删除时，它会尽可能避免旋转，除非触发特定条件。
2. 插入性能对比
- AVL树：由于AVL树保持严格的平衡性，它在插入时往往需要频繁旋转以重新平衡树。插入操作的平均和最差时间复杂度都是 O(logN)O(\log N)O(logN)，但旋转操作的频率较高，尤其在接近完全平衡的情况下，这会导致插入操作时间增加。
- 红黑树：红黑树在插入时通常只需要少量旋转，且更多情况下可以通过染色来维持平衡，而不进行旋转。插入操作的时间复杂度也是 O(logN)O(\log N)O(logN)，但由于旋转较少，因此在插入密集的应用场景中，红黑树往往表现得更好。
3. 删除性能对比
- AVL树：AVL树删除节点后会执行严格的平衡操作，频繁旋转调整确保树高度平衡，因此在删除操作时会消耗更多时间。
- 红黑树：红黑树的删除操作复杂度相对较低，因为其平衡策略宽松。删除时，红黑树往往可以通过染色操作或少量旋转恢复平衡，不会像AVL树那样频繁旋转。因此在删除操作密集的场景中，红黑树性能通常优于AVL树。
4. 查询性能对比
在查询性能上，二者的时间复杂度都是 O(logN)O(\log N)O(logN)，但由于它们的平衡策略不同，有以下几点差异：
- AVL树：因为严格平衡，AVL树的高度始终接近 logN\log NlogN，这使得查找路径较短。理论上，AVL树的查找性能略优于红黑树，特别是在数据分布接近最差情况时，AVL树会比红黑树更快。
- 红黑树：红黑树允许路径长度差达到2倍，意味着它的高度可能比AVL树稍大一些。因此在某些场景下，AVL树的查询可能略微快于红黑树。然而，在实际应用中，这种差距通常微乎其微。
5. 内存占用对比
- AVL树：AVL树每个节点除了存储左右子节点，还要存储平衡因子。因此内存消耗会稍微多一点。
- 红黑树：红黑树每个节点只需一个颜色标记（红或黑），因此在内存开销上相对较小。
6. 实际应用场景对比
- AVL树适用场景：AVL树适合频繁查找、不频繁更新（插入/删除）的场景。例如，适合用于静态数据库或对性能要求较高的读取密集型场景。
- 红黑树适用场景：红黑树适合需要频繁插入和删除操作的场景，特别是在数据动态变化的情况下。红黑树的宽松平衡机制在插入、删除密集的情况下能够减少旋转，从而提升性能。这使得红黑树广泛应用于系统中的许多集合操作，例如C++ STL的
map、set以及Linux内核中的调度器等。
7. 性能测试示例
假设插入和删除大量数据的性能测试，结果通常会显示：
- 插入/删除：红黑树的插入和删除操作时间较短，尤其在大量数据的随机插入/删除测试中，红黑树的性能比AVL树好。
- 查询：查询操作性能上，两者差距不大，AVL树可能在极端情况下稍快，但在实际应用中效果差别不大。
总结
| 属性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡机制 | 严格平衡，更多旋转 | 宽松平衡，染色+少量旋转 |
| 插入性能 | 较多旋转，插入稍慢 | 较少旋转，插入较快 |
| 删除性能 | 较多旋转，删除稍慢 | 较少旋转，删除较快 |
| 查询性能 | 高度接近完全平衡，稍快 | 高度略大于AVL，性能接近 |
| 内存开销 | 较高（存储平衡因子） | 较低（存储颜色标记） |
| 适用场景 | 查找频繁、更新较少的场景 | 插入/删除频繁的动态场景 |
总体而言，红黑树在插入和删除密集的动态应用场景中表现更好，而AVL树在静态或查找频繁的场景中性能稍优。
完整代码：
#pragma once
#include<iostream>
#include<map>
#include<assert.h>
#include<vector>
using namespace std;
enum Color
{
RED,
BREAK
};
template<class K, class V>
struct RBTreeNode
{
struct RBTreeNode<K, V>* _left;
struct RBTreeNode<K, V>* _right;
struct RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _color;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_color(RED)
{}
};
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);
_root->_color = BREAK;
return true;
}
else
{
Node* cur = _root;
Node* parent = _root;
while (cur)//比较Frist
{
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);
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_right)//父亲为右
{
Node* Uncle = grandfather->_left;
if (Uncle && Uncle->_color == RED)
{
parent->_color = Uncle->_color = BREAK;
grandfather->_color = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
grandfather->_color = RED;
parent->_color = BREAK;
}
else//交叉
{
RotateRL(grandfather);
grandfather->_color = RED;
cur->_color = BREAK;
}
}
}
else//父亲在左；
{
Node* Uncle = grandfather->_right;
if (Uncle && Uncle ->_color== RED)
{
parent->_color = Uncle->_color = BREAK;
grandfather->_color = RED;
cur = grandfather;
parent = cur->_parent;
}
else//叔叔不存在，或者等于黑色，我直线或者弯曲
{
if (cur == cur->_left)
{
RotateR(grandfather);
parent->_color = BREAK;
grandfather->_color = RED;
}
else
{
RotateLR(grandfather);
cur->_color = BREAK;
grandfather->_color = RED;
}
}
}
_root->_color = BREAK;
}
return true;
}
}
void RotateL(Node * parent)//穿的是问题节点，
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
cur->_left = parent;
if (curleft)
{
curleft->_parent = parent;
}
Node* pphead = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (pphead->_left == parent)
{
pphead->_left = cur;
}
else if (pphead->_right == parent)
{
pphead->_right = cur;
}
cur->_parent = pphead;
}
}
void RotateR(Node * parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
cur->_right = parent;
parent->_left = curright;
if (curright)
{
curright->_parent = parent;
}
Node* phead = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (phead->_left == parent)
{
phead->_left = cur;
}
else
{
phead->_right = cur;
}
cur->_parent = phead;
}
}
void RotateRL(Node * parent)//传谁谁父亲下去
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
RotateR(parent->_right);
RotateL(parent);
}
void RotateLR(Node * parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
RotateL(cur);
RotateR(parent);
}
bool IsBalanceTree()
{
return IsBalanceTree(_root);
}
bool IsBalanceTree(Node* root)
{
if (root == nullptr)
{
return true;
}
if (root->_color != BREAK)
{
return false;
}
int benchmark = 0;
Node* cur = root;
while (cur)
{
if (cur->_color == BREAK)
{
benchmark++;
}
cur = cur->_left;
}
return CheckColour(root, 0, benchmark);
}
bool CheckColour(Node* root, int blacknum, int benchmark)
{
if (root == nullptr)
{
if (blacknum != benchmark)
{
return false;
}
return true;
}
if (root->_color == BREAK)
{
blacknum++;
}
if (root->_color == RED && root->_parent && root->_parent->_color == RED)
{
cout << root->_kv.first << "出现连续红节点" << endl;
}
return CheckColour(root->_left, blacknum, benchmark);
}
private:
Node* _root = nullptr;
};