字典树特点
- 查询快
- 存储少
对相同前缀的字符串进行了压缩存储，存储空间少，访问一个字符串最多也只需要访问字符串的长度。
利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。
字典树有什么应用场景？
单词联想预测、单词纠错。
在搜索引擎中关键词提示，引擎会自动弹出匹配关键词的下拉框。
字符串检索
事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
例如：
- 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。
- 给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
这样一方面可以节约存储空间，另一方面先用字典树预处理了海量文本，之后进行字符串查找时，不用在整个文本中查找特定字符串
词频统计
给定很长的一个串，统计频数出现次数最多情况。
例如：
- 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
- 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
字符串最长公共前缀
Trie树利用多个字符串的公共前缀来节省存储空间，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀，所以可以利用这个特点来解决一些前缀问题。
例如：
- 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？