数据结构第八节：红黑树（初阶）

【本节要点】

红黑树概念
红黑树性质
红黑树结点定义
红黑树结构
红黑树插入操作的分析

一、红黑树的概念与性质

1.1 红黑树的概念

红黑树 ，是一种 二叉搜索树 ，但 在每个结点上增加一个存储位表示结点的颜色，可以是 Red和 Black 。通过对 任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍 ，因而是 接近平衡 的。

红黑树构造：[10(黑)] /        \[5(红)]     [20(黑)]/     \       /     \[3(黑)] [8(黑)] [15(红)] [25(红)]/  \    /  \     /  \    /  \NIL NIL  NIL NIL  NIL NIL NIL NIL

1.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

路径类型	示例路径	结点数	比例
最短路径	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的右子结点

识别为三角型冲突

转换为直线型处理