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

news/2024/5/6 21:34:13

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.mrgr.cn/p/38548747

相关文章

探索 去中心化的Web3.0

随着区块链技术的日益成熟和普及&#xff0c;Web3&#xff08;Web 3.0&#xff09;已经成为一个无法忽视的趋势。Web3不仅仅是一个技术概念&#xff0c;更是一个去中心化、透明、用户数据拥有权归还给用户的互联网新时代。在这篇文章中&#xff0c;我们将深入探讨Web3技术的核心…

百面算法工程师 | 分类和聚类

目录 6.1 为什么正确率有时不能有效评估分类算法&#xff1f; 6.2 什么样的分类器最好&#xff1f; 6.3 什么是聚类&#xff0c;你知道哪些聚类算法&#xff1f; 6.4 K-Means聚类算法如何调优? 6.5 K-Means聚类算法如何选择初始点? 6.6 K-Means聚类聚的是特征还是样本 …

Python爱心代码

爱心效果图&#xff1a; 完整代码&#xff1a; import random from math import sin, cos, pi, log from tkinter import *# 定义画布尺寸和颜色 CANVAS_WIDTH 640 CANVAS_HEIGHT 480 CANVAS_CENTER_X CANVAS_WIDTH / 2 CANVAS_CENTER_Y CANVAS_HEIGHT / 2 IMAGE_ENLARG…

爬虫2(页面解析和数据提取)

爬虫2(页面解析和数据提取)处理HTML文件,常用Xpath,先将HTML文件转换成XML文档,然后用Xpath查找HTML节点或元素。 一、HTML与XML二、XPath1、XPath路径表达式三、Lxml库html = etree.HTML(text) # 将字符串转换成HTML格式# print(etree.tostring(html)) # 补全HTMLresul…

平芯微PW7014中文规格书

产品概述PW7014 具有前端过电压和过温保护功能。 支持 3V 到 36V 的宽输入电压工作范围。 过压保护阈值可以外部设置 4V~22V 或采用内部默认 6.1V 设置。 超快的过压保护响应速度能够确保后级电路的安全。 集成了超低导通阻抗的 nFET 开关, 确保电路系统应用更好的性能。 它可…

hp惠普插入耳机右下角提示检测到音频设备 取消提醒弹窗

前言全局说明系统 Windows 11一、插入耳机屏幕右下角提示二、关闭提示 1.点击提示框 “个性化我的音频” 按钮2. 点“取消”,取消测试3. 去掉 "当检测到新的受支持设备时通知我" 前面的勾(如下图)再插耳机时候就不会有右下角提示了免责声明:本号所涉及内容仅供安…

使用PlantUML绘制活动图、泳道图

最近在学PlantUML 太漂亮了 给大家欣赏一下 我也记录一下 startuml |使用前| start :用户打开旅游App; |#LightSkyBlue|使用后| :用户浏览旅游信息; |#AntiqueWhite|登机前| :用户办理登机手续; :系统生成登机牌; |使用前| :用户到达机场; |登机前| :用户通过安检; |#Light…

Hadoop3:HDFS、YARN、MapReduce三部分的架构概述及三者间关系(Hadoop入门必须记住的内容)

一、HDFS架构概述 Hadoop Distributed File System&#xff0c;简称HDFS&#xff0c;是一个分布式文件系统。 1&#xff09;NameNode(nn)&#xff1a;存储文件的元数据&#xff0c;如文件名&#xff0c;文件目录结构&#xff0c;文件属性&#xff08;生成时间、副本数、文件…

Chartist.js折线图(三)

事件替换图形代码如下<!DOCTYPE html> <html><head><link rel="stylesheet" href="./chartist.min.css"><script src="./chartist.min.js"></script></head><body><div class="ct-char…

Linux给文件内容每行指定字符数据脱敏替换

需求:文件内容中有一批手机号,现在需要对手机号的第4-8位进行数据脱敏处理,我们可以用 sed 命令来截取字符替换操作sed s/./*/4 tel.txt | sed s/./*/5 | sed s/./*/6 | sed s/./*/7 | sed s/./*/8

Web3钱包开发获取测试币-Polygon Mumbai(一)

Web3钱包开发获取测试币-Polygon Mumbai(一) 由于主网区块链上的智能合约需要真正的代币&#xff0c;而部署和使用需要花费真金白银&#xff0c;因此测试网络为 Web3 开发人员提供了一个测试环境&#xff0c;用于部署和测试他们的智能合约&#xff0c;以识别和修复在将智能合约…

powershell@命令行提示符样式配置自定义@pwsh重写prompt显示电量内存时间等信息

文章目录 abstract流行的powershell prompt模块示例 powershell原生修改Prompt函数配置文档Prompt命令来自哪里 简单修改带上电量和时间的Prompt 复杂修改预览FAQ:没有必要修改相关仓库地址样式选择平衡样式花哨样式响应性能 小结 abstract 在 PowerShell 中&#xff0c;可以通…

nginx高性能负载均衡集群

高性能负载均衡集群 一、集群是什么简单地说,集群就是指一组(若干个)相互独立的计算机,利用高速通信网络组成的一个较大的计算机服务系统,每个集群节点(即集群中的每台计算机)都是运行各自服务的独立服务器。 这些服务器之间可以彼此通信,协同向用户提供应用程序,系统…

机器学习day1

一、人工智能三大概念 人工智能三大概念 人工智能&#xff08;AI&#xff09;、机器学习&#xff08;ML&#xff09;和深度学习&#xff08;DL&#xff09; 人工智能&#xff1a;人工智能是研究计算代理的合成和分析的领域。人工智能是使用计算机来模拟&#xff0c;而不是人类…

动态内存管理 柔性数组

文章目录 动态内存函数 malloc freecallocrealloc 重新开辟空间realloc 也可以第一个参数为NULL&#xff0c;则是直接开辟内存&#xff0c;类似于malloc用法 常见的动态内存错误对空指针进行解引用操作对开辟的内存越界访问对非动态开辟的内存使用free释放使用free释放动态开辟…

ABS10-ASEMI开关电源整流桥ABS10

ABS10-ASEMI开关电源整流桥ABS10编辑:ll ABS10-ASEMI开关电源整流桥ABS10 型号:ABS10 品牌:ASEMI 封装:ABS-4 正向电流(Id):1A 反向耐压(VRRM):1000V 正向浪涌电流:30A 正向电压(VF):1.10V 引脚数量:4 芯片个数:4 芯片尺寸:50MIL 功率(Pd):小功率设备 工作温…

揭露 FileSystem 引起的线上 JVM 内存溢出问题

本文主要介绍了由FileSystem类引起的一次线上内存泄漏导致内存溢出的问题分析解决全过程。作者:来自 vivo 互联网大数据团队-Ye Jidong本文主要介绍了由FileSystem类引起的一次线上内存泄漏导致内存溢出的问题分析解决全过程。内存泄漏定义(memory leak):一个不再被程序使用…

Docker镜像的创建 和 Dockerfile

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

nginx高级篇之location高级实战

nginx location高级实战location是nginx的核心重要功能,可以设置网站的访问路径,一个web server会有多个路径,那么location就得设置多个。 Nginx的locaiton作用是根据用户请求的URI不同,来执行不同的应用。 针对用户请求的网站URL进行匹配,匹配成功后进行对应的操作。1.语…

【树莓派】yolov5 Lite,目标检测,行人检测入侵报警

延续之前的程序&#xff1a; https://qq742971636.blog.csdn.net/article/details/138172400 文章目录 播放声音pygame不出声音怎么办&#xff08;调节音量&#xff09;树莓派上的音乐播放器&#xff08;可选&#xff09;命令行直接放歌&#xff08;尝试放mp3歌曲&#xff09; …