浅谈 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;
}