Trie树
创新互联是一家专业提供
衡阳县企业网站建设,专注与
成都网站设计、成都网站建设、
HTML5、小程序制作等业务。10年已为衡阳县众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。作用
用来高效快速存储和查找字符串集合的一种数据结构
存储图解
假设有若干个字符串
先创建了一个根结点root，代指字符串集合的开头，对第一个字符串abcdef存储就如上图所示
当存储abdef时，一直走到b都和abcdef相同，于是在b点另开一个分支存储之后的def
当存储aced时，一直走到a都和abcdef相同，于是在a点另开一个分支存储之后的ced
以此类推
…
我们就得到能够以树的形式存储一个字符串集合
并且在每个字符串的结尾的字母都标记一下，表示以该字母结尾的节点是存在一个字符串的
如果有类似abc这样的字符串，也要在c点标记一下
查找图解
如果要查找一个不存在的字符串，比如abcf
沿着树枝一直走，走到c之后发现没有f对应的路径，那么就说明该字符串不存在
或者查找一个字符串，该字符串在存储里的字符串不存在，但属于某个存储的字符串的前缀
比如abcdef中的abc作为要查找的字符串
沿着树枝走，发现c点没有标记，即使有对应对应路径也不能说明该字符串存在
代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;
const int N = 100010;
int son[N][26];//代表每个节点可以有26个子节点
int cnt[N];//以当前这个点结尾的字符串有多少个
int idx;//操作次数，当前用到了哪个下标
//下标是0的点，既是根节点，也是空节点
char str[N];
void insert(char str[])//插入新字符串
{int p = 0;//根节点
for (int i = 0;str[i];i++)
{int u = str[i] - 'a';//存储编号，字母a-'a'就变成了0，b就变成了1
//如果说该节点之后没有这个字母，即son[p][u] == 0
if (!son[p][u]) son[p][u] = ++idx;//把这个节点加进去
p = son[p][u];
}
cnt[p]++;//表示以该点结尾的数量又多了一个
}
int query(char str[])//查询字符串
{int p = 0;
for (int i = 0;str[i];i++)
{int u = str[i] - 'a';
if (!son[p][u]) return 0;//如果不存在直接返回0
p = son[p][u] ;
}
return cnt[p];//返回以该节点结尾的单词数量
}
int main()
{int n;
scanf("%d", &n);
while (n--)
{char op[2];//操作类型+空格
scanf("%s%s", op,str);
if (op[0] == 'I') insert(str);//插入操作
else printf("%d\n", query(str));//查询操作
}
return 0;
}
习题
暴力做法
利用两重for循环来寻找大异或
//暴力法
for (int i = 0;i< n;++i)
{for (int j = 0; j< i;++j)
res = max(res, (arr[i] ^ arr[j]));
}
能被看作是trie树的原因
因为运算方式是异或，而异或看的是二进制，如果两个数的二进制某一位相同则为0，不同则为1
因此可以用31个长度的数组存储两个数的每一位
且对二进制从左往右看时，假设一个数为0，可以用trie树查询最高位为1的数，再找下一位为1的数，以此类推，便可以快速找出异或后的大数
因此，对某个数查询能够在存储里的数寻找大异或时，可以从最高位依次查找每一位相异的数
实现代码
#define _CRT_SECURE_NO_WARNINGS 1
#include#include
using namespace std;
const int N = 100010;
const int M = N * 31;
int arr[N];
int son[M][2];
int idx;
void insert(int x)
{int p = 0;//尾节点
for (int i = 30;i >= 0;--i)
{int u = x >>i & 1;//得到该位
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int query(int x)
{int p = 0;
int res = 0;
for (int i = 30;i >= 0;i--)
{int u = x >>i & 1;
//如果该位相异的数存在
if (son[p][!u])
{ p = son[p][!u];
res = res * 2 + !u;//相当于把所有的位数进一再加上u
}
else
{ p = son[p][u];
res = res * 2 + u;
}
}
return res;
}
int main()
{int n;
scanf("%d", &n);
for (int i = 0;i< n;++i) scanf("%d", &arr[i]);
int res = 0;
for (int i = 0;i< n;++i)
{insert(arr[i]);
//先插入在查询，防止第一次查询不到的情况
int t = query(arr[i]);
res = max(res, (arr[i] ^ t));
}
printf("%d", res);
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：数据结构：字典树Trie-创新互联
网页链接：
http://cdkjz.cn/article/doisce.html
