浅谈 Trie 树

news/发布时间2024/4/20 22:29:53

浅谈 Trie 树

什么是 Trie 树?

Trie 树,又称字典树,可用于存储单词。

Trie 树的根节点不表示任何字母,但是除了根节点的所有字母都表示一个字母。

任何一个单词,都可以用一条从根节点出发的路径表示。在路径的终点做一个“结束”标记,对应一个单词的结尾。

举个例子:要存储 work,word,world,hello 这些单词。

红色节点表示“结束”标记。

可以看到,叶子节点都是一个单词的结尾;但是并不是所有的单词结尾都是叶子节点

再举个例子:假如要多存储一个 worker 单词。

Trie 树的好处之一,如果两个单词有公共前缀,则有公共路径,可以节省空间。

存储结构

Trie 树中的每个节点都可以用一个结构体来存储。

code

struct node{bool flg; // 结束标记int son[MAXC]; // 儿子们的“指针”,MAXC表示字符集的大小
}Trie[MAXN]; // MAXN表示Trie树的节点数

节点的字母(值)怎么表示?

一般在程序中,都是去枚举节点 \(i\),所以一般不用结构体来表示节点的字母。

构建 Trie 树

先分配足够大的空间(Trie 树),也就是定义足够大的 node 数组。

然后每读入一个单词,就插入在 Trie 树当中。

code

#define MAXC 26
struct node{bool flg;int son[MAXC];
}Trie[MAXN];
int root=1,tot=1;
void ins(int r,char *s){int len=strlen(s),val;for(int i=0;i<len;i++){val=s[i]-'a';if(Trie[r].son[val]==0)Trie[r].son[val]=++tot;r=Trie[r].son[val];}Trie[r].flg=1;
}

查询节点

bool query(int rt,char *s){int len=strlen(s),val;for(int i=0;i<len;i++){val=s[i]-'a';rt=Trie[rt].son[val];if(rt==0) return 0;}return Trie[rt].flg;
}

此代码可以返回“查询串”(char *s)的结尾的信息。

这里返回了 Trie[rt].flg,仅作示范。在实践中,可以返回 Trie[rt].cnt 等等定义的变量。

例 1 :单词查找树

P5755 [NOI2000] 单词查找树

算法分析

就是裸的 Trie 树,模板题。

code(这里直接复制了 Alex_Wei 的代码)

#include<bits/stdc++.h>
using namespace std;
string s;
int cnt,q[1<<15][26];//cnt为节点个数,q为儿子编号
int main(){while(cin>>s){int pos=0;for(int i=0;i<s.size();i++){int ch=s[i]-'A';if(!q[pos][ch])q[pos][ch]=++cnt;//如果没有这个节点,就新建一个pos=q[pos][ch];}}cout<<cnt+1<<endl;//本题中root也算一个节点,别忘了+1return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.jwkm.cn/p/22036463.html

如若内容造成侵权/违法违规/事实不符,请联系宁远站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

为什么阿里不推荐使用 AtomicLong?

作者:伴川 来源:blog.csdn.net/kologin/article/details/135126371 前言 在分布式系统中,计数器是一个常见的需求。为了实现高并发、高可用的计数器,我们需要选择一个合适的实现方式。 在 Java 中,有两种常见的计数器实现方式:AtomicLong 和 LongAdder。 最近,阿里巴巴…

【开源项目推荐】——纯中文本地GPT知识库搭建项目.assets

大家好,我是独孤风。 又到了本周的开源项目推荐。近一年多的时间,人工智能迎来了大爆发。GPT相关的大模型的发展让很多领域都发生了巨大的变化。 但是虽然GPT的自然语言识别功能异常的强大,但回答给我们的知识内容并不尽如人意。那么,有没有可以在本地部署搭建的AI知识库项…

激光雷达技术、数据和应用简介

激光雷达技术、数据和应用简介 介绍 光探测和测距(激光雷达)测绘是一种公认的生成关于地球形状和表面特征的精确和直接地理参考空间信息的方法。激光雷达测绘系统及其赋能技术的最新进展使科学家和测绘专业人员能够以比以往任何时候都更高的精度、精度和灵活性,在大范围内检…

RedisBloom 安装与使用

目录一、前言 二、RedisBloom 安装与使用 三、RedisBloom 常用命令汇总 四、通过 Jedis 使用 RedisBloom 五、Redisson 封装的布隆过滤器 六、使用哪种方式的过滤器比较好? 一、前言 布隆过滤器(Bloom Filter)是 Redis 4.0 版本提供的新功能,它被作为插件加载到 Redis 服务…

[考研] 数据结构

24考研期间关于数据结构相关的总结。(本地的markdown图片没问题,上传的图片排版有点小问题,懒得调了。) 基础 线性结构:线性表、栈、队列 非线性结构:图、树、集合 区分线性结构和非线性结构:线性结构的每个元素(除了第一个和最后一个元素)最多只有一个直接前驱和一个直…

[数字人] NeRF实现

[数字人] NeRF实现 体渲染 光沿着路径传播,如果路径上有物体,就会损失能量,我们将单位面积的光的能量记为\(I(t)\)。假设光走了\(\Delta t\)的路程,此时剩下的能量可以表示成: \[I(t+\Delta t) = I(t) * (1-\sigma(t)\Delta t) \]其中\(\sigma(t)\)是该点物体的“密度”,…