二叉搜索树、B-树、B+树

二叉搜索树

二叉查找树,也称为二叉搜索树、有序二叉树或排序二叉树,是指一棵空树或者具有下列性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉搜索树;

在这里插入图片描述
如果二叉查找树是平衡的则查找、插入的时间复杂度为O(logn)。如果二叉查找树完全不平衡则时间复杂度为O(n)。

中序遍历二叉搜索树可以获得关键字的递增序列

二叉搜索树的查找算法

在二叉查找树b中查找x的过程为:

  1. 若b是空树,则搜索失败,否则:
  2. 若x等于b的根节点的值,则查找成功;否则:
  3. 若x小于b的根节点的值,则搜索左子树;否则:
  4. 查找右子树。

二叉搜索树的节点插入算法

向一个二叉搜索树b中插入一个节点s的算法,过程为:

  1. 若b是空树,则将s所指节点作为根节点插入,否则:
  2. 若s->data等于b的根节点的值,则返回,否则:
  3. 若s->data小于b的根节点的值,则把s所指节点插入到左子树中,否则:
  4. 把s所指节点插入到右子树中。(新插入节点总是叶子节点)

二叉搜索树的节点删除算法

  1. 若待删除节点*p为叶子节点则直接删除即可
  2. 若待删除节点*p只有左子树PL或右子树PR,则当*p是左子树(右子树)时直接令PL或PR成为其父节点*f的左子树(右子树)
  3. 若待删除节点*p的左子树或右子树均不为空,
    • 其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树,*s为*p左子树的最右下的结点,而*p的右子树为*s的右子树;
    • 其二是令*p的直接前驱或直接后继替代*p,然后再从二叉查找树中删去它的直接前驱(或直接后继)。
      在这里插入图片描述

AVL树

AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和叶夫根尼·兰迪斯,他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

AVL树是一种自平衡二叉搜索树,在AVL树中任一节点对应的两棵子树的最大高度差为1,查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n),增加和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡。

平衡因子:节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。

旋转操作:

  • 右旋
    在这里插入图片描述
  • 左旋
    在这里插入图片描述

需要平衡的四种情况:
在这里插入图片描述

B-树

参考文章

B-树就是B树,中间的横线并不是减号

为什么数据库索引使用B-树而不是二叉搜索树?
考虑磁盘IO的问题,数据库索引是存储在磁盘上的,当数据量比较大的时候,索引的大小可能有几个G甚至更多,当我们利用索引查询的时候只能逐一加载每一个磁盘页这里的磁盘页对应索引树的节点,最坏情况下磁盘IO次数等于索引树的高度,所以需要把原本“瘦高”的树结构变得“矮胖”,这就是B-树的特征之一。

B树是一种多路平衡查找树,每个节点最多可以包含k个孩子,k为B树的阶(k的选择取决于磁盘页大小)

在这里插入图片描述

一个m阶的B树具有如下几个特征:

  1. 若根节点不是叶子节点则至少有两个子节点
  2. 每个中间节点都包含 k-1 个元素和 k 个孩子,其中 ⌈m/2⌉ <= k <= m
  3. 每个叶子节点都包含 k-1个元素,其中⌈m/2⌉ <= k <= m
  4. 所有的叶子节点都位于同一层
  5. 每个节点中的元素从小到大排列,节点当中k-1个元素刚好是k个孩子包含的元素的值域分划。

B-树主要应用于文件系统以及部分数据库索引,比如著名的非关系型数据库MongoDB,大部分关系型数据库比如Mysql则使用B+树作为索引。

B树的插入操作

参考博客
插入操作是指插入一条记录,即(key, value)的键值对。如果B树中已存在需要插入的键值对,则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

1)根据要插入的key的值,找到叶子结点并插入。

2)判断当前结点key的个数是否小于等于m-1,若满足则结束,否则进行第3步。

3)以结点中间的key为中心分裂成左右两部分,然后将这个中间的key插入到父结点中,这个key的左子树指向分裂后的左半部分,这个key的右子支指向分裂后的右半部分,然后将当前结点指向父结点,继续进行第3步。( 当阶数m为偶数时,需要分裂时就不存在排序恰好在中间的key,那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。 )

以5阶B树为例,介绍B树的插入操作,
在5阶B树中,结点最多有4个key,最少有2个key。

  1. 在空树中插入39
    在这里插入图片描述
    此时根结点就一个key,此时根结点也是叶子结点
  2. 继续插入22、97、41
    在这里插入图片描述
    根结点此时有4个key
  3. 继续插入53
    在这里插入图片描述
    插入后超过了最大允许的关键字个数4,所以以key值为41为中心进行分裂,结果如下图所示,分裂后当前结点指针指向父结点,满足B树条件,插入操作结束。(当阶数m为偶数时,需要分裂时就不存在排序恰好在中间的key,那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。)
    在这里插入图片描述
  4. 依次插入13、21、40
    在这里插入图片描述
    同样会造成分裂,结果如下图所示。
    在这里插入图片描述
  5. 依次插入30、27、 33 ;36、35、34; 24、29
    • 插入 30、27、 33
      在这里插入图片描述
    • 插入 36、35、34;
      在这里插入图片描述
      在这里插入图片描述
    • 插入24、29
      在这里插入图片描述
  6. 插入26
    在这里插入图片描述
    当前结点需要以27为中心分裂,并向父结点进位27,然后当前结点指向父结点,结果如下图所示。
    在这里插入图片描述
    进位后导致当前结点(即根结点)也需要分裂,分裂的结果如下图所示。
    在这里插入图片描述
    分裂后当前结点指向新的根,此时无需调整。
  7. 最后再依次插入key为 17、28、31、32 的记录
    在这里插入图片描述
    在这里插入图片描述

B树的删除操作

删除操作是指,根据key删除记录,如果B树中的记录中不存对应key的记录,则删除失败。

  1. 如果当前需要删除的key位于非叶子结点上,则用后继key(这里的后继key均指后继记录的意思)覆盖要删除的key,然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上,这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
  2. 该结点key个数大于等于Math.ceil(m/2)-1,结束删除操作,否则执行第3步。
  3. 如果兄弟结点key个数大于Math.ceil(m/2)-1,则父结点中的key下移到该结点,兄弟结点中的一个key上移,删除操作结束。
    否则,将父结点中的key下移与当前结点及它的兄弟结点中的key合并,形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针,指向这个新结点。然后当前结点的指针指向父结点,重复上第2步。
    有些结点它可能即有左兄弟,又有右兄弟,那么我们任意选择一个兄弟结点进行操作即可。

以5阶B树为例,介绍B树的删除操作
5阶B树中,结点最多有4个key,最少有2个key

  1. 原始状态
    在这里插入图片描述
  2. 在上面的B树中删除21,删除后结点中的关键字个数仍然大于等2,所以删除结束
    在这里插入图片描述
  3. 在上述情况下接着删除27。从上图可知27位于非叶子结点中,所以用27的后继替换它。从图中可以看出,27的后继为28,我们用28替换27,然后在28(原27)的右孩子结点中删除28。删除后的结果如下图所示。
    在这里插入图片描述
    删除后发现,当前叶子结点的记录的个数小于2,而它的兄弟结点中有3个记录(当前结点还有一个右兄弟,选择右兄弟就会出现合并结点的情况,不论选哪一个都行,只是最后B树的形态会不一样而已),我们可以从兄弟结点中借取一个key。所以父结点中的28下移,兄弟结点中的26上移,删除结束。结果如下图所示。
    在这里插入图片描述
  4. 在上述情况下接着删除32,结果如下图。
    在这里插入图片描述
    当删除后,当前结点中只有一个key,而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并,成为一个新的结点,当前结点的指针指向父结点。结果如下图所示。
    在这里插入图片描述
    当前结点key的个数满足条件,故删除结束。
  5. 上述情况下,我们接着删除key为40的记录,删除后结果如下图所示。
    在这里插入图片描述
    同理,当前结点的记录数小于2,兄弟结点中没有多余key,所以父结点中的key下移,和兄弟(这里我们选择左兄弟,选择右兄弟也可以)结点合并,合并后的指向当前结点的指针就指向了父结点。
    在这里插入图片描述
    同理,对于当前结点而言只能继续合并了,最后结果如下所示。
    在这里插入图片描述
    合并后结点当前结点满足条件,删除结束。

B+树

参考文章
B+树是B-树的一种变体,有着比B-树更高的查询性能
一个m阶的B+树具有如下几个特征:

  1. 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点
  2. 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
  3. 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)的元素

在这里插入图片描述
在B-树中无论是中间节点还是叶子节点都有卫星数据(牵引元素所指向的数据记录),而在B+树中只有叶子节点带有卫星数据,其余中间节点仅仅是索引,没有任何数据关联。

B+树的优点

  • 单行查询
    在单元素查询的时候,B+树会自顶向下逐层查找节点,最终找到匹配的叶子节点。步骤与B-树类似,但是B+树的中间节点没有卫星数据,所以同样大小的磁盘页可以容纳更多的节点元素,在数据量相同的情况下B+树比B-树更加“矮胖”查询IO的次数也更少。其次,B+树的查询必须最终查找到叶子节点,而B-树只要找到匹配元素即可,无论匹配元素处于中间节点还是叶子节点,因此B-树的查找性能不稳定(最好情况是根节点,最坏情况是叶子节点),而B+树的每次查找都是稳定的

  • 范围查询
    B-树的范围查询只能依靠繁琐的中序遍历,B+树的范围查询只需要在链表上做遍历即可

总结:

  1. 单一节点存储更多的元素,使得查询的IO次数更少。
  2. 所有查询都要查找到叶子节点,查询性能稳定。
  3. 所有叶子节点形成有序链表,便于范围查询。

红黑树

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

java入门-基本数据类型

今天开始开贴关注初学java的同学&#xff0c;写些基础内容&#xff0c;希望对大家有所帮助。如果对大家有帮助会一直写下去。 java基本语法-基本数据类型 概述 基本数据类型在程序运行中&#xff0c;需要内存空间来存储数据。数据存储的大小有不同&#xff0c;申请合理的内存空…

POJO简介

文章目录 简介POJO与ELB的区别POJO真正的意思 常见的POJO类DTODAOPOVOEntity 简介 什么是POJO&#xff1f;POJO&#xff08;Plain Ordinary Java Object&#xff09;简单的Java对象&#xff0c;实际就是普通JavaBeans&#xff0c;是为了避免和EJB(EJB是Enterprise Java Beans技…

Docker【docker使用】

文章目录 前言一、概念二、常用方法1.镜像2.容器 三、镜像构建贺管理 前言 上一篇文章讲了docker的安装&#xff0c;本片文章我们来聊聊docker的一些常用操作。以及镜像、容器之间的关系 一、概念 docker三大核心概念&#xff1a;镜像 Image、容器 Container、仓库 Reposito…

Opencv4+稀疏光流算法详解+实现

0. 写在前面 项目需要用到光流法找到图像中的点运动方向&#xff0c;想到光流法刚好适用。原理部分参考&#xff1a; 图像处理算法--光流法-原理-CSDN博客 1. Opencv4.5.4稀疏光流函数说明 1.1 稀疏光流API介绍 prevImg:视频前一帧图像/金字塔&#xff0c;单通道CV_…

获取远程管理软件保存的凭据

点击星标&#xff0c;即时接收最新推文 本文选自《内网安全攻防&#xff1a;红队之路》 扫描二维码五折购书 内网敏感数据的发现 内网的核心敏感数据&#xff0c;不仅包括数据库、电子邮件&#xff0c;还包括个人数据及组织的业务数据、技术数据等。可以说&#xff0c;价值较高…

(零)OpenOFDM接收端整体思路

一旦捕获射频信号并将其下变频至基带&#xff0c;解码管道就会启动&#xff0c;包括&#xff1a; OFDM&#xff0c;多载波调制的一种。通过频分复用实现高速串行数据的并行传输, 它具有较好的抗多径衰落的能力&#xff0c;能够支持多用户接入。 OFDM主要思想是&#xff1a;将信…

(1)fopen,fseek,fread,ftell,rewind作用和使用方法,大端小端

文章目录 1.fopen&#xff0c;fseek&#xff0c;fread&#xff0c;ftell&#xff0c;rewind作用和使用方法2.bin文件里从0x0000到0x0x0007是00 00 DF 00 00 01 00 00&#xff0c;但是用fread读出来前四个字节是DF0000&#xff0c;然后是0x1000&#xff0c;这是为什么&#xff1…

2024蓝桥杯每日一题(回溯)

备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一&#xff1a;木棒 试题二&#xff1a;n皇后问题 试题三&#xff1a;糖果 试题四&#xff1a;飞机降落 试题五&#xff1a;生日蛋糕 试题一&#xff1a;木棒 【问题描述】 乔治拿来一组等长…

steam_api.dll“是什么?打开游戏出现找不到steam_api.dll无法继续执行代码如何解决

"steam_api.dll"是什么&#xff1f;&#xff0c;steam_api.dll它是由windows系统Visual C Redistributable for Visual Studio提供的。当这个文件损坏或丢失时&#xff0c;会导致一些应用程序无法运行&#xff0c;显示找不到"steam_api.dll"缺失错误。本文…

马斯克开源的grok AI大模型

马斯克践行诺言&#xff0c;坚持开源原则&#xff0c;选择开源自家的 AI 大模型——Grok-1 下载链接如下: https://github.com/xai-org/grok-1 Grok-1 开源仅过去了 10 个小时&#xff0c;该项目便获得了 超过16k 的 Star&#xff0c;成为众人关注的焦点所在。 后续继续更新…

Python二级备考(1)考纲+基础操作

考试大纲如下&#xff1a; 基本要求 考试内容 考试方式 比较希望能直接刷题&#xff0c;因为不懂的比较多可能会看视频。 基础操作刷题&#xff1a; 知乎大头计算机1-13题 import jieba txtinput() lsjieba.lcut(txt) print("{:.1f}".format(len(txt)/len(ls)…

springcloud:4.2 GateWay结合JWT实现网关鉴权

概述 概述 简介 JWT是一种用于双方之间传递安全信息的简洁的、URL安全的声明规范。 定义了一种简洁的,自包含的方法用于通信双方之间以Json对象的形式安全的传递信息。 特别适用于分布式站点的单点登录(SSO)场景 传统的session认证的缺点 安全性:CSRF攻击因为基于cookie来…

掌握AI写作工具:引领内容创作潮流

随着技术发展&#xff0c;AI技术正日益渗透到各行各业&#xff0c;并对内容创作领域产生了深远影响。随着AI写作工具的不断发展和普及&#xff0c;内容创作者们正逐渐看到了AI在提高效率、创造力和质量方面的巨大潜力。本文将探讨AI写作工具如何引领内容创作潮流&#xff0c;以…

vue antd table嵌套表格 左侧展开图标动态控制显示隐藏

antd a-table想要实现如以下效果&#xff0c;有子级就显示展开图标&#xff0c;没有就不显示图标&#xff1a; 话不多说&#xff0c;直接上代码&#xff1a; <template><a-table :columns"columns" :data-source"dataSource"><template #b…

最新若依项目快速上手

最新若依项目快速上手 配套视频&#xff1a;若依项目快速上手视频 1. 下载源码 官网&#xff1a;https://ruoyi.vip/ 前端 git clone https://github.com/yangzongzhuan/RuoYi-Vue3.git后端 git clone https://gitee.com/y_project/RuoYi-Vue.git2. 数据库 创建数据库ry-vue…

JAVA后端调用OpenAI接口 实现打字机效果(SSE)

SSE SSE&#xff08;Server-Sent Events&#xff0c;服务器发送事件&#xff09;是一种基于HTTP协议的通信技术&#xff0c;它允许服务器持续地将数据推送给客户端&#xff0c;而无需客户端发起请求。这种通信方式通常用于实时性要求较高的场景&#xff0c;如实时更新、通知、或…

Linux:搭建ntp服务器

我准备两个centos7服务器 一个为主服务器连接着外网&#xff0c;并且搭建了ntp服务给其他主机同步 另外一个没有连接外网&#xff0c;通过第一台设备去同步时间 首先两个服务器都要安装ntp软件 yum -y install ntp 再把他俩的时间都改成别的 左侧的是主服务器&#xff0c;主…

【Docker篇】自定义Dockerfile的操作

文章目录 &#x1f354;镜像结构&#x1f6f8;什么是Dockerfile⭐基于Ubuntu镜像构建一个新镜像&#xff0c;运行一个java项目&#x1f50e;使用 java:8-alpine &#x1f354;镜像结构 镜像是将应用程序及其需要的系统函数库、环境、配置、依赖打包而成。 我们以MySQL为例&am…

JVM中对象创建过程

在JVM中对象的创建&#xff0c;我们从一个new指令开始&#xff1a; 这个过程大概图示如下&#xff1a; 虚拟机收到new指令触发。 类加载检查&#xff1a;如果类没有被类加载器加载&#xff0c;则执行类加载流程&#xff08;将class信息加载到JVM的运行时数据区的过程&#xff…

KiCad 从原理图创建或者导出原理图符号

KiCad 从原理图创建或者导出原理图符号 原理图中&#xff0c;在下那个要导出的符号上点击右键-》属性-》编辑符号 在符号编辑中选择&#xff1a;文件-》导出符号 加微信&#xff1a;jiyuyun18, 交流电子技术 留言&#xff1a;CSND 电子技术交流群&#xff0c;加入电子微信电…