##创作计划##Trie(字典树)详解
2025-05-30 12:28:07
发布于：北京
30阅读
0回复
0点赞
0.Trie介绍
Trie，即字典树、单词查找树，是一种使用空间换取时间的数据结构。
除了根节点（空字符），其它节点都是一个字符，所以字典树上的一条路径就是一个的字符串。也就是说，字符串共用一个前缀。
1.Trie的结构
以拥有字符串 a、abc、abcd、bnm、brx、lje 的一棵 Trie 为例（红色节点标志着这是一个字符串的最后字符，不然无法确认）：
可以发现 Trie 每个字符串的最后字符在树上离 root 节点即这个字符串的长度。
Trie 的每个节点的儿子也只可能有字符集的大小个，一般来说，这个数不超过 。
同时，Trie 最差的空间复杂度即 （ 代表字符串的长度），不难想到构造这样的例子只需要让前缀不同即可。
这里给出数组实现的代码（一样的，后文中我们也只使用数组实现）：
struct TrieNode
{
bool isend;//是否为字符串结尾
int son[256];//子节点
}t[200005];
2.Trie的基本操作
插入
例如我们将上图所示的 Trie 再插入一个字符串 aaa，Trie 就会变成：
操作顺序即：
- 从 root 节点出发，保存一个计数器 ，代表当前要插入的字符（插入 ，下标从 开始）。
- 寻找当前节点的子节点，若存在等同于 的节点，进入这个节点， 加一，继续这个操作直至 ；否则进入下一步。
- 插入 ， 加一，进入上一步（实际上已经没有意义，因为必定不存在子节点，故不用查询，但为了实现方便可以这样）。
代码实现为：
int Cnt=1;
void insert(char* s)
{
int cnt=0,len=strlen(s);
for(int i=0;s[i];i++)
{
if(t[cnt].son[s[i]]==0)t[cnt].son[s[i]]=Cnt++;
cnt=t[cnt].son[s[i]];
if(i==len-1)t[cnt].isend=1;
}
}
查询
以图中 Trie 寻找字符串 bna 为例（箭头为查询顺序）：
操作顺序即：
- 从 root 节点出发，保存一个计数器 ，代表当前要查询的字符（插入 ，下标从 开始）。
- 寻找当前节点的子节点，若存在等同于 的节点，进入这个节点， 加一，继续这个操作直至 ，直至 ，寻找当前节点的子节点是否有为最后且等于 的字符，没有或不是最后进入下一步；否则进入下一步。
- 字符串不存在。
代码实现为：
bool find(char* s)
{
int cnt=0;
for(int i=0;s[i];i++)
{
if(t[cnt].son[s[i]]==0)return 0;
cnt=t[cnt].son[s[i]];
}
if(t[cnt].isend==0)return 0;
return 1;
}
完整实现
仅为示例：
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct TrieNode
{
bool isend;//是否为字符串结尾
int son[256];//子节点
}t[200005];
int Cnt=1;
void insert(char* s)
{
int cnt=0,len=strlen(s);
for(int i=0;s[i];i++)
{
if(t[cnt].son[s[i]]==0)t[cnt].son[s[i]]=Cnt++;
cnt=t[cnt].son[s[i]];
if(i==len-1)t[cnt].isend=1;
}
}
bool find(char* s)
{
int cnt=0;
for(int i=0;s[i];i++)
{
if(t[cnt].son[s[i]]==0)return 0;
cnt=t[cnt].son[s[i]];
}
if(t[cnt].isend==0)return 0;
return 1;
}
int q,op;
char s[200005];
signed main()
{
cin>>q;
while(q--)
{
cin>>op>>s;
if(op==1)insert(s);
else
{
if(find(s))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
return 0;
}
时间复杂度
因为 Trie 的操作只会进入一条路径，故最差时间复杂度为 （ 为字符串长度）。
3.例题及对比其它算法或数据结构的比较
洛谷P8306 【模板】字典树
备注：模板
| 算法或数据结构 | 时间复杂度（单次） | 额外空间复杂度 |
|---|---|---|
| 暴力 | ||
| Trie | ||
| 二分 | ||
STL 库 map（平衡树） |
洛谷P4551 最长异或路径
洛谷P10471 最大异或对 The XOR Largest Pair
备注：01Trie
4.Trie的拓展
由于 Trie 的优越复杂度和树形的易拓展性，Trie 被应用于许多算法。例如 AC 自动机、01Trie 等算法，请读者自行了解。
有帮助，赞一个