字典树是一种非常有趣的数据结构。字典树被设计用来压缩字符串前缀，以便以内存高效的方式存储大量的字符串数据集。字典树被构建为子字符串的树。实际上，“trie”这个词被选中是因为“tree”这个词已经被占用；最初trie发音与tree相同，但拼写不同以区分这两种结构。

存在许多不同的字典树变体，每个都有不同的权衡。

静态字典树

动态字典树

• 数组字典树

• Patricia 数组

• 爆发字典树

• HAT 字典树

• Judy

• B-Trie

• 后缀树

• LOUDS-稀疏 / LOUDS-密集 / Surf

• 基数字典树

• 紧凑字典树

• R-way 字典树

• De la Briandais 字典树

• 列表字典树

• 三元搜索字典树

• 双数组

节点标签映射

在实践中，大多数字典树实际上并不在每个节点上存储字符，而是将它们存储在节点标签映射中，它是一个从唯一的整数 ID 到子字符串的映射数据结构。

存在不同的 NLM 实现，每个都再次提供不同的权衡。

• m-Bonsai

• FK-hash