Trie 把字符串集合组织成按字符延伸的路径，公共前缀只存一份，让前缀类查询的开销只与前缀长度相关、与词典规模解耦。本文讲清它的结构直觉、增删查流程、空间优化与工程落地。

它解决什么问题

哈希表擅长回答”这个词在不在”，却不擅长”所有以 app 开头的词有哪些”——除了全表扫描几乎无路可走。搜索建议、分词切分、路由匹配的共同点是：查询单位不是完整字符串，而是前缀。Trie 让前缀成为结构里一条显式的路径，前缀操作的代价不再随词典膨胀。

核心原理

根节点不代表任何字符，只是入口；从根向下的每条边对应一个字符，根到任意节点的路径拼出一个前缀。节点上挂一个终止标记，区分”这里只是某词的前缀”与”这里恰好是一个完整单词”——插入 app、apple、apply 之后，三者共享 a→p→p 这条路径，第三个 p 上的标记表明 app 自身也是词，而第四个字母处再分出 l、e 两支。公共前缀在结构上只存一份，这是 Trie 一切性质的根源：前缀越密集，共享越充分，空间和时间上的收益就越大。

深入机制

插入、查找与前缀匹配

设词长 L：插入沿路径逐字符下行，缺节点就建，O(L)；search 要求走完路径且终止标记为真；startsWith 只要求路径存在。三个操作的时间都只与词长相关，与词典里有多少单词没有直接线性关系——这正是 Trie 相对哈希表的立足点。

class Trie {
    private static class Node {
        Node[] child = new Node[26]; // 仅小写字母；大字符集改用 Map<Character, Node>
        boolean isWord;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.child[i] == null) cur.child[i] = new Node();
            cur = cur.child[i];
        }
        cur.isWord = true;
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isWord;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private Node walk(String s) {          // 沿字符路径下行，走不通返回 null
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.child[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }
}

删除是最容易写错的操作：词与词共享前缀，删 app 绝不能砍掉 a→p→p 这条 apple 还在用的路径。正确姿势是先清终止标记，再自底向上回收”无子节点且非他词结尾”的死节点；面试若无要求，通常只需把插入与两类查询写稳。另外注意，”列出某前缀下的所有单词”不是 O(L) 能完成的：定位前缀节点之后还要遍历整棵子树，成本与返回结果的数量成正比，评估接口性能时不能忽略这一段。

空间优化

裸 Trie 的痛点是空槽：26 格数组在稀疏分支上大量浪费。三条主流优化路线：

  • 孩子改 Map：只为真实出现的字符建边，用哈希开销换空间，适合大字符集，如按字或按词切的中文。
  • 压缩 Trie（Radix Tree / Patricia）：把只有一个孩子的连续链合并为一条边上的一段字符串，节点数从字符级降到分支级，空间与高度同时收缩。
  • 双数组 Trie（Double-Array Trie）：用 base、check 两个数组把整棵树编码进线性表，查询退化为两次数组寻址，极致紧凑且缓存友好；代价是构建复杂、动态增删困难，多用于离线静态词典。

工程实践

  • 搜索建议：沿用户输入的前缀走到对应节点，再 DFS 子树收集候选；生产系统常在节点上预存该前缀的热词 top-k，免去每次全子树扫描。
  • IP 路由最长前缀匹配：把 CIDR 网段按位（0/1）建成二叉 Trie，查路由时沿 IP 地址的比特下行，沿途记住最后一个命中的表项即得结果——这是 Trie 思想跨出字符串域的典型移植。
  • 敏感词过滤：敏感词库建 Trie，文本逐字符推进匹配；给节点补上失配指针就是 AC 自动机，一次扫描命中全部模式串，是内容安全系统的标配组件，面试里也常拿它当 Trie 的进阶追问。

对比与权衡

维度 Trie 哈希表 红黑树（TreeMap）
完整词查询 O(L) 均摊 O(L)，常数更小 O(L·log n)
前缀查询与枚举 原生支持 基本不支持 借范围扫描间接实现
有序遍历 按字符序 DFS 可得 无 天然有序
空间表现 共享前缀时省，稀疏时费 每词独立存储 每词一节点加指针
适用边界 前缀密集、需前缀操作 只做精确匹配 还需排序与范围语义

选型逻辑很直接：只判断存在性用哈希表；要排序和范围查询用红黑树；要前缀匹配、前缀枚举、最长前缀，用 Trie 或它的压缩变体。

面试视角

Trie 的查询是 O(1) 吗？ 不是，O(L) 与词长成正比。它的卖点是复杂度与词典规模 n 无关——词典再大，走完一条路径的步数不变。

isWord 标记为什么不可省略？ 它区分”路径存在”与”路径构成完整单词”。没有它，app 究竟是 apple 的前缀还是独立单词，结构上无从分辨。

Trie 一定比哈希表省空间吗？ 不一定。公共前缀多时才省；若单词几乎互不共享前缀、节点又用定长数组存孩子，Trie 反而更费空间。

中文场景怎么用 Trie？ 先明确切分单元——按字、按词还是按拼音，再让孩子改用 Map 承载大字符集；分词器里的词典匹配正是这一形态。

双数组 Trie 为什么快且省？ 每个节点只对应 base、check 两个整数，转移是 next = base[s] + c 加一次 check 校验，纯数组寻址、缓存行利用率高；树被压进两个线性数组，没有指针开销，代价是构建期要解冲突、插入删除很麻烦。

小结

  • Trie 的本质：字符为边、前缀为路径、终止标记区分词与非词。
  • 插入、查找、前缀匹配均为 O(L)，代价与词典规模解耦。
  • 空间优化三板斧：Map 孩子、Radix 压缩、双数组编码，按数据规模与是否静态选择。
  • 对照哈希表与红黑树划定边界，落地于搜索建议、IP 路由与敏感词过滤。