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

目录

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://www.rhkb.cn/news/255066.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

MacOS - M1芯片 Mac 在“恢复”模式中启用系统扩展教程

MacOS - M1芯片 Mac 在“恢复”模式中启用系统扩展教程

部分软件需要开启系统扩展才能正常使用&#xff0c;但是默然M1芯片的Mac不能直接打开系统扩展&#xff0c;如下两图。 若要启用系统扩展&#xff0c;您需要在“恢复”环境中修改安全性设置。 若要执行此操作&#xff0c;请将系统关机&#xff0c;然后按住触控ID或电源按钮以开…
阅读更多...
CSS高级技巧

CSS高级技巧

一、 精灵图 1.1 为什么需要精灵图&#xff1f; 1.2 精灵图&#xff08;sprites&#xff09;的使用 二、 字体图标 2.1 字体图标的产生 2.2 字体图标的优点 2.3 字体图标的下载 icomoom字库 http://icomoon.io 阿里iconfont字库 http://www.iconfont.cn/ 2.4 字体图标的引用…
阅读更多...
在 Docker 中启动 ROS2 里的 rivz2 和 rqt 出现错误的解决方法

在 Docker 中启动 ROS2 里的 rivz2 和 rqt 出现错误的解决方法

1. 出现错误&#xff1a; 运行 ros2 run rivz2 rivz2 &#xff0c;报错如下 &#xff1a; No protocol specified qt.qpa.xcb: could not connect to display :1 qt.qpa.plugin: Could not load the Qt platform plugin "xcb" in "" even though it was f…
阅读更多...
npm 上传一个自己的应用(2) 创建一个JavaScript函数 并发布到NPM

npm 上传一个自己的应用(2) 创建一个JavaScript函数 并发布到NPM

上文 npm 上传一个自己的应用(1) 搭建一个项目环境 带着大家创建了一个项目环境 我们打开 看json的配置 我们入口是一个叫 index.js 的文件 那么 我们就要把它创建出来 之后 我们的方法也就要写在这里面 和 json同一个目录 创建 index.js 我们这里 写个简单的求和操作 index…
阅读更多...
图论与图数据应用综述：从基础概念到知识图谱与图智能

图论与图数据应用综述：从基础概念到知识图谱与图智能

目录 前言1 图论基础概念1.1 节点度1.2 度分布1.3 邻接矩阵 2 探索图的高级概念2.1 最短路径的关键性2.2 图的直径与平均路径的意义2.3 循环与路径类型的多样性 3 深入探讨图的广泛应用领域3.1 知识图谱的知识管理3.2 图智能在复杂决策中的应用3.3 图数据挖掘与分析的多领域应用…
阅读更多...
5.electron之主进程起一个本地服务

5.electron之主进程起一个本地服务

如果可以实现记得点赞分享&#xff0c;谢谢老铁&#xff5e; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 Electron 将 Chromium 和 Node.js 嵌入到了一个二进制文件中&#xff0c;因此它允许你仅需一个代码仓库&#xff0c;就可以撰写支持 Windows、…
阅读更多...
Rust开发WASM，WASM Runtime运行

Rust开发WASM，WASM Runtime运行

安装wasm runtime curl https://wasmtime.dev/install.sh -sSf | bash 查看wasmtime的安装路径 安装target rustup target add wasm32-wasi 创建测试工程 cargo new wasm_wasi_demo 编译工程 cargo build --target wasm32-wasi 运行 wasmtime ./target/wasm32-wasi/d…
阅读更多...
小白水平理解面试经典题目LeetCode 20. Valid Parentheses【栈】

小白水平理解面试经典题目LeetCode 20. Valid Parentheses【栈】

20.有效括号 小白渣翻译 给定一个仅包含字符 ‘(’ 、 ‘)’ 、 ‘{’ 、 ‘}’ 、 ‘[’ 和 ‘]’ &#xff0c;判断输入字符串是否有效。 输入字符串在以下情况下有效&#xff1a; 左括号必须由相同类型的括号封闭。 左括号必须按正确的顺序关闭。 每个右括号都有一个对…
阅读更多...
10.0 Zookeeper 权限控制 ACL

10.0 Zookeeper 权限控制 ACL

zookeeper 的 ACL&#xff08;Access Control List&#xff0c;访问控制表&#xff09;权限在生产环境是特别重要的&#xff0c;所以本章节特别介绍一下。 ACL 权限可以针对节点设置相关读写等权限&#xff0c;保障数据安全性。 permissions 可以指定不同的权限范围及角色。 …
阅读更多...
解决IntellIJ Idea内存不足

解决IntellIJ Idea内存不足

突然有一天我在IDEA打开两个项目时&#xff0c;发生了报错&#xff0c;说我内存不足&#xff0c;我这电脑内存16G怎么会内存不足。下面是我的解决方案。 IntelliJ IDEA 报告内存不足的原因通常与以下几个因素有关&#xff1a; 项目规模较大&#xff1a;如果您正在开发的项目非…
阅读更多...
解决“使用Edge浏览器每次鼠标点击会出现一个黑色边框”的问题

解决“使用Edge浏览器每次鼠标点击会出现一个黑色边框”的问题

目录 一 问题描述 二 解决方案 三 方案来源 四 参考资料 & AI工具 一 问题描述 为了方便进行收藏夹同步&#xff0c;开始从Chrome浏览器切换到Edge浏览器。在使用Edge浏览器过程中发现“每次鼠标点击会出现一个黑色边框”&#xff08;效果如下图所示&#xff09;&#…
阅读更多...
7.electron之渲染线程发送事件，主进程监听事件

7.electron之渲染线程发送事件，主进程监听事件

如果可以实现记得点赞分享&#xff0c;谢谢老铁&#xff5e; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 Electron 将 Chromium 和 Node.js 嵌入到了一个二进制文件中&#xff0c;因此它允许你仅需一个代码仓库&#xff0c;就可以撰写支持 Windows、…
阅读更多...
VSCode无法启动：Waiting for server log...

VSCode无法启动：Waiting for server log...

问题基本情况 [13:30:20.720] > code 1.86.0 (commit 05047486b6df5eb8d44b2ecd70ea3bdf775fd937) [13:30:20.724] > Running ssh connection command... /var/fpwork/reiss/vscdata/server/cplane/.vscode-server/code-05047486b6df5eb8d44b2ecd70ea3bdf775fd937 comman…
阅读更多...
Linux应用 进程间通信之共享内存(System V)

Linux应用 进程间通信之共享内存(System V)

1、定义 System V共享内存是一种在Unix和类Unix操作系统上用于进程间通信的机制。它允许多个进程共享同一块物理内存区域&#xff0c;从而可以在这些进程之间传递数据。 应用场景&#xff1a; 数据共享&#xff1a;多个进程需要共享大量数据&#xff0c;如数据库缓存、图像处…
阅读更多...
k8s-项目部署案例

k8s-项目部署案例

一、容器交付流程 在k8s平台部署项目流程 在K8s部署Java网站项目 DockerFile 如果是http访问&#xff0c;需要在镜像仓库配置可信任IP 三、使用工作负载控制器部署镜像 建议至少配置两个标签 一个是声明项目类型的 一个是项目名称的 继续配置属性 资源配额 健康检查 五、使…
阅读更多...
TS项目实战二：网页计算器

TS项目实战二：网页计算器

使用ts实现网页计算器工具&#xff0c;实现计算器相关功能&#xff0c;使用tsify进行项目编译&#xff0c;引入Browserify实现web界面中直接使用模块加载服务。   源码下载&#xff1a;点击下载 讲解视频 TS实战项目四&#xff1a;计算器项目创建 TS实战项目五&#xff1a;B…
阅读更多...
零基础学编程从入门到精通，系统化的编程视频教程上线，中文编程开发语言工具构件之缩放控制面板构件用法

零基础学编程从入门到精通，系统化的编程视频教程上线，中文编程开发语言工具构件之缩放控制面板构件用法

一、前言 零基础学编程从入门到精通&#xff0c;系统化的编程视频教程上线&#xff0c;中文编程开发语言工具构件之缩放控制面板构件用法 编程入门视频教程链接 https://edu.csdn.net/course/detail/39036 编程工具及实例源码文件下载可以点击最下方官网卡片——软件下载—…
阅读更多...
Win32 SDK Gui编程系列之--ListView自绘OwnerDraw(续)

Win32 SDK Gui编程系列之--ListView自绘OwnerDraw(续)

通过所有者绘制的列表视图（2） 所有者绘制列表视图的基础已在前一页中说明。本页将展示如何在所有者绘制列表视图中显示数据库表数据。 1、访问日志 正如在另一个页面中所述，本网站的访问日志目前是通过SQLite3数据库管理的。 以下是上述程序执行的结果。为…
阅读更多...
网神 SecGate 3600 防火墙 route_ispinfo_import_save 文件上传漏洞复现

网神 SecGate 3600 防火墙 route_ispinfo_import_save 文件上传漏洞复现

0x01 产品简介 网神SecGate 3600防火墙是基于状态检测包过滤和应用级代理的复合型硬件防火墙，是专门面向大中型企业、政府、军队、高校等用户开发的新一代专业防火墙设备，支持外部攻击防范、内网安全、网络访问权限控制、网络流量监控和带宽管理、动态路由、网页内容过滤、邮…
阅读更多...
数据库管理-第146期 最强Oracle监控EMCC深入使用-03（20240206）

数据库管理-第146期 最强Oracle监控EMCC深入使用-03（20240206）

数据库管理145期 2024-02-06 数据库管理-第146期 最强Oracle监控EMCC深入使用-03&#xff08;20240206&#xff09;1 概览2 性能中心3 性能中心-Exadata总结 数据库管理-第146期 最强Oracle监控EMCC深入使用-03&#xff08;20240206&#xff09; 作者&#xff1a;胖头鱼的鱼缸&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023