Tree
自动关联目录:Tree
树是图的一个特例:连通且无环, 个点恰好 条边。
但它值得单独成章,因为:
- 递归结构天然适配分治和 DP
- 大量问题(文件系统、语法树、组织架构、决策树)本身就是树
- 图上的很多问题在树上简单得多(两点间路径唯一)
术语
| 术语 | 含义 |
|---|---|
| 根 / 叶子 | 最顶层 / 无孩子的节点 |
| 父 / 子 / 兄弟 | 相邻层级关系 |
| 祖先 / 后代 | 路径上的前后关系 |
| 深度 | 根到该节点的边数(根深度 0) |
| 高度 | 该节点到最深叶子的边数(叶子高度 0) |
| 度 | 孩子个数 |
| 子树 | 某节点及其所有后代 |
| 森林 | 若干棵不相交的树 |
注意:深度从根往下数,高度从叶子往上数。有的教材把根的高度定义为节点数,注意区分。
二叉树
每个节点最多两个孩子。
性质
- 第 层最多 个节点( 从 0 开始)
- 深度为 的二叉树最多 个节点
- 叶子数 = 度为 2 的节点数 + 1
- 个节点的不同二叉树形态数是卡特兰数
存储
链式
struct Node {
int val;
Node *l, *r;
};数组(完全二叉树专用)
// 下标从 1 开始(推荐),或 0 开始
// 1-indexed: 父 = i/2, 左 = 2i, 右 = 2i+1
// 0-indexed: 父 = (i-1)/2, 左 = 2i+1, 右 = 2i+2
int tree[N];完全二叉树用数组存最紧凑(堆就是这么做的)。普通树用数组会浪费大量空间(退化成链时需要)。
左孩子右兄弟表示法(普通树 → 二叉树)
每个节点: 第一个孩子 + 下一个兄弟
A A
/|\ |
B C D → B ─ C ─ D
|把任意树转成二叉树,可以用二叉树的算法处理。
二叉搜索树(BST)
性质:对任意节点,左子树所有值 < 它 < 右子树所有值。
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13价值:中序遍历得到有序序列。查找/插入/删除, 是树高。
致命问题:退化。按有序顺序插入 会得到一条链,,操作退化到。
平衡二叉搜索树
通过旋转维持。
AVL 树
严格平衡:任意节点的左右子树高度差。
- 插入/删除后通过旋转恢复平衡
- 查找快(树更矮),但插入删除要频繁旋转
- 适合查找远多于修改的场景
红黑树
宽松平衡(黑高平衡):
- 节点红或黑
- 根是黑
- 叶子(NIL)是黑
- 红节点的孩子必须是黑(不能连续红)
- 从任一节点到其所有后代叶子的黑节点数相同
保证:树高。
- 插入删除的旋转次数少(比 AVL 少)
- 实际性能更好(综合插入/删除/查找)
- C++
std::map/set、JavaTreeMap、Linux 内核的 rbtree 都用它
对比:
| AVL | 红黑树 | |
|---|---|---|
| 平衡严格度 | 更严格 | 宽松 |
| 树高 | 更低 | 略高 |
| 查找 | 更快 | 稍慢 |
| 插入/删除 | 旋转多 | 旋转少 |
| 适用 | 读多写少 | 读写均衡 |
其他平衡树
| 结构 | 特点 |
|---|---|
| Treap | BST + 堆(随机优先级),实现简单,期望 |
| Splay | 伸展树,访问后旋到根,均摊,缓存友好 |
| 替罪羊树 | 不平衡时重建子树 |
| B 树 / B+ 树 | 多路平衡,一个节点存多个 key。数据库和文件系统用它(减少磁盘 I/O) |
| 跳表 | 用概率替代平衡,实现简单,Redis 用它 |
B+ 树为什么是数据库的标配:一个节点可以存几百个 key,树高只有 3~4 层,且叶子节点用链表串起来支持范围扫描。而红黑树在磁盘上每个节点一次 I/O,树高 20 层就要 20 次 I/O。
堆(Heap)
完全二叉树 + 堆序性质(父 子 或 父 子)。
// 数组实现,1-indexed
int h[N], sz = 0;
void push(int x) {
h[++sz] = x;
int i = sz;
while (i > 1 && h[i] < h[i/2]) { swap(h[i], h[i/2]); i /= 2; } // 上浮
}
int top() { return h[1]; }
void pop() {
h[1] = h[sz--];
int i = 1;
while (true) { // 下沉
int l = 2*i, r = l+1, mn = i;
if (l <= sz && h[l] < h[mn]) mn = l;
if (r <= sz && h[r] < h[mn]) mn = r;
if (mn == i) break;
swap(h[i], h[mn]); i = mn;
}
}
// 建堆 O(n):从最后一个非叶子开始下沉
for (int i = sz/2; i >= 1; i--) sift_down(i);| 操作 | 复杂度 |
|---|---|
push | |
pop | |
top | |
| 建堆 | (不是!) |
| 堆排序 |
建堆是 的原因:大部分节点在底层,下沉距离短。严格证明:
C++ priority_queue:
priority_queue<int> pq; // 大根堆(默认)
priority_queue<int, vector<int>, greater<int>> minpq; // 小根堆应用:优先队列、Dijkstra、Huffman、Top-K、中位数维护(双堆)。
对顶堆求动态中位数
// 大根堆存较小的一半,小根堆存较大的一半
priority_queue<int> lo; // 较小的一半(大根)
priority_queue<int, vector<int>, greater<int>> hi; // 较大的一半(小根)
void add(int x) {
if (lo.empty() || x <= lo.top()) lo.push(x);
else hi.push(x);
// 平衡:保证 |lo| >= |hi| 且相差不超过 1
if (lo.size() > hi.size() + 1) { hi.push(lo.top()); lo.pop(); }
if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
}
double median() {
if (lo.size() > hi.size()) return lo.top();
return (lo.top() + hi.top()) / 2.0;
}树的性质与算法
树的直径
树中最长的路径。
两次 DFS/BFS 法:
1. 从任意点 s 出发,找到最远的点 u
2. 从 u 出发,找到最远的点 v
3. u-v 就是直径为什么对: 一定是直径的一个端点(可证明:若直径是-,从 出发的最远点必是 或 之一)。
// 树形 DP 法(同时求长度和端点)
int dia = 0;
int dfs(int u, int p) { // 返回从 u 向下的最大深度
int mx1 = 0, mx2 = 0; // 最长和次长的子路径
for (int v : g[u]) {
if (v == p) continue;
int d = dfs(v, u) + 1;
if (d > mx1) { mx2 = mx1; mx1 = d; }
else if (d > mx2) mx2 = d;
}
dia = max(dia, mx1 + mx2); // 经过 u 的最长路径
return mx1;
}应用:树的直径、最长路径、最小直径生成树。
树的重心
删掉它之后,最大连通块最小的节点。
int sz[N], best = INF, centroid;
void dfs(int u, int p, int total) {
sz[u] = 1;
int mx = 0; // 删掉 u 后的最大连通块
for (int v : g[u]) {
if (v == p) continue;
dfs(v, u, total);
sz[u] += sz[v];
mx = max(mx, sz[v]); // 子树方向
}
mx = max(mx, total - sz[u]); // 父方向
if (mx < best) { best = mx; centroid = u; }
}性质:
- 重心最多 2 个,且相邻
- 以重心为根,每棵子树大小
- 点分治的基础(保证递归深度)
最近公共祖先(LCA)
见倍增章节(Binary Lifting)。
树的同构
判断两棵无根树是否同构:树哈希 / AHU 算法(括号序列 + 排序)。
树形结构的选择
| 需求 | 结构 |
|---|---|
| 有序映射 / 范围查询 | 红黑树(map)、B+ 树(数据库) |
| 只需要最大/最小 | 堆 |
| 前缀查询 | Trie |
| 维护区间 | 线段树 / 树状数组(见其他章节) |
| 动态树(加边删边) | Link-Cut Tree |
| 树上路径查询 | 树链剖分 / LCA + 前缀和 |
常见坑
- 递归爆栈:树退化成链时,递归深度。 会爆栈
- 忘了跳过父节点:无根树 DFS 必须传
p并跳过,否则无限递归 - BST 退化:有序插入会让朴素 BST 变成链。用平衡树或
std::map - 堆的下标从 0 还是 1:搞混会导致父子关系错。建议 1-indexed
- 建堆复杂度记成:是
- 树的直径两次 DFS 法在带权树上的正确性:边权非负时成立,有负权不成立
- 重心的"最大连通块":别忘了父方向那部分(
total - sz[u]) - 删除 BST 节点:有两个孩子时,用中序后继(右子树最小)替换,不是随便找个孩子
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/170cf1e2.html
更新于:2026年11月16日