第6章 平衡树与红黑树
元数据卡
- 前置知识：二叉树与 BST（第5章）
- 预计时间：150 分钟
- 核心难度：
- 完成标志：能用 Python 写出 AVL 树插入后的平衡修复（四种旋转），能口述红黑树的五条性质和插入修复流程，能解释为什么 TreeMap 选择红黑树而不是 AVL
你在哪
但二叉树有个问题——如果你走的数字是顺序的（1, 2, 3, ...），这条路就退化成了一根笔直的长杆。你回想老陈的话："森林里有一些特殊的树，它们会自动修剪枝桠，让自己保持平衡。"
森林深处有一片被称为"失衡沼泽"的地方。这里的树都不正常——有的左歪右斜，有的已经彻底倒在地上变成了一根直直的木棍。
向导站在沼泽边缘，捡起一根倒在路边的枯枝。
"这就是上一章你没看到的东西。"他把枯枝立起来，从口袋里拿出一叠标签纸，依次贴上去："1, 2, 3, 4, 5。"
他手一松，枯枝又倒下了。
"BST 的问题就在这儿——数据是按顺序来的。如果你逐条插入，最后得到的不是一棵树，而是……"他指了指地上，"一条躺在泥里的树枝。"
然后他从背包里掏出一棵奇怪的小树苗。它的根深深地扎在土里，左右两侧显著对称——左侧和右侧的枝叶数量差不多。
"这棵不一样。不管你怎么插数据进去，它都会自己纠正歪斜。左右两边的高度差永远不超过1。"
他把标签纸往树苗的根附近一插，树苗"咔"地动了一下——左侧的枝叶微微向右旋转了一些。
"它在转。"
你的任务
本章分层
- 必读：理解为什么需要平衡树（BST 退化的本质）；AVL 树的平衡因子和四种旋转（有图+一两个例子）；红黑树的核心性质（五条规则）；理解工业界选红黑树而非 AVL 的原因（旋转次数的权衡）
- 选读：AVL 插入的完整实现；红黑树插入修复的概况
- 深水区：红黑树删除（完整 case）；2-3 树与红黑树的对应关系；B+ 树的设计——全部放到附录/数据库卷深入
本章不会要求你掌握
- 红黑树删除的 case 细节
- 2-3 树的完整分裂步骤
- B+ 树的满节点插入和删除——在数据库卷中详细展开
上一章的 BST 有个致命问题——插入有序数据时代化成链表，查找从 O(log n) 变成 O(n)。今天的任务是搞清楚计算机科学家们想了什么办法来"救"它。
你的核心目标是：理解为什么需要平衡树，能解释 AVL 与红黑树的取舍。
需要了解的内容：
- AVL 树 — 最早的平衡树发明，用"旋转"来保持平衡
- 红黑树 — 工业界使用最广泛的平衡树，用"颜色"来维持约束
- 为什么 Java 的
TreeMap用红黑树而不是 AVL 树？——旋转次数与查找效率的权衡 - （选读）2-3 树 — 红黑树的设计蓝图，放在附录
- （选读）B 树与 B+ 树 — 数据库卷中深入
遭遇战 → 获得技能
① AVL 的平衡因子——树的自测量尺
AVL 树（以发明者 Adelson-Velsky 和 Landis 命名）的定义异常简单：
任何节点的左右子树高度差不超过 1。
这个"高度差"就叫平衡因子（Balance Factor）：
平衡因子 = 左子树高度 - 右子树高度允许的取值范围：{-1, 0, 1}。
超出这个范围 → 不平衡 → 需要旋转来修复。
来看一个不平衡的树：
10 ← 平衡因子 = 2（左子树高度 2，右子树高度 0）
/
5 ← 平衡因子 = 0（左右子树高度相同）
/
3 ← 平衡因子 = 010 的左边比右边高 2——左边路径太长了。需要把结构"旋转"一下。
先看一个 AVL 节点是怎么定义的——比普通 BST 节点多一个高度字段：
class AVLNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1 # 新节点的高度初始为 1（叶节点高度为 1）** Java 差异：**
javaclass AVLNode { int val, height; AVLNode left, right; AVLNode(int val) { this.val = val; this.height = 1; } }
② AVL 四种旋转——把歪的树"拧回来"
AVL 的不平衡只有四种模式，对应四种修复手法。
模式 1：LL（左左）——右旋
插入在"左子树的左子树"上导致的不平衡：
10
/
5
/
3修复方法——右旋：把中间节点 5 提上来作根，10 变成它的右孩子。
def _rotate_right(self, y):
"""右旋——解决 LL 情况"""
x = y.left
T2 = x.right
# 旋转
x.right = y
y.left = T2
# 更新高度（先更新 y 再更新 x，因为 y 现在是 x 的孩子）
y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))
return x # 新的根右旋的效果：
y x
/ \ / \
x T3 ==> T1 y
/ \ / \
T1 T2 T2 T3模式 2：RR（右右）——左旋
跟 LL 对称——插入在"右子树的右子树"上。
def _rotate_left(self, x):
"""左旋——解决 RR 情况"""
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))
y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
return y模式 3：LR（左右）——先左旋再右旋
插入在"左子树的右子树"上——单一的右旋搞不定，因为 5 的右子树比左子树深。
10
/
5
\
8修复：先对 5 做左旋（变成 LL 模式），再对 10 做右旋。
# 在平衡修复逻辑中，LR 的处理方式是：
root.left = _rotate_left(root.left) # 先左旋左孩子
return _rotate_right(root) # 再右旋当前节点模式 4：RL（右左）——先右旋再左旋
跟 LR 对称。
# RL 的处理方式：
root.right = _rotate_right(root.right) # 先右旋右孩子
return _rotate_left(root) # 再左旋当前节点把这四种旋转整合到插入操作里——每次插入后沿着路径回溯，如果发现节点不平衡，就按四种模式之一旋转：
def _get_balance(self, node):
"""计算平衡因子"""
if node is None:
return 0
return self._get_height(node.left) - self._get_height(node.right)
def insert(self, node, val):
"""AVL 插入——插入后自动平衡"""
# 第1步：标准的 BST 插入
if node is None:
return AVLNode(val)
if val < node.val:
node.left = self.insert(node.left, val)
elif val > node.val:
node.right = self.insert(node.right, val)
else:
return node # 重复值不处理
# 第2步：更新当前节点的高度
node.height = 1 + max(self._get_height(node.left),
self._get_height(node.right))
# 第3步：检查平衡因子，判断是否需要旋转
balance = self._get_balance(node)
# LL 情况
if balance > 1 and val < node.left.val:
return self._rotate_right(node)
# RR 情况
if balance < -1 and val > node.right.val:
return self._rotate_left(node)
# LR 情况
if balance > 1 and val > node.left.val:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
# RL 情况
if balance < -1 and val < node.right.val:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node运行测试：
pythonavl = AVLTree() root = None for v in [10, 20, 30, 40, 50, 25]: root = avl.insert(root, v) # 插入后树是平衡的——高度约 log₂(n) # 如果普通 BST 插入 [10,20,30,40,50]，会退化成一条链 # AVL 插入同样的序列，树会"拧"回平衡态
AVL 删除的思想类似，但多了一个额外的步骤——删除后沿着路径回溯检查平衡因子，需要旋转也同样用那四种模式。
③ 红黑树——工业界的王者
AVL 树有一个缺点：太严格了。它要求左右子树高度差不超过1，这意味着每次插入都有可能触发旋转——甚至一路旋转到根。
现实世界需要一种更宽松的平衡约束，牺牲一点查找效率来换取更少的旋转次数。
这就是红黑树（Red-Black Tree）。
红黑树的五条性质
- 每个节点要么是红色，要么是黑色
- 根节点是黑色
- 叶节点（NIL/空节点）是黑色
- 红色节点的子节点必须是黑色（即不能有两个连续的红色节点）
- 从任意节点到其每个叶节点的所有路径包含相同数量的黑色节点
这五条规则确保了红黑树的核心保证：最长路径不超过最短路径的两倍。
为什么？规则4限定了红色不能连续出现，规则5限定了黑色数量在各路径上相等。一个路径上，如果红色节点能穿插在黑色节点之间，最多的情况是红黑交替（路径长度就是黑色数×2），最少的情况是全黑（路径长度就是黑色数×1）。所以最长的路径 = 最短路径 × 2。
这比 AVL 的严格平衡（1以内）宽松，但足够保证 O(log n) 的查找效率。
红黑树的节点定义
class RBNode:
"""红黑树节点——比普通节点多一个颜色字段"""
def __init__(self, val, color='RED'):
self.val = val
self.left = None
self.right = None
self.color = color # 'RED' 或 'BLACK'
self.parent = None # 红黑树需要父指针（旋转时需要）注意： 红黑树需要父指针，而 AVL 不需要——AVL 沿着递归回溯就能修复平衡，红黑树的旋转操作需要知道父节点是谁。这是实现上最关键的区别。
** Java 差异：** Java 的
TreeMap内部实现Entry<K,V>就有color、left、right、parent四个字段：java`static final class Entry<K,V> implements Map.Entry<K,V>` { K key; V value; `Entry<K,V> left;` `Entry<K,V> right;` `Entry<K,V> parent;` boolean color = BLACK; }
④ 红黑树插入——着色 + 旋转
新插入的节点默认是红色。为什么选择红色？因为插入红色节点不会违反规则5（黑色节点数量不变），只可能违反规则4（红色节点产生了连续红色）。
"产生连续红色"这个冲突叫"双红违规"（Double Red Violation）。修复双红有三种情况：
情况 1：叔叔节点是红色
最简单的修复——颜色翻转（Color Flip）：
插入前： 插入后：
B(黑) B(红)
/ \ / \
R(红) R(红) ← 叔叔 B(黑) B(黑) ← 叔叔变黑
/
R(新)把父节点和叔叔节点都变成黑色，祖父节点变成红色。如果祖父的父节点也是红色，就把问题向上传递。
情况 2：叔叔节点是黑色（或 NIL），新节点在"外侧"（左左/右右）
需要旋转 + 变色：
G(黑) P(黑)
/ \ / \
P(红) U(黑) ==右旋+变色==> N(红) G(红)
/ \
N(红) U(黑)情况 3：叔叔节点是黑色（或 NIL），新节点在"内侧"（左右/右左）
先对父节点旋转一次转换为情况2，再按情况2处理。
这跟 AVL 的四种旋转模式有惊人的相似之处——只是多了颜色处理。
下面是一个简化的红黑树插入修复逻辑（父节点为红色时的处理）：
def _fix_insert(self, node):
"""红黑树插入修复"""
while node != self.root and node.parent.color == 'RED':
parent = node.parent
grandparent = parent.parent
if parent == grandparent.left: # 父节点是祖父的左孩子
uncle = grandparent.right
if uncle and uncle.color == 'RED':
# 情况 1：叔叔是红色——颜色翻转
parent.color = 'BLACK'
uncle.color = 'BLACK'
grandparent.color = 'RED'
node = grandparent # 向上传递
else:
# 叔叔是黑色（或 NIL）
if node == parent.right:
# 情况 3（LR）：先左旋父节点，转换为情况2
node = parent
self._rotate_left(node)
parent = node.parent
# 情况 2（LL）：右旋祖父节点 + 变色
parent.color = 'BLACK'
grandparent.color = 'RED'
self._rotate_right(grandparent)
else:
# 对称情况：父节点是祖父的右孩子
# （RL 和 RR 的镜像处理）
uncle = grandparent.left
if uncle and uncle.color == 'RED':
parent.color = 'BLACK'
uncle.color = 'BLACK'
grandparent.color = 'RED'
node = grandparent
else:
if node == parent.left:
node = parent
self._rotate_right(node)
parent = node.parent
parent.color = 'BLACK'
grandparent.color = 'RED'
self._rotate_left(grandparent)
self.root.color = 'BLACK' # 规则 2：根始终是黑色这段代码看着长，但模式很固定：
外侧插入（LL/RR） → 转一次 + 变色 内侧插入（LR/RL） → 转两次 + 变色 叔叔是红色 → 只变色，不旋转
** Java 差异：** Java 的
TreeMap.put中，插入修复逻辑一模一样。fixAfterInsertion方法在TreeMap.java第 2100 行左右，核心就是一个 while 循环加左右两个对称分支。Oracle JDK 的代码跟你上面看到的伪代码结构完全一致。
** C++ 差异：** C++ 标准库的
std::map（内部是红黑树）同样的逻辑。但你不会直接看到这段代码——C++ STL 的实现更底层，用了很多指针操作和宏。真正去看 GNU libstdc++ 的_Rb_tree实现时，你会发现它用了一个哨兵节点_M_header而不是nullptr来表示 NIL——这个技巧简化了很多边界判断。
⑤ 为什么 TreeMap 选红黑树而不是 AVL ？
这是面试高频题。答案的关键在一个词上——插入密集度。
| 特性 | AVL 树 | 红黑树 |
|---|---|---|
| 查找速度 | 更快（严格 O(log n)） | 稍慢（最多 2log n） |
| 插入/删除性能 | 需要更多旋转 | 需要更少旋转（最多 3 次旋转修复） |
| 实现复杂度 | 相对简单 | 更复杂 |
| 空间开销 | 存高度（整数） | 存颜色（1 位） |
Java 的 TreeMap 是通用组件——你要拿它做插入、删除、查找各种操作。对通用组件来说，写操作的效率比读操作更关键。红黑树在插入/删除上的旋转次数远少于 AVL（红黑树插入最多 2 次旋转，删除最多 3 次，而 AVL 可能会有 O(log n) 次旋转），所以选红黑树。
反过来，如果你的场景是读远多于写（比如只建一次，然后疯狂查询），AVL 树可能是更好的选择。
红黑树删除——不说你也知道它更复杂
红黑树删除属于深水区，面试极少考到，工作中也没人手写。 了解核心思想即可，不必记忆 case。
删除比插入复杂得多。这里只讲核心思想，不展开全部代码。
红黑树删除的核心冲突不同于插入：当你删掉一个黑色节点时，规则5就会被打破——路径上的黑色节点数少了一个。
这个现象叫"双黑"（Double Black）。修复策略包括：
- 兄弟节点是红色 → 旋转 + 变色，转化为兄弟黑色时的情况
- 兄弟节点是黑色，兄弟的两个孩子都是黑色 → 兄弟变红，向上传递"双黑"
- 兄弟节点是黑色，兄弟的靠近节点一侧的孩子是红色 → 先旋转转换为情况4
- 兄弟节点是黑色，兄弟的远离节点一侧的孩子是红色 → 旋转 + 变色，结束
红黑树删除修复的核心思想：把"双黑"问题向上推，直到能用一个旋转+变色彻底解决。
不用背下所有case。知道为什么红黑树删除复杂就够了：黑色被删 → 路径黑数不相等 → 需要从兄弟节点"借"黑色 → 借的过程涉及各种拓扑关系和颜色约束。
选读：2-3 树——红黑树的设计蓝图
本节是附录内容，不影响主线。 2-3 树是理解红黑树设计思想的桥梁，跳过也不妨碍你理解平衡树的概念。
你可能从没见过 2-3 树，但红黑树的所有设计其实都来自它。
2-3 树的核心特点：每个节点可以有 1 个值（2-节点）或 2 个值（3-节点）。
2-节点： 3-节点：
[5] [3 | 8]
/ \ / | \
[1] [9] [1] [5] [10]2-3 树是完美平衡的：所有叶节点在同一个深度。因为它的增长机制不是"向下加节点"——而是"向上分裂"。
当一个 3-节点插入新值变成 4-节点时，中间的数值会向上冒泡：
[3 | 8] [3 | 5 | 8] [5]
/ | \ ==> / | \ ==> / \
[1] [5] [10] [1] [ ] [10] [3] [8]
/ \
[1] [10]你看——2-3 树用"节点分裂 + 向上传递"实现了完美平衡。
红黑树本质上是 2-3 树在二叉树上的编码。怎么编码的？
把 3-节点用红色链接表示。 红黑树中的红色节点，本质上就是"跟父节点一起构成一个 3-节点"。
2-3树中: 红黑树中:
[3 | 8] ==> B(8)
/
R(3)这就是为什么红黑树的性质4规定"红色节点不能有红色子节点"——因为一个 3-节点最多包含两个值，三个值就会分裂。
理解了这个对应关系，红黑树的五条性质就不再是死记硬背的规则，而是"把 2-3 树编码为二叉树时的自然结果"。
B 树与 B+ 树——当树大到磁盘装不下（附录/数据库卷预览）
本节作为概念预览。 B+ 树是数据库系统和文件系统的核心数据结构，将在 数据库卷 中详细展开。
以上所有的树都假设数据在内存中。但当你有 1 亿条记录时——内存装不下，大部分数据在磁盘上——情况就变了。
磁盘的物理特性： 读取一个字节和读取一个数据页（通常 4KB~16KB）的延迟基本上是一样的——因为大头在寻道时间和旋转延迟，而不是传输时间。所以：
磁盘上，一次 I/O 能读更多的数据 == 减少 I/O 次数 == 更快。
B 树（B-Tree）的核心思想：每个节点存储更多键值，减少树的高度。
B树节点（阶数=3，每个节点最多存 2 个值、3 个孩子）：
[20 | 40]
/ | \
[1|10] [25|30] [50|60]树的高度 ≈ log_M(n)，其中 M 是节点的大小（每个节点存多少个键）。如果 M=1000、n=10亿，高度 ≈ log_1000(1e9) ≈ 3！
查找只需要 3~4 次磁盘 I/O——比二叉树的 30 次快了一个数量级。
B+ 树的改进：
B+ 树是 B 树最常用的变体。两者的核心区别：
| 特性 | B 树 | B+ 树 |
|---|---|---|
| 内部节点存储数据 | 是 | 否（只存索引键） |
| 叶节点存数据 | 是 | 是 |
| 叶节点间有链表相连 | 否 | 是 |
| 范围查询效率 | O(n) 遍历 | O(log n) 找到起点后链式遍历 |
B+ 树用两个设计赢得了工业界（MySQL InnoDB、PostgreSQL 索引、文件系统）：
- 内部节点只存键——一个节点能存更多的键 → 树更矮 → I/O 更少
- 叶节点的链表连接——范围查询（如
WHERE id BETWEEN 10 AND 100）找到起点后沿着链表走，不用在树上反复查找
来看一个 B+ 树的示意图：
内部节点（只索引）：
[30 | 60]
/ | \
[...] [...] [...]
叶节点（数据 + 链表）：
[10→20→30] → [40→50→60] → [70→80→90]
↑——————链表连接——————↑** Java 差异：** Java 没有内置的 B 树/B+ 树实现。数据库系统（如 H2、Derby）有自己的实现。MySQL InnoDB 的索引结构默认是 B+ 树——每个表的主键索引都是 B+ 树。
** C++ 差异：** C++ 也没有标准库 B 树实现。Google 的 LevelDB 和 Facebook 的 RocksDB 用 LSMTree（Log-Structured Merge-Tree），这是另一种不同的磁盘数据结构——它将随机写转化为顺序写，在写密集场景下优于 B+ 树。
常见陷阱
场景 1：AVL 插入后忘更新高度
这是 AVL 实现里最常见的 bug——旋转之后忘了重新计算节点高度。
def _rotate_right(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
# 漏掉了：y.height = ...
# 漏掉了：x.height = ...
return x如果不更新高度，_get_balance 算出来的是旧高度——下一次插入时平衡判断会出错，旋转结果完全不对。
场景 2：红黑树忘记把根设为黑色
性质2要求根是黑色。插入修复函数的最后一行是 self.root.color = 'BLACK'——为什么需要这个？因为在情况1的颜色翻转中，祖父节点可能被染成红色。如果祖父节点碰巧是根，你就违反了性质2。加上最后那行强制保底。
场景 3：AVL vs 红黑树——选错场景
有人把红黑树用在"只建一次、查一亿次"的场景里。同样 O(log n) 的查找，AVL 更严格，查找更快（因为树更矮）。红黑树在查找密集型场景下不是最优选择。
反过来，在频繁插入删除的场景用 AVL，每次 O(log n) 的旋转加起来比红黑树多——拖慢整体性能。
通关挑战
🗡 热身（20 分钟必做）
- 画出一棵 AVL 树插入 [30, 20, 10] 后的每一步变化——注意旋转时机
- 对着上面的 AVL 插入代码，手写一次插入 [30, 20, 10, 40, 50] 的完整过程
- 口述红黑树五条性质，加上为什么要这五条
- 解释 2-3 树中 3-节点插入变成 4-节点的分裂过程
** 挑战（45 分钟选做）**
- AVL 完整实现： 补全 AVL 树的删除方法。思路：BST 删除 + 沿路径回溯修复平衡因子。
- 红黑树插入可视化： 写一个程序，输入插入序列，输出每一步后的树结构（节点附带颜色标记）。
- 查找比较： 在同一数据集上分别用 BST 和 AVL 树做 10 万次查找——记录平均耗时。用有序数据插入后对比更明显。
- B+ 树模拟： 用 Python 简单实现一个 B+ 树节点（不需要完整增删），验证"内部节点只存索引，叶节点存数据+链表"的机制。
** 排障**
| 问题 | 最常见原因 |
|---|---|
| AVL 插入后树不平衡 | 旋转后忘了更新左右子树的高度 |
| 红黑树双红违规修复不完整 | while 循环没正确向上传递 case 1 的冲突 |
| 插入后根的颜色不是黑色 | 忘了在修复函数最后强制设根为黑 |
| 旋转后子节点链接断裂 | 旋转时 T2（中间子树）的交接搞反了方向 |
验收标准
- [ ] 能手画 AVL 的四种旋转（LL/RR/LR/RL），并能用代码实现
- [ ] 能口述红黑树的五条性质，并用一条规则解释"最长路径不超过最短路径的两倍"
- [ ] 能解释"为什么 TreeMap 用红黑树而不是 AVL"（旋转次数 vs 查找效率的权衡）
- [ ] 能说出 2-3 树和红黑树的对应关系（3-节点 = 红链接）
- [ ] 能说出 B+ 树相比 B 树在范围查询上的优势
- [ ] 已完成热身的 4 道题目
常见卡点
1. 四种旋转记混了
不用死记名称。记住一条规律就够了：
- 往哪边歪就往反方向拧
- LL（左左）→ 右旋。RR（右右）→ 左旋
- LR（左右）→ 对左孩子左旋变成 LL → 再右旋
- RL（右左）→ 对右孩子右旋变成 RR → 再左旋
2. 红黑树的"双红"修复记不住
把红黑树的插入修复想象成"跟叔叔商量"：
- 叔叔是红色 → 大家一起变色（父亲、叔叔变黑，祖父变红）
- 叔叔是黑色 → 旋转 + 变色（看你是左边还是右边）
3. 2-3 树和红黑树的对应搞不明白
最关键的对应关系：红色节点就是跟它的父节点"绑定"在一起，共同构成一个 3-节点。 所以红色节点的父节点一定是黑色——否则一个 3-节点里不会有连续两个红色。
4. B 树阶数（order）vs 度的概念
不同教材里"阶"的定义不同。有些说"阶 = 最大孩子数"，有些说"阶 = 最小度数"。统一认识：MySQL InnoDB 的 page 大小是 16KB，一个 B+ 树节点就是 16KB。整型键（4 字节）+ 指针（6 字节）≈ 10 字节。16KB / 10 ≈ 1638。所以 InnoDB 的 B+ 树每个节点大约能存 1600 个键——三层树能索引 1600³ ≈ 40 亿条记录。这就是为什么 InnoDB 的主键索引深度很少超过 4 层。
现在不需要理解
- 红黑树删除的全部 case 细节 — 面试极少考，工作中没人手写红黑树
- B 树的分裂算法（满节点插入的完整过程） — 数据库课程会系统讲
- 为什么 Python 没有内置 TreeMap — Python 设计哲学（只有一只明显正确的方法）
- 伸展树（Splay Tree）、替罪羊树（Scapegoat Tree） — 其他自平衡方案，不同应用场景
- B+ 树的并发控制（锁分裂、B-link 树） — 高级数据库话题
旅人笔记
平衡树的故事，是计算机科学里关于"trade-off"的一个经典案例。
BST 是最自然的分支结构——但太脆弱。AVL 用"高度差 ≤ 1"的简单规则解决了退化问题——但旋转太频繁。红黑树放松了约束，用"最长路径 ≤ 2× 最短路径"换来了更少的旋转——但代码更复杂。B 树/B+ 树则换了一个完全不同的关注点——不再纠结于内存里的旋转次数，而是去减少磁盘 I/O。
每一种"改进"都不是简单的"更好"，而是在某个维度上做出牺牲、在另一个维度上获得收益。
Java 的 TreeMap 选择红黑树，是因为在通用场景下，写操作的旋转次数是最稀缺的资源。MySQL InnoDB 选择 B+ 树，是因为 磁盘 I/O 次数才是最稀缺的资源。
所以当有人问你"哪种树最快"，正确的回答不是"红黑树"不是"AVL"也不是"B+树"——而是"得看你的场景"。
从 AVL 到红黑树再到 B+ 树，其实是一个思维转变过程：
- AVL：关注"数学上的完美平衡"（严格 1 以内）
- 红黑树：关注"操作层面的效率平衡"（更少旋转）
- B+ 树：关注"物理层面的效率平衡"（更少 I/O）
这三种关注点，在不同场景下都是正确的选择。
→ 下一站预告
树的故事暂时告一段落——但不是结束。下一章我们要从"树"这种非线性结构转向另一种跟树有密切关系的结构：堆。
二叉树里的节点，我们关注的是"左小右大"的排列规则。而堆里，我们关注的是另一种规则——父节点要么大于等于所有子节点（最大堆），要么小于等于所有子节点（最小堆）。堆跟 BST 有一个关键的差异：BST 用来查找，堆用来维护最值。
这种差异导致了完全不同的底层实现——堆用数组存储，根本不需要指针。你会看到 PriorityQueue 的 O(log n) 入队出队机制、堆排序的原理、以及 Top-K 问题的最优解法。
第7章：堆与优先队列。