字典树
概述
字典树，又称单次查找树，Trie数，是一种树形结构，哈希表的变种。常常用于统计、排序和保存大量的字符串。
字典树可以利用字符串的公共前缀来减少存储空间，在存储、统计大量字符串的场景下比哈希表空间复杂度要小很多。
字典数的结构如下
字典树的核心思想是空间换时间。
字典树的每一个节点，只记录一个字符，根节点上不记录字符。从根节点到某个节点的路劲上的字符按顺序排列就是某一个字符串。
字符串相同前缀部分约大，越节约内存
每一个节点的所有子节点包含的字符都不相同
注意：如果统计的字符串长度相差很大，那么使用字典树是很不划算的，是比较浪费空间的。
应用
- 给你100000个长度不超过10个字母的单词，对于每一个单词，我们要判断它是否出现过，如果出现了，求第一次出现的位置
- 做即时响应用户输入的Ajax请求时，可以使用字典树
- 有一个1G大小的文件，里面每一行是一个词，词大小不超过16字节，内存限制1M，返回频率最高的100个词 哈希切分小文件 + 字典树
- 给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词 把熟词建一颗字典树
