---
title: 红黑树原理与 5 条性质
type: concept
domain: java-concurrency
tags: [red-black-tree, avl, self-balancing-bst, treeify, hashmap, treemap, treeset, cfs]
status: learning
created: 2026-10-09
last_reviewed: 2026-10-09
method: feynman
related_questions:
  - "什么是红黑树？"
  - "为什么在JDK8中HashMap要转成红黑树"
  - "为什么HashMap的Cap是2的n次方，如何保证？"
related_knowledge:
  - ./hash-map-evolution.md
  - ./hash-map-concurrent.md
anki_cards: 6
interview_rounds:
  - "2026-10-09-round-1-Q1"
---

# 红黑树原理与 5 条性质

> 用"颜色约束"代替 AVL 的"严格高度差 ≤ 1"，允许最长路径不超过最短路径 2 倍——本质是用平衡的严格度换实现复杂度和写性能。

## TL;DR（30 秒扫完）

- **本质**：红黑树是**自平衡二叉搜索树**，比普通 BST 加了 5 条颜色约束
- **5 条性质**（口诀"根黑叶黑红隔、黑高相等"）：①节点红或黑；②根黑；③NIL 黑；④红不邻红；⑤任一节点到叶子的黑高相同
- **复杂度**：查找/插入/删除均 O(log n)；树高 ≤ 2·log₂(n+1)；写操作至多 2-3 次旋转
- **vs AVL**：AVL 严格平衡（读写都 O(log n)），红黑树写多更快；工程上偏爱红黑树
- **典型应用**：TreeMap/TreeSet、JDK8 HashMap 树桶、JDK8 ConcurrentHashMap、Linux CFS 调度器、C++ std::map

## 关键结论

- **结论 A**：红黑树 5 条性质是"工程折中"——用有限的平衡换取更快的写入
- **结论 B**：最长路径不超过最短路径 2 倍（由性质 4 + 性质 5 推得）
- **结论 C**：AVL 严格平衡但写多时旋转更多；红黑树写性能优，读略慢
- **结论 D**：JDK8 HashMap 选红黑树（不是 AVL、不是跳表）是内存紧凑+改造侵入小的综合结果

## 完整讲解（费曼四步）

### STEP 1 · 概念

红黑树是一种**自平衡二叉搜索树**（Self-Balancing BST），本质仍是二叉搜索树（BST），左子树所有值小于根、右子树所有值大于根；在此基础上加了 5 条颜色约束，用**颜色**来保证平衡——每个节点是红色或黑色，通过约束红黑比例让树不会太歪。

### STEP 2 · 大白话

> **类比**：想象你在给一棵树染色（红或黑）。规则是：
> 1. 根必须是黑色（"根要稳重"）
> 2. 所有空叶子（NIL）是黑色（"末端统一黑"）
> 3. 红色节点旁边不能是红色（"红不邻红"——两个红不能挨着）
> 4. 从任何节点出发到任何叶子的路径上，**黑色节点数必须一样**（"黑高相等"）
>
> 有了这些规则，树的**最长路径最多是最短路径的 2 倍**——比如最短路径 3 个黑节点，最长路径最多 5 个节点（黑-红-黑-红-黑）。这样树不会太歪，查找还是 O(log n)。

> **和 AVL 比**：AVL 要求左右子树高度差 ≤ 1（更严格）；红黑树允许 2:1。AVL 读快但每次写入可能要旋转多次；红黑树写入时最多 2-3 次旋转，写性能更好。工程上写多的场景（HashMap、TreeMap、TreeSet）都用红黑树。

### STEP 3 · 底层

#### 5 条性质（严格定义）

| # | 性质 | 说明 |
|---|------|------|
| ① | 节点是红色或黑色 | 颜色只有两种 |
| ② | **根节点是黑色** | 防止根是红，破坏"红不邻红"边界 |
| ③ | **所有 NIL 叶子是黑色**（虚拟叶子） | 统一"到叶子的路径"定义 |
| ④ | **红节点的两个子节点必须是黑色** | 简称"红不邻红" |
| ⑤ | **任一节点到其所有叶子路径上的黑节点数相同**（黑高相等） | 核心平衡约束 |

**口诀**："根黑叶黑红隔、黑高相等"

#### 高度约束推导

设：
- h = 树的高度
- bh = 黑高（任一节点到叶子的黑节点数）

**由性质 5**：任何路径的黑节点数都是 bh
**由性质 4**：红节点必须夹在黑节点之间，所以：
- **最短路径**：全黑，长度 = bh
- **最长路径**：黑红相间，长度 = 2 × bh

**结论**：`h ≤ 2 × bh`，即 `bh ≥ h/2`

又因为节点数 n 和 bh 的关系：
- 完全二叉树：n = 2^(bh+1) - 1，所以 `bh = log₂(n+1) - 1`
- **树高上界**：`h ≤ 2 × (log₂(n+1) - 1) ≈ 2 · log₂(n)`

**推论**：查找/插入/删除复杂度都是 **O(log n)**

#### 插入修复流程

插入时先插入红色节点（如果插入黑色会破坏性质 5）。然后可能破坏：
- 性质 4：父节点是红 → 需要修复
- 性质 5：无影响（红不影响黑高）

**三种修复场景**（父节点必是红，根必黑）：

```
场景 1：叔叔节点是红色
  ─────────────────────────────
  爷爷（黑）→ 改红
  父、叔（红）→ 改黑
  颜色修复后继续向上处理爷爷
  
场景 2：叔叔是黑，父是左子，祖父是右子（右左）
  ─────────────────────────────
  先对父节点做旋转（右旋），变右右场景

场景 3：右右场景
  ─────────────────────────────
  对祖父左旋，然后重染色
```

#### 删除修复流程

删除最复杂：
1. 处理要删除节点的直接子节点
2. 如果被删节点是黑色，会破坏性质 5 → 需要"借黑"或"旋转+染色"
3. 修复过程可能需要多次旋转和染色

（详细修复流程较复杂，面试能说出"删除会破坏黑高，需要借黑/旋转修复"即可）

#### 红黑树 vs AVL

| 维度 | 红黑树 | AVL |
|------|-------|-----|
| 平衡约束 | 黑高相等，最长路径 ≤ 2×最短 | 左右高度差 ≤ 1 |
| 查找 | O(log n)，稍慢 | O(log n)，稍快 |
| 插入/删除 | 最多 2-3 次旋转 | 最多 O(log log n) 次旋转 |
| 内存 | 每节点多 1 位颜色 | 每节点多 2 位平衡因子 |
| 适用场景 | 写多（HashMap/TreeMap） | 读多（数据库索引） |

**为什么 HashMap JDK8 选红黑树不选跳表**：
- **内存紧凑**：TreeNode 只需 parent/left/right/红黑标记，比跳表的多层指针更省内存
- **改造侵入小**：HashMap 节点本身就是链表结构，转树改造只需改TreeNode，跳表需要额外维护多层
- **范围查询**：红黑树中序遍历天然有序；跳表也支持但实现复杂
- **并发扩展**：并发场景有 ConcurrentSkipListMap，不是 ConcurrentHashMap 的选择

#### 转树阈值 8 的数学原理

HashMap 容量是 2 的幂，负载因子 0.75，链长分布近似泊松分布。泊松分布参数 λ = 0.5 时，链长到 8 的概率：

```
P(k=8) = 0.5^8 / 8! ≈ 6 × 10⁻⁸
```

**极低概率**意味着链长到 8 大概率是**哈希冲突**而非随机分布。此时红黑树 O(log n) 的优势才体现（如果链长到 8 是随机的，说明 hash 分布有问题，转树也没用）。

容量阈值 64：容量太小时冲突是正常现象，应优先扩容而非转树。

#### 典型应用

| 应用 | 说明 |
|------|------|
| `TreeMap` / `TreeSet` | Java 有序 Map/Set 底层 |
| JDK8 `HashMap` 树桶 | 链长>8 且容量≥64 转树 |
| JDK8 `ConcurrentHashMap` | 桶级也支持树化（TREEBIN） |
| Linux CFS 调度器 | 用红黑树管理任务节点，避免遍历超时 |
| C++ `std::map` | 基于红黑树（Splay Tree 是备选） |
| 数据库 B+树 | 底层不是红黑树，但设计思想类似（多路平衡） |

### STEP 4 · 简化

> **一句话总结**：红黑树是 BST + 5 条颜色约束，允许最长路径 ≤ 2 倍最短路径，查找 O(log n)，写入至多 2-3 次旋转——工程上写多场景的默认选择。

## 常见误区

- **误区 1**：红黑树是"平均高度相等" → 错，是"黑高相等"，最长路径 ≤ 2 倍最短路径
- **误区 2**：红黑树完全平衡 → 错，是"自平衡"但允许一定不平衡
- **误区 3**：红黑树比 AVL 好 → 错，各有优劣；读多用 AVL、写多用红黑树
- **误区 4**：HashMap JDK8 选红黑树是因为 AVL 慢 → 错，是 AVL 写多时旋转更多（O(log log n)），红黑树写入至多 2-3 次
- **误区 5**：树桶永远不会退化 → 错，扩容后树桶 size < 6 会退化回链表

## 延伸追问

1. **红黑树 5 条性质为什么能保证 O(log n)？**
   - 性质 5 保证黑高相等；性质 4 保证红不邻红；推得最短路径 = bh、最长路径 ≤ 2·bh；树高 h ≤ 2·bh ≈ 2·log₂(n)

2. **红黑树插入一个红色节点后如何修复？**
   - 三种情况：①叔叔红则父叔改黑、爷爷改红向上递归；②叔叔黑且是左左/右右则单旋；③叔叔黑且是左右/右左则双旋

3. **HashMap 为什么选红黑树不选跳表？**
   - 红黑树内存紧凑、改造侵入小；跳表更适合范围查询或并发（Redis zset 用跳表）

4. **AVL 和红黑树的适用场景？**
   - 读多（数据库索引、静态数据）→ AVL；写多（TreeMap、HashMap）→ 红黑树

5. **HashMap 为什么链表阈值选 8？**
   - 泊松分布下自然概率链长到 8 约 6×10⁻⁸，超过就是哈希冲突，此时转树才有意义

6. **Linux CFS 为什么用红黑树？**
   - 需要按 nice 值排序调度；红黑树 O(log n) 查找/插入/删除；避免遍历超时

## 速查表（面试前 30 秒扫完）

```
5 条性质（口诀"根黑叶黑红隔、黑高相等"）：
  ① 节点是红或黑
  ② 根是黑色
  ③ NIL 叶子是黑色
  ④ 红节点的两个子节点必须是黑色（红不邻红）
  ⑤ 任一节点到其所有叶子路径上黑节点数相同（黑高相等）

高度约束：
  最短路径 = bh（黑高）
  最长路径 ≤ 2 × bh
  树高 h ≤ 2 · log₂(n)
  复杂度 O(log n)

写入旋转次数：最多 2-3 次

vs AVL：
  读多用 AVL（严格平衡）
  写多用红黑树（写入快）

典型应用：
  TreeMap/TreeSet
  JDK8 HashMap 树桶（链长>8 且容量≥64）
  JDK8 ConcurrentHashMap TREEBIN
  Linux CFS 调度器
  C++ std::map
```

## 关联题目（题库）

- [ ] 《什么是红黑树？》— 2026-10-09 Round 1 Q1, ⭐⭐（5 条性质只说 2 条，"平均树高等"表述错）
- [ ] 《为什么在JDK8中HashMap要转成红黑树》— 关联题

## 关联知识

- [HashMap 内部机制与 JDK7→JDK8 演进](./hash-map-evolution.md)
- [ConcurrentHashMap 并发机制与 synchronized 决策](./hash-map-concurrent.md)

## Anki 候选卡片

1. **正**：红黑树 5 条性质？
   **反**：① 节点是红或黑；② 根是黑色；③ NIL 叶子是黑色；④ 红节点的两个子节点必须是黑色（红不邻红）；⑤ 任一节点到叶子的路径上黑节点数相同（黑高相等）

2. **正**：红黑树的高度上界公式？
   **反**：树高 h ≤ 2 · log₂(n+1)；最长路径 ≤ 2 倍最短路径（由红不邻红 + 黑高相等推得）

3. **正**：红黑树和 AVL 的区别？
   **反**：AVL 严格平衡（左右高度差 ≤ 1）；红黑树允许 2:1 不平衡；AVL 写多时旋转更多（O(log log n)），红黑树写入至多 2-3 次；读多用 AVL、写多用红黑树

4. **正**：HashMap JDK8 为什么选红黑树不选跳表？
   **反**：红黑树内存紧凑（TreeNode 只有 parent/left/right + 颜色），跳表需要多层指针；红黑树改造侵入小（HashMap 节点本就是链表结构）；跳表更适合范围查询或并发（Redis zset 用跳表）

5. **正**：HashMap 转树的双门槛是什么？为什么？
   **反**：链长 > 8 且容量 ≥ 64；泊松分布下链长到 8 的概率约 6×10⁻⁸，超过就是哈希冲突（转树有意义）；容量 < 64 时应优先扩容而非转树

6. **正**：红黑树写入最多需要几次旋转？
   **反**：最多 2-3 次（LL/RR 单旋转，LR/RL 双旋转）；AVL 是 O(log log n)

---

*最后更新：2026-10-09*