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

   【本节要点】
  

• 红黑树概念
  
• 红黑树性质
  
• 红黑树结点界说
  
• 红黑树结构
  
• 红黑树插入操作的分析
  

  一、红黑树的概念与性质

1.1 红黑树的概念

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

1. 红黑树构造：
3.           [10(黑)]
4.           /        \
5.        [5(红)]     [20(黑)]
6.       /     \       /     \
7.     [3(黑)] [8(黑)] [15(红)] [25(红)]
8.      /  \    /  \     /  \    /  \
9.    NIL NIL  NIL NIL  NIL NIL NIL NIL

复制代码

1.2 红黑树的性质 

• 1. 每个结点不是红色就是黑色
  
• 2. 根节点是黑色的 
  
• 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 
  
• 4. 对于每个结点，从该结点到其所有后代叶结点的简朴路径上，均包含雷同数目的黑色结点 
  
• 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
  

 以上五点性质可以包管：其最长路径中节点个数不会凌驾最短路径节点个数的两倍。
 二、红黑树结点界说

1. // 结点的颜色
2. enum Colour
3. {
4.         RED,
5.         BLACK,
6. };
8. // 红黑树结点的定义
9. template<class K, class V>
10. struct RBTreeNode
11. {
12.         pair<K, V> _kv;            // 结点的键值对
13.         RBTreeNode<K, V>* _left;   // 结点的左孩子
14.         RBTreeNode<K, V>* _right;  // 结点的右孩子
15.         RBTreeNode<K, V>* _parent; // 结点的双亲（红黑树需要旋转，为了实现简单所以给出该结点）
16.         Colour _col;               // 结点的颜色
18.     // 结点的构造函数
19.         RBTreeNode(const pair<K, V>& kv)
20.                 :_kv(kv)
21.                 , _left(nullptr)
22.                 , _right(nullptr)
23.                 , _parent(nullptr)
24.                 , _col(RED)
25.         {}
26. };

复制代码

注意：红黑树界说结点时，默认结点颜色为红色，这一计划选择直接增加红黑树的平衡维护效率和团体性能，大大减少时间复杂度。
三、红黑树的结构

1. // 以本数组为例
2. num[3, 5, 8, 10, 15, 20, 25]

复制代码

1. 红黑树构造：
3.           [10(黑)]
4.           /        \
5.        [5(红)]     [20(黑)]
6.       /     \       /     \
7.     [3(黑)] [8(黑)] [15(红)] [25(红)]
8.      /  \    /  \     /  \    /  \
9.    NIL NIL  NIL NIL  NIL NIL NIL NIL

复制代码

图示阐明

• 根结点标记：根结点 10 为黑色，符合性质2（根结点必黑）
  
• 红色结点规则：红色结点 5、15、25 的子结点均为黑色，满足性质3（红色结点不连续）
  
• 黑高一致性验证：从根结点到恣意 NIL 的路径黑色结点数均为 2
  
• NIL结点处理：所有叶子结点显式标记为 NIL（黑色），符合性质5
  
• 最长/最短路径对比
     路径类型示例路径结点数比例最短路径10→20→NIL21:1最长路径10→5→3→NIL31.5:1理论极限红黑交替路径（未出现）≤4≤2:1
  

 四、红黑树的插入操作

1.                               [开始插入新结点Z]
2.                                       │
3.                                       ▼
4.                        ┌─────────执行标准BST插入─────────┐
5.                        │                                │
6.                        ▼                                ▼
7.                   [Z设为红色]                   [保持BST性质]
8.                        │
9.                        ▼
10.              ┌─────父结点P是否为红色？─────┐
11.              │                            │
12.              ▼ (是)                       ▼ (否)
13.     [存在双红冲突需处理]               [插入完成]
14.              │
15.              ▼
16.    ┌────叔结点U的颜色？────┐
17.    │                      │
18.    ▼ (红色)               ▼ (黑色/NIL)
19. [Case1: 颜色翻转]     [判断冲突结构类型]
20.    │                      │
21.    ▼                      ├─────────────────────────┐
22. [将P、U设为黑色]           ▼                         ▼
23.    │               [Z-P-G呈三角型]            [Z-P-G呈直线型]
24.    ▼                      │                         │
25. [将G设为红色]        [Case2: 旋转父结点]      [Case3: 旋转祖父结点]
26.    │                      │                         │
27.    ▼                      ▼                         ▼
28. [以G为新Z向上回溯]   [转为直线型冲突]         [交换颜色并旋转]
29.                                           
30.                                                     │
31.                                                     ▼
32.                                                 [调整完成]
33.                                                     │
34.                                                     ▼
35.                                            [最终确保根结点为黑]

复制代码

4.1 根本BST插入阶段

• 插入位置遵循二叉搜索树规则
  
• 新结点初始颜色必须为红色（最小化规则破坏）
  

4.2 冲突检测阶段

• 要素1：父结点状态判断
  
• 要素2：叔结点颜色判定
  
• 要素3：冲突结构类型识别
  

4.3  典范场景演练

   场景1：叔结点为红（Case1）

1.          G(黑)                 G(红)
2.         /   \     颜色翻转     /   \
3.       P(红) U(红)  →       P(黑) U(黑)
4.       /                   /
5.     Z(红)              Z(红)

复制代码

  检测要点：
  

• 确认U存在且为红
  
• 将冲突标记上移给G
  
• 继承以G作为新Z向上检测
  

    场景2：叔结点为黑-三角型（Case2）

1.      G(黑)            G(黑)
2.     /               /
3.   P(红)   →      Z(红)
4.     \           /
5.     Z(红)     P(红)

复制代码

  检测要点：
  

• 判断Z是P的右子结点
  
• 识别为三角型冲突
  
• 转换为直线型处理
  

    场景3：叔结点为黑-直线型（Case3）

1.       G(黑)             P(黑)
2.      /               /   \
3.    P(红)   →      Z(红) G(红)
4.    /
5. Z(红)

复制代码

  检测要点：
  

• 确认Z是P的左子结点
  
• 直接触发祖父旋转
  
• 完成颜色交换
  

   4.4 总结

冲突检测阶段通过三级条件筛选（父结点状态→叔结点颜色→冲突结构类型），将复杂的平衡题目分解为可控的局部操作。这种分层检测机制：

• 确保90%以上的插入操作只需1次检测即可完成
  
• 将最坏情况的时间复杂度严格控制在O(log n)
  
• 为后续的旋转/颜色调整提供精准的操作依据
  

该计划体现了红黑树"以检测换计算，以分类求高效"的焦点优化思想，是其能在大规模数据场景下保持杰出性能的关键地点。

---

以上就是红黑树初阶知识的了解，接下来我会继承更新红黑树进阶：红黑树的模仿实现、使用红黑树底层对map和set容器的模仿实现。制作不易，请各人多多点赞收藏啦！！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。