Trie字典树

字典树是一种树结构，适用于存储有公共字符串的文本。树的根节点不存储文本信息，每个子节点存储一个字符（字），比如 append 和 apple 两个词 存成如下结构：

存储结构

优点是减少无谓的的字符串比较，查询效率比哈希表高。核心思想是用空间换时间，利用字符串的公共前缀降低查询开销达到提高效率的目的。想象一下英文只有26个字母，大量单词都有公共前缀，这会让从所有单词中找xx开头的单词变得特别快。

一个简单的scala版本代码，要实现一颗字典树需要有：

https://github.com/itonc/dataSience/tree/master/address

1. 插入值的方法

输入一段文本，插入一颗树中

2. 完全匹配方法

输入一个字符串，返回在树中满足条件的结果

3. 包含前缀方法

输入一个字符串，返回是否有以该字符串为前缀的结果

4. 一个节点类
用来存储节点信息，尤其是节点需要保存一些额外的信息时候