数据结构——字典树
程序员文章站
2022-05-20 19:49:15
...
高大上,实用,真香;
字典树,顾名思义:用来当成字典用的 树型结构处理方式——(两种应用:1.字母数,2. 01字典树)
几个模块:1.建树。2.查询树。3.删除一些元素。
上图
这是一棵存储单词的字典树,数组tree[N][26], 表示字典树,图中的数字就是开辟空间的大小,从上至下每当没有相同字母时就开辟新的空间(代码中见详解),增加分支;
这儿需要注意的是:要灵活使用辅助数组进行,标记或者存储数据。输出查找数据、删除元素都是靠这
代码详解:
就N组单词,m次询问,若询问的单词在N组单词中输出Yes并删除,没有则输出No;
#include<stdio.h> //是时候锻炼自己阅读代码的能力了;
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
const int N=1e6;
int tree[N][26]; // 在开内存时要注意,尽量开大点防止RE;
int p[N],tot=1; // tot标记,记录内存开的大小;
bool q[N]; // 这应该认识吧!
void build_tree(char str[]) // 建树;
{
int root=0,i,len,pos;
len=strlen(str);
for(i=0;i<len;i++){
pos=str[i]-'a';
if(!tree[root][pos]){
tree[root][pos]=tot++;
}
root=tree[root][pos]; //理解这一步就懂了,root是字典树的指引,相当于是个指针,标号;
p[root]++; //标记字母出现的次数,方便后面的删除操作;其他情况也可以用;
}
q[root]=true; //标记再这一点是否有这个单词;
}
bool search_tree(char str[])
{
int root=0,i,len,pos;
len=strlen(str);
for(i=0;i<len;i++){
pos=str[i]-'a';
if(!tree[root][pos]||p[tree[root][pos]]<=0) //这儿p[]数组下标是指下一节点的字母剩余次数;
return false;
root=tree[root][pos]; //和上面一样;
}
if(!q[root])
return false;
return true;
}
void delet(char str[])
{
int root=0,i,len,pos;
len=strlen(str);
for(i=0;i<len;i++){
pos=str[i]-'a';
root=tree[root][pos]; //和上面一样;
p[root]--; //减去一次出现的次数;
}
}
int main()
{
int n,m,i;
char str[20];
memset(tree,0,sizeof(tree));
memset(p,0,sizeof(p));
memset(q,false,sizeof(q)); //用这个时注意头文件<cstring>;
scanf("%d%d",&n,&m);
getchar();
for(i=0;i<n;i++){
scanf("%s",str);
build_tree(str);
}
for(i=0;i<m;i++){
scanf("%s",str);
if(search_tree(str)){
printf("Yes\n");
delet(str);
}
else
printf("No\n");
}
return 0;
}
下面是01字典树,原理相似只是将数字转换成二进制储存在数组中;一般用于寻找最大异或数;
贴道题吧;
模版题:
N个数,m次询问,每次询问要求找出与x异或最大的数;
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
const int N=1e5+55;
long long p[N];
int tree[N][2];
int tot=1;
void build_tree(long long x)
{
int root=0,i,pos;
for(i=30;i>=0;i--){ //从最高位开始,因为最高位大小决定了异或数的大小,高位优先级最高;
pos=(x>>i)&1; // 取最高位;
if(!tree[root][pos]){
tree[root][pos]=tot++; // 开辟新的单元;
}
root=tree[root][pos];
}
p[root]=x; // 标记数字;
}
long long search_tree(long long x)
{
int root=0,i,pos;
for(i=30;i>=0;i--){
pos=(x>>i)&1;
if(tree[root][pos^1]) // 找异或最大的数字,不信自己手动模拟;
root=tree[root][pos^1];
else
root=tree[root][pos]; // 没有满足条件的就只能选另一个较小的了;
}
return p[root];
}
int main()
{
int n,i,m;
long long x;
memset(tree,0,sizeof(tree));
memset(p,0,sizeof(p));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%lld",&x);
build_tree(x);
}
for(i=0;i<m;i++){
scanf("%lld",&x);
printf("%lld\n",search_tree(x)); // 01字典树也存在删除元素哦;
}
return 0;
}
这是这是这是字典树,超好用,简单易懂;