Trie 前缀树

2026-06-02

每个节点存一个字符,从根到叶的路径就是一个完整字符串。共同前缀的字符串共用前面的节点 — 这就是为什么叫”前缀树”。插入/查询都是 ,跟字典里有多少词无关。

直觉 — 公共前缀共用节点

哈希表能 查一个词,但查不了”以 app 开头的所有词”。Trie 把字符摊到树上:共享前缀的字符串走同一段路径,分叉只发生在第一次出现不同字符的位置。

插入 apple, app, ant, bee 之后:

1
2
3
4
5
6
7
8
9
10
11
    root
    /  \
   a    b
  / \    \
 n   p    e
 |   |    |
 t   p    e (#)
(#)  |
     l
     |
     e (#)
  • apple 和 app 共用 a -> p -> p 这三个节点;
  • ant 在 a 之后才分叉;
  • bee 完全独立另开一支。

三件事一次看清:

  1. 每条边代表一个字符,每个节点代表”走到这里时的前缀”。 节点本身不存整个字符串。
  2. is_end(图里的 #)是必需的。 不加就分不清”app 是真的插入过”还是”app 只是 apple 路径上的某个点”。
  3. 查询代价是 , 是查询串的长度。 字典里有 1 万还是 1 亿个词,完全不影响。

对比一下:

操作 HashSet Trie
精确查找
前缀查询 不支持
列出所有以 P 开头的词 扫全表 走到 P,DFS 子树
内存 每个词独立存 共享前缀,字典越密越省

Trie 不是为了”更快地查一个词”,而是为了”按前缀批量操作”。 这是它存在的唯一理由。

动画 — 跟着字符落子

下面的动画依次插入 apple, app, ant, bee 四个词,再演示 search("app") 和 search("ap")。重点盯三件事:

  • 共享前缀:apple 已经把 a-p-p 三个节点建好,插入 app 时不再新建任何节点,只在最后那个 p 上挂一个 #。
  • # 标记:app 的 # 加上之后,search("app") 返回 True;但 search("ap") 路径虽然能走通,因为 p 上没 #,所以是 False — 它只是前缀,不是被插入过的词。
  • 节点数 ≠ 字符总数:四个词共 13 个字符,但树上只有 11 个节点(共用了 a-p-p 那段)。词典越密,节省越多。

模板 — Python class Trie

字典版,字符集不限,Python 首选:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        node['#'] = True                  # 结尾标记,不能省

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and '#' in node

    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

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

三处细节:

  1. search 和 starts_with 共用 _walk。 区别只在终点要不要检查 #。
  2. # 用任何字符集外的 key 都行,只是约定。换成 node.is_end = True 一样。
  3. 不要在 _walk 里写递归,Python 递归慢且会爆栈,直接 for 循环。

数组版(竞赛/C++ 常用)

固定字符集时,预分配节点池,用整数 ID 代替 dict 引用,内存紧凑、缓存友好:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TrieArray:
    def __init__(self, cap=100001):
        self.children = [[0] * 26 for _ in range(cap)]
        self.is_end = [False] * cap
        self.cnt = 0                      # 0 号永远是根

    def insert(self, word: str) -> None:
        node = 0
        for ch in word:
            c = ord(ch) - ord('a')
            if self.children[node][c] == 0:
                self.cnt += 1
                self.children[node][c] = self.cnt
            node = self.children[node][c]
        self.is_end[node] = True

选哪个:Python 刷题用 dict 版;字符集只有小写字母、追求常数、或要在 LeetCode 上卡进前 5% 时换数组版。

进阶 — 01-Trie 解决异或最大值

LC 421. 数组中两个数的最大异或值:给一组整数,求 。

朴素 。01-Trie 把它打到 。核心一句话:把整数当成 30 位的二进制字符串塞进 Trie,字符集只有 {0, 1},所以叫 01-Trie。

为什么能解最大异或?异或的特性:对应位不同结果为 1。从高位开始贪心,每一位都试着走”和当前位相反”的分支 — 走得通就这一位拿到 1,走不通才退而求其次。高位优先于低位,所以贪心最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def findMaximumXOR(nums):
    trie = {}
    # 1. 插入:每个数从高位到低位
    for x in nums:
        node = trie
        for i in range(30, -1, -1):
            b = (x >> i) & 1
            if b not in node:
                node[b] = {}
            node = node[b]

    # 2. 查询:对每个数贪心找"最反"的路径
    best = 0
    for x in nums:
        node, cur = trie, 0
        for i in range(30, -1, -1):
            b = (x >> i) & 1
            want = 1 - b                  # 想走相反方向
            if want in node:
                cur |= (1 << i)           # 这一位贡献 1
                node = node[want]
            else:
                node = node[b]            # 别无选择
        best = max(best, cur)
    return best

这道题是 01-Trie 的招牌应用,记住”从高位到低位 + 贪心走反向”这一个套路,变种题(异或在某个范围内的对数、子数组最大异或等)都是它的变形。

应用

不只是面试题,工程里到处都是:

  • 自动补全 / 搜索框联想:输入 自动,走到该前缀的子树 DFS,把所有词收上来按热度排。
  • IP 路由的最长前缀匹配:路由表本质是二进制 Trie,数据包来了从根往下走,匹配最长前缀那条路由。
  • 拼写检查 / 模糊匹配:Trie 上 DFS 时允许少量字符替换/插入/删除(编辑距离),比对全词表快得多。
  • 敏感词过滤(Aho-Corasick):多模式串匹配,在 Trie 上加 fail 指针,一次扫描查所有敏感词。
  • 字符串异或/位运算极值:见上面的 01-Trie。
  • 后缀树/后缀数组的同族:索引整个字符串所有后缀,做子串查询。

判断要不要上 Trie:只要题面里出现”前缀””字典””多模式”,先想 Trie。

记忆法

一句话:字符在边上,前缀在路径上,# 在词尾上。

三件事必须刻进肌肉记忆:

要点 内容
节点设计 children: dict[char, Node] + is_end: bool
时间复杂度 插入/查询都是 ,与词典大小无关
易错点 结尾标记 # 不能省,否则前缀和完整词分不开

判题口诀:

  • 看到”前缀” → Trie
  • 看到”多个字符串一起查” → Trie
  • 看到”异或最大/最小” → 01-Trie
  • 看到”敏感词/多模式匹配” → AC 自动机(Trie + fail 指针)

写模板的时候默念:新建节点 → 走过去 → 走完打标记。 三步,永远不会写错。

思考题

不加 # 会出什么具体问题?

插入 apple 后,search("app") 会返回 True — 因为路径 a-p-p 确实存在。但 app 这个词并没有被插入过,这就是误判。# 的作用是区分”路径上的节点”和”被显式插入过的词的终点”。

01-Trie 为什么从高位开始而不是低位?

异或结果是按位的二进制数,高位的权重远大于所有低位之和()。所以高位能拿到 1 就一定要拿,哪怕低位全部牺牲。从低位贪心会被高位翻盘。

Trie 的内存开销和 HashSet 比如何?

Trie 每个节点要存一个 dict(或 26 长度数组),开销不小。但词典越密(共享前缀越多)越省:1 万个英文单词,共享前缀后节点数远小于字符总数。稀疏字典(每个词都不同前缀)反而比 HashSet 费内存。

LeetCode 练习

热身:

进阶: