1 / 4概念
Trees & Heaps
树用层次组织有序数据,堆用部分有序组织优先级。判断标准不是“平衡树更高级”,而是要不要范围查询、最坏情况能否接受、数据在内存还是磁盘、只需要最小/最大还是完整顺序。
1 概念
1.1 一句话定义
树是 n 个节点的无环连通层次结构;二叉搜索树(BST)用左小右大维持全序;平衡 BST 通过旋转把高度压在 O(log n);B 树/B+ 树用高扇出把高度压到 O(log_t n);堆是满足父节点优先于子节点的完全二叉树,只保证局部顺序。
1.2 它解决什么问题
- 有序查找:BST/平衡树支持查找、前驱后继、范围查询,哈希表做不到。
- 最坏保证:AVL/红黑树把 O(n) 的退化链压回 O(log n),适合在线服务。
- 磁盘索引:B+ 树把多个键放进一个页,降低树高和 I/O 次数,是数据库索引的默认结构。
- 优先级:堆用 O(1) 取最小/最大,O(log n) 插入删除,是调度、Dijkstra、top-k 的基础。
没有树,有序操作只能排序后扫描;没有堆,优先队列只能用有序数组或每次重排。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 数组、链表、栈、队列、哈希表 | Linear Structures |
| 图的表示、拓扑排序、并查集 | Graph Structures |
| 排序算法与二分 | Sorting & Searching |
| B+ 树在数据库中的执行计划 | Indexing & Optimization |
| 堆在 Dijkstra/Prim 中的用法 | Graph Algorithms |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 高度 / 深度 | 到叶子的最长路径 / 到根的路径 | 不同教材对根的高度定义不同 |
| 完全二叉树 | 除最后一层外全满,最后一层靠左 | 不是“满二叉树” |
| 平衡因子 | 左右子树高度差 | AVL 限定为 -1/0/1 |
| 旋转 | 不破坏中序的局部重构 | 不是交换键值 |
| 黑高 | 红黑树中从节点到叶子的黑节点数 | 不是普通高度 |
| 阶 / 扇出 | B 树每个节点的子节点数范围 | 不同教材用 t 或 m 表示 |
| 堆序 | 父节点 ≤ 或 ≥ 子节点 | 不是全局有序 |
| 上浮 / 下沉 | 插入/删除后恢复堆序 | 不是排序 |
| 建堆 | 从无序数组构造堆 | 不是逐个插入 |
| 前驱 / 后继 | 中序下的相邻节点 | 不是父子关系 |
2 机制
2.1 心智模型
树是“用高度换顺序”:每往下一层,候选集缩小一个分支。BST 用二叉分支把候选减半;B 树用 t 叉分支把高度再除以 log t;堆放弃全局顺序,只维护“父优于子”,因此只能快速拿到极值。
2.2 机制拆解
- 二叉树遍历:前序(根左右)、中序(左根右,BST 得到有序序列)、后序(左右根)、层序(队列)。遍历是 O(n),递归深度可能 O(n)。
- BST:查找从根开始,小往左、大往右;插入走到空位;删除分 0/1/2 个子节点,2 个子节点用后继或前驱替换。平均 O(log n),最坏 O(n)。
- AVL:每个节点平衡因子 ∈ 1;插入/删除后从改动点向上更新,失衡时做 LL/RR/LR/RL 旋转。高度约 1.44 log₂(n+2),比红黑树更矮,但旋转更频繁。
- 红黑树:节点着色,根黑、叶黑、红节点不能相邻、从任意节点到叶子的黑节点数相同。高度 ≤ 2 log₂(n+1),插入/删除最多常数次旋转,适合频繁更新的有序映射。
- B 树:每个节点存多个键和多个孩子,所有叶子同深度;插入溢出时分裂,删除下溢时合并/借位。扇出 t 让高度为 O(log_t n)。
- B+ 树:内部节点只存索引键,所有键都在叶子;叶子用链表相连。点查走到叶子,范围查询沿叶子链扫描,磁盘 I/O 更可控。
- 堆:完全二叉树用数组存,0 起点的子节点是
2i+1、2i+2,父节点是(i-1)/2。插入上浮,删除堆顶把末尾移到根再下沉;自底向上建堆是 O(n),不是 O(n log n)。
2.3 完整枚举
| 结构 | 不变量 | 查找 | 插入 | 删除 | 极值 | 范围查询 | 空间 | 典型用途 |
|---|---|---|---|---|---|---|---|---|
| 二叉树 | 无 | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) | 表达式树、遍历 |
| BST | 左小右大 | 平均 O(log n),最坏 O(n) | 平均 O(log n) | 平均 O(log n) | O(log n) | O(log n + k) | O(n) | 有序映射(小规模) |
| AVL 树 | 平衡因子 ∈ 1 | O(log n) | O(log n) | O(log n) | O(log n) | O(log n + k) | O(n) | 读多写少的有序索引 |
| 红黑树 | 五条着色性质 | O(log n) | O(log n) | O(log n) | O(log n) | O(log n + k) | O(n) | 语言标准库的有序 Map |
| B 树 | 所有叶子同深度,节点多键 | O(log_t n) | O(log_t n) | O(log_t n) | O(log_t n) | O(log_t n + k) | O(n) | 磁盘索引、文件系统 |
| B+ 树 | 键全在叶子,叶子链表 | O(log_t n) | O(log_t n) | O(log_t n) | O(log_t n) | O(log_t n + k) | O(n) | 数据库索引、范围扫描 |
| 二叉堆 | 父 ≤/≥ 子,完全树 | O(n) | O(log n) | O(log n) | O(1) | 不支持 | O(n) | 优先队列、top-k |
| d 叉堆 | 同上,d 个孩子 | O(n) | O(log_d n) | O(log_d n) | O(1) | 不支持 | O(n) | 降低树高、缓存优化 |
| 斐波那契堆 | 惰性合并的堆序森林 | O(n) | 摊还 O(1) | 摊还 O(log n) | O(1) | 不支持 | O(n) | 图算法理论优化 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| AVL 高度 | ≈ 1.44 log₂(n+2) | 比红黑树更矮,旋转更多 |
| 红黑树高度 | ≤ 2 log₂(n+1) | 插入删除旋转次数少 |
| B+ 树高度 | O(log_t n) | t 为扇出,通常几十到几百 |
| 二叉堆建堆 | O(n) | 自底向上下沉,不是 n 次插入 |
| 二叉堆插入/删除 | O(log n) | 上浮/下沉路径长度等于高度 |
| 堆顶查询 | O(1) | 只保证极值,不保证顺序 |
| 堆排序 | O(n log n) | 原地、不稳定 |
| 中序遍历 BST | O(n) | 输出有序序列 |
3 实践
3.1 最小示例
# BST 查找:迭代版,避免深树递归爆栈。
BST_SEARCH(root, k):
while root != NIL and root.key != k:
root = (k < root.key) ? root.left : root.right
return root
# 二叉堆下沉:0 起点,n 为堆大小。
SIFT_DOWN(a, i, n):
loop:
l = 2*i + 1; r = 2*i + 2; smallest = i
if l < n and a[l] < a[smallest]: smallest = l
if r < n and a[r] < a[smallest]: smallest = r
if smallest == i: break
SWAP(a[i], a[smallest]); i = smallest
# 自底向上建堆:从最后一个非叶节点开始下沉,总代价 O(n)。
BUILD_HEAP(a):
for i from floor(n/2)-1 down to 0:
SIFT_DOWN(a, i, n)
# AVL 左旋:只改指针和高度,不改变中序。
ROTATE_LEFT(x):
y = x.right
x.right = y.left
y.left = x
UPDATE_HEIGHT(x); UPDATE_HEIGHT(y)
return y
3.2 常用操作与参数
| 操作 | 典型 API | 说明 |
|---|---|---|
| 有序查找 | map.get(k) / lower_bound | 平衡树 O(log n) |
| 范围查询 | range(lo, hi) | B+ 树沿叶子链扫描 |
| 插入 | insert(k, v) | 重复键要定义覆盖/计数策略 |
| 删除 | erase(k) | BST 两孩子用后继替换 |
| 取极值 | heap.peek() | 堆 O(1),不删除 |
| 取并删除极值 | heap.pop() | O(log n) |
| 建堆 | heapify(xs) | O(n),优于逐个插入 |
| 中序遍历 | inorder(root) | BST 输出有序序列 |
3.3 标准流程
- 明确操作组合:点查、范围、前驱后继、取极值、插入删除比例。
- 先排除不满足语义的结构:需要顺序就不能只用哈希;只需要极值就不必维护全序。
- 选择平衡策略:读多写少 AVL,写多读少红黑,磁盘 B+,内存优先队列堆。
- 定义重复键和比较器:相等键放左/右、覆盖还是计数,必须写清。
- 实现后用不变量测试:BST 中序有序、AVL 平衡因子、红黑黑高、堆序、B+ 叶子链。
- 压测最坏输入:有序插入、逆序插入、重复键、删除根、范围跨页。
3.4 与相邻技术的组合
- 排序:堆排序 O(n log n) 原地;BST 中序遍历得到有序序列。
- 图算法:Dijkstra/Prim 用堆取最小;并查集用树/森林但路径压缩后不再是普通树。
- 数据库:B+ 树索引决定范围扫描的 I/O;执行计划会选择索引还是全表。
- 缓存:红黑树/跳表可用于有序缓存;LRU 仍是哈希 + 双向链表。
- 语言标准库:Java
TreeMap红黑树,C++std::map红黑树,priority_queue二叉堆。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| 是否需要顺序 | 是 / 否 | 哈希 vs 树 |
| 查询类型 | 点查 / 范围 / 前驱后继 | B+ / 平衡树 |
| 读写比例 | 读多 / 写多 | AVL vs 红黑 |
| 存储介质 | 内存 / 磁盘 | 二叉树 vs B+ 树 |
| 最坏保证 | 需要 / 不需要 | 平衡树 vs 裸 BST |
| 只需要极值 | 是 / 否 | 堆 vs 全序结构 |
3.6 决策规则
- 只要点查、不要求顺序:哈希表,不要用树。
- 需要有序遍历/范围查询:平衡 BST;内存用红黑,读多写少可 AVL。
- 数据在磁盘、按页读:B+ 树,不要用二叉树。
- 只要最小/最大、频繁插入删除:二叉堆。
- 需要 top-k:大小为 k 的堆,O(n log k)。
- 需要最坏 O(log n) 且更新频繁:红黑树;AVL 旋转更多。
- 静态数据、只查不改:排序数组 + 二分,常数更小。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 哈希表 | 平均 O(1) 点查 | 无序、最坏 O(n) | 字典、去重 |
| 裸 BST | 实现简单、有序 | 有序输入退化成链 | 教学、小数据 |
| AVL 树 | 高度更低、查找快 | 旋转频繁、实现复杂 | 读多写少 |
| 红黑树 | 更新旋转少、最坏 O(log n) | 常数比 AVL 略大 | 通用有序 Map |
| B+ 树 | 扇出大、范围扫描好 | 实现复杂、节点分裂 | 数据库、文件系统 |
| 二叉堆 | 极值 O(1)、实现简单 | 不支持查找/范围 | 优先队列、top-k |
| 跳表 | 实现比平衡树简单、并发友好 | 概率性高度、额外指针 | 有序集合、Redis |
3.8 何时不该用
- 只需要点查却用平衡树:哈希表更简单、常数更小。
- 需要范围查询却用堆:堆没有全局顺序。
- 数据在磁盘却用二叉平衡树:每次节点访问一次 I/O,树高太高。
- 有序插入裸 BST:退化成链表,必须平衡或随机化。
- 需要稳定迭代顺序却用哈希:顺序不保证,改用有序结构。
- 堆里做任意查找:O(n),改用平衡树 + 堆或索引堆。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 查找从 O(log n) 退化成 O(n) | 有序插入裸 BST,树成链 | 用 AVL/红黑/随机化 |
| 插入后中序不再有序 | 比较器不一致或旋转写错 | 用不变量测试比较器与旋转 |
| AVL 高度/平衡因子错 | 旋转后未更新高度或漏了双旋 | 每次旋转后自底向上更新 |
| 红黑树黑高不等 | 插入/删除修复遗漏情形 | 用性质测试和随机对拍 |
| 堆的父子关系错 | 0/1 起点混用、下标算错 | 封装 parent/children 辅助函数 |
| 建堆比预期慢 | 用 n 次插入代替自底向上建堆 | BUILD_HEAP 从 n/2-1 开始 |
| 重复键丢失或重复 | 未定义相等键策略 | 覆盖、计数或固定放左/右 |
| B+ 树范围查询漏数据 | 叶子链断开或分裂未维护 | 检查叶子 next 指针和分裂逻辑 |
| 深树递归爆栈 | 递归深度 O(n) | 改迭代或平衡树 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 用裸 BST 存有序输入 | 退化成链表 | 平衡树/跳表 |
| 用堆做范围查询 | 只能全量弹出 | B+ 树/平衡树 |
| 用哈希表做前驱后继 | 只能全表扫描 | 有序结构 |
| 逐个插入建堆 | O(n log n) | 自底向上建堆 O(n) |
| 忽略比较器的相等语义 | 键丢失或顺序不稳 | 定义全序与重复键策略 |
4.3 可观测信号
树高、平衡因子分布、旋转次数、黑高、堆的数组长度与下沉次数、范围查询扫描的节点/页数、B+ 树分裂/合并次数。线上看查找 P99、树高随时间变化、索引页命中率。
4.4 安全 / 性能 / 一致性边界
- 最坏保证:裸 BST 的最坏是 O(n);对延迟敏感的系统必须用平衡结构。
- 磁盘:B+ 树的优势来自页和扇出,不是“树”本身;节点太小会失去意义。
- 一致性:平衡树的旋转必须保持中序;堆只保证偏序,不能当有序容器用。
- 重复键:必须显式定义策略,否则删除/查找行为和预期不一致。