前缀树 Trie

3.3 前缀树 Trie

本节摘要：前缀树把字符串集合组织成一棵共享公共前缀的多叉树。本节实现插入、查找、前缀查询三大接口，用自动补全场景解释它的价值，量化"查询耗时只与单词长度有关而与词典规模无关"的进化收益，并诚实讨论它的内存代价与压缩改良。

哈希表搞不定的查询

堆治"反复取最值"，本节的结构治另一个特殊操作：前缀匹配。设想输入法联想词、搜索引擎的下拉提示——用户敲了几个字母，系统要在几十万词条里找出所有以此开头的词。哈希表能 O(1) 回答"这个词在不在"，但对"哪些词以 app 开头"无能为力，只能全表扫描逐个比对前缀。瓶颈被锁定在两处：前缀重复比较（app 这一串在 apple 与 application 里被反复逐字符核对）、以及每次查询都要与海量候选对话。前缀树的解法优雅至极：把词典里所有公共前缀合并成共享路径，查询就是沿树走一条路，走的步数等于查询串长度，与词典多大毫无关系。

一、结构定义与三大接口

前缀树的每个节点代表一个前缀，边上标字符；从根到某节点的路径拼出该节点对应的前缀。节点需要一个 children 映射与个"是否构成完整单词"的标记——后者至关重要，因为词典里可能既有 app 又有 apple，走到 app 时必须知道"这里是个完整的词，也是个前缀"。

class TrieNode:
    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:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def search(self, word):            # 完整单词查找
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):     # 前缀查询
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

trie = Trie()
for w in ["apple", "app", "application"]:
    trie.insert(w)
print(trie.search("app"))            # 输出 True
print(trie.search("appl"))           # 输出 False（是前缀但不是完整词）
print(trie.starts_with("appl"))      # 输出 True
print(trie.starts_with("bana"))      # 输出 False
​

三大接口的复杂度都是 O(L)，L 为查询串长度，与词典规模完全无关。这就是前缀树的进化宣言：查询成本由你打字的速度决定，不由世界有多大决定。

二、自动补全：把价值落到实处

完整的自动补全=前缀定位加子树收集：先沿前缀走到节点，再深度优先收集该子树下所有 is_word 为真的路径。实现不难，但有个实用优化值得知道：候选太多时，按使用频次在每个节点上维护个堆（上一节的知识正好接上），只收集频次最高的前几个——前缀树管定位、堆管排序，两个进化产物无缝衔接，这正是输入法与搜索引擎的真实做法。

def autocomplete(trie, prefix):
    node = trie._walk(prefix)
    out = []
    if node is None:
        return out

    def dfs(n, path):
        if n.is_word:
            out.append(prefix + path)
        for ch, child in n.children.items():
            dfs(child, path + ch)

    dfs(node, "")
    return out

print(autocomplete(trie, "app"))    # 输出 ['app', 'apple', 'application']
​

三、诚实的代价清单

前缀树不是免费午餐，面试里能主动说清代价才是真懂。第一是内存：每个节点都带一个字符映射，英文字母就有二十六路，词典大而前缀共享少时，节点数量爆炸；改进方向是压缩前缀树——把单链路径压成一个边存整段字符串，Radix Tree 就是大名鼎鼎的落地实现。第二是只有字符集小才顺手：任意字符做键时哈希映射即可，但节点更散更耗内存。第三是删除操作要先递归到底再自底向上回收无用的单链节点，实现繁琐，工程上常软删除（只清 is_word 标记）。选型判据一句话：前缀查询频繁、词典稳定 → 前缀树；只查完整单词 → 哈希表足够；内存敏感 → 倒排或压缩结构。

四、Trie 的进阶变式

面试在基础三接口之后常见的追问方向有两条。第一条是单词搜索类：在二维网格里找单词是否存在，路径可上下左右走。它把前缀树与回溯嫁接：先把词典建成 Trie，再从每个格子出发做深度优先搜索，走的同时沿 Trie 前进，Trie 上无路可走就提前剪枝——相比逐词暴力搜索，Trie 把"明确不可能的前缀"整棵子树掐掉，这正是第三章回溯一节剪枝思想与前缀树的联合作战。第二条是前缀统计类：问某个前缀在词典里出现多少次，做法是节点上挂个 pass 计数，插入时沿途加一，查询走到前缀终点读数即可，三个接口复杂度不变。

内存优化的方向也值得能说两句。压缩前缀树把单链路径合并成一条边存整段字符串，节点数从字符数级别降到分支数级别，Radix Tree、 Patricia Tree 是路由表与搜索引擎的常见实现；双数组 Trie 用两个整数数组模拟树结构，空间更省、缓存更友好，代价是实现复杂度陡增。面试中不必展开实现，能报出"前缀共享率越高越省、越低越亏"这个判断方向即可。

本节要点回顾

• 公共前缀共享路径是前缀树的核心进化，查询耗时只与查询串长度相关；
• is_word 标记区分"是前缀"与"是完整单词"，app 与 apple 并存靠它；
• 三大接口插入、查找、前缀查询全部 O(L)；
• 自动补全等于定位加收集，配堆按频次取前几名即工业做法；
• 代价要主动说：节点内存、字符集限制、删除繁琐，压缩前缀树是正统改良。

下一节并查集：它几乎只做合并与查询两件事，却用两条看似微小的优化把均摊复杂度压到近乎常数——进化链上最漂亮的成绩单。