Trie 树和其它数据结构的比较

Trie 树，又叫做前缀树或者是字典树，是一种有序的树。从空字符串的根开始，往下遍历到某个节点，确定了对应的字符串，也就是说，任意一个节点的所有子孙都具备相同的前缀。每一棵 Trie 树都可以被看做是一个简单版的确定有限状态的自动机（DFA，deterministic finite automaton），也就是说，对于一个任意给定的属于该自动机的状态 (①) 和一个属于该自动机字母表的字符 (②)，都可以根据给定的转移函数 (③) 转到下一个状态去。其中：

• ① 对于 Trie 树中的每一个节点都确定了一个自动机的状态；
• ② 给定一个属于该自动机字母表的字符，在图中可以看到根据不同的字符形成的分支；
• ③ 从当前节点进入下一层次节点的过程经过状态转移函数得出。

一个非常常见的应用就是搜索提示，在搜索框中输入搜索信息的前缀，如 “乌鲁”，提示 “乌鲁木齐”；再有就是输入法的联想功能，也是一样的道理。

和二叉搜索树（binary search tree）相比

二叉搜索树又叫做二叉排序树，它满足：

• 任意节点如果左子树不为空，左子树所有节点的值都小于根节点的值；
• 任意节点如果右子树不为空，右子树所有节点的值都大于根节点的值；
• 左右子树也都是二叉搜索树；
• 所有节点的值都不相同。

其实二叉搜索树的优势已经在与查找、插入的时间复杂度上了，通常只有 O(log n)，很多集合都是通过它来实现的。在进行插入的时候，实质上是给树添加新的叶子节点，避免了节点移动，搜索、插入和删除的复杂度等于树的高度，属于 O(log n)，最坏情况下整棵树所有的节点都只有一个子节点，完全变成一个线性表，复杂度是 O(n)。

Trie 树在最坏情况下查找要快过二叉搜索树，如果搜索字符串长度用 m 来表示的话，它只有 O(m)，通常情况（树的节点个数要远大于搜索字符串的长度）下要远小于 O(n)。

我们给 Trie 树举例子都是拿字符串举例的，其实它本身对 key 的适宜性是有严格要求的，如果 key 是浮点数的话，就可能导致整个 Trie 树巨长无比，节点可读性也非常差，这种情况下是不适宜用 Trie 树来保存数据的；而二叉搜索树就不存在这个问题。

和 Hash 表相比

考虑一下 Hash 表键冲突的问题。Hash 表通常我们说它的复杂度是 O(1)，其实严格说起来这是接近完美的 Hash 表的复杂度，另外还需要考虑到 hash 函数本身需要遍历搜索字符串，复杂度是 O(m)。在不同键被映射到 “同一个位置”（考虑 closed hashing，这 “同一个位置” 可以由一个普通链表来取代）的时候，需要进行查找的复杂度取决于这 “同一个位置” 下节点的数目，因此，在最坏情况下，Hash 表也是可以成为一张单向链表的（对于 Hash 冲突问题，请阅读 《Hash Collision DoS 问题》）。

Trie 树可以比较方便地按照 key 的字母序来排序（整棵树先序遍历一次就好了），这是绝大多数 Hash 表是不同的（Hash 表一般对于不同的 key 来说是无序的）。

在较理想的情况下，Hash 表可以以 O(1) 的速度迅速命中目标，如果这张表非常大，需要放到磁盘上的话，Hash 表的查找访问在理想情况下只需要一次即可；但是 Trie 树访问磁盘的数目需要等于节点深度。

很多时候 Trie 树比 Hash 表需要更多的空间，我们考虑这种一个节点存放一个字符的情况的话，在保存一个字符串的时候，没有办法把它保存成一个单独的块。Trie 树的节点压缩可以明显缓解这个问题，后面会讲到。

和后缀树相比

后缀树压缩存储了一段文本的所有可能的后缀，如给定单词 “banana”，可能的后缀包括：a、na、ana、nana、anana、banana 这几种，上图已经将所有可能全部放在树中表示出来了，“$” 表示一个后缀的结束，同时，还做到了尽量的分支压缩（分支压缩的说明在下文中也有提及）。对于给定长度为 n 的文本构造后缀树，它的定义要点包括：

• 树有 n 个叶子节点，分别从 1 到 n 来命名；
• 除了根节点，所有的非叶子节点至少有两个孩子；
• 每一条边代表原文本的一个非空子串；
• 不存在两条边以同一个字符开串标记且以同一个字符结尾；
• 在从根节点到叶子 i 的路径上，连接所有字符串标记形成的字符串，都表示了一个原文本的后缀子串。

构造后缀树根据文本长度需要消耗线性的时间。和Trie 树相比，后缀树做到了用空间换时间，考虑全文搜索的情况，后缀树把所有可能的后缀子串都索引化了，就避免了 Trie 树深度遍历整棵树的过程。在算法题中许多关于 “前缀子串”问题上，我们经常使用 Trie 树来求解，但是如果问题仅仅涉及 “子串”，往往选用后缀树；另外，还有一个重要的使用在文本压缩算法上，通过后缀树可以找到重复率高的文本，实现重复文本抽取，放到字典映射表中去。

Trie 树的改进

1. 按位 Trie 树（Bitwise Trie）：原理上和普通 Trie 树差不多，只不过普通 Trie 树存储的最小单位是字符，但是 Bitwise Trie 存放的是位而已。位数据的存取由 CPU 指令一次直接实现，对于二进制数据，它理论上要比普通 Trie 树快。

2. 节点压缩。

• ① 分支压缩：对于稳定的 Trie 树，基本上都是查找和读取操作，完全可以把一些分支进行压缩。例如，前图中最右侧分支的 inn 可以直接压缩成一个节点 “inn”，而不需要作为一棵常规的子树存在。Radix 树就是根据这个原理来解决 Trie 树过深问题的。
• ② 节点映射表：这种方式也是在 Trie 树的节点可能已经几乎完全确定的情况下采用的，针对 Trie 树中节点的每一个状态，如果状态总数重复很多的话，通过一个元素为数字的多维数组（比如 Triple Array Trie）来表示，这样存储 Trie 树本身的空间开销会小一些，虽说引入了一张额外的映射表。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》