字典树 Trie：前缀检索与自动补全

FreeGuideOnline 最新 2026-06-18

什么是字典树（Trie）

字典树，又称前缀树或单词查找树，是一种专门用于处理字符串集合的树形数据结构。它的核心思想是利用字符串之间的公共前缀，将重复的前缀合并存储，从而大幅减少存储空间并加快检索速度。你可以把它想象成一棵“字母树”，从根节点出发，每一条路径代表一个字符串。

与哈希表、平衡树等通用数据结构不同，字典树在处理大量具有相同前缀的字符串时，展现出极高的效率。比如自动补全、拼写检查、IP 路由最长前缀匹配等场景，底层都离不开字典树的身影。

核心优势

前缀检索快速：判断一个字符串是否是已插入集合的前缀，时间复杂度仅与查询字符串长度成正比。
公共前缀压缩存储：大量共享前缀的字符串只需存储一次公共部分。
有序遍历：对字典树进行先序遍历可以直接得到所有字符串的字典序排列。

局限性

空间开销较大：每个节点都需要存储指向子节点的指针数组，当字符集较大（如 Unicode）时空闲指针会浪费很多内存。
不适合短字符串集合：如果集合中大多数字符串没有公共前缀，字典树的优势就会减弱。

字典树的结构与原理

一个典型的字典树由节点（Node）组成，每个节点包含两个关键信息：

子节点指针：通常用一个固定大小的数组（假设字符集为小写字母 a-z，则大小为 26）或哈希表、有序数组来存储指向下一层字符的引用。
结束标记：一个布尔值，表示从根节点到当前节点的路径是否构成一个完整单词。

例如，插入单词 "cat", "car", "dog" 后，字典树结构如下：

        root
       /   \
      c     d
     /       \
    a         o
   / \         \
  t   r         g
(单词) (单词)   (单词)

根节点不存储任何字符。
路径 c -> a -> t 的最后一个节点 t 标记为单词结束。
路径 c -> a -> r 的最后一个节点 r 标记为单词结束。
路径 d -> o -> g 的最后一个节点 g 标记为单词结束。

可以看到，公共前缀 "ca" 只存储了一次，这正是字典树节省空间的核心。

基本操作实现（以英文小写字母为例）

我们假设字符集只有 26 个小写英文字母，这样每个节点可以用一个长度为 26 的数组存放子节点指针。当然你也可以用 Map 或更紧凑的 List 来适配更大的字符集。

节点定义

class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # 26个小写字母
        self.is_end = False          # 标识是否为一个完整单词

为了简化操作，通常再包装一层 Trie 类，内部持有根节点。

class Trie:
    def __init__(self):
        self.root = TrieNode()

插入单词 (Insert)

从根节点开始，遍历单词的每一个字符：

计算字符对应的索引 index = ord(ch) - ord('a')。
如果当前节点的 children[index] 为空，则新建一个节点。
移动到该子节点，继续处理下一个字符。
遍历结束后，将最后一个节点的 is_end 设为 True。

def insert(self, word: str) -> None:
    node = self.root
    for ch in word:
        idx = ord(ch) - ord('a')
        if not node.children[idx]:
            node.children[idx] = TrieNode()
        node = node.children[idx]
    node.is_end = True

时间复杂度：O(L)，L 为单词长度。

查找单词 (Search)

与插入过程类似，但在遍历过程中如果发现某个 children[idx] 为空，说明该单词不存在，直接返回 False。如果顺利遍历完所有字符，最后需要检查当前节点的 is_end 是否为 True（因为可能只是一个前缀，而不是一个完整单词）。

def search(self, word: str) -> bool:
    node = self.root
    for ch in word:
        idx = ord(ch) - ord('a')
        if not node.children[idx]:
            return False
        node = node.children[idx]
    return node.is_end

前缀匹配 (StartsWith)

与前缀相关的查询非常关键。判断一个前缀是否存在于字典树中，过程和搜索几乎一样，唯一的区别是：遍历完所有字符后，不需要检查 is_end 标记。只要没有中途遇到空指针，就说明这个前缀存在。

def startsWith(self, prefix: str) -> bool:
    node = self.root
    for ch in prefix:
        idx = ord(ch) - ord('a')
        if not node.children[idx]:
            return False
        node = node.children[idx]
    return True

这个方法正是自动补全、拼写建议等功能的基础。

进阶应用：自动补全的实现

自动补全功能依赖两个关键步骤：

定位前缀终点：从根节点开始，沿着前缀字符串一直走到对应的节点。
深度优先遍历子树：从该节点出发，遍历所有可能的路径，每次遇到 is_end == True 的节点，就将路径上的字符拼接成一个完整单词，加入结果集。

下面给出一个简单实现，按字典序返回所有以给定前缀开头的单词。

def get_words_with_prefix(self, prefix: str) -> list:
    node = self.root
    # 第一步：定位前缀终点
    for ch in prefix:
        idx = ord(ch) - ord('a')
        if not node.children[idx]:
            return []  # 前缀都不存在
        node = node.children[idx]
    
    # 第二步：收集从该节点开始的所有单词
    result = []
    self._dfs(node, prefix, result)
    return result

def _dfs(self, node: TrieNode, current_word: str, result: list):
    if node.is_end:
        result.append(current_word)
    for i in range(26):
        if node.children[i]:
            ch = chr(i + ord('a'))
            self._dfs(node.children[i], current_word + ch, result)

如果需要根据词频排序，可以在节点中额外存储热度值，并在 DFS 时使用优先队列收集结果。

空间优化技巧

当字符集很大或者字符串非常稀疏时，固定大小的数组会浪费大量内存。此时可以考虑以下优化：

动态数组 + 二分查找：每个节点使用一个有序列表存储 (字符, 子节点指针)，通过二分查找定位字符。查询速度稍慢但节省内存。
哈希表节点：每个节点使用 HashMap 或 dict 存储子节点，查询仍为 O(1) 平均时间，对稀疏情况更友好，但哈希表本身有额外开销。
压缩前缀（Radix Tree）：将只有一个子节点的链压缩成一个节点，存储整个子串，可以有效减小树的高度和节点数量。这种结构常用于路由表和文件系统。
位图 + 数组（针对较小字符集）：例如对于 26 个字母，可以用一个 int 位图表示哪些子节点存在，同时动态分配一个非空子节点的数组，兼顾速度和内存。

常见面试题变体

单词搜索 II（LeetCode 212）：在二维字符网格中查找字典树中存在的所有单词。核心是将单词列表构建成 Trie，然后在网格上回溯时同步遍历 Trie，一旦发现当前路径节点在 Trie 中不存在即可剪枝。
键值映射（LeetCode 677）：单词对应一个数值，要求支持 insert 和 sum(prefix) 操作，返回所有以该前缀开头的单词的数值总和。可以在每个节点上存储以当前前缀为路径的数值总和，插入时沿途更新。
最大异或值（LeetCode 421）：给定非负整数数组，查找两个数异或后的最大值。可以将每个数的二进制表示插入字典树（只有 0 和 1），然后对于每个数，在树中优先走相反的位。
单词替换（LeetCode 648）：用词根替换句子中的单词。将词根插入字典树，对于句子中的每个单词，在树中查找最短匹配前缀并替换。

总结与延伸

字典树是一种以空间换时间的数据结构，特别擅长处理前缀相关的操作。在实际工程项目中，搜索引擎的搜索建议、IDE 的代码补全、输入法的联想输入都广泛使用了字典树或其变种。掌握字典树不仅能够帮助你更高效地解决字符串问题，也为理解压缩树、后缀树等更高级的数据结构打下基础。

如果你希望进一步深入，可以学习以下相关主题：

AC 自动机：在字典树基础上增加失败指针，用于多模式串匹配。
后缀树与后缀数组：处理字符串子串问题的高效结构。
双数组字典树 (Double-Array Trie)：一种内存极其紧凑的 Trie 实现，常用于电子词典和语言模型。

动手实践是掌握字典树的最佳方式。 你可以从实现一个基本的 Trie 开始，然后依次添加自动补全、删除单词、词频统计等方法，逐步体会这种结构的精妙之处。