适用读者：背过"红黑树和 AVL 都是平衡树"但说不出差别的人。
前置：S03-B02。
实测环境：Python 3.12.3（自实现 BST/AVL 并测树高）；实测日期 2026-11-05。
覆盖旧文：A-1505（BST，0 点空壳，本篇补写）、A-1506（AVL，189 点）、A-1507（2-3 树，92 点）、A-1508（红黑树，203 点）、A-1504（Trie，152 点）= 636 点。
覆盖扩展：E-S03-004（跳表）、E-S03-005（B+ 树与磁盘 IO）。
上一篇：S03-B05 · 堆：只要最大值，为什么要维护整棵树
下一篇：S03-B07 · 图与并查集。
1. 一句话结论
所有"平衡树"都在解决同一个问题：BST 会退化成链表。差别只在"用多严格的平衡，换多高的维护成本"。
| 结构 | 平衡条件 | 旋转/调整 | 典型用途 |
|---|---|---|---|
| BST | 无（有序 + 左小右大） | 无 | 教学、随机数据 |
| AVL | 左右子树高度差 ≤ 1 | 旋转频繁（严格） | 读多写少、内存索引 |
| 红黑树 | 黑高一致 + 红节点不相邻 | 旋转少、靠变色 | TreeMap、epoll、内核 |
| 2-3 树 / B 树 | 节点多路 | 分裂/合并 | 磁盘、数据库索引 |
| Trie | 按字符分层 | 无 | 前缀搜索、自动补全 |
2. 实测：BST 退化有多严重
5,000 个整数，三种插入方式（自实现，测树高）：
| 场景 | 树高 | 说明 |
|---|---|---|
| BST + 有序插入（0…4999） | 5,000 | 完全退化成链表 |
| BST + 随机插入 | 29 | 期望约 2·log₂n ≈ 26 |
| AVL + 有序插入 | 13 | 约 1.44·log₂n ≈ 17，实测更优 |
结论：BST 的性能完全取决于插入顺序——有序数据（时间戳、自增 ID）是最坏情况。这就是"为什么需要平衡树"的实证，不是理论担忧。
顺带说明：为什么"随机插入"树高是 ~2log₂n 而不是 log₂n？因为随机 BST 的期望高度是
4.311·ln n ≈ 2.99·log₂n（经典结果），实测 29 与理论 26 同量级。
3. BST：定义与补写（旧文 A-1505 是空壳）
定义：对任意节点，左子树全部小于它，右子树全部大于它（不允许重复或约定重复在右侧）。
| 操作 | 平均 | 最坏（退化） |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
| 中序遍历 | O(n) 且天然有序 | 同 |
BST 的真正价值：中序遍历 = 有序序列。所以"范围查询/前驱后继"是它的强项（哈希表做不到）。
删除的三种情况（这也是补写内容）：
| 情况 | 做法 |
|---|---|
| 叶子节点 | 直接删 |
| 只有一个孩子 | 用孩子顶替 |
| 有两个孩子 | 用右子树最小值（或左子树最大值）顶替，再删那个最值节点 |
4. AVL：用严格平衡换查询速度
平衡条件：每个节点左右子树高度差（平衡因子）∈ {−1, 0, 1}。
四种失衡与旋转：
| 失衡形态 | 旋转 |
|---|---|
| LL（左左） | 右旋一次 |
| RR（右右） | 左旋一次 |
| LR（左右） | 左旋 + 右旋 |
| RL（右左） | 右旋 + 左旋 |
代价：插入/删除后可能要沿路径回溯调整，写操作成本更高。所以：
| 场景 | 适合 |
|---|---|
| 读远多于写、要求最坏 O(log n) | AVL |
| 读写混合、可接受"近似平衡" | 红黑树 |
5. 红黑树：折中在哪里
五条性质（记这五条就够）：
- 节点非红即黑；
- 根是黑；
- 叶子（NIL）是黑；
- 红节点的子节点必须是黑（不能连续红）；
- 任一节点到其叶子的路径上黑节点数相同（黑高一致）。
由此推出的关键结论：最长路径 ≤ 2 × 最短路径，所以树高 ≤ 2·log₂(n+1) —— 近似平衡，但不严格。
| 对比 | AVL | 红黑树 |
|---|---|---|
| 树高 | 更矮（1.44 log n） | 略高（≤ 2 log n） |
| 插入旋转次数 | 可能多次（回溯） | ≤ 2 次 |
| 删除旋转 | 可能 O(log n) | ≤ 3 次 |
| 查询略慢、写入更快 | — | ✅ |
工程判据："写多"选红黑，"读多且要求最坏性能"选 AVL。JDK TreeMap、Linux epoll 的 fd 集合都用红黑树。
6. 2-3 树 / B 树：为磁盘而生（E-S03-005）
二叉树每个节点只有 2 个孩子 → 树高 log₂n。磁盘每次读一个"块"（4 KB），如果块里只能放 2 个 key，太浪费。
| 结构 | 分叉 | 树高（n=10⁹） | IO 次数 |
|---|---|---|---|
| 二叉树 | 2 | ~30 | 30 次随机 IO |
| B+ 树（分叉 100+） | 100–1000 | 3–5 | 3–5 次 |
这就是数据库索引用 B+ 树而不是红黑树的原因：减少磁盘 IO 次数，而不是减少比较次数。细节归 S11（数据库）。
7. Trie：按字符分层
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 插入/查询 | O(L)（L 为串长） | 与集合大小无关 |
| 前缀查询 | O(L) | 天然支持 |
| 空间 | 较大（每节点存子节点表） | 可用压缩 Trie 优化 |
用途：自动补全、敏感词过滤、IP 路由（最长前缀匹配）、拼写检查。
判据："要不要按前缀找？" 要 → Trie；只要精确找 → 哈希表。
8. 跳表：平衡树的替代（E-S03-004）
用"多层链表 + 随机层高"实现 O(log n) 查找，不需要旋转，实现比红黑树简单。Redis 的有序集合（ZSet）就用跳表。
| 对比 | 红黑树 | 跳表 |
|---|---|---|
| 实现复杂度 | 高（旋转/变色） | 低 |
| 范围查询 | 中序遍历 | 天然（链表） |
| 最坏性能 | 有保证 | 概率保证 |
| 并发友好 | 差（旋转影响全局） | 较好 |
9. 五个误区
| 误区 | 真相 |
|---|---|
| "BST 查找是 O(log n)" | 只在平衡时；有序插入退化成 O(n)（实测树高 5000） |
| "红黑树是严格平衡" | 是近似平衡（最长 ≤ 2× 最短） |
| "AVL 一定优于红黑" | 写多场景红黑更快（旋转少） |
| "数据库索引用红黑树" | 用 B+ 树（减少磁盘 IO） |
| "Trie 比哈希快" | 只在"前缀查询"场景；纯精确查找哈希更快 |
10. 自检
- 为什么有序插入会让 BST 退化成链表？实测树高多少？
- AVL 的四种失衡分别怎么旋转？
- 红黑树五条性质中，哪一条导致了"最长 ≤ 2×最短"？
- 数据库为什么用 B+ 树而不是红黑树？
- 什么场景该用 Trie 而不是哈希表？
11. 下一篇
S03-B07 · 图与并查集：连通性怎么维护
树是"无环连通图"。下一篇进入一般图：邻接表/矩阵的取舍、BFS/DFS、拓扑排序，以及并查集为什么能在近似 O(1) 内回答"两个点是否连通"（实测：朴素 5,789 ms → 路径压缩 185 ms）。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1504/1505/1506/1507/1508；扩展点 E-S03-004/005。树高实测（5,000 / 29 / 13）为 2026-11-05。