Sherfiter's wiki for fun

第 11 章 · 高级结构

主干结构(表、树、图、哈希)覆盖了八成的题,剩下两成的题各有一个「量身定制」的解法,本章收四个:并查集(连通性专用,代码十行)、跳表(有序结构的随机化答案)、Trie(前缀专用)、B/B+ 树(磁盘时代的主宰,数据库课第 9 章已经见过它,这里补数据结构视角)。它们的共同气质是:为特定问题放弃通用性,换取惊人的简单或常数。

11.1 并查集:十行代码回答「他和她是一伙的吗」

问题:维护一堆人,反复「把 A 和 B 拉进同一伙」并查询「A 和 B 是不是一伙的」。朴素做法每次合并合并整个集合,O(n²) 起步。并查集的答案优雅到失真:每个元素只记自己的「上级」,查到没有上级的「根」即代表整伙:

int parent[MAXN], rk[MAXN];

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),这个函数在宇宙原子数这么大的 n 下都不超过 4,工程上就是 O(1)。十行代码换这个性能,是全课性价比最高的数据结构。用途清点:第 6 章 Kruskal 的判环、社交网络的连通分量、编译器的变量等价类,以及「最小生成树」「动态连通性」类题目的标配。

11.2 跳表:用抛硬币代替旋转

有序数据要快查,教科书答案是 AVL/红黑树(第 5 章),但旋转的边界条件写起来极其磨人。跳表另辟蹊径:底层是完整有序链表,每个节点按随机(抛硬币)决定「晋升」到上层,上层节点稀疏,查找时从最高层大步跳、越跳越细:

L3  1 ──────────────────→ 40
L2  1 ─────→ 15 ────────→ 40
L1  1 ──→ 9 → 15 → 27 ──→ 40
L0  1→5→9→12→15→20→27→33→40    ← 底层完整有序

查找 27:高层直接跳过 5、9,两三步定位。数学保证:随机晋升让每层节点数期望减半,期望高度 O(log n),查找插入删除均摊 O(log n)。相比平衡树,跳表没有旋转,插入就是随机决定要不要多长一层,代码好写、区间查询天然顺(底层就是链表)、并发友好(锁的粒度小,Redis 的有序集合 ZSet 用的就是跳表)。代价是最坏情况靠概率兜底(理论上可能全挤在一层,概率小到可忽略),这是「随机化换确定性」的又一次交易,和第 7 章哈希表是同一笔账。

11.3 Trie:前缀就是地址

要回答「字典里有没有以 'app' 开头的词」「词 'apple' 存在吗」,哈希表只会整串匹配,前缀查询无能为力。Trie(前缀树)把字符串按字符逐层拆开,公共前缀只存一份:

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

void insert(Trie *r, const 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));
        r = r->next[c];
    }
    r->is_end = 1;                      // 单词结束标记(区别于「路过」)
}

查找任何串 O(len),与字典多大无关(只和串长有关),这是它和一切比较式结构分道扬镳的地方;「前缀自动补全」就是「走到节点,往下收集所有 is_end」。代价是内存:每个节点 26 个指针,英文单词字典动辄几百 MB,工程上用紧凑变体(孩子压缩、双数组 Trie)。应用除了输入法、搜索框补全,还有路由器的最长前缀匹配(网络课的第 5 章会撞见它)、以及后缀树的近亲场景。

11.4 B/B+ 树:给磁盘造的树

内存里的平衡树飞快,但放到磁盘上就露馅了:树的一个节点一次 IO,AVL 高 log₂n,十亿数据 30 层 = 30 次磁盘 IO,每次几毫秒,直接死刑。B 树的对策只有一个方向:树要矮。每个节点(恰好一个磁盘页,16KB)装几百个键、几百个孩子,十亿数据只要三四层,一次查询 3~4 次 IO:

B+ 树(3 层,度几百):
         [ 500 | 1000 ]                 ← 内部节点:只存键,当路标
        /        |        \
 [10..499]   [500..999]   [1000..]       ← 中间层
      │           │          │
叶子: 5→20→...→500→...→1000→...→2000   ← 数据全在这层,串成有序链表

B 树和 B+ 树的分岔在第 9 章数据库语境里讲过一半,这里补数据结构面的另一半:B 树的非叶节点也存数据(查找可能中途命中),B+ 树数据全压叶子、内部节点纯路标(一页塞更多键,树更矮),叶子链表让范围扫描变成「定位起点后顺链走」(第 9 章的 BETWEEN 为什么快,物理原因在此)。文件系统(第 8 章 ext4 的 extent)、数据库索引、LSM 的 SSTable,底层全是这族结构。它的设计哲学值得单独立碑:当 IO 成本主导时,把常数做小比把渐近阶做低更重要,这是内存思维转向磁盘思维的分水岭。

常见错误

  • 并查集只做路径压缩不做按秩合并(或反之)。单优化也能跑,但合并成链的极端数据会退化;两个都写,五行而已。
  • Trie 忘了 is_end。查找 "app" 在字典里不存在(只有 "apple")却返回成功,因为把「前缀存在」误当「单词存在」。
  • B+ 树节点当内存对象 malloc。磁盘树的核心是「节点 = 一个页」,自己用 malloc 拆碎节点就丢了「一次 IO 读一页」的全部意义;要按页对齐、按页读写。

练习

  1. 实现:用并查集解「朋友圈计数」(初始 n 人各自为营,给出若干「互相认识」关系,问最后几伙),再顺手实现第 6 章 Kruskal 的判环部分。
  2. 手算:对键 {1, 9, 15, 27, 40} 手动建跳表(假设硬币结果 1,0,1,1,0),画出每层;再查找 20,写出下降路径。
  3. 动手:实现 Trie,插入 5000 个随机单词,查询 10 万次(命中和未命中各半),和 qsort + bsearch 的方案对比耗时与内存,给「何时该用 Trie」写一条实测依据。
  4. 思考:Redis ZSet 为什么选跳表而不是红黑树?列出至少两条(提示:范围查询的实现难度、并发、以及代码简单性的工程价值),再查一下 Redis 作者 antirez 自己怎么说的。
豫ICP备2026027944号