每日学习一个数据结构-Trie树(字典树)

文章目录

      • 定义
      • 节点结构
      • 根节点
      • 插入操作
      • 查找操作
      • 删除操作
      • 特点
      • 应用
      • 示例

“Trie”树,又称为前缀树或字典树,是一种专门用于存储字符串的数据结构。它在许多应用程序中都非常有用,特别是在那些需要高效查找、插入和删除字符串的应用场景中。下面是对 Trie 树的详细说明:

定义

Trie 树是一种有序树,用于存储字符串,其中每个节点都代表输入字符串的一个字符。从根节点到任意一个叶子节点的路径上所包含的字符序列构成了一个字符串。
字典树

节点结构

每个节点通常包含以下部分:

  • 字符:代表该节点对应的字符。
  • 子节点引用:一个指向其子节点的数组或哈希表,数组或哈希表的索引通常是字符集中的字符。例如,如果存储的是小写字母组成的字符串,那么数组大小为26。
  • 标志位:表示该节点是否是一个字符串的结尾。有时候也会附加其他信息,如该字符串的频次等。

根节点

根节点通常不包含任何字符信息,它是一个虚拟节点,用于连接所有的字符串的第一个字符。

插入操作

当插入一个新的字符串时,会从根节点开始,沿着字符路径向下寻找。如果路径上的某个字符已经存在,则继续沿着该路径;如果某个字符不存在,则创建一个新的节点,并将该字符作为新节点的内容。

查找操作

查找一个字符串时,同样从根节点开始,沿着字符路径向下遍历。如果能够一直遍历到字符串的最后一个字符,并且该字符所在节点标记为字符串结尾,则表示找到了该字符串。

删除操作

删除一个字符串时,需要从根节点开始,沿着字符路径向下寻找。如果找到了字符串的最后一个字符,并且该字符所在的节点没有其他子节点,则可以删除该节点及其以上的无用节点。如果该节点还有其他子节点,则仅将该节点标记为非字符串结尾。

特点

  • 高效查找:Trie 树的时间复杂度为 O(L),L 是要查找的字符串的长度。这是因为每次查找都沿着字符路径进行一次比较。
  • 节省空间:共享公共前缀的字符串只需存储一次前缀,这使得 Trie 树在存储大量字符串时更加节省空间。
  • 方便排序:因为 Trie 树是按照前缀进行存储的,所以可以方便地对字符串进行排序。

应用

  • 自动补全:搜索引擎、文本编辑器等工具中的自动补全功能。
  • 拼写检查:用于检查输入的单词是否存在于词典中。
  • IP 路由:用于查找最长前缀匹配,例如在路由器的查找表中。
  • 词频统计:用于统计文本中单词出现的次数。

示例

假设我们要构建一个 Trie 树来存储字符串集合 {“cat”, “car”, “dog”, “caterpillar”}:

  1. 插入 “cat”:

    • 根 -> c -> a -> t(结束)
  2. 插入 “car”:

    • 根 -> c -> a -> r(结束)
  3. 插入 “dog”:

    • 根 -> d -> o -> g(结束)
  4. 插入 “caterpillar”:

    • 继续扩展根 -> c -> a -> t(非结束)-> e -> r -> p -> i -> l -> l -> a -> r(结束)

最终的 Trie 树看起来像这样:

(root)||___ 'c' : {'a' : {'t' : {'': {}} // cat, caterpillar'r' : {'': {}} // car},'d' : {'o' : {'g' : {'': {}}}} // dog}

在这个 Trie 树中,“caterpillar”和“cat”共享相同的前缀“cat”,而“car”和“cat”也共享相同的前缀“ca”。这种共享前缀的方式使得 Trie 树成为一种高效的字符串存储结构。

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

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

相关文章

[项目:微服务即时通讯系统客户端(基于C++QT)]三,左侧界面搭建

三,左侧界面搭建 一,导入 先把MainWidget类做成“单例类” 采用的是单例模式,让某一个类,在指定进程中只有唯一的实例 先看一下MainWidget的框架 QWidget//这部分是头文件保护宏,确保该头文件只被包含一次&#x…

低级编程语言和高级编程语言

一.区分低级编程语言和高级编程语言的方法 1.低级编程语言 低级编程语言,并不是简单的编程语言,而是写起来很费事的编程语言,如所有编程语言的"祖宗":汇编语言,写起来极其麻烦,说不定一个 int a1; 它就得写好几行,甚至十几行 这样麻烦的编程语言为什么还没消失那,因…

基于微信小程序的家教信息管理系统的设计与实现(论文+源码)_kaic

摘 要 随着互联网时代的来临,使得传统的家教模式已不复存在,亟需一种方便、快捷的在线教学平台。因此,利用Java语言作为支撑和MySQL数据库存储数据,结合微信小程序的便利性,为用户开发出了一个更加人性化、方便的家庭…

超越sora,最新文生视频CogVideoX-5b模型分享

CogVideoX-5B是由智谱 AI 开源的一款先进的文本到视频生成模型,它是 CogVideoX 系列中的更大尺寸版本,旨在提供更高质量的视频生成效果。 CogVideoX-5B 采用了 3D 因果变分自编码器(3D causal VAE)技术,通过在空间和时…

ps证件照蓝底换白底

ps证件照蓝底换白底 1、打开 Photoshop,导入需要处理的照片。 2、左侧工具栏中选择“魔棒工具”,点击证件照的背景区域进行选择。 3、使用快捷键 Shift F5 或者从顶部菜单选择“编辑” -> “填充”,在弹出的对话框中选择“填充内容”中…

【全网最全】2024年华为杯研究生数学建模A题成品论文

您的点赞收藏是我继续更新的最大动力! 一定要点击如下的卡片,那是获取资料的入口! 点击链接获取群聊【2024华为杯研赛资料汇总】:https://qm.qq.com/q/yB6JDUTaWAhttps://qm.qq.com/q/yB6JDUTaWAA题第一问是关于如何建立一个低复杂度模型&a…

【M-LOAM学习】

M-LOAM(INITIALIZATION) Article Analysis Scan-Based Motion Estimation 通过在consecutive frame (each LiDAR)(因为omp parallel)中寻找correspondences然后通过最小化所有考虑feature之间residual error的transformation between frame to frame 针…

通过解预测和机器学习促进蚁群优化

文章目录 Abstract1. Introduction2. Background and related work2.1 定向越野问题2.2 ACO优化3. 基于预测的蚁群优化算法3.1 构建训练集3.2 训练与解预测3.3 将预测解融入蚁群优化Abstract ML - ACO 算法的第一阶段,使用一组已知最优解的小定向越野问题实例训练一个 ML 模型…

tornado

Tornado通过使用非阻塞网络1/0,可以扩展到数以万计的开放链接,非常适合 长时间轮询,WebSockets和其他需要与每个用户建立长期连接的应用程序。 特点 注重性能优越,速度快解决高并发异步非阻塞websockets 长连接内嵌了HTTP服务器…

Linux 一些快捷键使用操作技巧

ctrl c : 强制停止 如图仅输入tail命令时程序会卡住,这时就需要强制停止 ctrl d : 退出或者登出 history : 查看历史输入命令 !命令 :自动执行上一次匹配前缀的命令 (注意不要用这个命令执行太过久远的,容易执行错误…

AWS 管理控制台

目录 控制台主页 AWS 账户信息 AWS 区域 AWS 服务选择器 AWS 搜索 AWS CloudShell AWS 控制面板小部件 控制台主页 注册新的 AWS 账户并登录后,您将看到控制台控制面板。这是与各种 AWS 服务以及其他重要控制台组件进行交互的起点。控制面板由页面顶部的导航…

C语言 | Leetcode C语言题解之第423题从英文中重建数字

题目&#xff1a; 题解&#xff1a; char * originalDigits(char * s) {int lenstrlen(s);int arr[26]{0},num[10]{0},cot0;for(int i 0; i < len; i)arr[s[i] - a];num[0] arr[z-a];num[2] arr[w-a];num[4] arr[u-a];num[6] arr[x-a];num[8] arr[g-a];num[1] arr[o…

nginx upstream转发连接错误情况研究

本次测试用到3台服务器&#xff1a; 192.168.10.115&#xff1a;转发服务器A 192.168.10.209&#xff1a;upstream下服务器1 192.168.10.210&#xff1a;upstream下服务器2 1台客户端&#xff1a;192.168.10.112 服务器A中nginx主要配置如下&#xff1a; log_format main…

双向链表:实现、操作与分析【算法 17】

双向链表&#xff1a;实现、操作与分析 引言 双向链表&#xff08;Doubly Linked List&#xff09;是链表数据结构的一种重要形式&#xff0c;它允许节点从两个方向进行遍历。与单向链表相比&#xff0c;双向链表中的每个节点不仅包含指向下一个节点的指针&#xff08;或引用&…

C语言 | Leetcode C语言题解之第429题N叉树的层序遍历

题目&#xff1a; 题解&#xff1a; #define MAX_LEVE_SIZE 1000 #define MAX_NODE_SIZE 10000int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {int ** ans (int **)malloc(sizeof(int *) * MAX_LEVE_SIZE);*returnColumnSizes (int *)mal…

旋转机械故障数据集 全网首发

旋转机械故障 数据集 11G资料 泵、齿轮箱、电机、流量、液压系统、轴承(西储大学、辛辛那提大学、FEMTO、MOSFET)、PHM08挑战数据集、我闪发动机降级模拟数据集、铣床等 旋转机械故障数据集 数据集描述 该数据集是一个综合性的旋转机械故障检测和诊断数据集&#xff0c;旨在…

【QT】系统-下

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;QT 目录 &#x1f449;&#x1f3fb;QTheadrun() &#x1f449;&#x1f3fb;QMutex&#x1f449;&#x1f3fb;QWaitCondition&#x1f449;&#x1f3fb;Q…

C/C++内存管理 ——

目录 五、C/C内存管理 1、C/C内存分布 2、C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free 3、C内存管理方式 1.new/delete操作内置类型 2.new和delete操作自定义类型 4、operator new与operator delete函数 5、new和delete的实现原理 1.内置类…

分布式事务详细笔记:什么是分布式事务--Seata--XA模式--AT模式

目录 1.分布式事务 1.1.什么是分布式事务 1.2.认识Seata 1.3.部署TC服务 1.3.1.准备数据库表 1.3.2.准备配置文件 1.3.3.Docker部署 1.4.微服务集成Seata 1.4.1.引入依赖 1.4.2.改造配置 1.4.3.添加数据库表 1.5.XA模式 1.5.1.两阶段提交 1.5.2.Seata的XA模型 1…

网络原理 HTTP与HTTPS协议

博主主页: 码农派大星. 数据结构专栏:Java数据结构 数据库专栏:MySQL数据库 JavaEE专栏:JavaEE 关注博主带你了解更多计算机网络知识 目录 1.HTTP概念 2.HTTP报文格式 3.HTTP请求 1.首行 1.1URL 1.2 GET⽅法 1.3 POST⽅法 1.4 其他⽅法 2.请求头&#xff08;head…