树与集合结构总览
比较堆、Trie、搜索树、平衡树、多路树和并查集各自维护的不变量与适用问题。
知识目录数据结构与算法：从基础到工程实践60 / 77
这篇来自我补“树与集合结构总览”基础时的一次复盘。我之前的问题是：树结构的名字越学越多时，我曾经只记规则：左小右大、保持平衡、多路节点，却没把它们解决的存储问题串起来。等我把输入、状态变化和边界条件分别写出来之后，原来看似突然出现的规则就有了来路。
线性结构把元素排成一条序列，树则用层次关系缩小搜索范围。堆、Trie、二叉搜索树、AVL 树、2-3 树、红黑树和并查集看起来差别很大，但都在回答：怎样利用关系和不变量，避免每次都扫描全部数据？
先分清这些树解决什么问题
| 结构 | 核心不变量 | 主要能力 |
|---|---|---|
| 二叉堆 | 父节点不大于或不小于子节点 | 快速取得极值、优先队列 |
| Trie | 从根到节点的路径代表前缀 | 字符串前缀检索 |
| 二叉搜索树 | 左子树小、右子树大 | 有序查找与遍历 |
| AVL 树 | 任一节点左右高度差不超过 1 | 更严格的平衡查找 |
| 2-3 树 | 节点可含多个键，叶子同层 | 绝对平衡的多路搜索 |
| 红黑树 | 颜色规则限制最长路径 | 较少旋转的近似平衡 |
| 并查集 | 每个集合由代表元组织 | 判断连通、快速合并集合 |
“都是树”并不意味着可以互换。堆只保证父子之间的偏序，不能像搜索树一样快速查找任意值；二叉搜索树有全局有序关系，却不保证根节点是极值优先队列的最佳实现；Trie 按字符路径组织，空间模型又与比较型树不同。
平衡为什么重要
一棵含 n 个节点的理想二叉搜索树，高度约为 log₂n，查找沿一条根到叶路径完成。但如果按递增顺序插入普通 BST，它可能退化成链表，高度变为 n。
图：不同树结构维护不同不变量，遍历只改变访问顺序
AVL 和红黑树都通过旋转修复结构。AVL 更严格，因此查找路径通常更短；红黑树容许有限的不平衡，插入删除时往往调整更少。选择标准不是“谁绝对更快”，而是读写比例、实现复杂度和库支持。
树的基本术语
- 根：没有父节点的起点。
- 叶子：没有孩子的节点。
- 深度：从根到当前节点经过的边数。
- 高度：从当前节点到最深叶子的最长路径。
- 度：节点拥有的孩子数量。
- 子树：某节点及其全部后代构成的树。
不同资料对“空树高度”和“单节点高度”可能采用不同定义。实现前必须统一：若空节点高度为 0，叶子高度通常为 1；若空节点为 -1，叶子则为 0。AVL 的平衡计算只要前后一致即可。
四种基础遍历
图：同一棵树在四种遍历方式下的访问顺序
| 遍历 | 顺序 | 常见用途 |
|---|---|---|
| 前序 | 根、左、右 | 复制树、输出结构 |
| 中序 | 左、根、右 | BST 得到有序序列 |
| 后序 | 左、右、根 | 删除树、计算子树信息 |
| 层序 | 按层从上到下 | 最短层级、序列化、宽度统计 |
深度优先遍历可以递归或显式栈实现，层序遍历使用队列。遍历时间通常为 O(n)，因为每个节点至少访问一次；额外空间取决于树高或最大层宽。
static <E> void levelOrder(Node<E> root) {
if (root == null) return;
java.util.ArrayDeque<Node<E>> queue = new java.util.ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.value);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
从操作目标选择结构
- 只需反复取得最大或最小值：堆。
- 需要按键排序、范围查询：平衡搜索树。
- 需要字符串前缀：Trie 或压缩基数树。
- 需要集合连通与合并：并查集。
- 数据位于磁盘页：B 树或 B+ 树。
- 数据静态、查询极多：排序数组加二分查找可能更简单。
树结构的复杂度常写成 O(log n)，但必须说明平衡保证。普通 BST 没有保证，堆的任意值查找也不是 O(log n)。
从二叉树走向多路树
2-3 树允许一个节点存一个或两个键，并拥有两个或三个孩子。多路节点可以降低树高，也是理解 B 树、B+ 树和数据库索引的入口。磁盘与页存储更关心一次 I/O 能带回多少键，因此真实数据库通常不会直接使用二叉树。
并查集为什么也像树
并查集用父指针把同一集合的元素连接起来。它不关心有序遍历，而关心两个操作：找到集合代表元 find，合并两个集合 union。路径压缩和按秩合并让树保持很浅，连续操作的摊销成本接近常数。
学习时抓住“不变量”
每学一种树，先写出它必须始终成立的条件，再分析插入、删除如何恢复条件：
- 节点保存哪些信息？
- 父子关系必须满足什么规则？
- 哪个操作可能破坏规则？
- 用交换、旋转、分裂、合并还是压缩修复？
- 修复会影响多大范围？
如果只背旋转步骤，很容易在边界条件中迷失；把旋转看作“保持有序关系的局部重连”，理解会稳定得多。
建议的实验方法
- 每次插入后打印树，不只看最终结果。
- 编写独立验证器，检查有序性、高度、颜色或黑高。
- 使用递增、递减、随机、重复和交错序列构造不同形态。
- 与标准库 TreeMap、PriorityQueue 的外部行为对照。
- 统计旋转次数、树高和比较次数，观察理论如何反映到运行数据。
图形化很有帮助，但图不能代替验证器。一张画对的示意图无法证明所有输入都正确，自动检查不变量才能持续发现结构损坏。
我自己的学习顺序
堆 → Trie → 普通二叉搜索树 → AVL → 2-3 树 → 红黑树 → 并查集。先看普通 BST 的退化问题，再看不同平衡策略为何出现；先理解 2-3 树，再理解红黑树用二进制颜色编码多路节点会更顺畅。
有哪里没看懂？可以只问这篇。
Jarvis 会限定在《树与集合结构总览》及其公开关联内容中检索，并把引用定位回原文章节。