【C++】从零到一掌握红黑树：数据结构中的平衡之道
个人主页: 起名字真南的CSDN博客
个人专栏:
- 【数据结构初阶】 📘 基础数据结构
- 【C语言】 💻 C语言编程技巧
- 【C++】 🚀 进阶C++
- 【OJ题解】 📝 题解精讲
目录
- 前言
- 1 红黑树的概念
- **红黑树的五大性质**
- 2 红黑树的实现
- 2.1 红黑树的结构
- 2.2 红黑树的插入
- 2.2.1 红黑树插入的大概过程
- 2.2.2 关于红黑树插入新节点的变色问题
- 2.2.3 单旋加变色
- 2.2.4 双旋加变色
- 2.2.5 具体代码实现
- 2.2.6 红黑树插入后变色旋转总结
- 红黑树插入时需要处理的问题
- 插入调整的基本步骤
- 插入调整的条件、操作和原因
- 情况 1：叔叔节点是红色
- 情况 2：叔叔节点是黑色（或不存在）
- 子情况 2.1：当前节点是父节点的左子节点（左左情况）
- 子情况 2.2：当前节点是父节点的右子节点（左右情况）
- 子情况 2.3：当前节点是父节点的右子节点（右右情况）
- 子情况 2.4：当前节点是父节点的左子节点（右左情况）
- 插入调整总结
- 图解：插入调整过程
- 2.3 红黑树的查找
- 2.4 判断是否平衡
前言
红黑树被广泛应用于许多领域，例如 C++ STL 中的 map 和 set，Java 的 TreeMap 和 TreeSet，以及 Linux 内核、数据库索引等。相比其他平衡树，红黑树调整代价更低，尤其适合插入和删除操作频繁的场景。
1 红黑树的概念
红黑树（Red-Black Tree）是一种自平衡二叉搜索树，通过对节点的颜色、结构及调整规则的约束，实现了树的动态平衡。它的主要目的是在插入、删除等操作后，保持树的高度尽可能小，从而保证在最坏情况下的时间复杂度为 ( O(\log N) )。
红黑树的五大性质
- 节点颜色：每个节点要么是红色，要么是黑色。
- 根节点黑色：根节点必须是黑色。
- 红色节点限制：红色节点的子节点必须是黑色（红色节点不能连续相邻，红黑交替）。
- 黑高相等：从任意节点到其每个叶子节点的路径中，包含相同数量的黑色节点。
- 叶子节点为黑色：所有的叶子节点（空节点）都被视为黑色。
2 红黑树的实现
我们想要实现红黑树就要像清楚红黑树的构成时候枚举类型Colour，以及节点，和树一起构成的
2.1 红黑树的结构
- 需要包含关键字段、包括键值对(Key，Value)、左右节点指针，父亲节点指针，以及枚举类型Colour用来记录节点的颜色
- 示例代码
#include<iostream>
using namespace std;
enum Colour
{
RED,
Black
};
template<class K,class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _colour;
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
};
-
树 的定义
- 包含节点。还有根节点
-
示例代码
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//实现树的各种操作
private:
Node* _root = nullptr;
};
在这串代码中并没有构造函数，是因为树是由节点和指针构成的，在构造时会调用节点的构造函数，根节点 也给了初始值。
2.2 红黑树的插入
2.2.1 红黑树插入的大概过程
- 在插入之前我们首先要了解以下红黑树的规则，也就是要遵循上面提到的五个性质
- 因为我们使用的枚举类型，只有两个变量即红色或黑色所以满足第一条
- 第二条根节点的颜色必须是黑色，所以我们在插入的过程中首先要进行判断插入的树是否为空树如果为空树则新增节点为黑色
- 不能出现两个连续的节点都是红色节点，如果一个节点是红色节点那么它的孩子必须是黑色，
- 黑高相等即每一条路径上面的黑色节点数量必须是一致的，所以我们新插入的节点必须是红色节点如果新插入的节点的父亲节点也是红色这里就涉及到我们接下来要讲的变色问题，
2.2.2 关于红黑树插入新节点的变色问题
首先我们要先确定好变色的前置条件就是新增节点是红色节点，并且它的父亲节点也是红色节点违反了红黑树的特性所以我们需要变色。
在接下来的图中用c来表示当前节点，p表示当前节点的父节点，u表示父亲节点的兄弟节点，g表示父亲节点的父亲节点
变色原因，因为c和p是两个连续的红色节点违反了红黑树的结构所以需要将p和u变成黑色，但是如果变成黑色以后会增加这两条路径上的黑色节点数量所以为了和以前保持一致需要将他们的父亲节点g节点变成红色，如果g节点的父亲节点也是红色则需要继续向上调整，由于情况有很多种所以我们将下面的结构抽象化处理。
在这里我们需要注意u和p一样在变化之前都是红色节点，如果u为黑色节点则c不是新增节点
2.2.3 单旋加变色
前置条件：出现了两个连续的红色节点并且u节点为黑色或者不存在，这个情况c可能不是新增节点，而是因为上述情况经过向上调整c为他们的g节点由开始的黑色变成了红色，此时如果新增的节点在左侧并且g节点也就是现在的c节点变成了红色此时u为黑色或者不存在，c在u的左侧这个时候需要进行右单旋，相反则需要进行左单旋，旋转以后需要将父亲节点变成黑色，祖父节点变成红色
2.2.4 双旋加变色
前置条件：在向上调整的时候出现了连续的红色节点并且叔叔节点为黑色或者不存在（因为如果不存在我们按照红黑树的特性也可以认为他有一个黑色的空结点）并且如果p在g的左侧，c在p的右侧这个时候我们需要先进行以p节点为旋转节点进行左旋在以g节点作为旋转节点进行右旋。
变色都是将g节点变成红色并且p节点和u节点变成黑色。
2.2.5 具体代码实现
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_colour = 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->_colour = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//父亲是红色，出现了连续的红色节点
while (parent && parent->_colour == RED)
{
Node* grandfarther = parent->_parent;
//找叔叔节点
if (grandfarther->_left == parent)
{
//叔叔在右边
Node* uncle = grandfarther->_right;
if (uncle && uncle->_colour == RED)
{
//变色是为了结点的数量不变，并且不能出现连续的红色结点
parent->_colour = Black;
uncle->_colour = Black;
grandfarther->_colour = RED;
//继续往上处理
cur = grandfarther;
parent = cur->_parent;
//如果cur是根节点，则父亲为空，while循环条件造成了空引用
//在循环条件中加上不能为空
}
else
{
if (cur == parent->_left)
{
//叔叔节点为黑色或者不存在
//右单旋
//对grandfather位置进行旋转
// g p
// p u -> c g
// c u
RotateR(grandfarther);
parent->_colour = Black;
grandfarther->_colour = RED;
}
else
{
// g c
// p u -> p g
// c u
//需要双旋
RotateL(parent);
RotateR(grandfarther);
cur->_colour = Black;
grandfarther->_colour = RED;
}
break;
}
}
else
{
//叔叔在左边
Node* uncle = grandfarther->_left;
if (uncle && uncle->_colour == RED)
{
//变色是为了结点的数量不变，并且不能出现连续的红色结点
parent->_colour = Black;
uncle->_colour = Black;
grandfarther->_colour = RED;
//继续往上处理
cur = grandfarther;
parent = cur->_parent;
//如果cur是根节点，则父亲为空，while循环条件造成了空引用
//在循环条件中加上不能为空
}
else
{
if (cur == parent->_right)
{
//左单旋
//对grandfather位置进行旋转
// g u
// u p -> c g
// c p
RotateL(grandfarther);
parent->_colour = Black;
grandfarther->_colour = RED;
}
else
{
// g c
// u p -> u g
// c p
//需要双旋
RotateR(parent);
RotateL(grandfarther);
cur->_colour = Black;
grandfarther->_colour = RED;
}
break;
}
}
}
//必须保证跟节点是黑色
_root->_colour = Black;
return true;
}
void RotateR(Node* parent)
{
// p subL
// subL -> c p
// c subLR a subLR
//a
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* pParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == pParent->_left)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
subL->_parent = pParent;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* pParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == pParent->_left)
{
pParent->_left = subR;
}
else
{
pParent->_right = subR;
}
subR->_parent = pParent;
}
}
具体的旋转细节请参考：
【C++】从「树」到「平衡」：全面解密 AVL 树的奥秘与实现
其中详细的介绍了单旋和双旋大家可以作为参考
2.2.6 红黑树插入后变色旋转总结
在红黑树的插入过程中，为了保持红黑树的性质，需要结合旋转和变色操作进行调整。以下是插入过程中各种旋转和变色的前置条件及其原因的详细梳理。
红黑树插入时需要处理的问题
插入新节点可能破坏以下红黑树性质：
- 性质 2：根节点必须是黑色。
- 性质 4：不能有两个连续的红色节点。
- 性质 5：每条从根到叶子节点的路径必须包含相同数量的黑色节点。
因此，调整过程主要是为了修复连续红色节点问题和黑高失衡问题。
插入调整的基本步骤
- 新插入的节点默认为红色（不会破坏黑高平衡）。
- 根据父节点和叔叔节点的颜色，可能需要变色和/或旋转调整。
插入调整的条件、操作和原因
情况 1：叔叔节点是红色
-
前置条件：
- 当前节点的父节点是红色。
- 当前节点的叔叔节点也是红色。
-
操作：
- 父节点和叔叔节点变为黑色。
- 祖父节点变为红色。
- 将当前节点移动到祖父节点，继续检查祖父节点。
-
原因：
- 变色的目的是修复性质 3（连续红色节点）。
- 因为祖父节点变红，可能导致祖父节点和它的父节点连续红色，所以需要继续向上调整。
情况 2：叔叔节点是黑色（或不存在）
子情况 2.1：当前节点是父节点的左子节点（左左情况）
-
前置条件：
- 当前节点的父节点是红色。
- 当前节点的叔叔节点是黑色或不存在。
- 当前节点是父节点的左子节点。
-
操作：
- 对祖父节点进行右旋。
- 父节点变为黑色，祖父节点变为红色。
-
原因：
- 右旋是为了修复树的平衡，避免左重失衡。
- 变色是为了满足性质 3 和性质 4。
子情况 2.2：当前节点是父节点的右子节点（左右情况）
-
前置条件：
- 当前节点的父节点是红色。
- 当前节点的叔叔节点是黑色或不存在。
- 当前节点是父节点的右子节点。
-
操作：
- 对父节点进行左旋，将问题转化为左左情况。
- 转换后再对祖父节点进行右旋。
- 父节点变为黑色，祖父节点变为红色。
-
原因：
- 左旋是为了将右偏问题化简为左偏问题。
- 后续的右旋和变色则恢复了树的平衡性和红黑树性质。
子情况 2.3：当前节点是父节点的右子节点（右右情况）
-
前置条件：
- 当前节点的父节点是红色。
- 当前节点的叔叔节点是黑色或不存在。
- 当前节点是父节点的右子节点。
-
操作：
- 对祖父节点进行左旋。
- 父节点变为黑色，祖父节点变为红色。
-
原因：
- 左旋是为了修复树的平衡，避免右重失衡。
- 变色是为了满足性质 3 和性质 4。
子情况 2.4：当前节点是父节点的左子节点（右左情况）
-
前置条件：
- 当前节点的父节点是红色。
- 当前节点的叔叔节点是黑色或不存在。
- 当前节点是父节点的左子节点。
-
操作：
- 对父节点进行右旋，将问题转化为右右情况。
- 转换后再对祖父节点进行左旋。
- 父节点变为黑色，祖父节点变为红色。
-
原因：
- 右旋是为了将左偏问题化简为右偏问题。
- 后续的左旋和变色则恢复了树的平衡性和红黑树性质。
插入调整总结
| 条件 | 操作 | 原因 |
|---|---|---|
| 叔叔节点是红色 | 变色 | 修复连续红色问题，可能需要向上递归调整 |
| 叔叔节点是黑色，左左情况 | 右旋 + 变色 | 修复左重失衡和连续红色问题 |
| 叔叔节点是黑色，左右情况 | 左旋 + 右旋 + 变色 | 转化为左左情况后再修复 |
| 叔叔节点是黑色，右右情况 | 左旋 + 变色 | 修复右重失衡和连续红色问题 |
| 叔叔节点是黑色，右左情况 | 右旋 + 左旋 + 变色 | 转化为右右情况后再修复 |
图解：插入调整过程
左左情况
插入前：
50(B)
/
30(R)
/
20(R)
右旋 + 变色后：
30(B)
/ \
20(R) 50(R)
右右情况
插入前：
20(B)
\
30(R)
\
50(R)
左旋 + 变色后：
30(B)
/ \
20(R) 50(R)
左右情况
插入前：
50(B)
/
20(R)
\
30(R)
左旋后：
50(B)
/
30(R)
/
20(R)
右旋 + 变色后：
30(B)
/ \
20(R) 50(R)
右左情况
插入前：
20(B)
\
50(R)
/
30(R)
右旋后：
20(B)
\
30(R)
\
50(R)
左旋 + 变色后：
30(B)
/ \
20(R) 50(R)
原因总结
- 变色：解决颜色冲突（连续红色节点）。
- 旋转：解决树的结构失衡（左重或右重）。
- 结合变色与旋转：保证红黑树的五条性质不被破坏。
2.3 红黑树的查找
按照二叉树的旋转逻辑即可：
Node* find(const K& k)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < k)
{
cur = cur->_right;
}
else if (cur->_kv.first > k)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
2.4 判断是否平衡
中心思想就是判断每个路径上的黑色节点数量是否相等，为了方便我们定义一个参考值用来记录其中一条路径上的黑色节点，然后再遍历其他路径和该路径的参考值进行比较，如果与参考值不相等则不平衡
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_colour == RED)
{
return false;
}
//参考值
int refnum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_colour == Black)
{
refnum++;
}
cur = cur->_left;
}
return check(_root, 0, refnum);
}
bool check(Node* root, int blacknum, const int refnum)
{
if (root == nullptr)
{
//前序遍历走到空了，意味着已经走完一条路径
//和参考值进行比较
if (blacknum == refnum)
{
return true;
}
else
{
cout << "黑色节点数量不匹配" << endl;
return false;
}
}
// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
if (root->_colour == RED && root->_parent->_colour == RED)
{
cout << root->_kv.first << "存在连续的红色结点" << endl;
return false;
}
if (root->_colour == Black)
{
blacknum++;
}
return check(root->_left, blacknum, refnum)
&& check(root->_right, blacknum, refnum);
}
