trie树

大数据时代必备算法----trie树
通俗一点来说，trie树在大数据分析领域用于“抽取文章中所有出现过的，用于统计，而非切词”。

举个简单例子来说说它如何工作
假设有b，abc，abd，bcd，abcd，efg，hii这6个单词，我们构建的树的形态如下图

对于每一个红色节点，从根遍历到他的过程就是一个单词。
在输入一个单词，进行查询匹配的时候，从根开始沿着这个单词包含的字母来遍历这个树的某个分支，假如输入单词的全部字母依序可以遍历trie树的某一个分支。那么来看看这个输入单词的最后一个字母对应的trie树某分支的某个节点。如果这个节点被标记为红色，就表示这个单词存在，否则不存在。

那么，对于一个单词，我只要依照它包含的字母按次序从trie树的根走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。

这样一来，对于每个输入单词，我们查询和插入这个单词可以在trie中一次完成，所用时间仅仅为单词长度。

假设trie树每层的层序号是n，那么trie树每一层的节点数是26^n这个数量级。
实现的时候，如果想节省空间，推荐使用动态链表。如果为了效率，就得忍痛用空间来换时间，用数组实现。
使用动态链表实现，花费的空间不会超过 “单词数 x 最长单词长度”。

朋友们可以考虑下，如果用哈希来完成以上需求，是不是无法达到这个效率呢？
trie树是AC算法的核心。