Theory · Data Structure · Trie / Prefix Tree
把"共享前缀"变成结构：O(L) 与元素个数无关 · 前缀查询专属 · 从搜索提示到 IP 路由
多叉树，边即字符，从根到节点路径拼出 key——前缀天然聚合
插入/查找/前缀全是 O(L)，L 为串长——与词典规模 n 无关
搜索提示词、敏感词过滤（AC 自动机）、IP 路由最长前缀匹配
Prefix Sharing · Visualized
Implementation · Go
type Trie struct { children [26]*Trie // 或 map[byte]*Trie isEnd bool } // 插入 O(L) func (t *Trie) Insert(w string) { node := t for i := 0; i < len(w); i++ { c := w[i] - 'a' if node.children[c] == nil { node.children[c] = &Trie{} } node = node.children[c] } node.isEnd = true } // 查找 O(L)：走完还要验 isEnd func (t *Trie) Search(w string) bool { n := t.walk(w) return n != nil && n.isEnd } // 前缀 O(L)：走完即是答案 func (t *Trie) StartsWith(p string) bool { return t.walk(p) != nil }
小写字母集 26 定长 → 数组最快（下标直达、无哈希开销）；字符集大/含中文 → map[byte]*Trie 或排序切片。工程折中：数组 + 惰性建节点。
走完路径后，Search 要检查 isEnd（"app" 在树里不代表 "ap" 是完整词）；StartsWith 只要路径存在就是 true。
自底向上递归：词尾去 isEnd，若节点无孩子且非其他词尾则逐层摘除；或用引用计数（路径被多词共享时不能真删）。
插入/查找/前缀全部 O(L)——与词典规模无关。空间最坏 O(26·总字符)，共享前缀多时远小于此。
Where Tries Live
输入 "app" → 沿 Trie 走到节点，收集其子树所有 isEnd 词，按热度排序返回——前缀查询是 Trie 的天赋，哈希表做不了。
把所有敏感词建入 Trie，加上失配指针就是 AC 自动机（多模式 KMP）：一次扫描文本同时匹配全部敏感词，O(文本长 + 命中数)。DFA 的工业标准做法。
路由表按 IP 的二进制位建 Trie（位级分支），查找时记录沿途最深的"有路由"节点——这就是"最长前缀匹配"（LPM）。Linux 内核路由查找的 LC-Trie 同理。
词典建 Trie + 编辑距离容错走分支（模糊匹配）；节点挂计数即词频统计——结构与统计一体。
| 场景 | Trie 提供的能力 |
|---|---|
| 输入提示词 | 前缀子树枚举 + 热度排序 |
| 敏感词过滤 | 多模式一次扫描（AC） |
| IP 路由 LPM | 位级前缀 + 最深命中 |
| 单词游戏 / 棋盘搜索 | DFS 时同步走 Trie 剪枝（LC 212） |
| 异或极值 | 01-Trie 贪心走相反位（LC 421） |
Variants · Trade-offs
单孩子链压缩成一条边（"app" 整段一条边），节点数从 O(字符) 降到 O(key 数)。Linux 内核的 radix tree（现 XArray）用页缓存索引、Patricia / crit-bit 变体用于路由。
每个节点三叉（小于/等于/大于），兼顾 BST 的省内存与 Trie 的前缀能力——C 实现经典，适合超大字符集。
用两个整数数组表达整棵树，无指针、缓存极佳——中文分词库（如 jieba 变体）的最爱。
在 Trie 上预构建 fail 指针（指向最长真后缀节点），把"匹配失败回退"变成 O(1) 跳转——KMP 思想在多模式上的推广。
| 维度 | Trie | 哈希表 | 平衡树 |
|---|---|---|---|
| 精确查找 | O(L) | O(1) 平均 | O(log n) |
| 前缀查询 | ✓ 天赋 | ✗ 需全扫 | ✗ 需遍历 |
| 有序输出 | ✓ DFS 字典序 | ✗ | ✓ 中序 |
| 空间 | 字符集 × 指针（贵） | O(n) | O(n) |
| 复杂度依赖 | 与 n 无关 | 散列质量 | 平衡性 |
LeetCode Shortlist
| 玩法 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 裸实现 | 208 实现 Trie M · 677 键值映射 M · 648 单词替换 M | 208 是模板题；648 最长前缀替换 |
| 通配/模糊 | 211 添加与搜索单词 M · 425 单词方块 H | 211 的 '.' 要 DFS 分支 |
| 矩阵 DFS 协同 | 212 单词搜索 II H · 421 数组两数最大异或 M | 212 = Trie + 回溯剪枝；421 = 01-Trie 贪心 |
| 前缀统计 | 1804 实现前缀树 II M · 面试题：敏感词/提示词设计 | 节点挂 pass/end 计数 |
Interview QA · Part 1
查找 = 沿 key 的每个字符走一步，步数只由 key 长度决定；不需要比较其他元素、也不依赖树平衡——L 固定时是严格常数（对比平衡树的 O(log n·L)）。
字符集小且固定（26 字母）→ 数组：下标直达、缓存友好；字符集大/Unicode → map 或排序切片+二分。数组版每个节点固定 26 指针 = 208B，词少时浪费明显。
只查完整 key → 哈希 O(1) 更省更快；要前缀查询、有序枚举、逐字符容错 → Trie。Trie 的 O(L) 无随机性假设，哈希是平均 O(1)。
把"单孩子链"合并成一条带字符串的边，节点数从 O(字符数) 降到 O(key 数)。Linux 内核页缓存索引（radix tree / XArray）与路由 LC-Trie 都是变体。
路由条目按 IP 二进制位建 Trie，查找 32 位过程中记录最深的有效前缀节点——走到头或断链时，最后记录的即最长匹配。这就是路由器 LPM 的标准结构。
AC = Trie 上加失配指针（指向当前串的最长真后缀节点），匹配失败不回退文本指针而是跳 fail——把 KMP 的单模式思想推广到多模式，一次扫描匹配全部敏感词。
支持：词尾清 isEnd，然后自底向上——节点无孩子且不是其他词尾则摘除；路径被共享（前缀包含）时只能删到安全深度。工程常用引用计数避免递归判断。
数组版每节点固定 26×8B=208B 指针，稀疏浪费严重。省法：① map children 按需建；② 压缩成 radix（边带串）；③ 双数组 Trie（纯整数数组）；④ 三向搜索树。
Interview QA · Part 2
棋盘每个格子向四方向 DFS，同时把"当前路径"在 Trie 里前移：路径不是任何词前缀时整枝剪掉。没有 Trie 就是每个词独立搜索 O(W·m·n·4³)，Trie 把共享前缀的重复比较全砍掉。
把每个数的 32 位二进制从高位到低位建入 01-Trie；查询 x 时从高位起贪心走"相反位"（异或想拿 1）——高位优先保证贪心正确。区间版（XOR 小于 K）在 Trie 上做计数 DP。
① Trie 存查询串、节点挂 TopK 热词小顶堆（或按热度排序的子节点）；② 用户输入沿 Trie 前移，到节点直接返回该节点 TopK；③ 热度更新用 dict 定位 + Trie 重插（或定时重建）。是 LC 642 的标准思路。
正则交替匹配多词会回溯爆炸；哈希只能整词匹配、无法处理文本内切分。AC 自动机一次 O(文本长) 扫描匹配全部词，无回溯——工业敏感词过滤的事实标准（DFA）。
能——children 换成 map[rune]*Trie 或按 UTF-8 字节建（字节级 Trie 字符集只有 256，数组也可行）。分词库普遍用双数组 Trie 存中文词典。
① key 之间几乎无公共前缀（如随机 UUID）→ 退化成"每词一条链"，空间浪费、还慢于哈希；② 只做点查；③ 词表静态且内存紧张 → 排序数组 + 二分前缀反而最优。Trie 的收益与前缀共享度成正比。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| E. Fredkin · Trie Memory (1960) / de la Briandais (1959) | Trie 的原始论文与词源（retrieval） |
| Aho & Corasick (1975) | AC 自动机：Trie + 失配函数的多模式匹配 |
| Linux kernel lib/xarray.c · net/ipv4（LC-Trie） | radix/XArray 页缓存索引与路由最长前缀匹配 |
| LeetCode 208/211/212/421/648/677 官方题解 | 裸实现、通配、矩阵协同、01-Trie |
| oi-wiki.org/string/trie | 01-Trie 与 01-字典树进阶（中文对照） |