五、红黑树（Red-Black Tree）

1、为什么需要红黑树？—— BST 的“退化”问题

要理解红黑树，必须先明白二叉搜索树（BST）的局限性。

红黑树插入演示

准备就绪

速度

插入数据

插入修复逻辑 (C-like)1. 执行标准BST插入，新节点为红色
2. 修复 Case 1: 叔叔为红色
   -> 翻转父、叔、祖父颜色
3. 修复 Case 2: 叔叔为黑色 (三角)
   -> 旋转父节点
4. 修复 Case 3: 叔叔为黑色 (直线)
   -> 翻转父/祖父颜色, 旋转祖父
5. 左旋操作
6. 右旋操作
7. 确保根节点为黑色

BST的理想状态：如果插入的数据是随机的，BST 大概率会“比较平衡”，其查找、插入、删除的时间复杂度都能达到 O(log n)。
BST的“退化”问题：如果插入的数据是有序的（例如，依次插入 1, 2, 3, 4, 5），BST 就会退化成一个链表。
```
  1
   \
    2
     \
      3
       \
        4
         \
          5
```
在这种情况下，查找、插入、删除的时间复杂度会恶化到 O(n)，失去了树形结构的优势。

为了解决这个问题，自平衡二叉搜索树（Self-Balancing BST）应运而生。它的核心思想是：在每次插入或删除节点后，通过一系列操作（如旋转）来调整树的结构，使其始终保持“大致平衡”，从而确保最坏情况下的时间复杂度也能维持在 O(log n)。

红黑树就是其中最著名、应用最广泛的一种。

2、什么是红黑树？—— 五条核心性质

定义：红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色（红色 RED 或黑色 BLACK）。

它必须同时满足以下五条性质：

颜色性质：每个节点要么是红色，要么是黑色。
根节点性质：根节点必须是黑色。
叶子性质：所有叶子节点（NIL 节点，即空指针）都视为黑色。
- 理解：这指的是概念上的、不存在的叶子节点。所有指向 NULL 的指针都指向一个虚拟的黑色NIL节点。
红色性质：如果一个节点是红色的，那么它的两个子节点必须都是黑色的。
- 推论：从根到叶子的任何路径上，都不可能出现连续的两个红色节点。
黑色性质：对任意一个节点，从它到其所有后代叶子节点的路径上，所包含的黑色节点数量必须相同。这个数量被称为该节点的“黑高（Black-Height）”。

核心保证：正是这五条性质，尤其是第4和第5条，共同保证了红黑树不会严重失衡。它们确保了从根到叶子的最长路径，不会超过最短路径的两倍。这就保证了树的高度始终是 log n 级别的。

3、红黑树如何保持平衡？—— 两种基本操作

当插入或删除节点导致上述五条性质被破坏时，红黑树通过以下两种基本操作来“自我修复”：

1. 变色（Recoloring）

操作：将一个节点的颜色由红变黑，或由黑变红。
作用：这是一种代价很小的调整方式，通常用于解决“红色性质”（父子皆红）的冲突。

2. 旋转（Rotation）

旋转是调整树结构的关键，它在不破坏二叉搜索树性质的前提下，改变节点的父子关系，从而降低树的高度。

左旋 (Left Rotation)：以某个节点 x 为轴进行左旋，x 会成为其右子节点 y 的左孩子。y 原本的左子树会成为 x 的新右子树。
```
    (P)             (P)
     |               |
     x               y
    / \             / \
   A   y    --->    x   C
      / \         / \
     B   C       A   B
```
- 效果：将右侧的分支“提”了上来，降低了右子树的高度。
右旋 (Right Rotation)：与左旋相反。以某个节点 y 为轴进行右旋，y 会成为其左子节点 x 的右孩子。
```
    (P)             (P)
     |               |
     y               x
    / \             / \
   x   C    --->    A   y
  / \                 / \
 A   B               B   C
```
- 效果：将左侧的分支“提”了上来，降低了左子树的高度。

4、红黑树的插入操作（核心流程）

插入是理解红黑树修复机制的最佳入口。

步骤 1：按 BST 规则插入，并染成红色

首先，像普通二叉搜索树一样，找到新节点的插入位置并插入。
然后，将新插入的节点标记为红色。
为什么是红色？
- 如果插入黑色节点，必然会改变某条路径的“黑高”，破坏了性质5。修复性质5通常需要复杂的全局调整。
- 如果插入红色节点，只会可能破坏性质4（如果其父节点也是红色），或者性质2（如果它是根节点）。这两种情况的修复都相对局部和简单。

步骤 2：向上回溯，修复冲突 从新节点 N 开始，检查是否违反了红黑树性质。如果 N 的父节点 P 是黑色，那么万事大吉，无需调整。如果 P 是红色，就违反了性质4，需要分情况讨论。

设 G 为祖父节点，U 为叔叔节点。

Case 1: 叔叔 `U` 是红色

这是最简单的情况。

操作：
1. 将父节点 P 变为黑色。
2. 将叔叔节点 U 变为黑色。
3. 将祖父节点 G 变为红色。
后续：此时，祖父节点 G 成为了新的红色节点。我们需要将 G 视为新的插入节点，从 G 开始继续向上检查是否还有冲突。问题被“传递”了上去。
```
     G(黑)             G(红)  <-- 变成新问题点
    /   \             /   \
  P(红)  U(红)  --->  P(黑)  U(黑)
  |                 |
  N(红)             N(红)
```

Case 2: 叔叔 `U` 是黑色（或NIL）

这种情况需要通过旋转来解决。它又分为两种子情况：

子情况 2.1: “折线”情况 (Triangle) 如果 N 是 P 的内侧孩子（例如，G -> P(左) -> N(右)），形成一个 < 或 > 形状。
- 操作：
  1. 以父节点 P 为轴进行一次旋转（左旋或右旋），将其变为“直线”情况。
  2. 然后按“直线”情况处理。
子情况 2.2: “直线”情况 (Line) 如果 N 是 P 的外侧孩子（例如，G -> P(左) -> N(左)），形成一条斜线。
- 操作：
  1. 将父节点 P 变为黑色。
  2. 将祖父节点 G 变为红色。
  3. 以祖父节点 G 为轴进行一次与 P 方向相反的旋转。
- 后续：经过这套操作后，该子树的冲突被完全解决，无需再向上回溯。
```
     G(黑)                 P(黑)
    /   \                 /   \
  P(红)  U(黑)    --->    N(红)  G(红)
  |                               \
  N(红)                             U(黑)
```

步骤 3：确保根节点是黑色 无论中间经过多少调整，最后一步都要检查根节点。如果根节点是红色，直接将其变为黑色。

5、红黑树的删除操作

删除操作比插入复杂得多，因为它可能同时破坏多个性质。

核心难点：删除一个黑色节点。这会减少路径上的黑高，破坏性质5。
基本思路：
1. 按BST规则删除节点。
2. 如果被删除（或替换）的节点是黑色的，其位置会出现一个“双重黑色（Double Black）”的窟窿。
3. 算法的目标就是通过一系列的变色和旋转，将这个“双重黑色”向上移动，直到它被一个红色节点吸收，或者到达根节点。
4. 这个过程需要分更多、更复杂的情况进行讨论。对于初学者，建议先掌握“删除黑色节点会引发复杂调整”这一概念即可。

6、复杂度

复杂度分析

操作	平均时间复杂度	最坏时间复杂度
查找	O(log n)	O(log n)
插入	O(log n)	O(log n)
删除	O(log n)	O(log n)

与 AVL 树的对比

特性	AVL 树	红黑树
平衡性	更严格（左右子树高度差<=1）	更宽松（最长路径<=2*最短路径）
查找效率	更高（树更矮，更平衡）	略低
插入/删除效率	略低（可能需要多次旋转）	更高（最多两次旋转即可完成平衡）
实现难度	相对简单	更复杂

结论：如果你的应用场景查找操作远多于插入/删除，AVL 树可能是更好的选择。但在写操作（插入/删除）频繁的场景中，红黑树因其更少的旋转次数而表现更佳。

7、总结

知识点	关键内容
核心目标	解决普通二叉搜索树的“退化”问题，保证 O(log n) 的最坏性能。
本质	一种自平衡的二叉搜索树，节点有红黑两种颜色。
平衡保证	通过五条核心性质，确保树“大致平衡”。
关键性质	1. 根黑； 2. 无连续红节点； 3. 任一节点到其所有叶路径的黑高相同。
调整操作	变色（代价小）和旋转（代价大，调整结构）。
插入策略	新节点染成红色，然后根据叔叔节点的颜色分情况调整。
性能特点	查找、插入、删除都是稳定的 O(log n)。
应用优势	在频繁插入和删除的场景下，性能优于 AVL 树。

1、 为什么需要红黑树？—— BST 的“退化”问题​

插入修复逻辑 (C-like)

2、 什么是红黑树？—— 五条核心性质​

3、 红黑树如何保持平衡？—— 两种基本操作​

1. 变色（Recoloring）​

2. 旋转（Rotation）​

4、 红黑树的插入操作（核心流程）​

Case 1: 叔叔 U 是红色​

Case 2: 叔叔 U 是黑色（或NIL）​

5、 红黑树的删除操作​

6、 复杂度​

复杂度分析​

与 AVL 树的对比​

7、 总结​

💬 留下你的问题或见解