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

字典树3个基本性质

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。

trie树每一层的节点数是26^i级别的。所以为了节省空间。用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。

字典树优缺点

优点：

1、插入，查询，删除等操作复杂度为O(h),其中h为单词的长度。为什么会这么快呢，本质是空间换时间（空间复杂度为26的h次方），利用指针来避免做其他不必要的查找。（初始化的时间复杂度为n O(h),n为单词个数）

2、当储存大量单词或者说储存的单词有着共同前缀时节省了空间。（比如说用线性存储boy,boyfriend如用trie存储的差别）

缺点：

指针占用的空间，空间复杂度大。如果储存少量的单词，并不能节省空间。

字典树的应用

• 字符串检索：事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
• 字符串最长公共前缀（转化为寻找共同祖先问题）。

与哈希的比较

实现

字典树结构体

TrieNode的结点结构中没有直接使用一个成员来保存结点值。而是使用字母映射表next，next中保存了对当前结点而言下一个可能出现的字符

struct TrieNode {
    bool isend;//字符串结束标志
    TrieNode* next[26];//字母映射表
    TrieNode()
    {
        this->isend = false;
        for (int i = 0; i < 26; ++i)
            this->next[i] = nullptr;
    }
};

插入

从根节点开始遍历，如果当前结点的字母映射表next中不存在word[i]，则在当前结点的next[word[i]]处建立一个新的结点，并将当前结点移动到next[word[i]]处，直到将word全部插入，还要将最后一个结点的isend置为true。

void Insert(string word)
{
    TrieNode* temp = Trie;
    for (char ch : word)
    {
        if (temp->next[ch - 'a'] == nullptr)
        {
            temp->next[ch - 'a'] = new TrieNode();
        }
        temp = temp->next[ch - 'a'];
    }
    temp->isend = true;
}

查找

查找word是否存在于Trie中 (注：查找必须要在到达word最后一个字符时，字典树也到达isend为true 的结点，也就是说word不能以前缀的形式存在于Trie中)。

从字典树的根节点开始，与word中的字符进行匹配，如果不存在word中某个字符的映射，则说明字典树中不包含这个单词，返回false。将word遍历完后若没有返回false，再判断isend是否为true。

bool Find(string word)
{
    TrieNode* temp = Trie;
    for (char ch : word)
    {
        temp = temp->next[ch - 'a'];
        if (temp == nullptr)
            return false;
    }
    return temp->isend;
}

前缀匹配

与查找相比，前缀匹配只要求word在字典树的一条根节点开始的分支中。所以我们不再需要判断isend的值。

bool prefix(string word)
{
    TrieNode* temp = Trie;
    for (char ch : word)
    {
        temp = temp->next[ch - 'a'];
        if (temp == nullptr)
            return false;
    }
    return true;
}