数据结构(6)

2-3查找树

2-结点:含有一个键(及其对应的值)和两条链,左链接指向2-3树中的键都小于该结点,右链接指向的2-3树中的键都大于该结点。

3-结点:含有两个键(及其对应的值)和三条链,左链接指向的2-3树中的键都小于该结点,中链接指向的2-3树中的键都位于该结点的两个键之间,右链接指向的2-3树中的键都大于该结点。

 查找:判断一个键是否在树中,先和根节点的键比较,如果相等,查找命中,如果不同,根据比较结果,在其子树中继续查找。还是空连接,查找未命中。

插入:

1.向2-结点插入:首先进行查找,将结点挂载未找到的结点上,如果未找到的结点是一个2-结点,将新元素放到里面变成3-结点。

2.向3-结点插入:将元素放入3-节点,变成4-结点,将4-结点中间元素提升,小于中间元素作为左节点,大于中间元素作为右结点。树的高度加1。

3.向父节点为2-结点,子结点为3-结点中插入:将元素插入3-结点中,变成临时的4-结点。将结点中的中间元素提升到2-结点中,父节点从2-结点变成3-结点,将左右元素挂载到适当的位置。

4.向父子结点为3-结点中插入:将元素插入子结点3-结点中,变成临时的4-结点。提升中间元素将父节点从3-结点变成4-结点,将左右元素放到适当位置。将父节点中的中间元素提升,直到遇到一个父节点是2-结点,将其变成3-结点为止,就可以了。

5.当插入时,所有结点都是3-结点时,将根节点变成一个临时4-结点,将根节点拆分成两个2-结点。树高度+1.

性质:

1.任意空链接到根结点的路径长度都是相等的。
2. 4-结点变换为3-结点时,树的高度不会发生变化,只有当根结点是临时的4-结点,分解根结点时,树高+1。
3. 2-3树与普通二叉查找树最大的区别在于,普通的二叉查找树是自顶向下生长,而2-3树是自底向上生长。        

直接实现2-3查找树较为复杂,但是其概念有利于红黑树、B树、B+树。

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

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

相关文章

什么是JVM ?

目录 一、JVM 简介 1.1 JVM 发展史 1.Sun Classic VM 2.Exact VM 3.HotSpot VM 4.JRockit 5.J9 JVM 6.Taobao JVM(国产研发) 1.2 JVM 和《Java虚拟机规范》 二、 JVM 运行流程 JVM 执行流程 三、JVM 运行时数据区 3.1 堆(线程共享…

【TypeScript】声明文件

在 TypeScript 中,声明文件(Declaration Files)用于描述已有 JavaScript 代码库的类型信息,以便在 TypeScript 项目中使用这些代码库时获得类型支持。 当你在 TypeScript 项目中引用外部 JavaScript 模块或库时,可能会…

【开发】tips:视频汇聚/视频云存储/视频监控管理平台EasyCVR如何提升网络稳定

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等,以及支持厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…

字节跳动 从需求到上线全流程 软件工程流程 需求评估 MVP

走进后端开发流程 整个课程会带大家先从理论出发,思考为什么有流程 大家以后工作的团队可能不一样,那么不同的团队也会有不同的流程,这背后的逻辑是什么 然后会带大家按照走一遍从需求到上线的全流程,告诉大家在流程的每个阶段&am…

iOS 分别对一张图的局部进行磨砂,拼接起来不能贴合

效果图 需求,由于视图层级的原因,需要对图片分开进行磨砂, 然后组合在一起 如图,上下两部分,上下两个UIImageVIew大小相同,都是和图片同样的大小,只是上面的UIimageVIew 只展示上半部份 &#…

flutter TARGET_SDK_VERSION和android 13

config.gradle ext{SDK_VERSION 33MIN_SDK_VERSION 23TARGET_SDK_VERSION 33COMPILE_SDK_VERSION SDK_VERSIONBUILD_TOOL_VERSION "33.0.0"//兼容库版本SUPPORT_LIB_VERSION "33.0.0"}app/build.gradle里面的 defaultConfig {// TODO: Specify your…

VMWare Workstation 17 Pro 网络设置 桥接模式 网络地址转换(NAT)模式 仅主机模式

文章目录 网络模式配网要求CentOSDHCP虚拟网络桥接模式默认配置测试手动配置测试 网络地址转发模式 (NAT)还原配置虚拟网络配置默认配置测试手动配置测试 仅主机模式 网络模式 桥接模式: 主机与虚拟机对等, 虚拟机注册到主机所在的局域网, 会占用该网络的IP该局域网内的所有机…

Git企业开发控制理论和实操-从入门到深入(二)|Git的基本操作

前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总https://blog.csdn.net/yu_cblog/cate…

solidity0.8.0的应用案例11:透明代理合约

选择器冲突 智能合约中,函数选择器(selector)是函数签名的哈希的前4个字节。例如mint(address account)的选择器为bytes4(keccak256("mint(address)")),也就是0x6a627842. 由于函数选择器仅有4个字节,范围很小,因此两个不同的函数可能会有相同的选择器,例如…

工厂方法模式介绍

韩敬海 设计模式(Java版) (一)定义 定义一个创建对象的接口,让子类决定实例化哪个类。工厂方法使一个类的实例化延迟到其子类。 工厂方法涉及的角色有: 1 .抽象工厂角色:工厂方法模式的核心&am…

【ElasticSearch】一键安装IK分词器无需其他操作

要注意的时下面命令中的es是我容器的名称,要换成你对应的es容器名 docker exec -it es /bin/bash # 进入容器 ./bin/elasticsearch-plugin install https://github.com/medcl/elasticsearch-analysis- ik/releases/download/v7.12.1/elasticsearch-analysis-ik-7.1…

sql递归查询

一、postgresql 递归sql with recursive p as(select t1.* from t_org_test t1 where t1.id2union allselect t2.*from t_org_test t2 join p on t2.parent_idp.id) select id,name,parent_id from p; sql中with xxxx as () 是对一个查询子句做别名,同时数据库会对…

使用Token方式实现用户身份鉴权认证

一、什么是Token? Token,也称为“令牌”,是服务端生成的一串字符串,以作客户端进行请求的一个令牌,当第一次登录后,服务器生成一个Token便将此Token返回给客户端,以后客户端只需带上这个Token前…

VBA Excel自定义函数的使用 简单的语法

一个简单的教程,实现VBA自定义函数。 新建模块 复制后面的代码放进来 函数的入口参数不定义,则认为是一块区域; 反之,如FindChar1 As String,则认为是输入的单值。 循环和分支如下例子,VB比较接近自然语…

LLM-Rec:基于提示大语言模型的个性化推荐

1. 基本信息 论文题目:LLM-Rec: Personalized Recommendation via Prompting Large Language Models 作者:Hanjia Lyu, Song Jiang, Hanqing Zeng, Yinglong Xia, Jiebo Luo 机构:University of Rochester, University of California Los Angeles, Meta AI, University of Ro…

【网络安全知识】Windows系统安全加固安全加固分析、概念及账户管理和认证权限

Windows系统安全加固分析 最小化方式安装 为了提高系统的安全性,采用最小化方式安装是最可靠的,只安装网络 服务所必需的组件。如果以后有新的服务需求,再安装相应的服务组件 ,并及时进行安全设置。 系统加固工作 对Windows系统安…

innovus set_ccopt_property insertion_delay

我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起来吧? 拾陆楼知识星球入口 set_ccopt_property insertion_delay -pin A/CP $value value的值是负的,意思是需要把A/CP tree做长,正值就是告诉这里有这么长,工具就会把…

Linux 可重入、异步信号安全和线程安全

可重入函数 当一个被捕获的信号被一个进程处理时,进程执行的普通的指令序列会被一个信号处理器暂时地中断。它首先执行该信号处理程序中的指令。如果从信号处理程序返回(例如没有调用exit或longjmp),则继续执行在捕获到信号时进程…

计算机竞赛 基于Django与深度学习的股票预测系统

文章目录 0 前言1 课题背景2 实现效果3 Django框架4 数据整理5 模型准备和训练6 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 **基于Django与深度学习的股票预测系统 ** 该项目较为新颖,适合作为竞赛课题方向&#xff…

通过C实现sqlite3操作,导入电子词典

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <sqlite3.h> int main(int argc, const char *argv[]) {//创建并打开一个数据库sqlite3 *db NULL;if(sqlite3_open("./dict.db",&db) ! SQLITE_OK){printf("…