字典树（Trie）

1、定义

  在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

  核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

2、性质

1. 根节点不包含字符，除根节点以外每个节点只包含一个字符；

2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串；

3. 每个节点的所有子节点包含的字符串不相同。

3、实现

  字典树的插入（Insert）、删除（ Delete）和查找（Find ）都非常简单，用一个一重循环即可，即第 i 次循环找到前 i 个字母所对应的子树，然后进行相应的操作。比较简单的实现方法是：对每个结点挂一个链表，按一定顺序记录每个儿子是谁。

#include <bits/stdc++.h>
using namespace std;
const int ALPHABET_SIZE  = 26;

typedef struct trie_node
{
    int count;
    trie_node *child[ALPHABET_SIZE];//纪录各个子节点
}*trie;

trie create_trie_node()
{
    trie_node* pNode = new trie_node();
    pNode->count = 0;
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        pNode->child[i] = nullptr;
    }
    return pNode;
}

void trie_insert(trie root, string &key)
{
    trie_node* pNode = root;
    for (int i = 0; i < key.size(); ++i)
    {
        //如果子树为空，则创建子树，否则就往下寻找，并将沿路的元素出现的次数累加。
        if (pNode->child[key[i]-'a'] == nullptr)
            pNode->child[key[i]-'a'] = create_trie_node();
        pNode = pNode->child[key[i]-'a'];
        pNode->count += 1;
    }
}

int trie_search_count(trie root, string key)
{
    trie_node* pNode = root;
    for (int i = 0; i < key.size() && pNode != nullptr; ++i)
    {
        pNode = pNode->child[key[i]-'a'];
    }
    if(pNode == nullptr)
        return 0;
    else
        return pNode->count;//搜索所有前缀为key的字符串的个数。
}

int main(int argc, char const *argv[])
{
    vector<string> str = {"cat", "cash", "cap", "app", "apply"};
    trie root = create_trie_node();
    for (int i = 0; i < str.size(); ++i)
    {
        trie_insert(root, str[i]);
    }
    cout << trie_search_count(root, "ca") << endl;
    return 0;
}

4、优缺点及应用

（1）优点

1. 利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高；

2. Trie树中不同的关键字不会产生冲突；

3. 自带排序功能（类似Radix Sort），中序遍历trie可以得到排序。

（2）缺点

1. 虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针；

2. 如果数据存储在外部存储器等较慢位置，Trie会较hash速度慢（hash访问O(1)次外存，Trie访问O(树高)）；

3. 长的浮点数等会让链变得很长。可用bitwise trie改进。

（3）应用

1. 字符串检索：检索、查询功能是Trie树最原始功能，思路就是从根节点开始一个一个字符进行比较；

2. Trie树常被搜索引擎用于文本词频统计；

3. Trie树可以对大量字符串按字典序进行排序；

4. 前缀匹配 ：如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

参考：https://blog.csdn.net/SunnyYoona/article/details/43900425
https://blog.csdn.net/hihozoo/article/details/51248823
https://www.cnblogs.com/justinh/p/7716421.html