上一章的哈希表快而不有序。这一章的主角们把「有序」和「快」焊死在一起：搜索树——查找、插入、删除全部 O(log n)，而且时刻保持有序。STL 的 map/set，数据库索引的鼻祖，全是这一章。
🌲 二叉搜索树（BST）：一条规则定乾坤
任意节点 x：左子树所有 key < x 的 key < 右子树所有 key。
有了这条规则，查找像二分：比 x 小往左走，比 x 大往右走，走到空位就是插入位置。中序遍历 BST，输出天然有序 📈。
一切美好，直到有序插入出现：依次插入 1, 2, 3, 4, 5... 树退化成一条链，查找变 O(n) 💀——BST 的阿喀琉斯之踵。本章后面所有结构，都是为了杀死这根链子。
⚖️ AVL 树：严格平衡派
规则：每个节点的左右子树高度差 ≤ 1。只要插入/删除破坏了平衡，立刻用旋转（rotation）修复——O(1) 摆平。
核心动作是 trinode restructuring（三节点重构）：设 z 是失衡节点（离新节点最近的祖先）、y 是 z 较高的孩子、x 是 y 较高的孩子——把 x/y/z 三个节点按 key 重新排列，中间的当新根。四种失衡（LL/RR/LR/RL），一个套路全解决。
效果：树高被数学钉死在 1.44 × log n 以内，查找铁定 O(log n)。代价：插入/删除可能触发多次旋转（删除甚至 O(log n) 次）。读多写少选 AVL 📚。
🎲 伸展树（Splay Tree）：懒惰的智慧
不维护严格平衡，规则只有一条：每次访问一个节点，就把它「伸展」到根部（通过旋转）。
- 刚访问过的元素就在根上 → 再次访问 O(1)（缓存友好到极致）；
- 实现比 AVL 简单（不用记高度），删除尤其优雅；
- 代价：单次操作最坏 O(n)，但均摊 O(log n)——第 6 章 doubling 的均摊思想再次出场；
- 神级性质：不用任何额外内存就能记住「访问历史」→ 热点数据自动上浮。频率不均匀的场景（网络路由表）奇效 📡。
🌳 (2,4) 树：为多叉铺路
每个节点存 2~4 个孩子（1~3 个 key），所有叶子同层。插入超员就「分裂」，删除欠员就「合并/借用」。单个节点操作最多 O(1) 次重排，树高 O(log n)。
它本身不常直接用，但它是下一节红黑树的思维跳板——红黑树就是把 (2,4) 树「压扁」装进二叉节点里的产物 🧬。
🌑 红黑树：工程界的最终答案
二叉树 + 每个节点染红或黑，四条规则：
- 根是黑的；
- 红节点的孩子必须全黑（红不接红）；
- 任一到叶子的路径上，黑节点数目相同（黑高相等）；
- 空节点（NULL）视为黑叶子。
这套染色相当于「放松版 AVL」：树可能有点歪，但最长路径 ≤ 最短路径的 2 倍 → 高度仍是 O(log n)。插入/删除最多 O(1) 次旋转（对比 AVL 删除的 O(log n) 次）——写多读也多的场景，红黑树称王 👑。
C++ STL 的 std::map、Linux 内核的调度器、epoll——全靠红黑树撑着。面试高频：AVL vs 红黑树怎么选？ 查询密集选 AVL（更矮更快），修改密集选红黑树（旋转更少）。能答出这句话，本章就毕业了 🎓。
🎯 本章通关清单
- [ ] 画出插入 1~7 到 BST 的退化链，说明问题所在
- [ ] 演示 AVL 的 LL 失衡如何用一次旋转修复
- [ ] 解释伸展树「均摊 O(log n)」的含义
- [ ] 背出红黑树四条规则，说出它与 AVL 的选型差异
树的故事到红黑树暂告段落。下一章换一个视角：排序——把所有学过的结构用起来 🔀