2018年2月6日
Trie树原理与实现
注:本文部分图片来自互联网,其相关权利归原作者所有,感谢原作者的分享。
概述
Trie树是一种具有字符串插入和查找功能的数据结构,又称前缀树。这里介绍它的原理和实现。
原理
结构
如上图,这就是一棵Trie树。这个Trie树中包含的单词有abc
、abd
、abcd
、b
、bcd
、efg
和hij
。可以看到,Trie的字母并不存在结点上,而是存在边上。每个结点的儿子表示以这个结点对应的前缀的字符串的延续。结点的标记代表字符串的终止。这就是一棵Trie树的结构。
查找
了解了它的结构特征后,我们尝试查找一个给定字符串。这一步骤的核心操作就是下跳。从根节点开始,逐字符下跳,直到没有对应的字符或者终止节点无标记,代表查找失败。而如果一直有对应的字符且终止节点有标记代表查找成功。如果能跳出一段,代表当前Trie树中有字符串与查找串有公共前缀。
各位可以在上图中自己尝试一下。
插入
同样是下跳,区别是在找不到字符时候手动建新结点,再给终止结点打标记。各位可以在上图手动尝试插入。
示例
查找abd
成功。
查找abe
失败。
查找bc
失败。
插入brqy
。
实现
准备工作
用一个结构体Node
来存储结点信息。
struct Node {
bool wrd;
int ch[26];
}
其中wrd
表示结点是否是字符串的结尾,ch
表示不同字符边对应的儿子编号。
创建Node
数组表示整个Trie树,并以Node[1]
作为树根。用siz
变量统计目前结点数。
查找
inline bool search(char* str) {
int t = 1;
for(int i = 0; i < strlen(str); i++) {
if(!trie[t].ch[str[i] - 'a']) {
return false;
} else {
t = trie[t].ch[str[i] - 'a'];
}
}
if(trie[t].wrd) {
return true;
} else {
return false;
}
}
模拟下跳过程,检查是否有结点、是否有标记。
插入
inline void insert(char* str) {
int t = 1;
for(int i = 0; i < strlen(str); i++) {
if(!trie[t].ch[str[i] - 'a']) {
t = trie[t].ch[str[i] - 'a'] = ++siz;
} else {
t = trie[t].ch[str[i] - 'a'];
}
}
trie[t].wrd = true;
}
动态开节点,加标记。
一道例题:于是他错误的点名开始了
题意
插入字符串,查找字符串,判断字符串找没找过。
题解
Trie可以胜任前两个操作。至于判断是否找过,在结束结点上记录访问过没有即可。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
struct Node {
bool wrd, vis;
int ch[26];
} trie[500005];
int siz = 1;
inline void insert(char* str) {
int t = 1;
for(int i = 0; i < strlen(str); i++) {
if(!trie[t].ch[str[i] - 'a']) {
t = trie[t].ch[str[i] - 'a'] = ++siz;
} else {
t = trie[t].ch[str[i] - 'a'];
}
}
trie[t].wrd = true;
}
inline int search(char* str) {
int t = 1;
for(int i = 0; i < strlen(str); i++) {
if(!trie[t].ch[str[i] - 'a']) {
return 0;
} else {
t = trie[t].ch[str[i] - 'a'];
}
}
if(trie[t].wrd) {
if(trie[t].vis) return -1;
trie[t].vis = true;
return 1;
} else {
return 0;
}
}
int n, m;
char str[55];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%s", str);
insert(str);
}
scanf("%d", &m);
for(int i = 0; i < m; i++) {
scanf("%s", str);
int res = search(str);
if(res == 1) printf("OK\n");
else if(res == -1) printf("REPEAT\n");
else printf("WRONG\n");
}
return 0;
}