【数据结构】前缀树的模拟实现

目录

1、什么是前缀树？

2、模拟实现

2.1、前缀树节点结构

2.2、字符串的添加

2.3、字符串的查寻

2.3.1、查询树中有多少个以字符串"pre"作为前缀的字符串

2.3.2、查询某个字符串被添加过多少次 

2.4、字符串的删除

3、完整代码


 

1、什么是前缀树？

前缀树又名字典树，单词查找树，Trie树，是一种多路树形结构，是哈希树的变种，和hash效率有一拼，是一种用于快速检索的多叉树结构,。典型应用是用于统计和排序大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词颛统计。

它的优点：最大限度地减少无谓的字符比较，查询效率比哈希表还高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低査询时间的开销以达到提高效率的目的。
Trie树的缺点：Trie树的内存消耗非常大。
性质:不同字符串的相同前缀只保存一份。
操作:查找，插入，删除。

注：本文章的前缀树功能都是基于字符串的

举个例子，例1：假设有：“abc”，“adf”，“cf”，“abcf”，“adf” 这五个字符串，则前缀树结构入下所示

2、模拟实现

以下的解析都是以上面的例1作为例子

2.1、前缀树节点结构

解释：创建一个前缀树节点类，前缀树节点中，我们并不放值，也就是并不放字符。我们把值，也就是字符，防止当前节点通往父节点的路上。前缀树节点类中有三个属性：int整形 pass、int整形 end  和  前缀树节点数组 nextS。

pass：pass用于记录当前这个节点经历过多少次，也就是上一级节点到当前节点的这条路通过了几次，这非常有助于查询树中有多少个字符串以某个字符串作为前缀。

end：记录这个节点是多少个字符串的结尾节点，这非常有助于查询某个字符串被加入过多少次。

节点数组 nextS[ ]：这是一个前缀树节点数组，用于记录当前这个节点通向下一个节点的路，比如：nextS[0] == null 没有走向'a’的路；nextS[0] != null 有走向'a’的路；......；nextS[25]!= nu1l 有走向'z’的路。这里数组中下标与字符的对应关系为：0->a; 1->b; 2->c; ......; 24->y; 25->z ，这钟关系在代码中的转换方式为：先定义一个下标变量index，然后每次要访问数组时，先让下标变量index等于要转换的字符减去字符‘a’就可以了，即：比如字符‘c’的转换为 index = 'c' - 'a'; 这条语句执行完后index会等于2，也就成功把字符'c'转换成数字2了。

节点结构代码

//前缀树的节点结构类public static class TreeNode {public int pass;  //pass用于记录当前这个点经历过多少次public int end;  //表示这个节点是多少个字符串的结尾节点//nextS是当前节点的下级节点，本实例中数组中的元素个数为26，从a到zpublic TreeNode[] nextS;  // HashMap<Char, TreeNode> nextS; 当字符种类特别多的时候，可以用HashMappublic TreeNode() {pass = 0;end = 0;// nextS[0] == null 没有走向'a’的路// nextS[0] != null 有走向'a’的路// ...// nextS[25]!= null 有走向'z’的路nextS = new TreeNode[26];}}

2.2、字符串的添加

字符串的添加从root节点开始，先把要添加的字符串转换成字符数组，然后从左往右开始遍历添加。

如当前节点node要添加一个字符，添加的规则为：

注：数组nextS[ ]中的数组元素都是前缀树节点类型，其实就是节点

当node的nextS[ ]中与该字符对应的数组元素为空时：那就要先为这个数组元素初始化，给这个数组元素new一个实例对象，这个实例对象起始就是一个新创建的节点，然后来到这个新建的节点，让这个节点的pass加一，然后看当前添加的这个字符在字符数组是不是最后一个字符：如果是，则还需要让这个节点的end加一；如果不是，则按这种规则继续添加字符数组中后面还没添加的字符。

当node的nextS[ ]中与该字符对应的数组元素不为空时：那就直接来到这个数组元素，也就是这个节点，让这个节点的pass加一，然后看当前添加的这个字符在字符数组是不是最后一个字符：如果是，则还需要让这个节点的end加一；如果不是，则按这种规则继续添加字符数组中后面还没添加的字符。

实现代码： 

//把字符串word加入到树中public void insert(String word) {if (word == null) {return;}char[] chs = word.toCharArray();  //把字符串word转换成字符数组TreeNode node = root;node.pass++;int index = 0;for (int i=0; i<chs.length; i++) {  //从左往右遍历字符index = chs[i] - 'a';  //由字符对应成要走哪条路if (node.nextS[index] == null) {//当node的nextS[ ]中与该字符对应的数组元素为空时node.nextS[index] = new TreeNode();}node = node.nextS[index];  //来到下一个节点node.pass++;}//当for循环结束了，就说明字符数组中的最后一个字符也添加完了，所以当前节点的end加一node.end++;}

2.3、字符串的查寻

2.3.1、查询树中有多少个以字符串"pre"作为前缀的字符串

例：比如我们要查询例1中的五个字符串中有多少个字符串以空字符串“ ”作为前缀，我们只需要返回root节点的pass，可以理解为root节点通往上一级节点的路为空，和空字符串对应，所以直接返回root节点的pass；

例：再比如我们要查询例1中的五个字符串中有多少个字符串以字符串“ab”作为前缀，我们先查看root下的a这条路是不是为空，如果为空就直接返回0，不为空就来到a这条路连接的下一个节点，然后我们查看来到的这个节点下的b这条路是不是为空，如果为空就直接返回0，不为空就来到b这条路连接的下一个节点，然后返回b这条路连接的下一个节点的pass，也就是2，这样我们就查询到了例1中的五个字符串中有2个字符串以字符串“ab”作为前缀。

以上两个例子都是在树中存在以字符串"pre"作为前缀的字符串的情况，如果不存在，那么在遍历字符数组时就会遇到有node的nextS[ ]中与当前查询字符对应的数组元素为空的情况，这时候直接返回0，因为这种情况就是表面树中不存在字符串“pre”，那就跟不可能存在以字符串"pre"作为前缀的字符串了

例：比如我们要查询例1中的五个字符串中有多少个字符串以字符串“aec”作为前缀，当我们来到a这条路连接的这个节点时，我们会发现这个节点的nextS数组中与字符‘e’对应的数组元素是空的，所以直接返回0。

实现代码： 

//查询所有加入的字符串中，有多少字符串是以字符串pre作为前缀的public int prefixNumber(String pre) {if (pre == null) {return 0;}char[] chs = pre.toCharArray();  //把字符串word转换成字符数组TreeNode node = root;int index = 0;for (int i=0; i<chs.length; i++) {index = chs[i] - 'a';if (node.nextS[index] == null) {return 0;}node = node.nextS[index];  //来到下一个节点}return node.pass;}

2.3.2、查询某个字符串被添加过多少次 

查询某个字符串被添加过多少次 和 查询树中有多少个以字符串"pre"作为前缀的字符串的规则是一样的，只是返回的节点属性不同，这里要返回的是节点的end，当字符数组遍历完后就会来到要查询的字符串的最后一个字符所对应的节点，然后返回这个节点的end就是这个字符串被添加过多少次 的结果了。

实现代码：

//查询word这个字符串加入过几次public int search(String word) {if (word == null) {return 0;}char[] chs = word.toCharArray();  //把字符串word转换成字符数组TreeNode node = root;int index = 0;for (int i=0; i<chs.length; i++) {index = chs[i] - 'a';if (node.nextS[index] == null) {return 0;}node = node.nextS[index];  //来到下一个节点}return node.end;}

2.4、字符串的删除

删除字符串和添加字符串规则相似，只是添加时是对节点的pass和end进行加一，而删除时是对节点的pass和end进行减一

实现代码： 

//删除字符串public void delete(String word) {if (search(word) != 0) {  //确定树中确实加入过word，才去执行删除操作char[] chs = word.toCharArray();TreeNode node = root;node.pass--;  //当前节点的pass减一int index = 0;for (int i=0; i<chs.length; i++) {index = chs[i] - 'a';if (--node.nextS[index].pass == 0) {//java会自动去释放内存空间，所以java里可以直接把node下级的路直接标空node.nextS[index] = null;return;}node = node.nextS[index];}node.end--;  //node已经来到了字符串word中的最后一个字符，然后这个node的end减一}}

3、完整代码

public class Code01_TrieTree {//前缀树的节点结构类public static class TreeNode {public int pass;  //pass用于记录当前这个点经历过多少次public int end;  //这个节点是多少个字符串的结尾节点//nextS是当前节点的下级节点，本实例中数组中的元素个数为26，从a到zpublic TreeNode[] nextS;  // HashMap<Char, TreeNode> nextS; 当字符种类特别多的时候，可以用HashMappublic TreeNode() {pass = 0;end = 0;// nextS[0] == null 没有走向'a’的路// nextS[0] != null 有走向'a’的路// ...// nextS[25]!= null 有走向'z’的路nextS = new TreeNode[26];}}//前缀树的类，内涵前缀树的构造方法和字符串的加入、删除、查找字符串加入了几次和以字符串pre作为前缀的字符串有多少个public static class Tree {private TreeNode root;public Tree() {root = new TreeNode();}//把字符串word加入到树中public void insert(String word) {if (word == null) {return;}char[] chs = word.toCharArray();  //把字符串word转换成字符数组TreeNode node = root;node.pass++;int index = 0;for (int i=0; i<chs.length; i++) {  //从左往右遍历字符index = chs[i] - 'a';  //由字符对应成要走哪条路if (node.nextS[index] == null) {//当node的nextS[ ]中与该字符对应的数组元素为空时node.nextS[index] = new TreeNode();}node = node.nextS[index];  //来到下一个节点node.pass++;}//当for循环结束了，就说明字符数组中的最后一个字符也添加完了，所以当前节点的end加一node.end++;}//删除字符串public void delete(String word) {if (search(word) != 0) {  //确定树中确实加入过word，才去执行删除操作char[] chs = word.toCharArray();TreeNode node = root;node.pass--;  //当前节点的pass减一int index = 0;for (int i=0; i<chs.length; i++) {index = chs[i] - 'a';if (--node.nextS[index].pass == 0) {//java会自动去释放内存空间，所以java里可以直接把node下级的路直接标空node.nextS[index] = null;return;}node = node.nextS[index];}node.end--;  //node已经来到了字符串word中的最后一个字符，然后这个node的end减一}}//查询word这个字符串加入过几次public int search(String word) {if (word == null) {return 0;}char[] chs = word.toCharArray();  //把字符串word转换成字符数组TreeNode node = root;int index = 0;for (int i=0; i<chs.length; i++) {index = chs[i] - 'a';if (node.nextS[index] == null) {return 0;}node = node.nextS[index];  //来到下一个节点}return node.end;}//查询所有加入的字符串中，有多少字符串是以字符串pre作为前缀的public int prefixNumber(String pre) {if (pre == null) {return 0;}char[] chs = pre.toCharArray();  //把字符串word转换成字符数组TreeNode node = root;int index = 0;for (int i=0; i<chs.length; i++) {index = chs[i] - 'a';if (node.nextS[index] == null) {return 0;}node = node.nextS[index];  //来到下一个节点}return node.pass;}}}

 

推荐：

java数据结构（哈希表—HashMap）含LeetCode例题讲解-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/m0_65277261/article/details/134712832?spm=1001.2014.3001.5501【计算机组成原理】存储器知识-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/m0_65277261/article/details/134770339?spm=1001.2014.3001.5501【计算机网络】（网络层）定长掩码和变长掩码_定长子网掩码和变长子网掩码-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/m0_65277261/article/details/134606175?spm=1001.2014.3001.5501

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Vue-Vue3 集成编辑器功能

Vue-Vue3 集成编辑器功能

1、安装依赖 编辑器插件需要安装 wangeditor/editor 和 wangeditor/editor-for-vue 两个插件 npm install wangeditor/editor --savevue3运行如下命令安装 npm install wangeditor/editor-for-vuenext --savevue2运行如下命令安装 npm install wangeditor/editor-for-vue -…
阅读更多...
设计模式3-责任链模式

设计模式3-责任链模式

责任链模式是一种行为设计模式&#xff0c;它允许你创建一个对象链。请求沿着这条链传递&#xff0c;直到有一个对象处理它为止。这种模式通常用于需要以某种方式动态地决定处理请求的顺序或方式的情况。 类图&#xff1a; 从图中可见最大的特点是AbstractHandler它自己聚合了自…
阅读更多...
华清作业day56

华清作业day56

SQLite特性&#xff1a; 零配置一无需安装和管理配置&#xff1b;储存在单一磁盘文件中的一个完整的数据库&#xff1b;数据库文件可以在不同字节顺序的机器间自由共享&#xff1b;支持数据库大小至2TB&#xff1b;足够小&#xff0c;全部源码大致3万行c代码&#xff0c;250KB…
阅读更多...
Redis——集群环境部署

Redis——集群环境部署

一般情况下的Redis&#xff0c;我们都是在一台服务器上进行操作的&#xff0c;也就是说读、写以及备份操作都是在一台Redis服务器上进行的。随着项目访问量的增加&#xff0c;对Redis服务器的操作也更加频繁&#xff0c;虽然Redis读写速度都很快&#xff0c;但是一定程度上也会…
阅读更多...
书生·浦语大模型全链路开源体系

书生·浦语大模型全链路开源体系

参考&#xff1a;https://www.bilibili.com/video/BV1Rc411b7ns/?spm_id_from333.788&vd_source3bbd0d74033e31cbca9ee35e111ed3d1 背景&#xff1a; 人工智能的发展从针对特定任务&#xff0c;用一个模型解决一个问题过渡到一个模型来应对多模态、多任务&#xff0c;大模…
阅读更多...
程序设计基础实验破解（5）

程序设计基础实验破解（5）

一.前言 我上大一时接触到程序设计基础这门课&#xff0c;这门课有时会有实验&#xff0c;我便常常摸鱼&#xff0c;利用CSDN来做&#xff0c; 虽然有时搜不到&#xff0c;但每次搜到时我想&#xff1a;爽&#xff01;&#xff01;&#xff01; 于是我也开始写&#xff0c;写…
阅读更多...
【FFmpeg】ffplay 命令行参数 ⑤ ( 设置音频滤镜 -af 参数 | 设置统计信息 -stats 参数 | 设置同步时钟类型 -sync 参数 )

【FFmpeg】ffplay 命令行参数 ⑤ ( 设置音频滤镜 -af 参数 | 设置统计信息 -stats 参数 | 设置同步时钟类型 -sync 参数 )

文章目录 一、ffplay 命令行参数 - 音频滤镜1、设置音频滤镜 -af 参数2、常用的 音频滤镜 参数3、音频滤镜链 示例 二、ffplay 命令行参数 - 统计信息1、设置统计信息 -stats 参数2、关闭统计信息 -nostats 参数 三、ffplay 命令行参数 - 同步时钟类型1、设置同步时钟类型 -syn…
阅读更多...
盘点2024年1月Sui生态发展，了解Sui近期成长历程！

盘点2024年1月Sui生态发展，了解Sui近期成长历程！

2024年1月是Sui生态开门大吉的一个月&#xff0c;在2023交出优异的成绩单后&#xff0c;2024年的首月也圆满结尾。在BTC现货ETF通过的大背景之下&#xff0c;Web3行业多项指标持续展现增长趋势。Sui也紧随行业脚步&#xff0c;开展了一系列活动助力Web3行业和生态持续发展。 其…
阅读更多...
改变终端安全的革命性新兴技术：自动移动目标防御技术AMTD

改变终端安全的革命性新兴技术：自动移动目标防御技术AMTD

自动移动目标防御技术通过启用终端配置的自适应防御来改变终端检测和响应能力。产品领导者可以实施AMTD来确保实时威胁响应&#xff0c;并减少检测和响应安全威胁所需的时间。 主要发现 通过动态修改系统配置、软件堆栈或网络特征&#xff0c;自动移动目标防御&#xff08;AMTD…
阅读更多...
肯尼斯·里科《C和指针》第13章 高级指针话题（1）进一步探讨指向指针的指针变量的高级声明

肯尼斯·里科《C和指针》第13章 高级指针话题（1）进一步探讨指向指针的指针变量的高级声明

13.1 进一步探讨指向指针的指针 上一章使用了指向指针的指针&#xff0c;用于简化向单链表插入新值的函数。另外还存在许多领域&#xff0c;指向指针的指针可以在其中发挥重要的作用。这里有一个通用的例子&#xff1a; 这些声明在内存中创建了下列变量。如果它们是自动变量&am…
阅读更多...
第四篇:数据库安装(命令行)

第四篇:数据库安装(命令行)

数据库命令行界面安装 mysql官网&#xff0c;下载解压 https://dev.mysql.com/downloads/mysql/ 在安装之前先去检查一下,本地计算机的用户合组 winr(输入lusrmgr.msc) -点击组-双击administrator 如果只有这两个,那么就添加一下,提高网络服务的权限(避免出现mysql启动失败) …
阅读更多...
Blazor SSR/WASM IDS/OIDC 单点登录授权实例2-登录信息组件wasm

Blazor SSR/WASM IDS/OIDC 单点登录授权实例2-登录信息组件wasm

目录: OpenID 与 OAuth2 基础知识Blazor wasm Google 登录Blazor wasm Gitee 码云登录Blazor SSR/WASM IDS/OIDC 单点登录授权实例1-建立和配置IDS身份验证服务Blazor SSR/WASM IDS/OIDC 单点登录授权实例2-登录信息组件wasmBlazor SSR/WASM IDS/OIDC 单点登录授权实例3-服务端…
阅读更多...
FPGA实现ISP用于无人车、无人机配送的方案调研

FPGA实现ISP用于无人车、无人机配送的方案调研

查到一个always 奥唯思公司做的用FPGA实现ISP的方案&#xff0c;采用易灵思钛金16nm的FPGA Ti60F225&#xff0c;通过MIPI CSI RX采集图像传感器的数据&#xff0c;在FPGA内部经过一系列复杂的ISP运算后&#xff0c;再通过MIPI CSI TX将图像数据发送给后端。 一套完整的ISP&a…
阅读更多...
（2024，仅高频分量的蓝噪声与高斯噪声线性插值，时变噪声）扩散模型的蓝噪声

（2024，仅高频分量的蓝噪声与高斯噪声线性插值，时变噪声）扩散模型的蓝噪声

Blue noise for diffusion models 公和众和号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 1. 简介 2. 相关工作 3. 方法 3.1 相关噪声 3.2 具有时变噪声的扩散模型 3.3 利用矫正…
阅读更多...
Hexo更换Matery主题

Hexo更换Matery主题

引言 在数字化时代&#xff0c;拥有一个个人博客已经成为许多人展示自己技能、分享知识和与世界互动的重要方式。而在众多博客平台中&#xff0c;Hexo因其简洁、高效和易于定制的特点而备受青睐。本文将详细介绍如何为你的Hexo博客更换主题&#xff0c;让你的个人博客在互联网…
阅读更多...
【前端高频面试题--Vue基础篇】

【前端高频面试题--Vue基础篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;前端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac;前端高频面试题--Vue基础篇 Vue基本原理双向绑定与MVVM模型Vue的优点计算属性与监听属性计算属性监…
阅读更多...
MySQL篇之回表查询

MySQL篇之回表查询

一、聚集索引 将数据存储与索引放到了一块&#xff0c;索引结构的叶子节点保存了行数据。特点&#xff1a;必须有,而且只有一个。 聚集索引选取规则: 1. 如果存在主键&#xff0c;主键索引就是聚集索引。 2. 如果不存在主键&#xff0c;将使用第一个唯一&#xff08;UNIQUE&am…
阅读更多...
【集合系列】TreeMap 集合

【集合系列】TreeMap 集合

TreeMap 集合 1. 概述2. 方法3. 遍历方式4. 排序方式5. 代码示例16. 代码示例27. 代码示例38. 注意事项9. 源码分析 其他集合类 父类 Map 集合类的遍历方式 TreeSet 集合 具体信息请查看 API 帮助文档 1. 概述 TreeMap 是 Java 中的一个集合类&#xff0c;它实现了 SortedMap…
阅读更多...
Aethir和Well-Link Tech携手革新云游戏，释放人工智能(AI)潜力

Aethir和Well-Link Tech携手革新云游戏，释放人工智能(AI)潜力

​Aethir将为Well-Link Tech的2亿用户提供先进的GPU计算能力&#xff0c;大幅提升他们的游戏体验。 新加坡&#xff0c;2024年2月7日 - 先驱性的去中心化GPU网络Aethir与实时云渲染技术领导者Well-Link Tech携手共创云游戏和元宇宙发展的新时代。 借助Well-Link Tech对领先游戏…
阅读更多...
CTFSHOW命令执行web入门29-54

CTFSHOW命令执行web入门29-54

description: >- 这里就记录一下ctfshow的刷题记录是web入门的命令执行专题里面的题目，他是有分类，并且覆盖也很广泛，所以就通过刷这个来，不过里面有一些脚本的题目发现我自己根本不会笑死。 如果还不怎么知道写题的话，可以去看我的gitbook，当然csdn我也转载了我自己的…
阅读更多...
最新文章

Copyright @ 2022~2023