Trie 又称前缀树、字典树、单词查找树，是一种二叉树衍生出来的多叉树，通常用来保存字符串，它的节点和字符串的字符对应，而路径和字符串对应，主要应用场景是处理字符串前缀相关的操作。
核心思想是空间换时间。利用字符串的公共前缀来减少无谓的字符串比较以达到提高效率的目的。 常用于统计和排序大量字符串。相比较 hash 表，它支持动态查询。
前缀树的特点 #
前缀树有几个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点之间的所有子节点包含的字符都不相同。
- 如果一个单词是另一个单词的前缀，那么较短的单词对应的路径是较长的单词对应的路径的一部分。
- 如果前缀树路径到达某个节点时它表示了一个完整的字符串，那么字符串最后一个字符对应的节点有特殊的标识，例如上图的红色标识。
优点 #
- 插入和查询效率都很高，都为 O(n)，其中 n 为待插入/查询的字符串长度。
- 相比哈希函数实现的哈希表，前缀树的不同关键字不会产生碰撞冲突。
- 前缀树只有在一个关键字对应多个值的情况下才会发生冲突。
- 前缀树不求 hash 值，对短字符串有更快的速度。（求 hash 值也需要遍历字符串）
- 前缀树可以对关键字按字典序排序。
缺点 #
- 空间消耗比较大。
- hash 函数的性能很好时，前缀树的查询效率会低于哈希表。
与哈希表的区别 #
在哈希表中，只有输入完整的字符串才能进行查找操作，在前缀树中就没有这个限制。
实现一个前缀树 #
请实现一个前缀树，它有如下函数：
- 函数
insert，在前缀树中添加一个字符串。 - 函数
search，查找字符串，如果前缀树中包含该字符串，则返回 TRUE，否则返回 FALSE。 - 函数
startwith，查找字符串前缀，如果前缀树中包含以该前缀树开头的字符串，则返回 TRUE，否则返回 FALSE。
如果只考虑英文小写字母，那么前缀树的每个节点有26个子节点。为了标注某些节点和字符串的最后一个字符对应，前缀树节点中通常需要一个布尔类型的字段。
常见题型 #
使用前缀树解决问题通常需要两步：第 1 步是创建前缀树，第 2 步是在前缀树中查找。虽然相关的面试题千变万化，但这两步及其代码却大同小异。
字符串检索 #
词频统计 #
例题：给你 100000 个长度不超过 10 的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
字符串排序 #
Trie 树可以对大量字符串按字典序进行排序，思路也很简单：遍历一次所有关键字，将它们全部插入trie 树，树的每个结点的所有儿子很显然地按照字母表排序，然后先序遍历输出 Trie 树中所有关键字即可。
前缀匹配 #
例如：找出一个字符串集合中所有以 ab 开头的字符串。我们只需要用所有字符串构造一个 trie 树，然后输出以 a->b-> 开头的路径上的关键字即可。