Trie学习总结

佚名 6年前 (2019-04-10) 随笔 419人围观抢沙发百度已收录

Trie树学习总结

字典树，又称前缀树，是用于快速处理字符串的问题，能做到快速查找到一些字符串上的信息。

另外，Trie树在实现高效的同时，会损耗更多的空间，所以Trie是一种以空间换时间的算法。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Trie的思想

Trie的思想十分简单，其实我在很早之前就已经懂了Trie的思想，只不过一直没有实现，所以就……

咕咕，没事，Trie无论是思想还是代码思想都还是很简单。现在我重新再搞回Trie也很快就代码实现了。

Trie是思想其实用图更容易展现。下面放一张图给大家看看，相信大家很快就会明白了。

如果我们插入字符串：

zlh
AK
tql
AKIOI
AKnoip

上面就是一颗我们建的Trie树。

如果我们要查找“zlh”，那么就会沿着1->2->3点找下去。

如果我们要查找“AKIOI”，那么我们就会沿着4->5->9->10->11点找

也可以十分容易发现"AK"是"AKIOI"的前缀。

那么大家现在应该就能明白Trie的构造了吧。

简单说就是顺着之前Trie树的构造去插入点，例如我们最后插入"AKnoip"，就会先走过"A"和"K"，然后发现没有匹配的字符了，就先后新建了'n','o','i','p'，这几个点。复杂度O(len(字符串))。

查询就会沿着Trie的构造一个一个跳，所以查询复杂度是O(len(字符串))。

那么Trie的思想就是这样了。

Trie的实现

明白了思想，实现就应该很简单了吧，这里通过一道例题来实现Trie。

题目：P2580 于是他错误的点名开始了

定义

struct kkk{
    int son[27],cnt;
    bool flag;
}trie[maxn];

首先是插入操作：

void insert(string s){
    int len=s.size(),u=0;       //获取长度len，u是当前点的编号，根的编号是0
    for(int i=0;i<len;i++){
        int v=s[i]-'a';     //获取位置
        if(!trie[u].son[v]) //如果没有继续下去的节点
        trie[u].son[v]=++num;   //就新建一个
        u=trie[u].son[v];   //跳到下一个点去插入
    }
    trie[u].flag=true;  //标记此处是一个单词
}

然后是查询操作：

int find(string s){
    int len=s.size(),u=0;
    for(int i=0;i<len;i++){
        int v=s[i]-'a';     //同上
        if(!trie[u].son[v])return 3;    //找不到返回没有
        u=trie[u].son[v];   //同上
    }
    if(trie[u].flag==false)return 3;    //不是一个单词就返回没有
    if(!trie[u].cnt){       //如果没有被点过
        trie[u].cnt++;      //标记被点过了
        return 1;           //返回有
    } return 2;         //不然返回重复
}

那么Trie的实现就这样了。