第八节红黑树初阶
目录
第八节：红黑树（初阶）
【本节要点】
- 红黑树概念
- 红黑树性质
- 红黑树结点定义
- 红黑树结构
- 红黑树插入操作的分析
一、红黑树的概念与性质
1.1 红黑树的概念
红黑树
，是一种
二叉搜索树
，但
在每个结点上增加一个存储位表示结点的颜色，可以是
Red和
Black
。 通过对
任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍
，因而是
接近平衡
的。
红黑树构造：
[10(黑)]
/ \
[5(红)] [20(黑)]
/ \ / \
[3(黑)] [8(黑)] [15(红)] [25(红)]
/ \ / \ / \ / \
NIL NIL NIL NIL NIL NIL NIL NIL1.2 红黑树的性质
每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含
相同数目的黑色结点
每个
叶子结点都是黑色
的
(
此处的叶子结点指的是空结点
)
以上五点性质可以保证： 其最长路径中节点个数不会超过最短路径节点
个数的两倍。
二、红黑树结点定义
// 结点的颜色
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 _col; // 结点的颜色
// 结点的构造函数
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};注意：红黑树定义结点时，默认结点颜色为红色，这一设计选择直接增加红黑树的平衡维护效率和整体性能，大大减少时间复杂度。
三、红黑树的结构
// 以本数组为例
num[3, 5, 8, 10, 15, 20, 25]红黑树构造：
[10(黑)]
/ \
[5(红)] [20(黑)]
/ \ / \
[3(黑)] [8(黑)] [15(红)] [25(红)]
/ \ / \ / \ / \
NIL NIL NIL NIL NIL NIL NIL NIL图示说明
- 根结点标记
：根结点
10为黑色，符合 性质2 （根结点必黑） - 红色结点规则：
红色结点
5、15、25的子结点均为黑色，满足 性质3 （红色结点不连续） - 黑高一致性验证： 从根结点到任意 NIL 的路径黑色结点数均为 2
- NIL结点处理： 所有叶子结点显式标记为 NIL（黑色），符合 性质5
- 最长/最短路径对比
路径类型 示例路径 结点数 比例 最短路径 10→20→NIL 2 1:1 最长路径 10→5→3→NIL 3 1.5:1 理论极限 红黑交替路径（未出现） ≤4 ≤2:1
四、红黑树的插入操作
[开始插入新结点Z]
│
▼
┌─────────执行标准BST插入─────────┐
│ │
▼ ▼
[Z设为红色] [保持BST性质]
│
▼
┌─────父结点P是否为红色？─────┐
│ │
▼ (是) ▼ (否)
[存在双红冲突需处理] [插入完成]
│
▼
┌────叔结点U的颜色？────┐
│ │
▼ (红色) ▼ (黑色/NIL)
[Case1: 颜色翻转] [判断冲突结构类型]
│ │
▼ ├─────────────────────────┐
[将P、U设为黑色] ▼ ▼
│ [Z-P-G呈三角型] [Z-P-G呈直线型]
▼ │ │
[将G设为红色] [Case2: 旋转父结点] [Case3: 旋转祖父结点]
│ │ │
▼ ▼ ▼
[以G为新Z向上回溯] [转为直线型冲突] [交换颜色并旋转]
│
▼
[调整完成]
│
▼
[最终确保根结点为黑]4.1 基本BST插入阶段
- 插入位置遵循二叉搜索树规则
- 新结点初始颜色必须为 红色 （最小化规则破坏）
4.2 冲突检测阶段
- 要素1：父结点状态判断
- 要素2：叔结点颜色判定
- 要素3：冲突结构类型识别
4.3 典型场景演练
场景1：叔结点为红（Case1）
G(黑) G(红) / \ 颜色翻转 / \ P(红) U(红) → P(黑) U(黑) / / Z(红) Z(红)检测要点 ：
- 确认U存在且为红
- 将冲突标记上移给G
- 继续以G作为新Z向上检测
场景2：叔结点为黑-三角型（Case2）
G(黑) G(黑) / / P(红) → Z(红) \ / Z(红) P(红)检测要点 ：
- 判断Z是P的右子结点
- 识别为三角型冲突
- 转换为直线型处理
场景3：叔结点为黑-直线型（Case3）
G(黑) P(黑) / / \ P(红) → Z(红) G(红) / Z(红)检测要点 ：
- 确认Z是P的左子结点
- 直接触发祖父旋转
- 完成颜色交换
4.4 总结
冲突检测阶段通过 三级条件筛选 （父结点状态→叔结点颜色→冲突结构类型），将复杂的平衡问题分解为可控的局部操作。这种分层检测机制：
- 确保 90%以上的插入操作 只需1次检测即可完成
- 将最坏情况的时间复杂度严格控制在 O(log n)
- 为后续的旋转/颜色调整提供精准的操作依据
该设计体现了红黑树 “以检测换计算，以分类求高效” 的核心优化思想，是其能在大规模数据场景下保持卓越性能的关键所在。
以上就是 红黑树初阶知识 的了解，接下来我会 继续更新红黑树进阶 ： 红黑树的模拟实现 、使用红黑树底层对 map和set容器的模拟实现。 制作不易，请大家多多点赞收藏啦！！
