字典树（Trie）

字典树用于处理前缀相关查询。能以 O(单词长度) 的时间完成插入、查找、前缀统计，并天然支持自动补全、词频统计、最长公共前缀等操作。在算法竞赛中，Trie 是字符串处理的基础武器，尤其适合多模式匹配和大量字符串的集合维护。

字典树的思想

Trie 是一棵多叉树，每个结点代表一个字符，从根到该结点的路径拼起来即为一个前缀。根结点为空，每个结点拥有若干子结点，对应下一个字符。

• 结点结构：

• children：子结点映射（字符 → 结点）
• cnt：经过该结点的单词数量（即以此为前缀的单词个数）
• is_end：标记是否存在以该结点结尾的单词

• 插入：从根开始，沿字符路径向下走，若某字符无对应子结点则新建，最后在结尾结点标记 is_end=True，同时沿途所有结点的 cnt++

• 查找单词：同样沿路径走，若中途缺失则不存在，否则检查最后结点的 is_end

• 前缀统计：走完前缀路径后，返回结点的 cnt

样板

classTrie:
def__init__(self):
        self.children = {}
        self.cnt = 0# 经过该结点的单词数（前缀次数）
        self.is_end = False# 是否有单词在此结束

definsert(self, word):
        node = self
for ch in word:
if ch notin node.children:
                node.children[ch] = Trie()
            node = node.children[ch]
            node.cnt += 1
        node.is_end = True

defsearch(self, word):
        node = self
for ch in word:
if ch notin node.children:
returnFalse
            node = node.children[ch]
return node.is_end

defstarts_with(self, prefix):
        node = self
for ch in prefix:
if ch notin node.children:
return0
            node = node.children[ch]
return node.cnt

实例：

t = Trie()
words = ["apple", "app", "application", "appetite", "banana"]
for w in words:
    t.insert(w)
print(t.search("apple"))      # True
print(t.search("app"))        # True
print(t.search("appl"))       # False（前缀，不完整）
print(t.search("banana"))     # True

print(t.starts_with("app"))   # 4 (apple, app, application, appetite)
print(t.starts_with("appl"))  # 2 (apple, application)
print(t.starts_with("ban"))   # 1 (banana)
print(t.starts_with("cat"))   # 0

关键点解读

1. children 用字典实现：通用性最好，支持任意字符集。对于仅小写字母的题目，可用长度为 26 的数组加速，children = [None]*26，并通过 ord(ch)-97 映射。数组版常数更小，但需要事先知道字符集大小。
2. cnt 的作用：不仅用于前缀计数，还可用于删除操作，实现动态维护。
3. is_end：区分“单词”与“前缀”。如果不需要区分可以省略。

复杂度分析

• 插入/查找/前缀检查：O(L)，L 为单词或前缀长度
• 空间：最坏情况下，每个结点存储一个字符，结点数 ≈ 所有单词的字符总数。插入 N 个单词，平均长度 L，则空间复杂度 。但只要单词间共享前缀，实际结点数远小于 。

典型应用场景

1. 单词集合维护（插入、删除、查询）

• 支持动态增删单词（删除时只需沿路径将 cnt 减 1，并将 is_end 置 False，可考虑回收无子结点）。
• 查询单词是否存在：search(word)

2. 前缀统计 & 自动补全

• 给定前缀，返回有多少单词以它为前缀：starts_with(prefix)
• 进一步可收集所有以某前缀开头的单词（需要遍历子树）。

3. 最长公共前缀

• 插入所有字符串后，从根开始向下走，只要当前结点只有一个子结点，就继续，遇到分支或结束则停止。

4. 词频统计（带权 Trie）

• 可以给每个结点增加一个 freq 字段，统计该前缀出现的总次数（例如搜索引擎的搜索词提示）。

5. 异或最大值问题（二进制 Trie）

• 将数字的二进制位（从高位到低位）插入 Trie，然后对每个数贪心走相反位寻找最大异或值。这是 Trie 在数字处理中的经典应用（如 LeetCode 421）。

6. 字符串排序

• 对 Trie 进行 DFS 即得到字典序排序结果（因为子结点有序时，先序遍历即排序）。

变种

1. 数组实现

当字符集为小写字母时，用列表代替字典可大幅提升效率：

classTrieArray:
def__init__(self):
        self.children = [None]*26
        self.cnt = 0
        self.is_end = False

definsert(self, word):
        node = self
for ch in word:
            idx = ord(ch)-97
if node.children[idx] isNone:
                node.children[idx] = TrieArray()
            node = node.children[idx]
            node.cnt += 1
        node.is_end = True

2. 删除操作

defdelete(self, word):
    node = self
    path = []
for ch in word:
if ch notin node.children:
returnFalse
        path.append((node, ch))
        node = node.children[ch]
ifnot node.is_end:
returnFalse
    node.is_end = False
# 逆向沿途减少 cnt，并删除无用的分支
for n, ch in reversed(path):
        n.children[ch].cnt -= 1
if n.children[ch].cnt == 0:
del n.children[ch]
else:
break
returnTrue

3. 持久化 Trie

可持久化 Trie 用于处理区间异或等问题，是高级数据结构。

4. AC 自动机 = Trie + KMP 的失败指针

用于多模式串匹配，是 Trie 最重要的扩展之一。

练习题

• 入门：
  LeetCode 208. 实现 Trie (前缀树)
  LeetCode 720. 词典中最长的单词
  洛谷 P2580 于是他错误的点名开始了（简单 Trie 统计）

• 前缀相关：
  LeetCode 211. 添加与搜索单词 - 数据结构设计（支持通配符 '.'）
  LeetCode 677. 键值映射（带权 Trie）

• 二进制 Trie（异或最值）：
  LeetCode 421. 数组中两个数的最大异或值
  洛谷 P4551 最长异或路径（树上前缀异或 + Trie）

• 进阶：
  LeetCode 212. 单词搜索 II（Trie + DFS/回溯）
  Codeforces 706D Vasiliy's Multiset（删除操作的二进制 Trie）