Trie树的详解及应用

Trie树，又称单词查找树或键树，是1种树形结构，是1种哈希树的变种。典型利用是用于统计和排序大量的字符串（但不但限于字符串），所以常常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效力比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来下降查询时间的开消以到达提高效力的目的。

　　Trie 的强大的地方就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与
Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k) ，而且还有碰撞之类的问题；Trie 的缺点是空间消耗很高。

Trie树特性：

1）根节点不包括字符，除根节点外每个节点都只包括1个字符。

2）从根节点到某1节点，路径上经过的字符连接起来，为该节点对应的字符串。

3）每一个节点的所有子节点包括的字符都不相同。

4）如果字符的种数为n，则每一个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。

5）插入查找的复杂度为O(n)，n为字符串长度。

基本思想（以字母树为例）：
1、插入进程
对1个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。
2、查询进程
一样的，从根开始依照单词的字母顺序向下遍历trie树，1旦发现某个节点标记不存在或单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。

字典树的数据结构：
    利用串构建1个字典树，这个字典树保存了串的公共前缀信息，因此可以下降查询操作的复杂度。
    下面以英文单词构建的字典树为例，这棵Trie树中每一个结点包括26个孩子结点，由于总共有26个英文字母(假定单词都是小写字母组成)。
    则可声明包括Trie树的结点信息的结构体: