Trie树的个人理解与总结

Trie树又称为字典树，单词查找树是一种能够高效储存和查找字符串集合的数据结构。

储存方式如下：

假设有如下字符串集合需要储存

abc，abcde，bce，abcef，acbd，cstf。

?由图可知：

Trie树储存字符串集合的方式是首先将具有相同前缀的字符串合并为一个字符串集合，再储存这些合并以后的集合。而图中的六芒星是为了标记Trie树中已储存的字符串。（只需要要储存对字符串最后一个字符做标记即可）。

接下来我们用一道简单题看看怎么用数组来模拟Trie树。

该题为Acwing的835号题 （有兴趣的道友可以去Acwing的网站做题）

数组模拟Trie树

首先是一些变量定义的含义

trie[p][u]； //这是用来模拟Trie树的数组

{

p代表当前节点的大致位置；

u代表对应的字母（该题只用26个小写字母）；

p与u共同确定节点的位置；

其中储存的是下一个节点的位置；

}

idx；//这是一个有着类似指针作用的变量（指向当前的使用的节点）

cut[ ]；//用来记录单词出现的次数；

str[ ];；//用来储存要储存的字符串的；

?插入操作代码

void insert( char *str){
? ? int p=0;//一个类似指针的变量，指向当前节点;
? ? for(int i = 0;str[i] ;i++){
? ? ? ? int u = str[i] - 'a';//将a~z的小写字母映射为0~25的数字；
? ? ? ? if(!trie[p][u]) trie[p][u] = ++idx;

//该节点不存在，创造节点，其中储存下一个节点的位置;
? ? ? ? p=trie[p][u];

//使p指针指向下一个节点；
? ? }
? ? cut[p]++;//字符串储存结束的标记，同时也可以记录该字符串插入的次数；
? ? return;
}

查找操作代码

?int search(char *str){
? ? int p = 0;//同上
? ? for(int i = 0;str[i];i++){
? ? ? ? int u = str[i] - 'a';//同上；
? ? ? ? if(!trie[p][u]) return 0 ; //该节点不存在，即字符串不存在；
? ? ? ? p = trie[p][u] ; //同上
? ? }
? ? return cut[p];//返回该字符串出现的次数
}

?完整代码

#include<iostream>
using namespace std;

const int N=1e5+10;
int trie[N][26],cut[N],idx;
char str[N];
void insert(char *str){
? ? int p=0;
? ? for(int i=0;str[i];i++){
? ? ? ? int u =str[i]-'a';
? ? ? ? if(!trie[p][u])trie[p][u]=++idx;
? ? ? ? p=trie[p][u];
? ? }
? ? cut[p]++;
? ? return;
}
int search(char *str){
? ? int p=0;
? ? for(int i=0;str[i];i++){
? ? ? ? int u = str[i] - 'a';
? ? ? ? if(!trie[p][u]) return 0;
? ? ? ? p = trie[p][u];
? ? }
? ? return cut[p];
}
int main(){
? ? int n;
? ? char c[2];
? ? scanf("%d",&n);
? ? while(n--){
? ? ? ? scanf("%s%s",c,str);
? ? ? ? if(c[0]=='I'){
? ? ? ? ? ? insert(str);
? ? ? ? }
? ? ? ? else{
? ? ? ? ? ? printf("%d\n",search(str));
? ? ? ? }
? ? }
? ? return 0;
}