树与层级结构：权力的架构

效率的形状

在一个扁平的世界（数组）里，找东西是件苦差事。你必须检查街上的每一栋房子 ($O(N)$)。 在一个层级的世界（树）里，找东西很容易。你先问国家，再问州，然后问城市，最后问街道。只需几个问题 ($O(\log N)$)，你就能精准地找到所需。

树是 “分而治之” 的物理体现。它们通过将问题分解为子问题来解决问题，通过严格的父级控制来管理巨大的复杂性。

分支的策略

在本章中，我们将探索不同的树结构如何解决不同的工程问题：

树的三大法则

1. 高度即成本： 找到任何东西所需的时间与树的高度成正比。一棵矮胖的树（B 树）比一棵瘦高的树要快。
2. 平衡是关键： 一棵向右倾斜太严重的树本质上就变成了链表 ($O(N)$)。AVL 和红黑树等算法的存在纯粹是为了保持树的“平衡”。
3. 从根到叶： 所有逻辑自上而下流动。要解决一个节点的问题，你通常依赖于它的孩子提供的答案（递归）。

小结

在本章中，我们将看到数据库、文件系统和内存分配器如何使用层级结构来管理世界的信息。我们将明白，有时候，处理自由的最好方法是施加一点点结构。

让我们从万树之祖开始：二叉搜索树。