trie树(前缀树)

news/2024/4/19 16:31:02/

前缀树

  • 1. 前缀树的的介绍
  • 2.前缀树的实现
    • 2.1插入功能
    • 2.2删除功能
    • 2.3查找前缀和查找单词功能
    • 2.4 哈希表版本

1. 前缀树的的介绍

在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

2.前缀树的实现

如何实现一颗前缀树呢?这里有两种实现的方法,对应了不同的情况。

我们首先来定义一下前缀树的节点,我们让每一个根节点有两个值,一个为pass,一个为end,pass表示经过这个节点的次数,end表示走到叶子节点的次数(也就是这个单词出现的次数)。

我们先看看这棵树的结构。比如我们插入字符串{“aa”,“aaa”,“bba”,“ssba”},我们看看这颗树的结构。

在这里插入图片描述

现在我们模拟这个过程来写代码
先来定义好节点

struct TreeNode // 创建结点
{TreeNode *next[26];int end;int pass;TreeNode() // 初始化结点{end = 0;path = 0;for(int i=0;i<26;i++)next[i]=NULL;}
};

下面我们实现树的部分,我们就储存一个头节点和所需要的接口

class Trie
{
private:TreeNode* root;
public:Trie(){root = new TreeNode;}void insert_Node(string word); // 插入void Delete_Node(string word); // 删除int  search(string word); // 查找int prefixNumber(string word);//查找有多少以word作为前缀的单词
};

2.1插入功能

void Trie::insert_Node(string wrod)
{if (wrod == "") return;int idx = 0;TreeNode* node = root;root->pass++;for (int i = 0; i < wrod.size(); i++){idx = wrod[i] - 'a';if (node->next[idx]==nullptr)node->next[idx] = new TreeNode;node = node->next[idx];node->pass++;}node->end++;
}

2.2删除功能

//这个函数java的可以不用写,因为Java有JVM垃圾回收机制。
void Delete(TreeNode* node)
{if (node == NULL)return;for (int num = 0; num < 26; num++){if (node->next[num]){Delete(node->next[num]);}}delete(node);node=NULL;
}void Trie::Delete_Node(string word)
{if (!search(word))return;int index = 0;TreeNode* node = root;node->pass--;for (int i = 0; i < word.size(); i++){index = word[i] - 'a';if (--node->next[index]->pass == 0){// Java的直接将 node。next[index] = NULL  即可Delete(node->next[index]);node->next[index] = NULL;return;}node = node->next[index];}node->end--;
}

2.3查找前缀和查找单词功能

int Trie::prefixNumber(string word)
{if (word == "") return 0;int idx = 0;TreeNode* node = root;for (int i = 0; i < word.size(); i++){idx = word[i] - 'a';if (node->next[idx] == nullptr) return 0;node = node->next[idx];}return node->pass;
}
int Trie::search(string word)
{if (word == "") return 0;int idx = 0;TreeNode* node = root;for(int i=0;i<word.size();i++){ idx = word[i] - 'a';if (node->next[idx] == nullptr) return 0;node = node->next[idx];}return node->end;
}

2.4 哈希表版本

如何单词不只有26个小写字母,我们该如何去实现呢,我们可以通过哈希表去进行映射来实现。
只需要以ASIII作为key,代码稍微改动一下就可以了。

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;struct TreeNode
{int pass;int end;unordered_map<int, TreeNode*> next;TreeNode(){pass = 0;end = 0;}};class Trie
{
private:TreeNode* root;
public:Trie(){root = new TreeNode;}void insert_Node(string word); // 插入void Delete_Node(string word); // 删除int  search(string word); // 查找int prefixNumber(string word);//查找有多少以word作为前缀的单词
};void Trie::insert_Node(string wrod)
{if (wrod == "") return;int idx = 0;TreeNode* node = root;root->pass++;for (int i = 0; i < wrod.size(); i++){idx = (int)wrod[i];if (!node->next.count(idx)){node->next[idx] = new TreeNode;}node = node->next[idx];node->pass++;}node->end++;
}int Trie::search(string word)
{if (word == "") return 0;int idx = 0;TreeNode* node = root;for(int i=0;i<word.size();i++){ idx = (int)word[i];if (!node->next.count(idx)) return 0;node = node->next[idx];}return node->end;
}
//这个函数java的可以不用写,因为Java有JVM垃圾回收机制。
void Delete(TreeNode* node)
{if (node == NULL)return;for (int num = 0; num < 26; num++){if (node->next[num]){Delete(node->next[num]);}}delete(node);node = NULL;
}void Trie::Delete_Node(string word)
{if (!search(word))return;int index = 0;TreeNode* node = root;node->pass--;for (int i = 0; i < word.size(); i++){index = (int)word[i];if (--node->next[index]->pass == 0){// Java的直接将 node。next[index] = NULL  即可Delete(node->next[index]);node->next[index] = NULL;return;}node = node->next[index];}node->end--;
}int Trie::prefixNumber(string word)
{if (word == "") return 0;int idx = 0;TreeNode* node = root;for (int i = 0; i < word.size(); i++){idx = (int)word[i];if (!node->next.count(idx)) return 0;node = node->next[idx];}return node->pass;
}int main()
{Trie tr;tr.insert_Node("aad");tr.insert_Node("jjafp");tr.insert_Node("jjdafp");tr.insert_Node("jjdafp");tr.insert_Node("jjafp");tr.insert_Node("jjdap");cout << tr.search("jjdafp") << endl;cout << tr.prefixNumber("j") << endl;return 0;
}

http://www.ppmy.cn/news/1365080.html

相关文章

Stable Diffusion 模型分享:【Checkpoint】YesMix(动漫、2.5D)

本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四下载地址模型介绍 条目内容类型大模型基础模型SD 1.5来源

C语言第三十二弹---自定义类型:联合和枚举

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 目录 1、联合体 1.1、联合体类型的声明 1.2、联合体的特点 1.3、相同成员的结构体和联合体对比 1.4、联合体大小的计算 1.5、联合的⼀个练习 2、枚举类型 …

关于CSS常见选择器应用的基础教程

在网页开发中&#xff0c;CSS选择器是非常重要的一部分&#xff0c;它们用来指定你想要样式化的HTML元素。熟练掌握各种选择器的用法可以帮助你更有效地实现网页布局和设计。本文将介绍一些常见的CSS选择器&#xff0c;并演示它们的基本用法及应用场景。 一、元素选择器&#…

Android 接入指纹识别

接入指纹框架&#xff1a;https://github.com/Tencent/soter implementation com.github.Tencent.soter:soter-wrapper:2.0.91.Application中初始化 class IApplication : Application() {override fun onCreate() {super.onCreate()instance thisinitSort()}private fun in…

数仓项目6.0(二)数仓

中间的几步意义就在于&#xff0c;缓存中间处理数据样式&#xff0c;避免重复计算浪费算力 分层 ODS&#xff08;Operate Data Store&#xff09; Spark计算过程中&#xff0c;存在shuffle的操作&#xff0c;而shuffle会将计算过程一分为二&#xff0c;前一阶段不执行完&…

我的NPI项目之设备系统启动(八) -- Android14的GKI2.0开发步骤和注意事项

GKI是什么&#xff1f; Google为什么要推行GKI&#xff1f; GKI全称General Kernel Image。GKI在framework和kernel之间提供了标准接口&#xff0c;使得android OS能够轻松适配/维护/兼容不同的设备和linux kernel。 Google引入GKI的目的是将Framework和Kernel进一步的解耦。因…

IBM在闪存系统集成实时恶意软件I/O检测功能

IBM在其最新一代FlashCore Modules&#xff08;FCMs&#xff09;固件中集成了使用机器学习进行实时勒索软件和其他攻击检测的功能。这些FCMs是专用于IBM FlashSystem 5000和Storwize阵列的闪存驱动器&#xff0c;采用U.2外形尺寸及NVMe接口。现有的第三代FCMs分别提供4.8、9.6、…

连接未来:嵌入式系统在物联网时代的应用

连接未来&#xff1a;嵌入式系统在物联网时代的应用 随着物联网技术的不断发展&#xff0c;嵌入式系统在物联网时代扮演着至关重要的角色。嵌入式系统作为连接物理世界和数字世界的桥梁&#xff0c;为物联网的实现提供了技术支持和基础设施。以下将从几个方面探讨嵌入式系统在…

Rocky Linux 运维工具 Systemd

一、Systemd 的简介 Systemd是一个用于管理Linux系统启动进程和服务的系统和服务管理器&#xff0c;取代了传统的init系统。它提供了并行启动、依赖关系管理、动态加载服务文件等功能&#xff0c;成为现代Linux发行版中主流的初始化系统。 二、Systemd 的参数说明 [Unit] Des…

Linux设备模型(二) - kset/kobj/ktype APIs

一&#xff0c;kobject_init_and_add 1&#xff0c;kobject_init_and_add实现 /** * kobject_init_and_add() - Initialize a kobject structure and add it to * the kobject hierarchy. * kobj: pointer to the kobject to initialize * ktype: p…

来分析两道小题

一、源码 二、分析 首先它会接两个参数一个是id一个是ps&#xff0c;传递的话会包含一个flag.php&#xff0c;然后数据库连接&#xff0c;之后传递过滤&#xff0c;然后查询&#xff0c;如果查到了就会取id&#xff0c;取出来看是不是跟adog一样&#xff0c;如果是它告诉你账号…

备战蓝桥杯————k个一组反转单链表

k个反转单链表&#xff0c;顾名思义就是k个节点为一组进行反转&#xff0c;这是一道困难的题目&#xff0c;如何解答&#xff0c;可以在我们前面的反转链表中得到思路。 如何 K 个一组反转单链表 题目描述 给你链表的头节点 head &#xff0c;每 k 个节点一组进行翻转&#xf…

React引入css的几种方式以及应用

1.直接引入css文件 import "./parent.css" 2.引入css模块&#xff0c;定义文件名[组件名.module.css]&#xff1b;该方式可避免类名的重复&#xff0c;每个组件都有独立的作用域&#xff0c;避免了全局污染&#xff0c;保证了类名的唯一性 import styles from &qu…

300分钟吃透分布式缓存-15讲:如何深入理解、应用及扩展 Twemproxy?

Twemproxy 架构及应用 Twemproxy 是 Twitter 的一个开源架构&#xff0c;它是一个分片资源访问的代理组件。如下图所示&#xff0c;它可以封装资源池的分布及 hash 规则&#xff0c;解决后端部分节点异常后的探测和重连问题&#xff0c;让 client 访问尽可能简单&#xff0c;同…

vue3编写H5适配横竖屏

具体思路如下&#xff1a; 1、监听浏览器屏幕变化&#xff0c;通过监听屏幕宽高&#xff0c;辨别出是横屏&#xff0c;还是竖屏状态 在项目的起始根页面进行监听&#xff0c;我就是在App.vue文件下进行监听 代码如下&#xff1a; <template><RouterView /> <…

Mycat核心教程--Mycat 监控工具【四】

Mycat核心教程--Mycat 监控工具 九、Mycat 监控工具9.1.Mycat-web 简介9.2.Mycat-web 配置使用9.2.1.ZooKeeper 安装【上面有】9.2.2.Mycat-web 安装9.2.2.1.下载安装包9.2.2.2.安装包拷贝到Linux系统/opt目录下&#xff0c;并解压9.2.2.3.拷贝mycat-web文件夹到/usr/local目录…

LVS负载均衡服务器

简介: LVS (Linux Virtual Server):四层路由设备&#xff0c;是由中国人章文松研发的(阿里巴巴的副总裁)根据用户请求的IP与端口号实现将用户的请求分发至不同的主机。 工作原理: LVS工作在一台server上提供Directory(负载均衡器)的功能&#xff0c;本身并不提供服务&#xff…

s-table和columns初始化不完整,造成table文件的filter报错

问题 顺藤摸瓜找errorHandler.js文件 发现文件并没有什么问题 顺藤摸瓜找index.vue文件 首先找到报错的filter&#xff0c;发现与columnsSetting相关 找到columnsSetting发现等于columns 返回自己使用S-table组件的地方&#xff0c;发现columns初始化时仅初始化为ref()未表明…

【web】云导航项目部署及环境搭建(复杂)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、项目介绍1.1项目环境架构LNMP1.2项目代码说明 二、项目环境搭建2.1 Nginx安装2.2 php安装2.3 nginx配置和php配置2.3.1 修改nginx文件2.3.2 修改vim /etc/p…

状态模式(State Pattern)

定义 状态模式&#xff08;State Pattern&#xff09;是一种行为设计模式&#xff0c;它允许对象在其内部状态改变时改变其行为。这意味着&#xff0c;当对象的状态发生变化时&#xff0c;它的行为也会发生变化。状态模式特别适用于行为依赖于其状态的对象&#xff0c;而且当这…