Lecture 17: 拓展专题：Trie 与并查集（Bonus: Tries & Union-Find）（延伸专题，官方 2026 夏季未设独立讲座）

目录 · ← l16 · appendix →

Lecture 17: 拓展专题：Trie 与并查集（Bonus: Tries & Union-Find）（延伸专题，官方 2026 夏季未设独立讲座）

概述

本章为延伸专题：官方 2026 夏季学期共 28 讲，未设独立讲座讲解 Trie 与并查集。 不过官方与它们并非毫无交集：L24（哈希那讲）权衡“按 8 位学号存取学生记录”的方案时，提到有人建议“建一棵每个节点 10 个孩子、沿学号数字逐位下行的树”——那正是 trie（字典树）的思路；Stanford 的 Lexicon（整本英语词典的查找结构）内部也与 trie 异曲同工。并查集则完全不在本季大纲内。把它们收进笔记，是因为：Trie 是自动补全、拼写检查、前缀统计的标准答案；并查集是“动态连通分量”与 Kruskal 算法判环的标配工具；二者都是技术面试与后续课程（CS161）的高频储备。本章前半实现 Trie 的插入/查找/前缀查询，后半实现带路径压缩与按秩合并的 UnionFind，并给出连通分量计数与判环演示。官方对应：无对应讲座（延伸专题；官方 L24 曾提 trie 思路）。

核心概念与算法原理

Trie（前缀树 / 字典树）

问题定义。 维护一个词典，支持三类查询：① 某单词是否存在（search）；② 是否存在以某前缀开头的单词（startsWith，自动补全的地基）；③ 以某前缀开头的单词共有几个。用二叉搜索树存词典：查找要 O(k log n)（k 为词长，每次节点比较都要逐字符比）；用哈希表存词典：整词查找 O(k)、很优秀，但它无法回答前缀问题——“startsWith(“ca”)”要枚举所有键，退化为 O(nk)。Trie 用“按字符共享前缀”的树结构同时解决两者。

直观解释（它是什么？）。 把词典想象成电话簿整理现场：凡是共享前缀的单词，就让它们共用前缀这一段路，只在分叉处才另开枝杈。树的每条边标一个字符，从根出发沿边下行，路径上拼出的字符串就是“走到这里为止所代表的前缀”；某个节点若是某个完整单词的结尾，就给它打个“词尾”标记（isWord）。于是：查单词 = 沿字符下行看能否走完且终点带词尾标记；查前缀 = 只看能否走完，不问词尾。

Trie 结构图示（词表：cat, car, card, cart, dog, do）：

                 (root)
           'c' /        \ 'd'
             [ ]          [ ]
         'a' /              \ 'o'
           [ ]                [*]          ← 词尾：拼出 "do"
       'r' /   \ 't'          \ 'g'
         [*]    [*]            [*]         ← "car" / "cat" / "dog"
      'd'/ \'t'
      [*]   [*]                            ← "card" / "cart"
（* 表示该节点是一个完整单词的结尾；同一字符在不同深度可以出现多次，
  因为前缀路径不同——图中两个 't' 分别属于 cat 与 cart）

操作/步骤分解（孩子集合用“字符 → 子节点”的映射存储）：

insert("cart")：
  1. 从根开始，逐个字符 'c'→'a'→'r'：都存在则沿指针下行
  2. 到字符 't'：当前节点没有 't' 孩子 → 新建子节点并下行
  3. 走完所有字符后，把所在节点标记 isWord = true

search("car")：沿 c-a-r 下行成功；终点节点 isWord == true  → 存在
search("ca")：沿 c-a 下行成功；但终点 isWord == false       → 不是单词
startsWith("ca")：沿 c-a 下行成功（不管 isWord）            → 有此前缀
startsWith("cx")：走到 'x' 时找不到孩子                       → 无此前缀

孩子容器的取舍（实现时必选其一）：定长数组（如 Node* children[26]）：按下标 O(1) 直达孩子，速度最快，但每个节点都占 26 个指针槽——词典稀疏时大量空槽，仅适合“纯小写英文字母”这类小字母表；std::map<char, Node*>：孩子按需分配、内存只随实际分叉走，代价是每次找孩子 O(log 字母表)——字母表通常很小（26/52/256），可视为常数，代码也更通用（可存任意字符集）；std::unordered_map：期望 O(1) 找孩子，但引入哈希开销与无序遍历，对字符键收益有限。本讲示例选 map 版本，重点讲清“共享前缀”的树逻辑。

应用：拼写检查与词典（Lexicon）、搜索框自动补全与联想、IP 路由的最长前缀匹配、基因序列匹配、前缀计数/词频统计。代价与收益一句话：一次查询只与词长 k 有关，与库中单词总数 n 无关——这正是 Trie 相对树/哈希的杀手锏。

Union-Find（并查集 / 不相交集合 Disjoint Set）

问题定义。 维护 n 个元素，它们被动态地合并成若干组（集合）。支持两个操作：find(x) 回答“x 属于哪一组”（返回该组的代表元/根）；union(a, b) 把 a、b 所在的两组合并为一组。应用：社交网络“两人是否间接认识”、电网/计算机是否连通、Kruskal 求最小生成树时判断“加这条边会不会成环”、图像区域标记、网格渗透模拟等——凡是“关系不断增多、随时要问是否同组”的问题都是它的主场。

直观解释与实现思路。 把每个集合表示成一棵“只认爹”的树：每个元素记一个 parent（parent[i] 指向父节点），根节点的 parent 指向自己，根就是集合代表元。find(x) 沿 parent 链爬到根；union(a,b) 先 find 出两个根，若相同说明本就在一组（合并无意义，甚至意味着“这条边成环”），否则把一棵树的根接到另一棵根下。朴素实现最坏会退化成 O(n) 的深链（每次把一棵整树挂到另一棵下），所以必须配两个加速器：

1. 按秩合并（union by rank/size）：永远把“矮树/小树”的根接到“高树/大树”的根下。这样树高最多 O(log n)，单次 find 最坏 O(log n)。
2. 路径压缩（path compression）：find 爬向根的过程中，把沿途经过的所有节点直接挂到根下。下次再 find 它们就是一步直达。

两者合体后，单次操作的摊还复杂度是 O(α(n))——α 是增长极慢的反阿克曼函数，对任何现实规模的 n 都 ≤ 4，工程上可放心当作 O(1)。

按秩合并示意（rank 即树高）：              路径压缩示意（箭头 = parent 指向）：
  集合1（根0，rank 2）   集合2（根3，rank1）    find(5) 之前           find(5) 之后
        [0]                   [3]                 0 ← 1                0 ← 1
       /   \                   |                  0 ← 2 ← 4 ← 5    →   0 ← 2
     [1]   [2]               [4]                  0 ← 3                0 ← 3
  rank[3] < rank[0] → 把 3 挂到 0 下：              （5 沿 4、2 爬到 0）   0 ← 4
        [0]                                                             0 ← 5
       / | \
    [1] [2] [3]                                    （沿途 5、4、2 全部直指根 0，
              \                                         树从此“变扁”）
              [4]

代码示例与实现详解

示例 1：Trie 类（insert / search / startsWith / 前缀计数）。

#include <iostream>
#include <map>
#include <string>
using namespace std;

class Trie {
public:
    Trie() : root_(new Node()) {}
    ~Trie() { delete root_; }                       // 级联释放整棵树
    Trie(const Trie&) = delete;                     // 含裸指针：禁拷贝防双重释放
    Trie& operator=(const Trie&) = delete;

    void insert(const string& word) {
        Node* cur = root_;
        for (char c : word) {
            auto it = cur->children.find(c);
            if (it == cur->children.end())          // 缺孩子就新建
                it = cur->children.emplace(c, new Node()).first;
            cur = it->second;
        }
        cur->isWord = true;                         // 词尾打标
    }

    bool search(const string& word) const {         // 整词存在？
        Node* cur = findNode(word);
        return cur != nullptr && cur->isWord;
    }

    bool startsWith(const string& prefix) const {   // 有此前缀？
        return findNode(prefix) != nullptr;
    }

    int countWordsWithPrefix(const string& prefix) const {
        Node* cur = findNode(prefix);
        return cur == nullptr ? 0 : countWords(cur);
    }

private:
    struct Node {
        map<char, Node*> children;                  // 字符 → 子节点
        bool isWord = false;
        ~Node() {                                   // 递归销毁子树
            for (auto& p : children) delete p.second;
        }
    };

    Node* findNode(const string& s) const {         // 沿字符下行，走不通返回空
        Node* cur = root_;
        for (char c : s) {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) return nullptr;
            cur = it->second;
        }
        return cur;
    }

    static int countWords(const Node* cur) {        // 统计子树里的词尾数
        int total = cur->isWord ? 1 : 0;
        for (auto& p : cur->children) total += countWords(p.second);
        return total;
    }

    Node* root_;
};

int main() {
    Trie t;
    for (const string& w : {"cat", "car", "card", "cart", "dog", "do"})
        t.insert(w);
    cout << "search(cat)  = " << t.search("cat") << "  (整词)\n";
    cout << "search(ca)   = " << t.search("ca") << "  (前缀不是词!)\n";
    cout << "startsWith(ca) = " << t.startsWith("ca") << "\n";
    cout << "startsWith(do) = " << t.startsWith("do") << "\n";
    cout << "startsWith(xy) = " << t.startsWith("xy") << "\n";
    cout << "以 ca 开头的完整单词数 = " << t.countWordsWithPrefix("ca")
         << " (期望 4: cat/car/card/cart)\n";
    cout << "以 car 开头的完整单词数 = " << t.countWordsWithPrefix("car")
         << " (期望 3: car/card/cart)\n";
    return 0;
}

【代码做什么】 用图示词表建树，逐条验证四类查询：search("cat") 为真而 search("ca") 为假（演示“走到前缀 ≠ 单词存在”，词尾标记在此刻是关键）；startsWith 只问“路通不通”；前缀计数用递归统计子树里的词尾总数——输出与上节结构图完全对应。

【实现机制解说】 ① “词尾标记 + 路径可达”两个条件分别支撑 search 与 startsWith：findNode 只负责“路是否走得通”，isWord 负责“走到这里是否是一个完整的词”，两者缺一不可。② 孩子用 std::map<char, Node*> 按需分配，树上只有“实际分叉”才有子节点；每个节点 O(log 26) 的查孩子代价可视为常数。若换成 Node* children[26]：查找变 O(1) 直取，但每个节点固定 26 个指针（约 208 字节），空分叉越多浪费越大——空间换时间的老戏码，按字符集大小取舍。③ 裸指针意味着必须管好内存：Node 析构时递归 delete 所有孩子，Trie 析构 delete 根即可级联清空；同时把拷贝构造/赋值 delete 掉，防止浅拷贝导致双重释放。④ 若只问“有多少词以某前缀开头”，可给每个节点额外存一个 count（插入时沿途 +1），把递归统计降为 O(k)——自动补全里常用的优化。

示例 2：UnionFind（路径压缩 + 按秩合并，含连通分量计数与判环演示）。

#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

class UnionFind {
public:
    explicit UnionFind(int n)
        : parent_(n), rank_(n, 0), count_(n) {
        iota(parent_.begin(), parent_.end(), 0);   // 初始每人自成一组，parent[i]=i
    }

    int find(int x) {                              // 带路径压缩
        if (parent_[x] != x)
            parent_[x] = find(parent_[x]);         // 沿途节点全部直挂根下
        return parent_[x];
    }

    // 合并 a、b 所在组；返回 false 表示它们本就在一组（可用于判环）
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                // 已同组：若这是条边，则成环
        if (rank_[ra] < rank_[rb]) swap(ra, rb);   // 矮树根挂到高树根下
        parent_[rb] = ra;
        if (rank_[ra] == rank_[rb]) ++rank_[ra];   // 两树等高手动加一
        --count_;                                  // 两个连通分量合并成一个
        return true;
    }

    bool connected(int a, int b) { return find(a) == find(b); }
    int count() const { return count_; }           // 当前连通分量个数

private:
    vector<int> parent_;
    vector<int> rank_;                             // 树高上界
    int count_;
};

int main() {
    cout << "--- 连通性演示 ---\n";
    UnionFind uf(6);                               // 顶点 0..5
    uf.unite(0, 1);
    uf.unite(1, 2);                                // 现在 {0,1,2} 一组
    uf.unite(3, 4);                                // {3,4} 一组，5 单独
    cout << "分量数 = " << uf.count() << " (期望 3)\n";
    cout << "connected(0,2) = " << uf.connected(0, 2) << "\n";
    cout << "connected(0,3) = " << uf.connected(0, 3) << "\n";
    uf.unite(2, 3);                                // 打通两大组
    cout << "合并 {0,1,2} 与 {3,4} 后分量数 = " << uf.count() << " (期望 2)\n";
    cout << "connected(0,4) = " << uf.connected(0, 4) << "\n";

    cout << "\n--- Kruskal 式判环演示（加边时若 unite 返回 false 即成环）---\n";
    UnionFind k(3);
    cout << "边 0-1: " << (k.unite(0, 1) ? "加入" : "成环!") << "\n";
    cout << "边 1-2: " << (k.unite(1, 2) ? "加入" : "成环!") << "\n";
    cout << "边 2-0: " << (k.unite(2, 0) ? "加入" : "成环!") << "  ← 0、2 已同组\n";
    return 0;
}

【代码做什么】 前半在 6 个顶点上做四次 union，实时打印连通分量个数（3 → 2），并验证 0 与 2 连通、0 与 3 起初不连通、打通后 0 与 4 连通——模拟“社交网络逐渐相连”。后半用 3 个顶点模拟 Kruskal 加边：前两条边正常合并，第三条边 2-0 时两端早已同组，unite 返回 false，报出“成环”——这正是 Kruskal 判环的完整机理。

【实现机制解说】 ① find 的递归压缩 parent_[x] = find(parent_[x]) 一行同时完成“查根”与“把沿途节点直挂根下”：递归返回时层层改写 parent，下次查询一步到位；递归深度由按秩合并保证在 O(log n) 内，不会爆栈（压栈优化前）。② 按秩合并维护的是“树高的上界”而非精确高度：rank 小的根挂到 rank 大的根下，只有两棵等高的树合并才把新根 rank +1——这让任何一棵树的高度始终被钉在 O(log n)。若改为按大小合并（size 大的当根），效果等价、语义更直观，二者选一即可。③ unite 返回“是否真的合并”是刻意设计：判环（Kruskal）、统计最终连通分量都依赖这个返回值；count_ 每次成功合并减一，比事后数根更省。④ 思考“为什么不能省略路径压缩”：只有压缩没有按秩，摊还仍接近 O(1)；只有按秩没有压缩，最坏 O(log n)——两个都做才是教科书级的 O(α(n))。

复杂度分析

设 k = 单词长度/操作涉及的词长，n = 词典词数或元素总数，S = 词典总字符数（所有单词长度之和）。

对比参考：BST 版词典查找 O(k log n)；哈希表整词查找 O(k) 但无法做前缀查询——Trie 的 O(k) 前缀能力正是它不可替代之处。Union-Find 不按树高而按“接近常数”收费，是“摊还分析”的又一范例。

关键要点

• Trie 以字符为边、共享前缀：查询代价 O(词长) 与词库规模无关，且天然支持前缀匹配——BST 与哈希都做不到。
• “路径走得通”与“终点是词尾”是两回事：search 要 isWord，startsWith 只要路通——词尾标记是 Trie 设计的第一性细节。
• 孩子存储按字母表取舍：小字母表用定长数组换速度，通用/稀疏场景用 map 按需分配；裸指针树务必写析构与禁拷贝。
• Union-Find 两板斧缺一不可：按秩合并把树高钉在 O(log n)，路径压缩让 find 一步到位——合体后单次操作摊还 O(α(n))，工程上视为 O(1)。
• unite 的返回值就是判环信号：Kruskal 与“数连通分量”都建立在“合并失败 = 早已同组”这一观察上。

常见陷阱与注意事项

• Trie 忘打 / 漏查 isWord：search("do") 与 startsWith("do") 语义被混淆。规避：整词查询必须“走到位 + 查词尾标记”。
• Trie 把“节点存在”当“单词存在”：前缀节点不是词。规避：回忆 search("ca") 应为 false 的例子。
• Trie 的 insert 每词都从根开始、共享前缀时重复建节点：造成空间浪费与错误计数。规避：逐字符找现有孩子，缺了才 new。
• Trie 内存泄漏 / 双重释放：忘写析构会泄漏整棵树；浅拷贝会让两对象共享指针、析构两次。规避：Node 递归析构 + 类内 delete 拷贝构造/赋值（或改用 unique_ptr 树）。
• 空字符串当单词插入：根节点即词尾，search(“”) 语义要定义清楚。规避：明确约定并让根节点 isWord 可被置位。
• Union-Find 的 find 忘了压缩：只做按秩合并最坏 O(log n) 虽可用，但失去接近 O(1) 的威力。规避：find 里顺手改写 parent。
• union 时把 parent 方向搞反（parent[ra] = rb 写成 parent[rb] = ra 与 rank 判断不配套），或忘了 rank 相等时 +1：树高失控。规避：先比 rank 再定谁当父；等高合并必须给新根加秩。
• 把 count_ 忘减 / 在 union 失败时也减：分量数失真。规避：只在 unite 成功返回 true 时 --count_（本实现已内置）。
• find 写迭代版却忘记第二次循环压缩：迭代实现要再走一遍路径改写 parent。规避：递归版一行完成，初学者最不易错。

思考题（带答案）

问题 1：为什么 Trie 的 search 必须检查词尾标记，而 startsWith 不需要？请以词表 {“do”} 为例说明。 答案：查 “d” 时路径是通的（它是 “do” 的前缀节点），但 “d” 并不是词典中的词——search 若不查 isWord 就会误报存在；startsWith 只问“有没有以 d 开头的词”，路径通即可回答“有”。所以 search(“d”) = false、startsWith(“d”) = true 的差别全部由词尾标记承载。

问题 2：若要从 Trie 中删除一个单词（而不只是查询），步骤是什么？删除 “cart” 而保留 “car” 时能删掉哪些节点？ 答案：先沿路径走到词尾节点、把 isWord 置 false；然后从该节点自底向上回收“不再被任何单词使用”的节点——即既非词尾、又没有孩子的节点（“cart” 的尾字符 t 节点符合，可删；其父节点 r 是 “car” 的词尾，必须保留）。实现常配合引用计数或“children 为空才删”的递归回收。

问题 3：只用 unite 的返回值，如何在完全不改动并查集的情况下数出“加完所有边后还剩几个连通分量”，并指出哪条边是“多余”的？ 答案：初始分量数 = n；每调用一次 unite 且返回 true 就减一，返回 false 的那条边两端早已连通——它要么成环（判环），要么是冗余边。最终剩余计数就是连通分量个数。这正是 Kruskal 求最小生成树时“按边权从小到大加边、成环就跳过”的判环内核。