字典树

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

插入 to 先建立 t→o，并把 o 标为词尾；插入 tea 时复用 t，新建 e→a；插入 ten 时继续复用 te，只新建末尾 n。因此三个词只需五个非根节点。查询 te 能到达节点，但它没有词尾标记，所以精确查询失败；前缀查询则从这里枚举得到 tea,ten。输出这些词的时间还要计入遍历和输出字符，不能把整个枚举都记成 $O(2)$。

图中还存有 in,inn：in 所在节点既是词尾又有孩子，这说明词尾并不等于叶子。删除 tea 时只去掉末尾 a，不能连同仍被 ten 使用的 te 一起删除；删除 in 时则先清除词尾标记，保留通向 inn 的路径。

字符编码粒度必须一致：按 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，回答模式区间而不保存字典中每个前缀节点。三条路线共享“前缀”图像，却索引不同对象并提供不同接口。