多出的一维，足以改变整个搜索世界的格局。
0. 引言：为什么是树？
在顺序表、链表、栈和队列统治的线性世界里，所有数据排成一条单行的队伍。查找一个元素，要么遍历全场（O(N)），要么依赖二分法在有序数组中跳跃（O(log N)），然而数组的插入删除却要付出O(N)的移动代价。
树结构打破了“一对一”的桎梏，引入了分支与层次。它让查找、插入、删除在平均和最坏情况下获得了惊人的平衡——O(log N) 的复杂度，成为了数据库索引、文件系统、编译器和路由算法的基石。
本文将从最基础的二叉树开始，一路深入到自平衡树、B树族以及 Trie 树，揭示树形结构背后的设计哲学与工程取舍。
1. 二叉树（Binary Tree）：递归之美的起点
1.1 定义与性质
二叉树是每个节点最多有两个子树的树结构，通常称左子树和右子树。其递归定义带来天然的递归遍历算法。
关键性质：
第 i 层最多有 2^(i-1) 个节点（i≥1）。
深度为 k 的二叉树最多有 2^k - 1 个节点。
对任何非空二叉树，若叶子节点数为 n0，度为2的节点数为 n2，则 n0 = n2 + 1。
1.2 遍历体系
前序（根→左→右）：用于生成复制树或前缀表达式。
中序（左→根→右）：对二叉搜索树而言，输出有序序列。
后序（左→右→根）：用于释放树节点或计算表达式树。
层序：广度优先，借助队列实现。
三种深度优先遍历的递归写法看似简洁，但在深度过大时有栈溢出风险。迭代版本借助显式栈可规避，且能锻炼对状态机的理解。
1.3 存储方式
链式存储：每个节点包含 data、left、right 指针。
顺序存储：用数组按完全二叉树的编号存放，对任意节点 i（从1开始），左子为 2i，右子为 2i+1。这种方式仅适合完全二叉树，否则会大量浪费空间。
2. 二叉搜索树（BST）：秩序的确立
2.1 不变量
对任意节点，其左子树所有节点的键值小于该节点，右子树所有节点的键值大于该节点。这个约束将查找、插入、删除的时间复杂度收窄为 O(h)，其中 h 为树高。
在理想情况下，h = log N，但极端输入（如已排序序列）会退化成链表，h = N，导致操作降级为 O(N)。这就是平衡问题的源头。
2.2 删除操作的三种情况
叶子节点：直接删除。
只有左或右子树：将子节点提升到当前位置。
有两个子树：找到后继节点（右子树最左节点）或前驱节点（左子树最右节点），用其值替换当前节点，再递归删除该后继/前驱。
2.3 缺陷与改进
BST 的致命弱点是无自平衡能力。为了应对工业级场景（数据动态增删、不可预知顺序），自平衡二叉搜索树应运而生。
3. 自平衡二叉树：与退化赛跑
3.1 AVL 树：严格的高度平衡
AVL 树要求任意节点的左右子树高度差（平衡因子）绝对值 ≤ 1。插入或删除后，通过单旋（LL / RR）或双旋（LR / RL）恢复平衡。
旋转细节：
LL：对失衡节点的左子右旋。
RR：对失衡节点的右子左旋。
LR：先左旋左子，再右旋当前节点。
RL：先右旋右子，再左旋当前节点。
AVL 树保证了最坏情况下 h = 1.44 log N（近似），查找极快，但频繁的旋转在插入删除上开销较大。适用于读多写少的场景，如内存中的只读字典。
3.2 红黑树：弱平衡的艺术
红黑树放弃了严格的平衡条件，转而维护五条染色规则：
每个节点是红色或黑色。
根节点为黑色。
所有叶子节点（NIL）为黑色。
红色节点的子节点必须为黑色（即无连续红）。
从任一节点到其每个叶子的所有路径上，黑色节点数量相同。
这些约束保证了最长路径 ≤ 2 × 最短路径，即 h ≤ 2 log (N+1)。与 AVL 相比，插入和删除最多只需要 O(1) 次旋转（变色视为 O(1)），大幅减少调整成本。
工程应用：Linux CFS 调度器、Java HashMap（链表树化）、C++ std::map / std::set。红黑树是工业界最流行的自平衡树，在读写混合负载下表现优异。
4. 堆（Heap）：并非排序，而是优先
堆是一种完全二叉树，但它的核心能力不是搜索，而是快速获取极值。
最大堆：每个节点 ≥ 子节点。
最小堆：每个节点 ≤ 子节点。
4.1 数组实现
由于是完全二叉树，堆天然适合用数组存储。节点 i 的左子为 2i+1，右子为 2i+2，父节点为 floor((i-1)/2)。
4.2 核心操作
上浮（shift up）：插入元素时放在尾部，逐层与父节点比较交换，O(log N)。
下沉（shift down）：删除堆顶时，将尾部元素移至堆顶，然后与较大的子节点（最大堆）交换，O(log N)。
建堆（heapify）：从最后一个非叶子节点开始向下调整，时间复杂度 O(N)，不是 O(N log N)！
4.3 应用
堆排序（原地排序，不稳定）、优先队列（任务调度）、Top K 问题（小顶堆）、Dijkstra 算法中的距离松弛。
5. 多路搜索树：迈向磁盘的胜利
内存中的二叉树每下降一层只需一次指针跳转，非常快。但磁盘 IO 以块（4KB~16KB）为单位，二叉树节点太小，深度过大（百万数据约 20 层），导致 20 次磁盘寻道，性能噩梦。
多路树通过增加每个节点的分支数（即“路数”），降低树高。
5.1 B 树
一棵 m 阶 B 树满足：
每个节点最多 m 个子节点。
除根和叶子外，每个节点至少有 ⌈m/2⌉ 个子节点。
所有叶子在同一层，且不带信息（实际数据在内部节点也可能存储）。
B 树节点通常设计为磁盘页的大小，内部节点存储多个键和子指针。查找时，在单个节点内对键进行二分查找，确定下降路径。
5.2 B+ 树：数据库索引的真正王者
B+ 树与 B 树的核心差异：
数据只存于叶子节点，内部节点只存键作为路标。
所有叶子节点通过链表串联，支持范围扫描。
这一改动带来了巨大优势：
内部节点能容纳更多键 → 树高更低（如 3 层可支撑数百万条记录）。
范围查询时，找到下界后沿叶子链表遍历即可，无需回溯。
磁盘读入的每个内部节点含大量有效信息，缓存命中率高。
MySQL InnoDB 的索引结构就是 B+ 树。聚簇索引的叶子节点直接存储整行数据，辅助索引存储主键值。
6. Trie 树：空间换时间的字符串利刃
Trie（前缀树、字典树）不是比较型树，而是通过字符路径匹配字符串。每个节点包含若干指针（通常 26 个字母），根节点为空。
插入：逐字符向下，不存在则创建。
查找：同样路径，结束位置标记为单词结尾。
时间复杂度：O(L)，L 为字符串长度，与已有数据量无关。
6.1 变体与优化
压缩前缀树（Radix Tree）：合并单分支路径，节省内存，用于 Linux 路由表、IP 路由查找。
后缀树：字符串的所有后缀构成的压缩 Trie，可在 O(N) 内求解最长重复子串、回文串等。
6.2 应用
自动补全、拼写检查、敏感词过滤（AC 自动机融合了 Trie 与失配指针）。
7. 树的工程权衡指南
| 需求场景 | 推荐结构 | 理由 |
|---|---|---|
| 纯内存、高频查找、低频插入 | AVL 树 | 最严格平衡，查找最快 |
| 内存、读写混合、工业级通用 | 红黑树 | 旋转少，综合性能均衡 |
| 动态获取最大/最小元素 | 堆 | 极值 O(1)，插入删除 O(log N) |
| 磁盘数据库、大规模范围查询 | B+ 树 | 树高超低，支持高效范围扫描 |
| 字符串前缀匹配 | Trie / Radix Tree | 时间与字符串长度相关，无需比较 |
| 关系网络、最短路径 | 图（不是树，但常从树派生） | 树是图的无环特例 |
8. 结语：树，永不凋零
从编译器中的抽象语法树，到 Linux 内核的 red-black tree，再到谷歌 Bigtable 的 SSTable 跳表（虽不是树，但受 B 树启发），树形结构不断演变，但其核心思想从未改变：通过多级索引和分支，将线性扫描的复杂度降为对数，并针对存储介质的特点做极致优化。
理解树，就是理解计算机科学中“以空间换时间”以及“局部性原理”的完美体现。下一回当你写下一行std::map或一条CREATE INDEX时，或许会想起，无数条路径正在那棵看不见的 B+ 树上，以 log 级别的优雅速度，奔向它们各自的数据归宿。
