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

【本节要点】

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

一、红黑树的概念与性质

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的右子结点

识别为三角型冲突

转换为直线型处理

场景3：叔结点为黑-直线型（Case3）
      G(黑)             P(黑)
     /               /   \
   P(红)   →      Z(红) G(红)
   /
 Z(红)
检测要点：

确认Z是P的左子结点

直接触发祖父旋转

完成颜色交换