Featured image of post 浅谈 Trie 树

浅谈 Trie 树

浅谈 Trie 树

什么是 Trie 树?

Trie 树,又称字典树,可用于存储单词。

Trie 树的根节点不表示任何字母,但是除了根节点的所有字母都表示一个字母。

任何一个单词,都可以用一条从根节点出发的路径表示。在路径的终点做一个“结束”标记,对应一个单词的结尾。

举个例子:要存储 work,word,world,hello 这些单词。

红色节点表示“结束”标记。

可以看到,叶子节点都是一个单词的结尾;但是并不是所有的单词结尾都是叶子节点

再举个例子:假如要多存储一个 worker 单词。

Trie 树的好处之一,如果两个单词有公共前缀,则有公共路径,可以节省空间。

存储结构

Trie 树中的每个节点都可以用一个结构体来存储。

code

1
2
3
4
struct node{
    bool flg; // 结束标记
    int son[MAXC]; // 儿子们的“指针”,MAXC表示字符集的大小
}Trie[MAXN]; // MAXN表示Trie树的节点数

节点的字母(值)怎么表示?

一般在程序中,都是去枚举节点 $i$,所以一般不用结构体来表示节点的字母。

构建 Trie 树

先分配足够大的空间(Trie 树),也就是定义足够大的 node 数组。

然后每读入一个单词,就插入在 Trie 树当中。

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#define MAXC 26
struct node{
    bool flg;
    int son[MAXC];
}Trie[MAXN];
int root=1,tot=1;
void ins(int r,char *s){
    int len=strlen(s),val;
    for(int i=0;i<len;i++){
        val=s[i]-'a';
        if(Trie[r].son[val]==0)
            Trie[r].son[val]=++tot;
        r=Trie[r].son[val];
    }
    Trie[r].flg=1;
}

查询节点

1
2
3
4
5
6
7
8
9
bool query(int rt,char *s){
    int len=strlen(s),val;
    for(int i=0;i<len;i++){
        val=s[i]-'a';
        rt=Trie[rt].son[val];
        if(rt==0) return 0;
    }
    return Trie[rt].flg;
}

此代码可以返回“查询串”(char *s)的结尾的信息。

这里返回了 Trie[rt].flg,仅作示范。在实践中,可以返回 Trie[rt].cnt 等等定义的变量。

例 1 :单词查找树

P5755 [NOI2000] 单词查找树

算法分析

就是裸的 Trie 树,模板题。

code(这里直接复制了 Alex_Wei 的代码)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
string s;
int cnt,q[1<<15][26];//cnt为节点个数,q为儿子编号
int main(){
    while(cin>>s){
        int pos=0;
	for(int i=0;i<s.size();i++){
	    int ch=s[i]-'A';
	    if(!q[pos][ch])q[pos][ch]=++cnt;//如果没有这个节点,就新建一个
	    pos=q[pos][ch];
	}
    }
    cout<<cnt+1<<endl;//本题中root也算一个节点,别忘了+1
    return 0;
}