平衡二叉树、红黑树、B树、B+树

server/2024/9/20 6:13:51/ 标签: b树, 数据结构

Tree

  • 1、前言
  • 2、平衡二叉树和红黑树
  • 3、B树和B+树
    • 3.1、B树的构建
    • 3.2、B树和B+树的区别
    • 3.3、数据的存储方式

1、前言

本文侧重在理论方面对平衡二叉树、红黑树、B树和B+树的各方面性能进行比较。不涉及编程方面的实现。而关于于平衡二叉树在C++中的实现,我的上一篇文章平衡二叉树(AVLTree)有所介绍。

2、平衡二叉树和红黑树

平衡二叉树又称平衡二叉搜索树,由于是Adelson-Velsky and Landis二人发明的,所以又叫AVL树。平衡二叉树要求左右子树的高度差不能大于一。所以极限条件下,搜索的时间复杂度是O(logn)。但由于其调整起来十分麻烦,所以并不适用于经常需要进行插入和删除的环境。因此引入红黑树(也是二叉搜索树的一种)来解决这一问题。
红黑树,顾名思义是有红黑两种节点。然而对于红黑树的构成却有许多限制,我们先来看看这些限制。

  • 1、根节点必须是黑色的。
  • 2、不能有两个红节点构成亲子关系,即不能有两个连在一起的红节点。
  • 3、从任意节点到叶子节点的所有路径都包含相同数目的黑节点。
  • 4、所有叶子节点都是黑色的,这里的叶子节点指的是最末端的虚拟节点(NULL节点)。个人觉得,设置这些虚拟节点,是为了使限制3不失一般性。

通过以上四点设置便可以限制左右子树的高度差在一倍之内。我们不妨设一种极限情况,从根节点出来的左路径全是黑节点,右路径全是红黑交叉的节点。那么由于红节点不能两两相连,且右路径的黑节点数必须和做路径相同,所以右路径的节点是顶多是左路径的两倍。
在这里插入图片描述
如果把所有红色节点擦除,那么N个黑色节点所构成的必然是一颗平衡二叉树,搜索时的时间复杂度是logn。那么加上所有红色节点,由于极限情况下,最长路径是纯黑色节点的两倍。故而搜索时间复杂度是2logn,忽略常数项,那么复杂度还是O(logn)。
此外,基于红黑树的限制条件,在插入一个新的节点之后,红黑树的调整次数通常较少,大多数情况下不超过三次旋转。这是因为红黑树的设计允许它在维持平衡的同时允许某种程度的不完全平衡,因此调整的复杂性和频率通常低于AVL树。
至于如何插入节点,仅作了解吧。
首先,除了根节点之外,任何新增的节点都先被视为红节点,然后再进行以下判定。请添加图片描述
这里的左旋右旋具体时如何操作的,和平衡二叉树那里基本差不多,所以不赘述了。
由于红黑树在搜索中,时间复杂度是O(logn),且插入节点所需的调整的频率也低于AVL树,所以应用比较广泛。如C++中map和set这两种容器的底层就是红黑树。
以map为例,在C++中,map和python的字典很想,其第一个元素被视为key,第二个元素被视为value。而key是不允许修改和重复的,存储key的数据结构正式红黑树。这也保证了map在搜索时,时间复杂度为O(logn)。

using namespace std;map<int, int> myMap;
myMap[0] = 5;
myMap[1] = 7;

当然map也允许key是字符串类型,但即使是字符串类型,其还是会以红黑树的方式进行存储。只不过不再此时要按照字典顺序进行排序。

map<string, int> myMap1;
map<string, string>	myMap2;

3、B树和B+树

B树和B+树都是被广泛应用的数据结构。它们最显著的特征便是每一个节点可以存放多个数据,且可以有N个子树。下图是B树的示意图。
在这里插入图片描述
在构建一棵B树的时候,需要预先定义它的阶数m,限制一个节点至多存放m-1个值,并且也表明一个节点至多可以有m个子树。故而B树也可以被叫做m叉树。
一颗m叉树的每一个节点大概长这样。
在这里插入图片描述
n表示这个节点存放n个数据,k1,k2,…,kn-1是这个节点存放的数据,这些数据从小到达依次排序。p0,p2,…,pn是指向子树的指针。其中p0所指的子树的值全部在0和k1之间,p1所指子树的值全部在k1和k2之间,以此类推。

3.1、B树的构建

为了方便演示,我所展示的一个B树是一棵三叉树,即m=3。然后我依次插入1,3,5,2。流程图如下,当我们插入的数大于3个数的时候,变会取中间的值变成一个新的节点。当然我应该再演示一下它有三个子树的情况,但已经懒得画了。。。
在这里插入图片描述
总之B树的构建大抵如此。
其实B树更像是在2叉树和单链表之间妥协的产物。因为在每一个节点上进行搜索,其实就相当于在链表上进行搜索,所以当m取很大的时候,其搜索时间复杂度就接近一个链表了。当然由于其是一个有序的链表,我们在节点上也可以进行二分查找以降低复杂度。总而言之,m的取值是两种数据结构的权衡,故而也很重要。

3.2、B树和B+树的区别

顾明思意B+树事B树的升级版,克服了B树的许多缺点,有更高的搜索效率。但它们之间的较量关乎内存和磁盘,我放在最后讲。先来看看B树和B+树在构成上的区别。

  • 1、B+树的每一个子节点都会存储父节点的key,这里的key就是图中节点的值。
  • 2、B+树的所有叶子节点(末端的那些节点)通过指针串在一起。因而B+树除了随机搜索的方式(从根节点开始搜索),还多了一种顺序搜索方式(直接从叶子节点开始按顺序搜索)。

在这里插入图片描述
以上两点就是B树和B+树从观感上比较明显的差别。但其核心差距还是在存储方式上。

3.3、数据的存储方式

前文反复提到了B树和B+树节点中存放的数字是一个key,key有钥匙的含义。之所以这样叫,是因为key是访问另一个信息的钥匙。以B树为例,很多时候,节点中的key存放的看似是一个数字,其实是一个段文本信息的代表。而如果希望这些文本信息不至于在程序结束的时候随着程序而丢失,我们就需要将其放入磁盘当中。
在这里插入图片描述
这就涉及到一些操作系统的知识。我们在运行一个程序的时候,实际上是在RAM(Random Access Memory)上开辟一块区域,此时如果需要读取看到磁盘中的内容,就需要通过I/O操作以block为单位去把磁盘中的内容加载进RAM中。这里的block是数据读取的最小单位。在B树中,一般一个节点的数据,包括key,key指向的文本信息,指针等都放在同一个block中。这样block存储的key就不会很多,那么搜索一个信息的时候就不得不读取很多个block,进行很多次I/O操作。而I/O操作时非常费时的。
在这里插入图片描述
为了解决这个问题,B+树在非叶子节点(末端节点)上,只存放key,而把各个节点key对应的文本信息都存放到最后一个叶子节点上。通过这样的操作,每个block,即每个非叶子节点能存放的key就大大增多。当我们搜索一个信息的时候,需要经过的节点就减少了,从而I/O操作的频率也随之降低,进而提高了搜索效率。这便是B树和B+树的核心区别。


http://www.ppmy.cn/server/16822.html

相关文章

Laravel 6 - 第十七章 配置数据库

​ 文章目录 Laravel 6 - 第一章 简介 Laravel 6 - 第二章 项目搭建 Laravel 6 - 第三章 文件夹结构 Laravel 6 - 第四章 生命周期 Laravel 6 - 第五章 控制反转和依赖注入 Laravel 6 - 第六章 服务容器 Laravel 6 - 第七章 服务提供者 Laravel 6 - 第八章 门面 Laravel 6 - …

重新理解React-hook

Hook是什么 Hook是React16.8版本新增的特性,它可以让我们在不写类组件的情况下使用state以及其他的React特性。 它解决了以下这些问题: 逻辑复杂的组件难以开发和维护,当我们的组件需要处理多个互不相关的local state时,每个生命周期函数中可能包含着各种互相关的逻辑类组…

微软如何打造数字零售力航母系列科普02 --- 微软低代码应用平台加速企业创新 - 解放企业数字零售力

微软低代码应用平台推动企业创新- 解放企业数字零售力 微软在2023年GARTNER发布的魔力象限图中处于头部领先&#xff08;leader&#xff09;地位。 其LCAP产品是Microsoft Power Apps&#xff0c;扩展了AI Builder、Dataverse、Power Automate和Power Pages&#xff0c;这些都包…

Docker镜像的创建 和 Dockerfile

一. Docker 镜像的创建 创建镜像有三种方法&#xff0c;分别为基于已有镜像创建、基于本地模板创建以及基于 Dockerfile 创建。 1 基于现有镜像创建 &#xff08;1&#xff09;首先启动一个镜像&#xff0c;在容器里做修改docker run -it --name web3 centos:7 /bin/bash …

大语言模型在研究领域的应用——信息检索中的大语言模型

信息检索中的大语言模型 大语言模型提升信息检索任务利用大语言模型进行信息检索大语言模型增强的信息检索模型.检索增强的大语言模型输入优化策略.指令微调策略.预训练策略.总结应用建议未来方向大语言模型对于传统信息检索技术与应用范式带来了重要影响。这两者在技术路径上具…

LabVIEW专栏七、队列

目录 一、队列范例二、命令簇三、队列应用1.1、并行循环队列1.2、命名队列和匿名队列1.2.1、命名队列1.2.2、匿名队列 1.3、长度为1的队列 队列是一种特殊的线性表&#xff0c;就是队列里的元素都是按照顺序进出。 队列的数据元素又称为队列元素。在队列中插入一个队列元素称为…

绿联搭建rustdesk服务器

绿联搭建rustdesk服务器&#xff0c;不再使用向日葵 注意&#xff1a;本服务器需要有动态公网IP以及自己的域名&#xff0c;ipv6未测试。 1. 拉取镜像 rustdesk/rustdesk-server-s6:latest 注意是这个-s6的镜像。 2. 部署镜像 2.1 内存配置 本服务器比较省内存&#xff0…

通俗易懂说模型——RNN

​&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;《深度学习基础知识》 相关专栏&#xff1a; ⚽《机器学习基础知识》 &#x1f3d0;《机器学习项目实战》 &#x1f94e;《深度学习项目实…

智慧火电厂合集 | 数字孪生助推能源革命

火电厂在发电领域中扮演着举足轻重的角色。主要通过燃烧如煤、石油或天然气等化石燃料来产生电力。尽管随着可再生能源技术的进步导致其比重有所减少&#xff0c;但直至 2023 年&#xff0c;火电依然是全球主要的电力来源之一。 通过图扑软件自主研发 HT for Web 产品&#xf…

软考137-上午题-【软件工程】-软件质量

一、软件质量 软件质量是指反映软件系统或软件产品满足规定或隐含需求的能力的特征和特性全体。软件质量管理是指对软件开发过程进行独立的检查活动&#xff0c;由质量保证、质量规划和质量控制3个主要活动构成。软件质量保证是指为保证软件系统或软件产品充分满足用户要求的质…

数仓开发LAG 和 LEAD 函数详细解析和用例

在做Iot大数据开发时&#xff0c;需要用到lag和lead函数来计算设备故障。下面详细解析lag和lead函数的作用和例子。 LAG 和 LEAD 函数是用于在 Spark SQL 中进行窗口函数操作时常用的两个函数&#xff0c;它们用于获取某一行在分组内的前一行或后一行的数值。下面详细解释它们…

一般神经网络的微分与网络参数的初始化

(文章的主要内容来自电科的顾亦奇老师的 Mathematical Foundation of Deep Learning, 有部分个人理解) 一般深度神经网络的微分 上周讨论的前向和反向传播算法可以推广到任意深度神经网络的微分。 对于一般的网络来说&#xff0c;可能无法逐层分割&#xff0c;但仍然可以用流…

git忽略文件.gitignore如何使用?

创建 .gitignore 文件 首先&#xff0c;在你的项目根目录下创建一个名为 .gitignore 的文件。可以通过命令行或者你的编辑器来创建这个文件。 打开 .gitignore 文件&#xff0c;你可以将以下内容粘贴到文件中&#xff1a; 忽略编译生成的文件 *.class *.jar *.war忽略系统文件…

L2-052 吉利矩阵

题目描述 题解思路 这个道题就是很简单&#xff0c;就跟n皇后问题一样&#xff0c;给矩阵填数&#xff0c;使得矩阵满足一个什么条件&#xff0c;最后求方案数或者方案。很容易想到回溯法&#xff0c;根据数据范围&#xff0c;应该能够确定回溯法是没有问题的。 我们只需要枚举…

(九)Pandas表格样式 学习简要笔记 #Python #CDA学习打卡

目录 一. Pandas表格样式 1&#xff09;举例数据 2&#xff09;字体颜色 3&#xff09;背景高亮 4&#xff09;极值背景高亮 &#xff08;a&#xff09;高亮最大值 highlight_max() &#xff08;b&#xff09;高亮最小值 highlight_min() &#xff08;c&#xff09;同时…

ubuntu22.04 CH340/CH34x 驱动安装

CH34x驱动地址&#xff1a;CH341SER_LINUX.ZIP - 南京沁恒微电子股份有限公司 1、卸载旧驱动&#xff08;如果存在&#xff09; sudo rmmod ch341.ko 2、解压进入 driver 目录 unzip CH341SER_LINUX.ZIP cd CH341SER_LINUX/driver 3、编译 make 可能错误&#xff1a; make[1]…

npm包管理器

npm&#xff08;Node Package Manager&#xff09;是Node.js的包管理器&#xff0c;用于安、发布和管理JavaScript模块。它是世界上最大的开源软件注册表&#xff0c;拥有超过100万个包供开发者使用。 使用npm可以轻松地安装和管理项目所需的各种模块。下面是npm包管理器的一些…

Mybatis入门(入门案例,IDEA配置SQL提示,JDBC介绍,lombok介绍)

目录 一、Mybatis入门案例介绍整体步骤创建SpringBoot项目pom依赖准备测试数据新建实体类配置Mybatis数据库连接信息新建接口类,编写SQL代码单元测试 二、IDEA配置SQL提示三、JDBC是什么案例JDBC和Mybatis对比 四、数据库连接池介绍如何实现一个数据库连接池切换数据库连接池 五…

CentOS 7虚拟机配置过程中所需组件的安装(二)

1.安装net-tools组件&#xff08;解决无 ifconfig&#xff09; # yum install net-tools 2.安装gcc、c编译器以及内核文件 # yum -y install gcc gcc-c kernel-devel 验证安装成功 3.安装nano&#xff08;文本编辑器&#xff09; # yum install nano

英特尔数据中心渠道业务部总经理蒋健一行到访Gooxi

4月16日&#xff0c;英特尔数据中心渠道业务部总经理蒋健一行到访Gooxi&#xff0c;在Gooxi公司董事长兼总裁赵士亮等领导陪同下参观了深圳研发总部并进行深入交流&#xff0c;详细了解Gooxi在Intel产品线的业务布局、产品研发、市场营销等领域的合作成果。 Gooxi公司董事长兼总…