第 11 章 · 高级结构

四个结构各解一类问题：连通性、有序动态查找、字符串前缀、磁盘索引。

11.1 并查集：动态连通性

维护若干不相交集合，支持近乎 O(1) 的 find（找根）和 union（合并）。两个优化：

#define MAXN 1000
int parent[MAXN], rk[MAXN];   // rk 记录树高的上界（按秩合并）

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);  // 路径压缩：沿途直接挂到根
    return parent[x];
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rk[rx] < rk[ry]) { parent[rx] = ry; }
    else { parent[ry] = rx; if (rk[rx] == rk[ry]) rk[rx]++; }
}

路径压缩 + 按秩合并把均摊复杂度压到反阿克曼函数 α(n)（近似 O(1)）。用于 Kruskal 判环（第 6 章）、连通分量。

11.2 跳表：随机化的有序结构

链表（第 2 章）有序但只能线性查找。跳表给节点加多层指针，上层「跳过」大量节点，查找时从高层逐层下探，平均 O(log n)。

L3  ──→──────────→─────→  最高层：大步跳
L2  ──→──→──→──→──→──→
L1  ──→─→─→─→─→─→─→─→─→
L0  →→→→→→→→→→→→→→→→→→  底层：完整有序链表

每层「晋升」由随机决定（抛硬币），期望高度 O(log n)。查找、插入、删除都平均 O(log n)，实现比 AVL 简单、无需旋转。

11.3 Trie：前缀树

把字符串按字符分层存成树，共享公共前缀。

typedef struct Trie { struct Trie *next[26]; int is_end; } Trie;

void insert(Trie *r, char *s) {
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (!r->next[c]) {
            r->next[c] = calloc(1, sizeof(Trie));
            if (!r->next[c]) return;
        }
        r = r->next[c];
    }
    r->is_end = 1;
}

查找一个串 O(len)，与集合大小无关；支持前缀查询（自动补全、词频）。代价是空间大（每个字符一个指针数组）。

11.4 B 树 / B+ 树：磁盘索引

内存里平衡树 O(log n) 已经很快，但磁盘每次读写以块（页）为单位，访问一个节点 = 一次磁盘 IO，IO 才是瓶颈。B 树让每个节点存多个键、多个孩子（多路），树高大幅降低，一次 IO 能读入更多键。

	B 树	B+ 树
数据存哪	内部节点 + 叶子都存	只在叶子存，内部仅存键
叶子	不连	用链表串起来，支持范围扫描
查找	可能中途命中	必须走到叶子

数据库（如 MySQL InnoDB）用 B+ 树：叶子链表让范围查询（BETWEEN）一次 IO 后顺序扫，且非叶节点不含数据、一页能塞更多键、树更矮。

对比：跳表靠随机化省旋转、并发友好，但多指针开销；平衡树最坏有保证，但旋转复杂。

对比：B 树单点可能更早命中；B+ 树数据全压叶子并连表，换高效范围查询。

对比：普通集合支持任意增删查但合并贵；并查集只回答「同集合 + 合并」，用极小常数换近 O(1) 连通判断。