# 08-红黑树

## 💡 核心结论

### 红黑树本质
- **定义**：自平衡二叉搜索树，通过颜色约束保持近似平衡
- **性能**：所有操作O(log n)，最坏情况有保证
- **平衡性**：最长路径 ≤ 2倍最短路径（比AVL宽松）
- **核心**：用颜色规则代替严格高度平衡，减少旋转次数
- **应用**：C++ STL、Java TreeMap、Linux内核

### 红黑树 vs AVL树
| 特性 | 红黑树 | AVL树 |
|------|--------|-------|
| 平衡度 | 近似平衡 | 严格平衡 |
| 插入旋转 | ≤2次 | ≤2次 |
| 删除旋转 | ≤3次 | O(log n) |
| 查询性能 | 稍慢 | 最快 |
| 插入删除 | 最快 | 较慢 |
| **选择** | **插入删除多** | **查询多** |

### 五大性质（必背）
1. 节点是红色或黑色
2. 根节点是黑色
3. 叶子节点（NIL）是黑色
4. 红色节点的子节点都是黑色（无连续红色）
5. 任一节点到叶子的所有路径包含相同数量的黑色节点

### 为什么这样设计
- **性质4**：避免连续红色，限制红色节点数量
- **性质5**：保证黑高度相同，确保平衡性
- **结果**：最长路径（红黑交替）≤ 2倍最短路径（全黑）

## 🌳 红黑树性质

### 五大性质
1. **节点是红色或黑色**
2. **根节点是黑色**
3. **所有叶子节点（NIL）是黑色**
4. **红色节点的两个子节点都是黑色**（不能有连续的红色节点）
5. **从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点**

### 性质保证
- 最长路径（红黑交替）≤ 最短路径（全黑）的2倍
- 树的高度：h ≤ 2log(n+1)
- 查找、插入、删除：O(log n)

## 🎯 红黑树 vs AVL树

| 特性 | AVL树 | 红黑树 |
|------|-------|--------|
| 平衡性 | 严格平衡 | 近似平衡 |
| 平衡因子 | 高度差≤1 | 最长路径≤2倍最短路径 |
| 旋转次数 | 插入1-2次，删除O(log n) | 插入≤2次，删除≤3次 |
| 查询性能 | 更快 | 稍慢 |
| 插入删除 | 较慢 | 更快 |
| 应用场景 | 查询密集 | 插入删除密集 |
| 实际应用 | Windows NT内核 | Linux内核、C++ STL |

## 🔄 旋转操作

### 左旋
```
    x                y
   / \              / \
  a   y    =>      x   c
     / \          / \
    b   c        a   b
```

### 右旋
```
      y            x
     / \          / \
    x   c  =>    a   y
   / \              / \
  a   b            b   c
```

## 🎨 插入操作

### 插入步骤
1. 按BST规则插入新节点（红色）
2. 修复红黑树性质
3. 情况分类处理

### 插入修复情况

**情况1：叔叔是红色**
- 父亲和叔叔变黑
- 爷爷变红
- 爷爷作为新节点继续修复

**情况2：叔叔是黑色，当前节点是右孩子**
- 左旋父节点
- 转换为情况3

**情况3：叔叔是黑色，当前节点是左孩子**
- 父亲变黑
- 爷爷变红
- 右旋爷爷

## 🗑️ 删除操作

### 删除步骤
1. 按BST规则删除节点
2. 如果删除的是黑色节点，需要修复
3. 情况分类处理

### 删除修复情况

**情况1：兄弟是红色**
- 父亲变红
- 兄弟变黑
- 左旋父亲
- 转换为其他情况

**情况2：兄弟是黑色，兄弟的两个孩子都是黑色**
- 兄弟变红
- 父亲作为新节点继续修复

**情况3：兄弟是黑色，兄弟的左孩子是红色，右孩子是黑色**
- 兄弟变红
- 兄弟的左孩子变黑
- 右旋兄弟
- 转换为情况4

**情况4：兄弟是黑色，兄弟的右孩子是红色**
- 兄弟颜色 = 父亲颜色
- 父亲变黑
- 兄弟的右孩子变黑
- 左旋父亲

## 🔧 应用场景

### C++ STL
- `std::map`
- `std::set`
- `std::multimap`
- `std::multiset`

### Java
- `TreeMap`
- `TreeSet`

### Linux内核
- 完全公平调度器（CFS）
- 虚拟内存管理

### 其他
- epoll实现
- nginx定时器

## 💡 实现要点

### 哨兵节点（NIL）
```python
class NIL:
    """哨兵节点"""
    def __init__(self):
        self.color = BLACK
        self.left = self
        self.right = self
        self.parent = None

# 使用全局NIL节点
NIL_NODE = NIL()
```

### 颜色表示
```python
RED = 0
BLACK = 1

class RBNode:
    def __init__(self, val, color=RED):
        self.val = val
        self.color = color
        self.left = NIL_NODE
        self.right = NIL_NODE
        self.parent = None
```

## 📚 时间复杂度分析

| 操作 | 平均 | 最坏 |
|------|------|------|
| 查找 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
| 删除 | O(log n) | O(log n) |
| 最小/最大 | O(log n) | O(log n) |

空间复杂度：O(n)

## 🎯 性能特点

### 优势
1. 最坏情况性能保证 O(log n)
2. 插入删除平均旋转次数少
3. 实现相对简单（相比B树）

### 劣势
1. 代码复杂度高于AVL树
2. 常数因子较大
3. 查询性能略逊于AVL树

## 📚 LeetCode练习

虽然LeetCode很少直接考察红黑树实现，但理解红黑树有助于：
- 理解STL容器性能
- 系统设计问题
- 面试中的数据结构选择

## 💡 学习建议

1. **先掌握BST和AVL树**
2. **理解五大性质的作用**
3. **画图理解旋转和变色**
4. **重点掌握插入过程**
5. **删除操作可以适当简化理解**
6. **了解实际应用场景**

## 📚 参考资料

- 《算法导论》第13章
- 《STL源码剖析》
- Linux内核源码（rbtree.c）
- [Red-Black Tree Visualization](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)

## 💻 完整代码实现

### Python 实现

```{literalinclude} rb_tree.py
:language: python
:linenos:
```

### C++ 实现

```{literalinclude} rb_tree.cpp
:language: cpp
:linenos:
```