专题进阶 · 树与范围查询推荐总顺序 · 第 52 / 148 课

按字符共享前缀,区分路径存在与完整单词结束。

先学会这些,再进入本课 字符串 哈希表 二叉树
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

字典树Trie

共享字符串前缀的树,查询时间与键长有关,空间取决于字符分支表示。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

按字符共享前缀,区分路径存在与完整单词结束。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

词典含 to、tea、ten。判断 te 是否为前缀,以及是否为完整单词,为什么需要不同答案?

02一步步得到方法

把字符串拆成逐字符决策

根代表空前缀,从根沿字符边前进,走过的路径拼成当前前缀。to、tea、ten 共享第一条 t 边;tea 与 ten 还共享 e 边,因此无需为每个词重复保存完整前缀。

节点需要终止标记。路径 te 存在只能证明某些单词以 te 开头;只有终止标记为真才表示 te 本身在词典中。空字符串若允许存入,则终止标记写在根上。

结构选择决定空间

每节点可用固定字母表数组,索引快但浪费空槽;也可用字典只保存存在的边。字典版适合字符集大而分支稀疏的情况,代价包含哈希与对象开销。

查询长度 m 的词最多走 m 条边,不依赖词典中其他词的长度。要列出一个前缀的所有补全,还要遍历对应子树并输出答案,成本不能只写 O(m)。

前缀存在与完整单词是两件事

插入 apple 会创建 a、ap、app 等前缀路径,但不意味着这些前缀都已作为完整单词插入。终止标记负责区分路径存在和单词结束,空字符串则对应根节点的终止标记。

删除时先取消单词结束标记,再决定哪些没有孩子且不再表示单词的节点可回收。不能因为删一个单词就把整条路径移除,否则会破坏共享前缀的其他单词。

03把一个小例子完全算清楚

插入 to、tea、ten,再查询 te。

步骤计算与状态为什么这样做
插入 to根→t→o,o 标记结束创建两条边
插入 tea复用 t,新建 e、aa 标记结束
插入 ten复用 t、e,新建 nn 标记结束
查询 te路径到达 e,但 e 未结束前缀 True,完整词 False

窄屏可左右滑动表格,阅读完整计算与理由。

终止标记将单词集合与所有前缀集合区分开。

04为什么这个方法成立

  1. 每次插入沿已有边复用,不存在的边才新建,因此路径与字符前缀一一对应。
  2. 词尾终止标记恰好对应曾完整插入的字符串。
  3. 查询遇到缺边即可否定;走完后检查词尾标记即可判断完整成员。

05把推导翻译成代码

Python · 可独立运行的教学实现

class Trie:
    def __init__(self):
        self.root = {}
        self.end = object()
    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end] = True
    def walk(self, text):
        node = self.root
        for char in text:
            if char not in node:
                return None
            node = node[char]
        return node
    def contains(self, word):
        node = self.walk(word)
        return node is not None and self.end in node
    def starts_with(self, prefix):
        return self.walk(prefix) is not None

逐个理解关键决定

self.end = object()
独立哨兵不会与任何字符串字符冲突。
node is not None
空字典也是合法节点,不能把真假值直接当路径是否存在。

06时间、空间与实现范围

插入、精确查询与前缀存在查询平均 O(m),m 为码点数。

节点数至多总字符数加根,字典节点开销可能显著;列举补全还需加访问和输出规模。

07改变条件,检查哪里会出错

节点存在就说明单词存在

必须检查终止标记。

删除单词时直接删除整条路径

会误删共享前缀;先去掉终止标记,再仅清理没有孩子且非词尾的节点。

忽略字符集与节点表示

固定大字母表数组可能浪费空间,字典更稀疏;复杂度要结合字符长度和边存储成本。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

再插入 te 后,tea 会消失吗?

需要一点提示

只增加终止标记。

查看解析与答案

不会。e 同时是词尾和更长词的前缀。

练习 2 · 边界与辨析

空前缀是否存在?

需要一点提示

它对应根。

查看解析与答案

存在,即使词典为空也有根;是否有任何补全则是另一个问题。

练习 3 · 变式与迁移

AC 自动机在 Trie 上补了什么?

需要一点提示

文本失配后如何复用后缀?

查看解析与答案

失败链接,使一次文本扫描能转向仍可能匹配的最长后缀前缀状态,下一专题会推导。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。