Part 6.2：Trie 树（字典树）

引言：搜索引擎的“自动补全”魔法

当你在搜索引擎的输入框中键入“algo”时，它会立刻弹出一个下拉列表，提示“algorithm”、“algorithms tutorials”、“algorithmic trading”等可能的补全选项。这个看似神奇的“自动补全”功能，背后就有一种强大的数据结构在支撑——Trie 树。

Trie 树，又称字典树或前缀树，是一种专门为高效处理字符串集合而设计的树形数据结构。它的核心思想是空间换时间，利用字符串的公共前缀来减少不必要的比较，从而实现对字符串的快速插入、查找和前缀搜索。

想象一下，如果用哈希表来存储一个庞大的词典，并实现前缀搜索功能。当你输入“algo”时，你不得不遍历整个哈希表，检查每一个单词是否以“algo”开头。当词典规模达到百万级别时，这种方法的延迟是无法接受的。

Trie 树则完美地解决了这个问题。它将字符串的每个字符作为树的一个节点，将整个词典构建成一棵巨大的树。查找以“algo”为前缀的所有单词，就变成了在这棵树上沿着路径 a -> l -> g -> o 走下去，然后遍历该路径终点节点下的所有子树即可，效率极高。

为什么 Trie 树如此重要？

面试价值：Trie 树是面试中考察字符串处理和数据结构设计能力的经典题目。能徒手实现一个 Trie 树，并解释其原理和应用，是展现你数据结构功底的绝佳方式。
工程价值：Trie 树是许多现实应用的核心。除了搜索引擎的自动补全，它还广泛应用于敏感词过滤、IP 路由表、拼写检查、输入法联想等场景。

本文将带你从零开始，构建一个 Trie 树，并掌握其核心操作的实现。

背景知识：树形结构与字符映射

Trie 树是一种多叉树。与二叉树每个节点最多有两个子节点不同，Trie 树的一个节点的子节点数量，取决于字符集的大小。

如果只处理小写英文字母，那么每个节点最多有 26 个子节点。
如果处理 ASCII 字符，那么每个节点最多有 128 个子节点。

每个节点通常包含以下信息：

子节点指针数组：一个大小为字符集大小的数组（或哈希表），children[i] 指向代表下一个字符的子节点。
结束标记：一个布尔值 is_end_of_word，用于标记从根到当前节点所构成的路径是否代表一个完整的单词。

图示：Trie 树的节点结构

class TrieNode:
  children: array/map of TrieNode
  is_end_of_word: boolean

详细算法原理

1. 算法的“直觉”：按“字母表”构建路径

Trie 树的构建过程非常直观，就像我们查字典一样。

假设我们要插入单词 tea 和 ten：

**插入 tea**：
- 从根节点开始，查找 t 的分支。没有，创建一个 t 节点。
- 移动到 t 节点，查找 e 的分支。没有，创建一个 e 节点。
- 移动到 e 节点，查找 a 的分支。没有，创建一个 a 节点。
- 移动到 a 节点，将其 is_end_of_word 标记为 True。
**插入 ten**：
- 从根节点开始，查找 t 的分支。有！直接沿着该分支走。
- 移动到 t 节点，查找 e 的分支。有！直接沿着该分支走。
- 移动到 e 节点，查找 n 的分支。没有，创建一个 n 节点。
- 移动到 n 节点，将其 is_end_of_word 标记为 True。

通过这种方式，公共前缀 te 被完美地复用了。

2. 核心操作

a. 插入 (Insert)

从根节点开始，遍历要插入单词的每个字符。
对于每个字符，检查当前节点的子节点中是否存在对应的分支。
如果不存在，创建一个新的 Trie 节点作为分支。
移动到对应的子节点。
单词遍历结束后，将最后一个节点的 is_end_of_word 标记为 True。

b. 查找 (Search)

从根节点开始，遍历要查找单词的每个字符。
对于每个字符，检查当前节点的子节点中是否存在对应的分支。
如果不存在，说明该单词不在 Trie 树中，返回 False。
如果存在，移动到对应的子节点。
单词遍历结束后，检查最后一个节点的 is_end_of_word 标记是否为 True。只有为 True，才说明这是一个完整的单词，而不是某个单词的前缀。

c. 前缀搜索 (Starts With)

与查找操作几乎完全相同。
区别在于，当要搜索的前缀遍历结束后，不需要检查 is_end_of_word 标记。只要路径存在，就说明存在以该字符串为前缀的单词，返回 True。

步骤分解 & 动画式案例

操作序列: insert("apple"), insert("apply"), search("apple"), search("app"), startsWith("app")

1. insert("apple")

root -> a -> p -> p -> l -> e (标记 e 为单词结尾)

图示 1
root -a-> (p) -p-> (p) -l-> (l) -e-> (e*) (*代表单词结尾)

2. insert("apply")

root -> a -> p -> p (路径复用)
p -> l (路径复用)
l -> y (创建新分支，标记 y 为单词结尾)

图示 2

         (p) -p-> (p) -l-> (e*)
        /               \
root -a->                 (y*)

3. search("apple")

root -> a -> p -> p -> l -> e (路径存在)
检查 e 节点的 is_end_of_word 标记，为 True。
返回 True。

4. search("app")

root -> a -> p -> p (路径存在)
检查 p 节点的 is_end_of_word 标记，为 False。
返回 False。

5. startsWith("app")

root -> a -> p -> p (路径存在)
不需要检查标记。
返回 True。

Python 实现

class TrieNode:
    def __init__(self):
        # 使用字典来存储子节点，更灵活，可以处理任意字符
        self.children = {}
        self.is_end_of_word = False

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

    def insert(self, word: str) -> None:
        """向 Trie 树中插入一个单词"""
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_end_of_word = True

    def search(self, word: str) -> bool:
        """查找一个单词是否在 Trie 树中"""
        curr = self.root
        for char in word:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return curr.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        """查找是否存在以指定前缀开头的单词"""
        curr = self.root
        for char in prefix:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return True

# --- 案例测试 ---
trie = Trie()
trie.insert("apple")
print(f"Search 'apple': {trie.search('apple')}")       # True
print(f"Search 'app': {trie.search('app')}")         # False
print(f"StartsWith 'app': {trie.startsWith('app')}")   # True
trie.insert("app")
print(f"Search 'app' after insert: {trie.search('app')}") # True

复杂度推导过程

设 n 为要操作的字符串的平均长度，m 为 Trie 树中字符串的总数。

时间复杂度

插入 (Insert): O(n)。我们需要遍历字符串的每一个字符。
查找 (Search): O(n)。我们需要沿着路径遍历字符串的每一个字符。
前缀搜索 (StartsWith): O(n)。我们需要沿着路径遍历前缀的每一个字符。

核心优势：Trie 树的所有核心操作的时间复杂度都只与待操作字符串的长度有关，而与 Trie 树中已经存储了多少个单词无关！这就是它比哈希表在某些场景下更高效的原因。

空间复杂度

空间复杂度: O(L * C)。其中 L 是所有单词的总长度，C 是字符集的大小。
在最坏情况下（所有单词都没有公共前缀），空间复杂度是所有单词字符数的总和。
在最好情况下（所有单词都是同一个单词），空间复杂度为 O(n)。

优势 / 劣势 / 易错点

优势

极高的前缀查询效率：前缀搜索的时间复杂度与词典大小无关，这是其最大优势。
排序输出：可以对 Trie 树进行 DFS 遍历，以按字典序输出所有单词。
无哈希冲突：与哈希表不同，Trie 树没有哈希冲突的问题。

劣势

空间开销大：如果字符集很大，或者公共前缀很少，Trie 树会占用大量内存。
只适用于字符串：Trie 树是为字符串类型专门设计的数据结构。

易错点

search 和 startsWith 的区别：search 必须检查 is_end_of_word 标记，而 startsWith 不需要。
根节点：根节点不代表任何字符，它只是所有路径的起点。
子节点存储：如果字符集固定且较小（如小写字母），可以用数组 [None]*26 来存储子节点，通过 ord(char) - ord('a') 映射索引，效率更高。如果字符集不固定或很大，用哈希表更灵活。

适用场景

自动补全 / 搜索建议：搜索引擎、代码编辑器、输入法。
敏感词过滤：将所有敏感词构建成一棵 Trie 树，可以快速判断一段文本是否包含敏感词（AC 自动机的基础）。
IP 路由：路由器的转发表（FIB）可以用 Trie 树（特别是压缩的 Patricia Tree）来存储，实现高效的最长前缀匹配。
拼写检查：快速判断一个单词是否存在于词典中。

总结

Trie 树（字典树）是一种通过牺牲空间来换取时间的数据结构，它将字符串的公共前缀信息编码在树的结构中，从而实现了与词典规模无关的高效前缀查询。

本文核心要点

✅ 核心思想：利用字符串的公共前缀，将每个字符映射为树的一个节点，形成一棵多叉树。
✅ 节点结构：包含一个子节点指针集合和一个单词结束标记。
✅ 三大操作：insert, search, startsWith 的时间复杂度均为 O(L)，其中 L 是操作字符串的长度。
✅ 关键区别：search 必须检查单词结尾标记，而 startsWith 不需要。
✅ 适用性：特别适用于需要高效处理大量字符串前缀相关问题的场景。

掌握了 Trie 树，你就拥有了一个处理字符串集合问题的强大工具。在下一篇文章中，我们将学习另一个精妙的字符串算法——Z-Algorithm，看看它是如何在线性时间内计算字符串与其所有后缀的最长公共前缀的。

大学算法全体系 > Part 6：字符串算法

#数据结构 #字符串 #Trie #字典树 #前缀树

Part 6.2：Trie 树（字典树）

https://hjjjkh.github.io/posts/f3d753f3

作者

李国强

发布于

2025年11月16日

许可协议

Part 3.5：二分查找：O(log n) 的有序搜索艺术上一篇

Part 3.4：堆排序：原地 O(n log n) 的选择下一篇