每日学习一个数据结构-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.xdnf.cn/news/148361.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

网络通信——路由器、交换机、集线器(HUB)

注意:传输层,应用层没有网路设备 一.路由器(网络层设备) 1.分割广播域 2.一个接口就是一个广播域 3.一般接口位4,8,12。 4.数据转发 (由路由表转发数据) 5.根据路由表来进行路径选…

MySQL连接查询解析与性能优化成本

文章目录 一、连接查询1.连接查询基础1. INNER JOIN内连接2. LEFT JOIN (或 LEFT OUTER JOIN)左外连接3. RIGHT JOIN (或 RIGHT OUTER JOIN)右外连接4. FULL OUTER JOIN 2.连接查询的两种过滤条件3.连接的原理 二、性能优化成本1.基于成本的优化2.调节成本常数(1)mysql.server_…

【最基础最直观的排序 —— 冒泡排序算法】

最基础最直观的排序 —— 冒泡排序算法 冒泡排序(Bubble Sort)是一种计算机科学领域的较简单的排序算法,属于交换排序。其基本思想是在待排序的一组数中,将相邻的两个数进行比较,若前面的数比后面的数大就交换两数&am…

【C++】继承(上)

个人主页~ 继承 一、继承的概念以及定义1、继承的概念2、继承的定义(1)定义格式(2)继承基类成员访问方式的变化 二、基类和派生类对象赋值转换三、继承中的作用域 一、继承的概念以及定义 1、继承的概念 继承机制是面向对象程序…

Java集合(Map篇)

一.Map a.使用Map i.键值(key-value)映射表的数据结构,能高效通过key快速查找value(元素)。 ii.Map是一个接口,最常用的实现类是HashMap。 iii.重复放入k-v不会有问题,但是一个…

周邦彦,北宋文坛的独特乐章

周邦彦,字美成,号清真居士,生于北宋仁宗嘉祐元年(公元1056年),卒于北宋徽宗宣和三年(公元1121年),享年65岁。他是宋代“婉约派”词人的代表之一,与柳永、晏几…

java日志框架之Log4j

文章目录 一、Log4j简介二、Log4j组件介绍1、Loggers (日志记录器)2、Appenders(输出控制器)3、Layout(日志格式化器) 三、Log4j快速入门四、Log4j自定义配置文件输出日志1、输出到控制台2、输出到文件3、输出到数据库 五、Log4j自…

comp 9517 Computer Vision week1

本篇博文为课堂笔记,因为英语不好现在不得不课下看录像复习一遍 颜色模型 RGBHSVYCbCrL\*a\*b RGB 有红、绿、蓝三通道 problem:不同通道之间高度相关,包含同种信息 如果想要紧凑的(as compactly as possible)存储图像RGB不合适,…

[DRAM Test]内存测试维修工具大全

目录 1、《HCI MemTest, RunMemtestPro》 2、《MEMTEST64》 3、AIDA64稳定性测试 4、《MEMTEST86》与《MEMTEST86》 5、Windows Memory Diagnostic Tool(微软内存诊断工具) 6、《RAM STRESS TEST》 7、《AMT64和AMT128》 8、《DocMemory》 9、《RAMFIX V110516B》 10…

word如何快速打开文档中的网址超链接?

1、鼠标放在文档中超链接上: 2、然后左手按住【CTRL】键,之后鼠标光标会变成一个手形, 然后右手,点击鼠标左键,即可快速使用电脑当前设置的默认浏览器打开并跳转到网址:

力扣反转链表系列【25. K 个一组翻转链表】——由易到难,一次刷通!!!

力扣《反转链表》系列文章目录 刷题次序,由易到难,一次刷通!!! 题目题解206. 反转链表反转链表的全部 题解192. 反转链表 II反转链表的指定段 题解224. 两两交换链表中的节点两个一组反转链表 题解325. K 个一组翻转…

回溯算法(递归+回退)——1基础理论

文章目录 一、概念二、算法原理三、代码模板四、例题实现1、参数确定2、确定终止条件3、for循环的构建4、AC代码JavaC 5、剪枝优化理论:代码编写方式:JavaC 一、概念 回溯算法(BackTracking)一种通过递归,实现暴力枚举…

Python | Leetcode Python题解之第429题N叉树的层序遍历

题目: 题解: class Solution:def levelOrder(self, root: Node) -> List[List[int]]:if not root:return []ans list()q deque([root])while q:cnt len(q)level list()for _ in range(cnt):cur q.popleft()level.append(cur.val)for child in c…

【数据结构与算法】LeetCode:二分查找

文章目录 二分查找二分查找搜索插入位置 (Hot 100)x 的平方根搜索二维矩阵(Hot 100)在排序数组中查找元素的第一个和最后一个位置 (Hot 100)搜索旋转排序数组 (Hot 100)寻找旋转排序…

postman工具

postman是什么接口工具。接口是什么api(俗称应用编程接口,简称接口);也就是程序(服务端程序)与程序(客户端程序)之间的通信方式。例如模仿服务端发送请求到客户端例如模仿客户端发送…

情指行一体化平台建设方案和必要性-———未来之窗行业应用跨平台架构

一、平台建设必要性 以下是情指行一体化平台搭建的一些必要性: 1. 提高响应速度 - 实现情报、指挥和行动的快速协同,大大缩短从信息获取到决策执行的时间,提高对紧急情况和突发事件的响应效率。 2. 优化资源配置 - 整合各类资源信…

没有 Microsoft Wi-Fi Direct Virtual Adapter #2 导致无法打开热点

我的环境 电脑打不开热点 系统 win11 64位 品牌 hp 笔记本电脑 解决方法: https://answers.microsoft.com/zh-hans/windows/forum/all/%E7%A7%BB%E5%8A%A8%E7%83%AD%E7%82%B9%E6%97%A0/9285620a-71d9-4671-b125-4cd607b6371a 解决 😓 扫描一下设…

Codeforces Round 969 (Div. 1) C. Eri and Expanded Sets(线段树维护差分数组gcd+双指针+尺取)

题目 转化一下题意就是&#xff0c; 给定一个n(n<4e5)&#xff0c;代表数组a的长度&#xff0c; 求有多少区间&#xff0c;满足区间内两两差分后得到的新数组的gcd∈{0,1} 实际t(t<1e4)组样例&#xff0c;保证sumn不超过4e5 思路来源 乱搞acjiangly代码 题解 一个…

摆脱困境并在 Android 手机上取回删除照片的所有解决方案

没有什么比不小心从 Android 智能手机中删除所有照片更糟糕的了。这样&#xff0c;除非您在重置之前已经备份了数据&#xff0c;否则您的所有照片都会消失。如果您忘记备份照片&#xff0c;您仍然可以按照一些简单的技术在 Android 设备上恢复已删除的照片。 您的 Android 智能…

【漏洞复现】用友 NC-Cloud queryStaffByName Sql注入漏洞

免责声明&#xff1a; 本文内容旨在提供有关特定漏洞或安全漏洞的信息&#xff0c;以帮助用户更好地了解可能存在的风险。公布此类信息的目的在于促进网络安全意识和技术进步&#xff0c;并非出于任何恶意目的。阅读者应该明白&#xff0c;在利用本文提到的漏洞信息或进行相关测…