【本节要点】
- 红黑树概念
- 红黑树性质
- 红黑树结点定义
- 红黑树结构
- 红黑树插入操作的分析
一、红黑树的概念与性质
1.1 红黑树的概念
红黑树 ，是一种 二叉搜索树 ，但 在每个结点上增加一个存储位表示结点的颜色，可以是 Red和 Black 。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍 ，因而是 接近平衡 的。
红黑树构造：[10(黑)] / \[5(红)] [20(黑)]/ \ / \[3(黑)] [8(黑)] [15(红)] [25(红)]/ \ / \ / \ / \NIL NIL NIL NIL NIL NIL NIL NIL1.2 红黑树的性质
- 1. 每个结点不是红色就是黑色
- 2. 根节点是黑色的
- 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
以上五点性质可以保证：其最长路径中节点个数不会超过最短路径节点个数的两倍。
二、红黑树结点定义
// 结点的颜色
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容器的模拟实现。制作不易，请大家多多点赞收藏啦！！
