形式陈述

Trie（前缀树）以根表示空串，边标记字母；从根沿路径读出的串对应前缀，终止标记指出哪些前缀本身是已存单词。插入、查询和删除一个长度 $m$ 的词通常访问 $O(m)$ 个节点，与集合中词的数量无直接对数因子。节点孩子可用定长数组、哈希表或有序映射表示，空间取决于总前缀数和字母表。

直觉

具有公共前缀的词共享从根开始的路径，因此 trie 把字符串比较逐字符展开成树导航，避免重复存储相同前缀。

例子与边界

存入 to、tea、ten 时，首字母 t 与第二字母分支被共享。仅到达某节点不代表该前缀是完整词，必须有终止标记。复杂度 $O(m)$ 假设每步孩子查找为 $O(1)$ 或把字母表成本计入；大 Unicode 字母表用稠密数组会浪费空间。压缩 trie 可合并单孩子路径，后缀树则索引所有后缀，概念不同。删除词时不能误删仍被其他词共享的节点。

推论与应用

Trie 用于自动补全、最长前缀匹配、路由表、词典和字符串集合；与失败链接结合形成 Aho–Corasick 多模式匹配。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983，Chs. 1–6。