字典树

Trie 按字符逐层共享公共前缀，把字符串比较逐字符展开成树导航，避免重复存储相同前缀。从根到某节点的路径标签就是一个前缀，终止标记区分“某词到此结束”和“只是更长词的前缀”。查询时间与键长度成正比而不直接依赖词典大小，代价是节点与稀疏子指针可能占用大量内存。它利用的是字母表结构，不是键的全序比较。

插入 to,tea,ten 时，三个词共享首字符 t，后两者继续共享 te。查询 te 能走到节点但若没有终止标记，就不能判定它是已存单词；前缀查询则可返回其子树中所有词。

字符编码粒度必须一致：按 UTF-8 字节建树与按 Unicode 字符建树会有不同深度和边标签。操作为 $O(m)$ 还隐含每一步能在 $O(1)$ 时间找到孩子，或已把孩子字典的成本计入；对大 Unicode 字母表直接为每个节点分配稠密数组通常会浪费空间。普通 Trie 的一字符一节点空间较大，压缩 Trie/Patricia 把单分支路径合并；删除时还需保留被其他词共享的前缀。后缀树索引固定文本的全部后缀，并不是把词典 Trie 简单压缩后的同一接口。

词公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。与树公理库树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。定义前缀路径。自动补全、词频和路由最长前缀匹配使用字符 Trie；Aho–Corasick 再加入失败链接实现多模式匹配。二进制 Trie 与 Patricia Trie公理库二进制 Trie 与 Patricia 压缩Binary trie · Patricia trie把整数视为定长位串，并以路径压缩只保留真正分叉的位置。把整数按 bit 导航，并压缩单分支路径，复杂度通常依赖字长 $w$ 而非字符串字符数。求集合中与查询整数 $x$ 的 XOR 最大值时，可从最高位起优先走与 $x$ 当前位相反的孩子；若该分支不存在才走同位分支，这给出了位 Trie 独有而字符自动补全没有的贪心接口。

x-fast/y-fast Trie公理库x-fast 与 y-fast Triex-fast trie · y-fast trie以全前缀哈希实现双对数前驱查询，再用抽样分桶把空间压到线性。进一步在 Word-RAM 上组合前缀哈希与分桶，服务整数前驱问题；其期望或最坏界需要明确哈希与字长模型。FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。则预处理固定文本的 BWT 与 rank，回答模式区间而不保存字典中每个前缀节点。三条路线共享“前缀”图像，却索引不同对象并提供不同接口。