Tree

自动关联目录:Tree

树是图的一个特例:连通且无环,nn 个点恰好n−1n-1 条边。

但它值得单独成章,因为:

  • 递归结构天然适配分治和 DP
  • 大量问题(文件系统、语法树、组织架构、决策树)本身就是树
  • 图上的很多问题在树上简单得多(两点间路径唯一)

术语

术语含义
根 / 叶子最顶层 / 无孩子的节点
父 / 子 / 兄弟相邻层级关系
祖先 / 后代路径上的前后关系
深度根到该节点的边数(根深度 0)
高度该节点到最深叶子的边数(叶子高度 0)
度孩子个数
子树某节点及其所有后代
森林若干棵不相交的树

注意:深度从根往下数,高度从叶子往上数。有的教材把根的高度定义为节点数,注意区分。

二叉树

每个节点最多两个孩子。

性质

  • 第ii 层最多2i2^{i} 个节点(ii 从 0 开始)
  • 深度为hh 的二叉树最多2h+1−12^{h+1} - 1 个节点
  • 叶子数 = 度为 2 的节点数 + 1
  • nn 个节点的不同二叉树形态数是卡特兰数Cn=1n+1(2nn)C_n = \frac{1}{n+1}\binom{2n}{n}

存储

链式

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];

完全二叉树用数组存最紧凑(堆就是这么做的)。普通树用数组会浪费大量空间(退化成链时需要2n2^n)。

左孩子右兄弟表示法(普通树 → 二叉树)

每个节点: 第一个孩子 + 下一个兄弟

  A             A
 /|\            |
B C D    →      B ─ C ─ D
                    |

把任意树转成二叉树,可以用二叉树的算法处理。

二叉搜索树(BST)

性质:对任意节点,左子树所有值 < 它 < 右子树所有值。

    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

价值:中序遍历得到有序序列。查找/插入/删除O(h)O(h),hh 是树高。

致命问题:退化。按有序顺序插入1,2,3,4,51,2,3,4,5 会得到一条链,h=nh = n,操作退化到O(n)O(n)。

平衡二叉搜索树

通过旋转维持h=O(log⁡n)h = O(\log n)。

AVL 树

严格平衡:任意节点的左右子树高度差≤1\le 1。

  • 插入/删除后通过旋转恢复平衡
  • 查找快(树更矮),但插入删除要频繁旋转
  • 适合查找远多于修改的场景

红黑树

宽松平衡(黑高平衡):

  1. 节点红或黑
  2. 根是黑
  3. 叶子(NIL)是黑
  4. 红节点的孩子必须是黑(不能连续红)
  5. 从任一节点到其所有后代叶子的黑节点数相同

保证:树高≤2log⁡2(n+1)\le 2\log_2(n+1)。

  • 插入删除的旋转次数少(比 AVL 少)
  • 实际性能更好(综合插入/删除/查找)
  • C++ std::map/set、Java TreeMap、Linux 内核的 rbtree 都用它

对比:

AVL红黑树
平衡严格度更严格宽松
树高更低略高
查找更快稍慢
插入/删除旋转多旋转少
适用读多写少读写均衡

其他平衡树

结构特点
TreapBST + 堆(随机优先级),实现简单,期望O(log⁡n)O(\log n)
Splay伸展树,访问后旋到根,均摊O(log⁡n)O(\log n),缓存友好
替罪羊树不平衡时重建子树
B 树 / B+ 树多路平衡,一个节点存多个 key。数据库和文件系统用它(减少磁盘 I/O)
跳表用概率替代平衡,实现简单,Redis 用它

B+ 树为什么是数据库的标配:一个节点可以存几百个 key,树高只有 3~4 层,且叶子节点用链表串起来支持范围扫描。而红黑树在磁盘上每个节点一次 I/O,树高 20 层就要 20 次 I/O。

堆(Heap)

完全二叉树 + 堆序性质(父≤\le 子 或 父≥\ge 子)。

// 数组实现,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);
操作复杂度
pushO(log⁡n)O(\log n)
popO(log⁡n)O(\log n)
topO(1)O(1)
建堆O(n)O(n)(不是O(nlog⁡n)O(n \log n)!)
堆排序O(nlog⁡n)O(n \log n)

建堆是O(n)O(n) 的原因:大部分节点在底层,下沉距离短。严格证明:

∑i=0hn2i+1⋅i=O(n)\sum_{i=0}^{h} \frac{n}{2^{i+1}} \cdot i = O(n)

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 就是直径

为什么对:uu 一定是直径的一个端点(可证明:若直径是aa-bb,从ss 出发的最远点必是aa 或bb 之一)。

// 树形 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 个,且相邻
  • 以重心为根,每棵子树大小≤n/2\le n/2
  • 点分治的基础(保证递归深度O(log⁡n)O(\log n))

最近公共祖先(LCA)

见倍增章节(Binary Lifting)。

树的同构

判断两棵无根树是否同构:树哈希 / AHU 算法(括号序列 + 排序)。

树形结构的选择

需求结构
有序映射 / 范围查询红黑树(map)、B+ 树(数据库)
只需要最大/最小堆
前缀查询Trie
维护区间线段树 / 树状数组(见其他章节)
动态树(加边删边)Link-Cut Tree
树上路径查询树链剖分 / LCA + 前缀和

常见坑

  • 递归爆栈:树退化成链时,递归深度O(n)O(n)。n=105n = 10^5 会爆栈
  • 忘了跳过父节点:无根树 DFS 必须传 p 并跳过,否则无限递归
  • BST 退化:有序插入会让朴素 BST 变成链。用平衡树或 std::map
  • 堆的下标从 0 还是 1:搞混会导致父子关系错。建议 1-indexed
  • 建堆复杂度记成O(nlog⁡n)O(n \log n):是O(n)O(n)
  • 树的直径两次 DFS 法在带权树上的正确性:边权非负时成立,有负权不成立
  • 重心的"最大连通块":别忘了父方向那部分(total - sz[u])
  • 删除 BST 节点:有两个孩子时,用中序后继(右子树最小)替换,不是随便找个孩子