主题
第四章 树形结构、搜索树与堆
📖 ⏱️ 预计阅读时长 1 分钟 👑 会员专属
1. 树的基本概念
当数据之间不再是简单的前后关系，而是呈现层次关系时，线性结构就不再足够，树形结构由此出现。树是一种典型的非线性结构，适合表示层次关系。
树中常见术语包括：
- 根节点：树的起始节点。
- 父节点、子节点：体现层次关系。
- 兄弟节点：具有相同父节点的节点。
- 叶子节点：没有子节点的节点。
- 节点的度：该节点拥有的子节点个数。
- 树的高度或深度：树的层数或最长路径层级。
树在现实中的应用非常广泛，如组织结构图、文件目录、HTML DOM 树、表达式树等。
树之所以重要，在于它能自然表达“部分从属于整体”的层次关系。在线性结构中，元素之间主要是前后关系；而在树结构中，一个节点可以派生出多个下级节点，这使它特别适合表示目录、语法、机构、决策和索引等层级对象。
2. 二叉树
二叉树是每个节点最多只有两个子节点的树结构，通常称为左子树和右子树。
2.1 二叉树的性质
- 第
i层最多有2^(i-1)个节点。 - 高度为
h的二叉树最多有2^h - 1个节点。 - 满二叉树、完全二叉树、二叉排序树等都是常见特殊类型。
二叉树之所以在教学和工程中都占据核心地位，是因为“每个节点最多两个孩子”这一限制既足够简单，便于分析和实现，又足够灵活，能够承载搜索、表达式处理、优先级管理等多种任务。很多更复杂的树结构，都可以看作对二叉树思想的扩展。
2.2 二叉树遍历
遍历是树结构中的基础操作，常见方式如下：
- 前序遍历：根 -> 左 -> 右。
- 中序遍历：左 -> 根 -> 右。
- 后序遍历：左 -> 右 -> 根。
- 层序遍历：按层从上到下、从左到右访问。
在实际应用中，表达式求值、编译语法分析、文件系统处理等都依赖树遍历思想。
2.3 为什么遍历顺序重要
同一棵树，只因访问顺序不同，就可能得到完全不同的结果。例如：
- 前序遍历适合表达“先访问节点，再处理子问题”的场景。
- 中序遍历在二叉搜索树中会得到有序序列。
- 后序遍历适合先处理子树、再处理根节点的场景，如释放整棵树内存。
- 层序遍历适合逐层分析结构，如最短层级问题。
3. 二叉搜索树
二叉搜索树（BST, Binary Search Tree）满足如下性质：对于任一节点，其左子树所有关键字小于该节点关键字，右子树所有关键字大于该节点关键字。
基于这一性质，二叉搜索树在理想情况下能以较高效率完成查找、插入和删除。
它之所以比无序线性结构更适合查找，是因为每比较一次关键字，通常就能排除一整部分无关节点。也就是说，二叉搜索树并不是简单“把节点排成一棵树”，而是在结构中编码了大小关系，从而把查找过程转化为不断缩小范围的过程。
3.1 性能特点
- 若树较平衡，则查找、插入、删除通常为
O(log n)。 - 若树严重退化为链表，则上述操作最坏可能为
O(n)。
这也解释了为什么“树结构”本身并不自动等于高效。只有当树的高度保持合理时，查找路径才会足够短；一旦结构失衡，二叉搜索树就会失去原有优势。这正是后续需要引入平衡树的根本原因。
3.2 删除操作的三种情况
在二叉搜索树中，删除操作通常分为三种情况：
- 待删除节点是叶子节点，可直接删除。
- 待删除节点只有一个孩子，可让其孩子直接接替原位置。
- 待删除节点有两个孩子，通常用其中序前驱或中序后继替换该节点，再删除被替换位置的节点。
之所以要区分这三种情况，是因为二叉搜索树删除后仍必须保持左小右大的搜索性质，不能像普通链表删除那样只断开一个指针即可。
4. C 语言示例：二叉搜索树插入与中序遍历
c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int key;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode *create_node(int key) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
if (node == NULL) {
return NULL;
}
node->key = key;
node->left = NULL;
node->right = NULL;
return node;
}
TreeNode *insert(TreeNode *root, int key) {
if (root == NULL) {
return create_node(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
}
return root;
}
void inorder(TreeNode *root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
int main(void) {
TreeNode *root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
inorder(root); /* 输出：20 30 40 50 70 */
return 0;
}该示例的中序遍历结果是有序序列，这正是二叉搜索树的重要性质。
5. 平衡二叉树与红黑树
普通二叉搜索树可能退化，因此在工程中常使用平衡搜索树。
5.1 平衡二叉树（AVL 树）
AVL 树要求任一节点左右子树高度差的绝对值不超过 1。它的查找效率稳定，但插入删除时可能需要较频繁旋转调整。
5.2 红黑树
红黑树通过颜色规则控制树的整体平衡。它不要求像 AVL 那样“严格平衡”，但能保证树高不会过分失控，因此在标准库映射结构、操作系统内核、调度系统中应用广泛。
从总体上看：
- AVL 树查找更“紧凑”，适合查找密集场景。
- 红黑树更新代价更平衡，工程应用更广。
5.3 为什么工程实现更偏爱红黑树
很多标准库和系统组件更偏爱红黑树，而不是 AVL 树，原因并不在于红黑树“更高级”，而在于其平衡要求相对宽松，插入和删除时通常需要的调整更少，因此在查找、插入、删除都较频繁的综合场景中表现更均衡。
6. 堆与优先队列
堆是一种特殊的完全二叉树，分为大根堆和小根堆。
- 大根堆：每个节点值都不小于其孩子节点。
- 小根堆：每个节点值都不大于其孩子节点。
堆通常用数组实现，因为完全二叉树非常适合按层顺序存储。若根节点下标为 i，则：
- 左孩子通常为
2i + 1。 - 右孩子通常为
2i + 2。 - 父节点通常为
(i - 1) / 2。
完全二叉树之所以适合数组实现，是因为其节点分布非常规整，不会像一般树那样出现大量“空洞位置”。这种规则性使得父子关系可以直接通过下标计算得到，从而省去了显式指针连接的开销。
6.1 堆的复杂度
| 操作 | 复杂度 |
|---|---|
| 读取堆顶 | O(1) |
| 插入元素 | O(log n) |
| 删除堆顶 | O(log n) |
| 建堆 | O(n) |
6.2 典型应用
- 优先队列。
- 堆排序。
- Dijkstra 算法、A* 搜索等图算法中的最优候选选择。
- 大规模数据中的 Top K 问题。
上图是一个大根堆的示意。需要注意，堆并不要求像二叉搜索树那样满足“左小右大”，它只要求父节点与孩子节点之间满足大小关系。因此，堆更适合维护最值，而不适合中间查找。
这也解释了一个常见误区：很多人看到堆和树，就误以为堆也适合高效查找任意元素。事实上，堆擅长的是“快速得到当前最大值或最小值”，而不是维护整体有序关系。它服务的是优先队列问题，不是一般查找问题。
7. 字典树与多路搜索树
7.1 字典树（Trie）
Trie 常用于字符串前缀匹配。它把字符串按字符逐层展开，适合处理：
- 自动补全。
- 敏感词过滤。
- 词典检索。
- 最长公共前缀查询。
若字符串长度为 L，查找或插入的复杂度通常与 L 成正比，而与集合中字符串总数关系较弱。
7.2 B 树与 B+ 树
B 树和 B+ 树属于多路平衡搜索树，特别适合外存环境与数据库索引。
其核心思想是：
- 一个节点存放多个关键字和多个子指针。
- 通过提高树的分支因子，显著降低树高。
- 尽量减少磁盘 I/O 次数。
数据库系统之所以广泛采用 B+ 树，是因为它不仅保持平衡，而且叶子节点通常形成有序链，十分适合范围查询与顺序扫描。
7.3 为什么数据库偏爱 B+ 树而不是普通二叉搜索树
根本原因在于数据库面对的是磁盘或 SSD 上的大规模数据，而不是只放在内存中的小规模对象。B+ 树通过一个节点容纳多个关键字和子指针，提高了分支因子，降低了树高，从而减少了外存访问次数。同时，叶子节点有序链结构又让范围查询非常高效。这些特性都是普通二叉搜索树难以替代的。
8. 本章小结
树形结构使计算机能够高效表达层次关系，搜索树使“查找”问题获得了系统化解决方案，平衡树解决了退化问题，堆则把“按优先级取出元素”的需求高效落地，Trie 与 B+ 树则针对字符串检索和外存索引提供了专门方案。本章的核心不是记住树的种类多少，而是理解每一种树究竟在解决什么问题。