Trie（前缀树）详解：原理、代码与时间复杂度

Trie 解决什么问题

哈希集合能快速回答“这个确切的单词是否已存储？”，但如果不检查每个单词，就无法回答“哪些已存储的单词以 pre 开头？”。有序列表可以用二分查找回答前缀查询，但插入很慢。Trie 按前缀组织，所以前缀问题正是它的强项：搜索框中的自动补全、文字游戏、拼写检查，以及网络路由的最长前缀匹配。

用大白话理解 Trie

想想手机通讯录，你每输入一个字母就缩小一次范围。输入 c 会显示所有以 c 开头的人，输入 ca 范围更小，依此类推。Trie 存储单词的形状正是如此。根代表空前缀。每个节点有一个从下一个字符到子节点的映射，外加一个单词结束标志，因为像 car 这样的单词既可以是完整的单词，也可以是 cart 的前缀。

示例演练：插入 car、cart、cat 和 dog

这四个单词一共有 13 个字母，但根下面只需要 8 个节点（c, a, r, t, t, d, o, g），因为 car、cart 和 cat 共享 ca。查找 ca 会走过两个节点，作为前缀成功，但 ca 不是单词，因为它的节点没有标记为结束。查找 cow 在第二步就失败了：节点 c 没有孩子 o。

Python 实现

每个节点持有一个子节点的 dict，可以处理包括 Unicode 在内的任何字母表。starts_with 方法会收集某个前缀下的所有单词，这是自动补全的核心。

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node
    def contains(self, word):
        node = self._find(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            node, path = stack.pop()
            if node.is_word:
                out.append(path)
            for ch, child in node.children.items():
                stack.append((child, path + ch))
        return sorted(out)

t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
print(t.contains("car"), t.contains("ca"))  # True False
print(t.starts_with("ca"))                  # ['car', 'cart', 'cat']
print(t.starts_with("x"))                   # []

starts_with 会对输出排序，以得到稳定的顺序。真正的自动补全还会在前几个结果之后停止并对结果排名，例如按存储的热度计数排名。

时间与空间复杂度

时间不取决于单词数量 n，这是相对于字符串平衡树（O(m log n) 次比较）的主要优势。代价是内存：每个节点都是带有自己字典的独立对象，所以 Trie 占用的内存可能是原始字符串的许多倍。

变体与常见错误

• 数组子节点：对小写英文字母使用固定的 26 个槽位的数组。比 dict 快，但对稀疏或很大的字母表很浪费。
• 压缩 Trie（基数树、Patricia Trie）：把只有一个孩子的节点链合并成一条带字符串标签的边，能节省大量内存。基数树用于 IP 路由表和某些 HTTP 路由器。
• 三叉搜索树：每个节点有三个孩子（小于、等于、大于），比宽数组占用的内存更少。
• 计数 Trie：在每个节点中存一个计数器，就能在 O(m) 内回答“有多少单词以这个前缀开头？”。
• 按位 Trie：逐位存储数字，用来解决最大异或问题。

何时使用 Trie，以及典型面试题

当你需要前缀查询、最长前缀匹配，或对许多带共享前缀的字符串做有序遍历时，请使用 Trie。如果只需要精确匹配查找，请使用 set 或 dict：在 Python 中更简单，占用内存也更少。对于小而固定的单词表，用 bisect 模块配合有序列表也能很好地回答前缀查询。

典型问题：实现 Trie（插入、查找、前缀判断）、在网格中用多个目标词做单词搜索、用最短词根替换单词、最长公共前缀、设计搜索自动补全系统，以及用按位 Trie 求两个数的最大异或。