说说你对数据结构-树的理解
对树 - 二叉搜索树的理解
二叉搜索树是一种常见的二叉树结构,它具有以下特点:
- 每个节点最多只有两个子节点,分别称为左子节点和右子节点;
- 对于任意节点,其左子树中的所有节点均小于该节点,其右子树中的所有节点均大于该节点;
- 对于每个节点,其左子树和右子树也都是二叉搜索树。
因此,二叉搜索树具有以下特性: - 高效的查找功能。由于所有节点按照大小顺序排列,我们可以通过比较查找目标与节点值的大小来决定是继续往左子树搜索还是往右子树搜索,从而实现快速的查找。查找操作的时间复杂度为 O(log n),其中 n 是二叉搜索树中节点数量。
- 高效的插入和删除功能。由于插入和删除节点时需要保持二叉搜索树的性质,我们可以通过递归地比较目标值与当前节点的值来找到合适的位置,并进行插入或删除操作。插入和删除操作的时间复杂度同样为 O(log n)。
需要注意的是,如果二叉搜索树的左子树或右子树过于极端,会导致树的深度过大,从而降低查找和操作的效率。
对树 - 平衡二叉树的理解
平衡二叉树是一种特殊的二叉搜索树,旨在解决普通二叉搜索树的性能问题。它通过限制左右子树的高度差不超过一个常数来保持树的平衡性。平衡二叉树的设计使得插入、删除和查找等操作的时间复杂度维持在较小的范围内。
其中,AVL树和红黑树是两种常见的平衡二叉树。
AVL树通过维护每个节点的平衡因子(左子树高度减去右子树高度)来实现自平衡,当平衡因子超过阈值时通过旋转操作调整树的结构。红黑树通过在每个节点上增加一个颜色属性(红色或黑色)来维持平衡,通过变换和重新着色操作来调整树的结构。
平衡二叉树的优点在于它可以保持树的高度相对较小,从而提高了数据的存储和检索效率。相比于普通的二叉搜索树,平衡二叉树的操作时间复杂度更加稳定,在最坏情况下也能达到O(log n)的复杂度。
树 - 红黑树的理解
红黑树是一种自平衡的二叉搜索树,它在普通二叉搜索树的基础上通过引入颜色属性和一些特定规则来维持树的平衡性。
红黑树的特性包括以下几点:
- 每个节点都被标记为红色或黑色。
- 根节点始终为黑色,这是确保整个树的平衡的起点。
- 叶子节点是特殊的空节点,标记为黑色。
- 没有两个相邻的红色节点,这样确保了没有连续的红色路径。
- 从任意节点到其每个叶子节点的简单路径上都包含相同数目的黑色节点,这就是所谓的黑色平衡,它确保了红黑树的整体高度相对平衡。
红黑树通过这些特性保持树的平衡,避免了最坏情况下的退化。它的插入、删除和查找操作具有稳定的时间复杂度,通常为O(log n),适用于需要高效的动态数据结构。
对树 - 哈夫曼树的理解
哈夫曼树是一种用于数据压缩的树形结构,通过构建最优二叉树来实现高效的编码和解码。
在构建哈夫曼树的过程中,首先需要统计待编码数据中每个字符的出现频率。然后,将每个字符及其频率创建为一个叶子节点,并将它们组成一个节点集合。
接着,从节点集合中选择权重最小的两个节点作为左右子节点,创建一个新的父节点。新的父节点的权重为两个子节点的权重之和。将新的父节点放回节点集合中,并重复这个过程,直到节点集合中只剩下一个节点,即哈夫曼树的根节点。
在哈夫曼树中,字符出现频率越高的节点越靠近树的根部,这样可以让频率高的字符拥有较短的编码,而频率低的字符拥有较长的编码。编码的方式是,从根节点开始,向左子树走路径加0,向右子树走路径加1。最终,每个叶子节点都有一个表示字符编码的二进制串。
哈夫曼树采用前缀编码,即任何一个字符的编码都不是另一个字符编码的前缀,使得解码过程能够唯一确定。用哈夫曼编码表示数据,可以有效地减小存储空间和提高传输效率。
对树 - 前缀树的理解
前缀树也被称为字典树,是一种用于高效存储和检索字符串的数据结构。
前缀树的基本思想是将每个字符串拆分成字符序列,然后使用树形结构进行存储。树的根节点为空,每个字符都对应着一个节点。从根节点到叶子节点的路径表示一个完整的字符串。
在构建前缀树时,将待存储的字符串逐个字符插入树的路径。如果某个字符在当前节点的子节点中不存在,则创建一个新的子节点,并将该字符放入子节点中。通过这样的方式,构建出的前缀树能够有效地存储大量的字符串,并且支持快速的插入和查找操作。
前缀树的一个重要特点是,每个节点存储的字符序列为从根节点到该节点的路径上的字符集合。这使得在树中查找以给定前缀开头的字符串非常高效。只需从根节点开始,按照给定前缀依次遍历子节点,直到遍历完前缀中的所有字符或者无法继续匹配为止。
前缀树的应用非常广泛。它可以用于实现自动补全功能,即根据用户输入的前缀快速匹配出可能的后续字符或单词。前缀树还可以用于搜索引擎中的关键词索引,以及字典和拼写检查等任务。
相关文章:

说说你对数据结构-树的理解
对树 - 二叉搜索树的理解 二叉搜索树是一种常见的二叉树结构,它具有以下特点: 每个节点最多只有两个子节点,分别称为左子节点和右子节点;对于任意节点,其左子树中的所有节点均小于该节点,其右子树中的所有…...

Docker实例
华子目录 docker实例1.为Ubuntu镜像添加ssh服务2.Docker安装mysql docker实例 1.为Ubuntu镜像添加ssh服务 (1)访问https://hub.docker.com,寻找合适的Ubuntu镜像 (2)拉取Ubuntu镜像 [rootserver ~]# docker pull ubuntu:latest latest: Pulling from library/ub…...

python基础——模块【模块的介绍,模块的导入,自定义模块,*和__all__,__name__和__main__】
📝前言: 这篇文章主要讲解一下python基础中的关于模块的导入: 1,模块的介绍 2,模块的导入方式 3,自定义模块 🎬个人简介:努力学习ing 📋个人专栏:C语言入门基…...

【HTML】标签学习(下.2)
(大家好哇,今天我们将继续来学习HTML(下.2)的相关知识,大家可以在评论区进行互动答疑哦~加油!💕) 目录 二.列表标签 2.1 无序列表(重点) 2.2有序列表(理解) 2.3 自定义列表(重点…...
os模块篇(十一)
文章目录 os.chdir(path)os.chmod(path, mode, *, dir_fdNone, follow_symlinksTrue)os.chown(path, uid, gid, *, dir_fdNone, follow_symlinksTrue)os.getcwd()os.getcwdb()os.lchflags(path, flags)os.lchmod(path, mode)os.lchown(path, uid, gid) os.chdir(path) os.chdi…...
编译amd 的 amdgpu 编译器
1,下载源码 git clone --recursive https://github.com/ROCm/llvm-project.git 2, 配置cmake cmake -G "Unix Makefiles" ../llvm \ -DLLVM_ENABLE_PROJECTS"clang;clang-tools-extra;compiler-rt" \ -DLLVM_BUILD_EXAMPLESON …...
github 多个账号共享ssh key 的设置方法
确认本机是否已有ssh key 首先确认自己系统内有没有 ssh key。 bash复制代码cd ~/.ssh ls *.pub # 列出所有公钥文件id_rsa.pub若有,确认使用当前 key 或者生成新 key,若没有,生成新 key。由于我需要登录两个帐号,所以在已经存在…...
dm8修改sysdba用户的密码
1 查看达梦数据库版本 SQL> select * from v$version;LINEID BANNER ---------- --------------------------------- 1 DM Database Server 64 V8 2 DB Version: 0x7000c 3 03134283904-20220630-163817-200052 …...

基于boost准标准库的搜索引擎项目
零 项目背景/原理/技术栈 1.介绍boost准标准库 2.项目实现效果 3.搜索引擎宏观架构图 这是一个基于Web的搜索服务架构 客户端-服务器模型:采用了经典的客户端-服务器模型,用户通过客户端与服务器交互,有助于集中管理和分散计算。简单的用户…...

语言模型进化史(下)
由于篇幅原因,本文分为上下两篇,上篇主要讲解语言模型从朴素语言模型到基于神经网络的语言模型,下篇主要讲解现代大语言模型以及基于指令微调的LLM。文章来源是:https://www.numind.ai/blog/what-are-large-language-models 四、现…...
设计模式之旅:工厂模式全方位解析
简介 设计模式中与工厂模式相关的主要有三种,它们分别是: 简单工厂模式(Simple Factory):这不是GoF(四人帮,设计模式的开创者)定义的标准模式,但被广泛认为是工厂模式的…...
大数据时代的生物信息学:挖掘生命数据,揭示生命奥秘
在当今科技日新月异的时代,大数据如同一座蕴藏无尽宝藏的矿山,而生物信息学则是那把锐利的探矿锤,精准有力地敲击着这座“生命之矿”,揭示出隐藏在其深处的生命奥秘。随着基因测序技术的飞速进步与广泛应用,生物医学领…...

微信小程序开发【从入门到精通】——页面导航
👨💻个人主页:开发者-曼亿点 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 曼亿点 原创 👨💻 收录于专栏:…...

嵌入式|蓝桥杯STM32G431(HAL库开发)——CT117E学习笔记15:PWM输出
系列文章目录 嵌入式|蓝桥杯STM32G431(HAL库开发)——CT117E学习笔记01:赛事介绍与硬件平台 嵌入式|蓝桥杯STM32G431(HAL库开发)——CT117E学习笔记02:开发环境安装 嵌入式|蓝桥杯STM32G431(…...

SQLite中的隔离(八)
返回:SQLite—系列文章目录 上一篇:SQLite版本3中的文件锁定和并发(七) 下一篇:SQLite 查询优化器概述(九) 数据库的“isolation”属性确定何时对 一个操作的数据库对其他并发操作可见。 数据库连接之…...

Zabbix6 - Centos7部署Grafana可视化图形监控系统配置手册手册
Zabbix6 - Centos7部署Grafana可视化图形监控系统配置手册手册 概述: Grafana是一个开源的数据可视化和监控平台。其特点: 1)丰富的可视化显示插件,包括热图、折线图、饼图,表格等; 2)支持多数据…...
Electron无边框自定义窗口拖动
最近使用了electron框架,发现如果自定义拖动是比较实用的;特别是定制化比较高的项目,如果单纯的使用-webkit-app-region: drag;会让鼠标事件无法触发; 过程中发现问题: 1.windows缩放不是100%后设置偏移界面会缩放,感觉像吹起的气…...
vue3+echarts:echarts地图打点显示的样式
colorStops是打点的颜色和呼吸灯、label为show是打点是否显示数据、rich里cnNum是自定义的过滤模板用来改写显示数据的样式 series: [{type: "effectScatter",coordinateSystem: "geo",rippleEffect: {brushType: "stroke",},showEffectOn: &quo…...
vue3从精通到入门7:ref系列
Vue 3 的 Ref 是一个集合,包括多个与响应式引用相关的功能,这些功能共同构成了 Vue 3 响应式系统的重要组成部分。以下是更全面的介绍: 1.ref ref 接受一个内部值并返回一个响应式且可变的 ref 对象。这个对象具有一个 .value 属性…...

灵动翻译音频文件字幕提取及翻译;剪映视频添加字幕
参考:视频音频下载工具 https://tuberipper.com/21/save/mp3 1、灵动翻译音频文件字幕提取及翻译 灵动翻译可以直接chorme浏览器插件安装: 点击使用,可以上传音频文件 上传后自动翻译,然后点击译文即可翻译成中文,…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...