红黑树原理与 5 条性质

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 推得）

结论 CAVL 严格平衡但写多时旋转更多；红黑树写性能优，读略慢

结论 DJDK8 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：右右场景
  ─────────────────────────────
  对祖父左旋，然后重染色

删除修复流程

删除最复杂：

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

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

红黑树 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 次旋转——工程上写多场景的默认选择。

延伸追问

红黑树 5 条性质为什么能保证 O(log n)？

性质 5 保证黑高相等；性质 4 保证红不邻红；推得最短路径 = bh、最长路径 ≤ 2·bh；树高 h ≤ 2·bh ≈ 2·log₂(n)

红黑树插入一个红色节点后如何修复？

三种情况：①叔叔红则父叔改黑、爷爷改红向上递归；②叔叔黑且是左左/右右则单旋；③叔叔黑且是左右/右左则双旋

HashMap 为什么选红黑树不选跳表？

红黑树内存紧凑、改造侵入小；跳表更适合范围查询或并发（Redis zset 用跳表）

AVL 和红黑树的适用场景？

读多（数据库索引、静态数据）→ AVL；写多（TreeMap、HashMap）→ 红黑树

HashMap 为什么链表阈值选 8？

泊松分布下自然概率链长到 8 约 6×10⁻⁸，超过就是哈希冲突，此时转树才有意义

Linux CFS 为什么用红黑树？

需要按 nice 值排序调度；红黑树 O(log n) 查找/插入/删除；避免遍历超时

速查表

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要转成红黑树》— 关联题

关联知识

红黑树=BST+5 条颜色约束（根黑叶黑红隔、黑高相等）；允许最长路径≤2 倍最短路径；查找 O(log n)，写入至多 2-3 次旋转——工程上写多场景的默认选择

给一棵树染色：根要黑、叶要黑、红不邻红、任何路径黑节点数相同——这样树不会太歪，最长路径最多是最短路径的 2 倍

✦ 记忆口诀 ✦

根黑叶黑红隔、黑高相等；最长路径≤2×最短；h≤2·log₂(n)；写入至多 2-3 次旋转

关键可视化

红黑树 5 条性质

flowchart TB
  R["红黑树 5 条性质"] --> P1["① 节点是红色或黑色"]
  R --> P2["② 根节点是黑色"]
  R --> P3["③ NIL 叶子是黑色"]
  R --> P4["④ 红节点的两个子节点必须是黑色<br/>红不邻红"]
  R --> P5["⑤ 任一节点到其所有叶子路径上<br/>黑节点数相同（黑高相等）"]
  P4 -.推.-> H1["最短路径 = bh"]
  P5 -.推.-> H1
  H1 -.+P4.-> H2["最长路径 ≤ 2 × bh"]
  H2 --> H3["树高 h ≤ 2 · log₂(n)"]
  H3 --> H4["复杂度 O(log n)"]

红黑树 vs AVL

flowchart TB
  subgraph AVL["AVL 树"]
    A1["平衡约束：左右高度差 ≤ 1"]
    A2["查找：O(log n) 稍快"]
    A3["写入：O(log log n) 次旋转"]
    A4["内存：多 2 位平衡因子"]
    A5["适用：读多场景"]
  end
  subgraph RBT["红黑树"]
    B1["平衡约束：最长路径≤2×最短"]
    B2["查找：O(log n) 稍慢"]
    B3["写入：至多 2-3 次旋转"]
    B4["内存：多 1 位颜色"]
    B5["适用：写多场景"]
  end
  AVL -.读多vs写多.-> RBT

红黑树插入修复三种情况

flowchart TB
  I["插入红色节点"] --> C1{"父是红？"}
  C1 -- 根黑 --> OK["不需要修复"]
  C1 -- 是 --> U{"叔叔是红？"}
  U -- 是 --> R1["场景 1：染色
父叔改黑、爷爷改红
向上递归处理爷爷"]
  U -- 是黑 --> G{"节点位置？"}
  G -- 左右/右左 --> R2["场景 2：双旋
先对父旋转变右右"]
  G -- 右右/左左 --> R3["场景 3：单旋
对祖父旋转+染色"]
  R1 --> DONE["修复完成"]
  R2 --> DONE
  R3 --> DONE

红黑树典型应用

flowchart TB
  APP["红黑树应用"] --> A1["Java TreeMap/TreeSet<br/>有序 Map/Set"]
  APP --> A2["JDK8 HashMap 树桶<br/>链长>8 且容量≥64"]
  APP --> A3["JDK8 ConcurrentHashMap<br/>TREEBIN 桶级"]
  APP --> A4["Linux CFS 调度器<br/>按 nice 值排序"]
  APP --> A5["C++ std::map<br/>红黑树实现"]
  APP --> A6["数据库 B+树<br/>设计思想类似<br/>（多路平衡）"]

HashMap 转树阈值 8 的泊松分布原理

flowchart LR
  H1["hash 分布均匀<br/>泊松分布 λ=0.5"] --> H2["P(链长=8)<br/>≈ 6 × 10⁻⁸"]
  H2 --> H3["极低概率<br/>=哈希冲突不是分布问题"]
  H3 --> H4["转树有意义<br/>O(n) → O(log n)"]
  H4 --> H5["且容量≥64<br/>避免小表误转树"]

知识关系

⬆️ 前置（Prerequisite）

hash-map-evolution

🔄 延伸（Extends）

concurrency-foundations

⚡ 对比（Contrast）

HashMap 树桶— HashMap JDK8 链长>8 且容量≥64 转红黑树，是红黑树最直接的工程落地

🎯 概念 📏 规则 ⚠️ 误区 🔍 追问 ✨ 口诀共 0 张卡，点击翻面