Trie 树（数据结构）

Trie 树（数据结构） 1.Trie树的概念

Trie树是数据结构比较简单的一种。Trie 树的基本用法是高效的存储和查找字符串集合的数据结构。Trie树也叫做字典树，它是一个树形结构。是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串。Trie树本质，利用字符串之间的公共前缀，将重复的前缀合并在一起。

2.Trie树的三个性质：

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

3.Trie树的 *** 作

2.1存储

  Trie树的存储是从根节点开始从前往后依次便利每一个字符。 存储方式如图所示，从根节点开始，如果需要的字符不存在那么就创造一个新的点来存储这个字符，另外每个字符串结尾需要做上标记。做标记是为了查找时方便。例如Trie树中存储有abcdef这个字符串，但是没有abc这个字符串。如果输入完一个字符串以后不加上一个标记在查找abc这个字符串是可以找到的，这就出现了问题。

存储模板：（存储26个小写字母）

#include
using namespace std;
const int N=100010;
int son[N][26],cnt[N],idx;//son[N][26]用来存储Trie树中的子节点，cnt[N]存储的是以当前结尾的字符串有多少个，idx存储当前用到的那个下标。*这里需要注意下标是0的点，既是根节点，又是空节点。
char str[N];//输入的字符串
void insert(char str[])//调用存储函数
{
    int p=0;//根节点
    for(int i=0;str[i];i++)//判断是不是走到最后
    {
        int u=str[i]-'a';//当前字母子节点的编号
        if(!son[p][u])  son[p][u]=++idx;//如果当前子节点不存在就创造一个点来存储子节点
        p=son[p][u];//让p走到子节点的位置
    }
    cnt[p]++;//结尾是p的字符串个数加加
}

2.2查找

     查询 *** 作和插入 *** 作其实差不多，就是在Trie树中找这个单词的每个字母，若找到了就继续找下去，若没有找到就可以直接退出了，因为若没找到就说明没有这个单词。还是以下图为例。

例如我们想要查找yes中个字符串，查询第一个字符y存在那么继续查询第二个字符，如果不存在e那么返回0；

查询模板：（26个小写字母）

int query(char str[])//调用查找函数
{
    int p=0;//根节点
    for(int i=0;str[i];i++)//判断是不是走到最后
    {
        int u=str[i]-'a';//当前字母子节点的编号
        if(!son[p][u])  return 0;//如果当前字符不存在那么直接返回0
        p=son[p][u];//让p走到子节点的位置
    }
    return cnt[p];//最后返回以p结尾的字符串个数
}

4.Trie树总结

    Trie树其实是一种用空间换时间的算法，它占用的空间一般很大，但时间是非常高效的，插入和查询的时间复杂度都是O（l）的，总体来说还是很优秀的。不用担心字节个数过大的情况，一般题上会给出已知条件来控制子节点个数，例如字符串只包括小写字母大写字母等等。