Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。

一、Trie树的介绍

一个例子，如下图所示：
图片说明
上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。
从上图可以归纳出Trie树的基本性质：
1.根结点不包含字符，除根结点外每个结点包含一个字符。
2.从根结点到某一个结点，路径上经过的字符连接起来，为该结点对应的字符串。
3.每个结点的所有子节点包含的字符互不相同。
通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。（或者是设置一个变量统计该单词的出现次数，常用于词频统计)

可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）。

二、Trie优缺点

Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。
优点
插入和查询的效率很高，都为O(m)，其中 m 是待插入/查询的字符串的长度。
Trie树中不同的关键字不会产生冲突。
Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。
Trie树不用求 hash 值，对短字符串有更快的速度。通常，求hash值也是需要遍历字符串的。
Trie树可以对关键字按字典序排序。

缺点
1.当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。
2.空间消耗比较大。
##三、Trie树的应用
词频统计、字符串检索、字符串排序、前缀匹配

例题1

图片说明 

class Trie {
public:
    int count; // 统计某字符串出现次数
    Trie* next[26];  // 标准26叉字典树
    Trie() {
        count = 0;
        memset(next,0,sizeof(next));
    }

    // 插入一个字符串
    void insert(string word) {
        Trie* node = this;
        for(char c : word)
        {
            if(node->next[c-'a']==NULL)
            {
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->count += 1;
    }

    // 搜索一个字符串
    bool search(string word) {
        Trie* node = this;
        for(char c : word)
        {
            if(node->next[c-'a']==NULL) return false;
            node = node->next[c-'a'];
        }
        if(node->count==0) return false;
        else return true;
    } 

    // 判断是否有以某前缀开头的字符串
    bool startsWith(string prefix) {
        Trie* node = this;
        for(char c : prefix)
        {
            if(node->next[c-'a']==NULL) return false;
            node = node->next[c-'a'];
        }
        return true;

    }
};

总结：

1.Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。
2.查找或插入一个长度为 L 的单词，访问 next 数组的次数最多为 L+1，和 Trie 中包含多少个单词无关。
3.Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m^n)