数据结构与算法-前缀树

数据结构与算法-前缀树详解

  • 1 何为前缀树
  • 2 前缀树的代码表示及相关操作

 

1 何为前缀树

 
前缀树 又称之为字典树,是一种多路查找树,多路树形结构,是哈希树的变种,和hash效率有一拼,是一种用于快速检索的多叉树结构。

性质:不同字符串的相同前缀只保存一份。

操作:查找,插入,删除

例如 字符数组
[“abc”,“bck”,“abd”,“ace”]
构建成一颗前缀树


 

2 前缀树的代码表示及相关操作

 

 

前缀树中的节点

 

coding

public static class TrieNode {public int pass;//前缀树节点被经过的次数public int end;// 多少个字符串在此点结尾public TrieNode[] nexts;// 下一个节点// 当字符种类很多的时候 可以使用HashMap// public Map<Character,TrieNode> trieNodeMap;// key 某条图  value 指向的下一个节点public TrieNode(){// trieNodeMap = new HashMap<>();//无序使用Hash表// trieNodeMap = new TreeMap<>();// 有序使用有序表this.pass = 0;this.end = 0;nexts = new TrieNode[26];}
}

 

前缀树代码表示及相关操作

 

public static class Trie {private TrieNode root;//头结点public Trie() {this.root = new TrieNode();}/*** 将字符串word加入到前缀树中** @param word*/public void insert(String word) {if (word == null) {return;}char[] chars = word.toCharArray();TrieNode node = root;node.pass++;int index = 0;// 从左往右遍历字符串for (int i = 0; i < chars.length; ++i) {// 由字符计算得出 该走哪条路index = chars[i] - 'a';//如果没有此字符的路 则新建if (node.nexts[index] == null) {node.nexts[index] = new TrieNode();}//来到下一个节点node = node.nexts[index];node.pass++;}node.end++;}/*** @param word* @return 字符串在前缀树中加入过几次*/public int search(String word) {if (word == null) {return 0;}// 临时前缀树节点 用于遍历前缀树TrieNode node = root;char[] chars = word.toCharArray();int index = 0;for (int i = 0; i < chars.length; ++i) {index = chars[i] - 'a';// 没有通往当前字符串的路 则说明没有加入过这个字符串 直接返回 0if (node.nexts[index] == null) {return 0;}// 下一个节点node = node.nexts[index];}// 所有字符的路都有  则返回最后一个节点的 end 值return node.end;}/*** @param pre* @return 有多少个字符串是以 pre开头的*/public int prefixNumber(String pre) {if (pre == null) {return 0;}TrieNode node = root;int index = 0;char[] chars = pre.toCharArray();for (int i = 0; i < chars.length; ++i) {index = chars[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];}return node.pass;}/*** 删除前缀树中的字符串word** @param word*/public void delete(String word) {if (search(word) != 0) { // 前缀树中存在字符串再删除char[] chars = word.toCharArray();TrieNode node = root;node.pass--;int index = 0;// 遍历每一个节点 将节点的pass值减 1for (int i = 0; i < chars.length; ++i) {index = chars[i] - 'a';if (--node.nexts[index].pass == 0) {node.nexts[index] = null;return;}node = node.nexts[index];}node.end--;}}
}

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

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

相关文章

力扣 -- 5. 最长回文子串

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:string longestPalindrome(string s) {int ns.size();vector<vector<bool>> dp(n,vector<bool>(n));//最长回文串的起始位置int start0;//最长回文串的长度int len0;for(int in-1;i>…

一道经典的指针笔试题!!!!

文章目录 写在前面1. 笔试题代码2. 代码解释3. 代码执行运行结果总结 写在前面 本篇文章讲解了一道关于指针和数组的经典笔试题。 前两篇关于指针和数组的讲解&#xff0c;链接如下&#xff1a; 详解C语言指针&#xff08;一&#xff09; 详解C语言指针&#xff08;二&#xf…

紧固行业内卷严重,张友君的飞沃科技能独善其身吗?

文&#xff5c;新熔财经 作者&#xff5c;文泽 “历经转折”的飞沃科技(301232.SZ)于今年6月&#xff0c;登陆资本市场。 公开资料显示&#xff0c;飞沃科技主要从事风电类高强度紧固件业务&#xff0c;主要产品包括预埋螺套、整机螺栓、锚栓组件。公司的实际控制人是张友君…

端口隔离 MAC地址安全配置

二、知识点 目前网络中以太网技术的应用非常广泛。然而&#xff0c;各种网络攻击的存在&#xff08;例如针对ARP、DHCP等协议的攻击&#xff09;&#xff0c;不仅造成了网络合法用户无法正常访问网络资源&#xff0c;而且对网络信息安全构成严重威胁&#xff0c;因此以太网交…

美容美甲小程序商城的作用是什么

美容院往往有很高需求&#xff0c;女性悦己经济崛起&#xff0c;加之爱美化程度提升&#xff0c;无论线下环境还是线上互联网信息冲击&#xff0c;美容服务、化妆产品等市场规格一直稳增不减。 通过【雨科】平台制作美容美甲商城&#xff0c;售卖相关服务/产品&#xff0c;模块…

【多级缓存】

文章目录 1. JVM进程缓存2. Lua语法3. 实现多级缓存3.1 反向代理流程3.2 OpenResty快速入门 4. 查询Tomcat4.1 发送http请求的API4.2 封装http工具4.3 基于ID负载均衡4.4 流程小结 5. Redis缓存查询5.1 实现Redis查询 6. Nginx本地缓存6.1 本地缓存API6.2 实现本地缓存查询 7. …

一文教你如何快速备考云计算HCIE 3.0 !

大家好&#xff0c;在誉天实验辅导老师的耐心帮助下&#xff0c;本人在9月21日的云计算HCIE 3.0考试已顺利通过&#xff0c;很高兴有这个机会给大家分享备考的经历&#xff0c;希望对还在备考的同学能有一定的帮助。 备考准备 在云计算HCIE3.0的课程学习结束之后&#xff0c;就…

Flink--8、时间语义、水位线(事件和窗口、水位线和窗口的工作原理、生产水位线、水位线的传递、迟到数据的处理)

星光下的赶路人star的个人主页 将自己生命力展开的人&#xff0c;他的存在&#xff0c;对别人就是愈疗 文章目录 1、时间语义1.1 Flink中的时间语义1.2 哪种时间语义更重要 2、水位线&#xff08;Watermark&#xff09;2.1 事件时间和窗口2.2 什么是水位线1.3 水位线和窗口的工…

zabbix监控,zabbix部署

目录 zabbix监控 zabbix概述 zabbix 监控原理 zabbix 6.0功能组件 1、Zabbix Server 2、数据库 3.、Web 界面 4、Zabbix Agent 5、Zabbix Proxy 6、Java Gateway Zabbix部署 部署 zabbix 服务端 zabbix的客户端部署 自我监控 添加zabbix的其他客户端主机 zabbix…

React核心原理与实际开发

学习目标 React是啥&#xff1f; 官方定义&#xff1a;将前端请求获取到的数据渲染为HTML视图的JavaScript库。 一、React入门 1、React项目创建 直接创建react&#xff0c;使用初始化会创建package.json npm init -y再安装 2、React基本使用 使用纯JS创建ReactDOM&#…

项目_数据可视化| 折线图.散点图.随机漫步

安装matplotlib 在正式开始编写程序之前&#xff0c;需要先安装pip、matplotlib模块&#xff0c;苹果系统的安装问题在之前的文章中有相关介绍内容&#xff0c;如果pycharm运行模块报错&#xff0c;可以再次检查是否版本兼容问题。 绘制折线图 调用subplot&#xff08;&#x…

C++设计模式-单件(Singleton)

目录 C设计模式-单件&#xff08;Singleton&#xff09; 一、意图 二、适用性 三、结构 四、参与者 五、代码 C设计模式-单件&#xff08;Singleton&#xff09; 一、意图 保证一个类仅有一个实例&#xff0c;并提供一个访问它的全局访问点。 二、适用性 当类只能有一…

机器学习 不均衡数据采样方法:imblearn 库的使用

✅作者简介&#xff1a;人工智能专业本科在读&#xff0c;喜欢计算机与编程&#xff0c;写博客记录自己的学习历程。 &#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&…

BigDecimal使用方法

文章目录 引入BigDecimaBigDecima的使用舍入模式updownCEILINGFLOORhalf_UPhalf_UP BigDecimal存储原理总结 引入 知识引入:如下图 0.266小数部分二进制需要55位存储,如果我们double接收那么将丢掉最后三位,所以我们在代码中进行小鼠的加减运算结果有时候并不是我们想要的 Bi…

如何实现chatGPT批量问答,不用token

3分钟&#xff0c;教你做个GPT批量问答还不用token | 有源码 解压压缩包&#xff1b;在Pycharm打开这个文件夹 执行 pip install undetected_chromedriver 和 pip install selenium 执行第1到63行代码&#xff0c;后台会自动打开浏览器&#xff0c;需要手动登录账号和点掉系…

Visual Studio自定义模板参数、备注

模板路径&#xff1a; VS2022 x64&#xff1a;C:\Program Files\Microsoft Visual Studio\2022\Enterprise\Common7\IDE\ItemTemplatesVS2022 x86&#xff1a;C:\Program Files (x86)\Microsoft Visual Studio\2022\Enterprise\Common7\IDE\ItemTemplates 一、声明和启用模板…

想升级macOS Big Sur,但是MacBook内存空间不够该怎么办?

随着使用时间的增长&#xff0c;我们会发现Mac电脑的存储空间越来越少&#xff0c;这时候我们就需要对Mac电脑进行清理&#xff0c;以释放更多的存储空间。那么&#xff0c;Mac空间不足怎么解决呢&#xff1f; 1.清理垃圾文件 Mac空间不足怎么解决&#xff1f;首先要做的就是清…

Tomcat服务器下载、安装、配置环境变量教程(超详细)

请先配置安装好Java的环境&#xff0c;若没有安装&#xff0c;请参照如下博客上的步骤进行安装&#xff01; 安装Java环境教程Windows配置Java环境变量(下载、安装、配置环境)_第三女神程忆难的博客-CSDN博客 Tomcat部署Web项目&#xff08;一&#xff09;内嵌 Tomcat部署网站…

力扣 -- 516. 最长回文子序列

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:int longestPalindromeSubseq(string s) {int ns.size();vector<vector<int>> dp(n,vector<int>(n));//记得从下往上填表for(int in-1;i>0;i--){//记得i是小于等于j的for(int ji;j&l…

vscode 乱码解决

windows 10 系统 vs code 编译运行和调试 C/C_vscode windows编译_雪的期许的博客-CSDN博客 VS Code默认文件编码时UTF-8&#xff0c;这对大多数情况是没有问题的&#xff0c;却偏偏对C/C有问题。如果以UTF-8编码保存C/C代码&#xff0c;那么只能输出英文&#xff0c;另外使用…