树：二叉树、BST 与堆
环境：Windows 11 x64，GCC 13.1.0，
g++ -std=c++17 -O2。所有高度、耗时都是本机实测，遍历实现经过 500 棵随机树对拍验证。
一、三种遍历：递归与显式栈必须互相验证
void pre_rec(TNode *t, vector<int> &o) { if (!t) return; o.push_back(t->v); pre_rec(t->l,o); pre_rec(t->r,o); }
void in_rec(TNode *t, vector<int> &o) { if (!t) return; in_rec(t->l,o); o.push_back(t->v); in_rec(t->r,o); }
void post_rec(TNode *t, vector<int> &o) { if (!t) return; post_rec(t->l,o); post_rec(t->r,o); o.push_back(t->v); }迭代版：前序用单栈（先压右再压左），中序用”一路向左压栈”，后序用双栈（前序的变体再倒序输出）。
500 棵随机树，前序/中序/后序的递归版与迭代版全部一致=1
树 {50,30,70,20,40,60,80}
前序 = 50 30 20 40 70 60 80
中序 = 20 30 40 50 60 70 80
后序 = 20 40 30 60 80 70 50
中序是否已排序：1三个必须内化的事实：
- 中序遍历 BST 得到升序序列——这是 BST 的定义性性质，也是验证一棵树是否合法的最快方法（
std::is_sorted）。 - 前序 + 中序（或后序 + 中序）能唯一确定一棵二叉树；前序 + 后序不能（无法区分只有左孩子和只有右孩子）。
- 层序遍历用的是队列，不是栈，它才是”逐层”的那个。
递归转迭代时，显式栈里存的不是”节点”而是续作——后序的双栈技巧本质是把”左右根”倒过来生成。深度无界的树（比如从日志构建的表达式树）必须用迭代版，否则栈溢出。
二、BST：输入顺序决定它是树还是链表
1 万个整数依次插入，三种输入：
已排序输入 节点 10000 高度 10000 （log2 n ≈ 13.3）
随机打乱输入 节点 10000 高度 34
随机值(可能重复) 节点 10000 高度 31有序输入让 BST 彻底退化成链表，高度 = 节点数，查找从 O(log n) 变成 O(n)。随机输入的高度约 2.5·log₂n（34 vs 13.3），比理想值高但仍是 O(log n)。
这就是为什么”平衡”是 BST 的核心工程问题。三条应对路径：
| 方案 | 做法 | 代价 |
|---|---|---|
| AVL | 严格平衡（左右高度差 ≤ 1） | 查找最快，插入/删除旋转多 |
| 红黑树 | 近似平衡（最长路径 ≤ 2×最短） | 旋转少，插入删除更便宜 |
| 伸展树 / 跳表 | 均摊/概率平衡 | 实现简单（跳表）或访问局部性好 |
实践建议：不要手写 BST。 需要有序映射就用 std::map（红黑树）或 sorted vector + 二分；需要并发就用并发跳表。手写唯一有价值的场景是理解原理和面试。
顺带一个高频 bug：允许重复键时，v < (*t)->v 走左、否则走右，会让所有相等值一路往右堆成链。要么显式拒绝重复，要么用 std::pair<key, seq> 打破平局。
三、堆：数组实现的完全二叉树
parent(i) = (i - 1) / 2
left(i) = 2i + 1
right(i) = 2i + 2堆用数组存，不需要任何指针——这是它比树快的第一个原因（缓存友好、零分配）。验证堆性质只要一个循环：
父 ≥ 子 的检查：1；堆顶（最大值）= 2147481919建堆：O(n) 真的比 O(n log n) 快很多吗
300 万个随机整数：
make_heap 37.7 ms | 逐个 push_heap 45.1 ms（差 1.2 倍，结果一致=0）理论上 O(n) vs O(n log n)，实测只差 1.2 倍。 原因是那个理论太粗糙：逐个插入时，绝大多数元素落在数组末尾，向上 sift-up 的平均距离是常数（一半元素根本不用动，四分之一动一层……），所以增量建堆在实践中接近 O(n)。而 make_heap 的向下 sift-down 也只在少数高层节点上走长路。两者都是”线性时间 + 小常数”，差距自然小。
另一个更重要的观察：结果一致=0 不是 bug。 同一个多重集可以对应多个合法的堆数组，v1 == v2 本来就不该成立。验证堆只能验证”父 ≥ 子”这个不变式，或者比较排序后的结果——不能比较数组本身。这个坑在写测试时很容易踩。
Top-K：别全排序
300 万元素里取最大的 10 个：
全排序 420.2 ms | partial_sort 4.2 ms | nth_element 23.4 ms（三者前 10 之和都是 21474756296）partial_sort比sort快 100 倍（O(n log k) vs O(n log n)）。- 只要”最大的 k 个、不要求有序”就用
nth_element（平均 O(n)），比partial_sort还快 5 倍以上——上面三者求和相同，正说明选出的集合一致。 - 数据是流式/内存放不下时，用大小为 k 的小顶堆：新元素比堆顶大就替换，O(n log k) 时间、O(k) 内存。
选算法的顺序永远是：能不能不排序（nth_element）→ 能不能只排一部分（partial_sort）→ 才考虑全排序。
四、AVL 与红黑树：什么时候真的需要平衡树
std::map/std::set 就是红黑树。判断”要不要它”的三个问题：
- 需要有序遍历或范围查询吗？（
lower_bound/upper_bound/区间统计）→ 需要就用平衡树。 - 只有点查？ →
unordered_map通常快 10 倍（C++ 专栏第五节实测：30 万次访问 map 30.9ms vs unordered_map 3.1ms）。 - 数据构建后不再变？ → 排序数组 + 二分最快（第一节实测 sorted vector 8.9ms vs std::set 13.7ms），因为省掉了所有指针追逐。
也就是说：“需要有序”是平衡树存在的唯一理由。只要这个理由不成立，就换别的结构。
五、B+ 树：为什么数据库不用红黑树
把上面的逻辑推到磁盘上就得到 B+ 树。核心是一次 I/O 读一个页（4–16KB），所以要最大化每个节点能装的关键字数：
| 红黑树 | B+ 树（阶 200） | |
|---|---|---|
| 每节点关键字 | 1 | ~200 |
| 1000 万数据的高度 | ~24 | ~3 |
| 一次查找的磁盘读 | ~24 次 | 3–4 次 |
| 范围查询 | 中序回溯，随机 I/O | 叶子串成链表，顺序 I/O |
1000 万条记录，红黑树要从根走到叶子 24 层，每层一次磁盘寻道；B+ 树只需 3 层——这就是 InnoDB 用 B+ 树的全部理由（数据库专栏会展开）。
顺带解释一个常见误解：B 树和 B+ 树不是一回事。B+ 树把数据全部放叶子、非叶子只存索引、叶子用链表串联，因此范围查询和稳定性都更好；B 树每个节点都带数据，查找可能在中间层命中。数据库和文件系统几乎都用 B+ 树。
六、这一节的自查清单
- 遍历的递归版和迭代版用随机树互相验证，别只测一棵”教科书树”
- 验证 BST 用”中序是否升序”，验证堆用”父 ≥ 子”，不要比较堆数组是否相等
- 手写 BST 只在教学场景；生产用
std::map或 sorted vector - 插入有序数据到 BST 会退化成链表——这是真实事故（比如按时间戳建索引）
- Top-K 优先考虑
nth_element/partial_sort/ 大小为 k 的堆，最后才是sort - 只有点查用
unordered_map；需要有序才用map；构建后不变就用排序数组 - 树的递归深度无界时必须改迭代 + 显式栈
- 允许重复键时要有确定的打破平局规则，否则会退化成链
- 磁盘/Flash 上的索引结构按”页大小”设计，别按节点数量设计
下一节讲堆与优先队列：手写二叉堆的下沉上浮、std::priority_queue 的三个陷阱、Dijkstra 与堆的关系，以及为什么 make_heap 是 O(n)。