基础数据结构第七期 Trie树
2024-01-07 18:48:17
前言
Trie树大家能够掌握即可,其实用到的地方并不多,本文将为大家介绍一下。
一、Trie树的基本内容
1、根节点不包含字符,除根结点之外每一个结点都只包含一个字符;
2、字典树用边表示字母表示
3、从根节点到某一结点, 路径上经过的字符连接起来,为该结点对应的字符串
4、每个节点的所有子结点包含的字符都不同。每个结点最多有26个子节点(假设给定字符集中包含26个英文字母)
5、有相同前缀的单词共用前缀节点
6、整棵树的根节点是空的,便于插入和查找
7、每个单词结束的时候用一个特殊字符表示,那么从根节点到任意一个特殊字符,所经过的边的所有字母表示一个单词
8、Trie树的空间效率较低,实际上是用空间来换时间的一种数据结构
图解:
二、典型例题
例1:
AC代码:
数组:
#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;//下标是0的点,既是根节点,又是空节点
char str[N];
//插入操作
void insert(char str[]) {
int p = 0;//从根节点开始
for (int i = 0; str[i]; i++) {//字符串末尾是0
int u = str[i] - 'a';//把小写字母映射成0~25
if (!son[p][u])//如果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;
p = son[p][u];
}
return cnt[p];//返回以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;
}
STL:
#include<iostream>
using namespace std;
#include<map>
int n;
char c;
string x;
map<string,int>m;
int main()
{
cin>>n;
while(n--){
cin>>c>>x;
if(c=='I')
m[x]++;
if(c=='Q')
cout<<m[x]<<endl;
}
return 0;
}
例2:
AC代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 31 * N;
int son[M][2];
int a[N];
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, 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;
}
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", &a[i]);
int res = 0;
for (int i = 0; i < n; i ++)
{
insert(a[i]);
int t = query(a[i]);
res = max(res, a[i] ^ t);
}
printf("%d\n", res);
return 0;
}
总结
这部分不是很难理解,大家熟练掌握即可,感谢大家的观看谢谢大家!!!
文章来源:https://blog.csdn.net/2301_80882026/article/details/135390751
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!