Trie树

    Trie树，又称为单词查找树、字典树，是一种树形结构，是一种哈希树的变种，是一种用于快速检索的多叉树数据结构。
   
    典型应用：统计和排序、查询大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本的词频统计等。
    优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
    核心思想：空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
    缺点：内存消耗非常大。

    实现过程包括以下两个阶段：
    1）插入过程
        对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入trie树。
    2）查找过程
        其方法为：
         (1) 从根结点开始一次搜索；
         (2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
         (3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
         (4) 迭代过程……
         (5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
         其他操作类似处理。
即从根开始按照单词的字母顺序向下遍历trie树， 一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。如下图 中：trie树中存在的就是abc、d、da、dda四个单词。在实际的问题中可以将标记颜色的标志位改为数量count等其他符合题目要求的变量。

    查找分析
        在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。
        而二叉查找树的查找时间和树中的结点数有关O(log2n)。
        如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。

    
    应用
        1、字符串检索，词频统计，搜索引擎的热门查询

           事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
           举例：
            1）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
            2）给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
            3）给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。
            4）1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串
            5）寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的 长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度 越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
        2、字符串最长公共前缀           
            Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。
            举例：
            1) 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少.
            解决方案：
                首先对所有的串建立其对应的字母树。此时发现，对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了离线 （Offline）的公共祖先（Least Common Ancestor，简称LCA）问题。
而公共祖先问题同样是一个经典问题，可以用下面几种方法：
                1、利用并查集（Disjoint Set），可以采用采用经典的Tarjan 算法；
                2、求出字母树的欧拉序列（Euler Sequence ）后，就可以转为经典的最小值查询（Range Minimum Query，简称RMQ）问题了；

        3、排序

            Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。
            举例：
            给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。

        4、作为其他数据结构和算法的辅助结构
            如后缀树，AC自动机等。