【数据结构】什么是红黑树(Red Black Tree)?

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022


目录

📌红黑树的概念

📌红黑树的操作

🎏红黑树的插入操作

🎏红黑树的删除操作

结语


📌红黑树的概念

        我们之前学过了二叉搜索树和平衡二叉搜索(AVL)树, 除了它们, 还有一个被广泛运用的平衡二叉搜索树是红黑树(RB-Tree)

        红黑树是一种平衡二叉搜索树的变体, 它的左右子树高差有可能大于 1,所以红黑树不是严格意义上的平衡二叉搜索树(AVL),但对之进行平衡的代价较低, 其平均统计性能要强于 AVL 。

        红黑树在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

        红黑树的规则如下:

  1. 每个结点不是红色就是黑色
  2. 根结点是黑色
  3. 如果一个结点是红色的,则它的子结点一定是黑色
  4. 任一结点到NULL(树尾)的任何路径上,所含的黑色结点数一定相同
  5. 每个NULL(树尾)空结点都是黑色的

        依照红黑树的规则,红黑树能确保没有一条路径会比其他路径长出俩倍的原因是:

        因此假设所有路径的黑节点数是n,那么最短路径的长度为n,而最长路径的长度为2n-1.

        红黑树和AVL树的效率差异:

        因为AVL树是较严格的平衡二叉搜索树,因此当数据量为n时,它的查询效率最坏大概在log_{2}n。而对于红黑树来讲,假设它的最短路径层高和AVL树的层高一样,那它的最坏查询效率大概就在2log_{2}n。虽然略逊AVL树,但两者的效率仍然处于一个量级,即使有10亿数据,AVL树的查询次数在30次左右,而红黑树的查询次数在60次左右,差距不是很大,但是在插入时红黑树对于AVL树的消耗却少了不少,因此STL库中set和map的底层都是通过封装红黑树实现的.


📌红黑树的操作

🎏红黑树的插入操作

        我们同样以一组数据为例, 在模拟红黑树插入的过程中学习红黑树对于插入结点的处理方法

        在此之前,我们需要先搞清楚一个问题, 那就是每个结点都有颜色,或红色或黑色,那么新插入的结点应该是红色还是黑色呢?答案是, 必须是红色!

        我们简单分析一下插入新结点的情况, 假设我们现在需要给下面这颗红黑树中插入一个新结点7:

        我们先来看看如果这个结点为黑节点的情况:

        给大家举一个例子, 想来大家或多或少都有听说过或者经历过被人催婚的经历, 有一个很有趣的现象, 不知道大家有没有观察到, 那就是催婚的力度, 和年龄的关系不是很大,但是和同辈人有没有结婚生子关系非常大,也就是说,当家里亲戚里同辈人都没有结婚生子时,催婚的力度可能就是"天街小雨润如酥"。但是一旦同辈人中有人已经结婚生子了,那催婚的力度可就是"涧底松摇千尺雨"了。

        上图中新插入黑节点的行为就像是第一个结婚生子的同辈人,明明同辈人大家一起在坚守战线, 但是他却叛变了, 这下剩下所有的结点的平衡都因为它而打破, 破坏力简直是毁灭级的, 所以我们新插入的结点一定不能是黑色的。

        那假如我们插入的新节点是红结点呢?

        我们可以看到,如果插入的红结点父亲是黑节点,那么红结点的插入就不会破坏任何红黑树的规则, 这就相当于同辈人没有直接结婚生子,而只是谈了一个男/女朋友,并不会真正影响到平衡的格局, 只是偶尔会遇到父节点也是红结点的情况,这个时候我们按后面学到的处理方法将他们处理一下就可以.

        如果我们遇到了插入后违反红黑树规则的情况,那么红黑树的调整规则如下:

  1. 插入结点是根节点(即破坏了根节点是黑色的规则)--->解决方法,直接将该节点变黑
  2. 插入结点的父节点也是红色(即破坏了红结点的孩子必须是黑色的规则),分两种情况
  • 插入结点的叔叔结点是红色: 将叔叔和父亲变为黑色, 爷爷结点变为红色, 然后继续向上判定爷爷结点是否违反了红黑树的规则并进行调整
  • 插入结点的叔叔结点不存在或是黑色: 根据形态进行相应的旋转操作,旋转完成后,将旋转后的根节点变黑,将祖父结点变红即可

         接下来我们就一起按照这组数据来模拟红黑树的插入过程:

17 18 23 34 27 15 9 6 8 5 25 

         首先插入第一个结点17:

        可以看到,插入根节点时,我们违反了根结点为黑的性质,解决办法也很简单,把根节点变黑就行:

        继续插入下一个结点18:

        插入后没有破坏红黑树的任何性质,继续插入

         插入下一个结点23:

        此时违反了红黑树不能有两个连续红结点的性质,并且对新插入的结点23来讲,它的叔叔结点不存在,因此我们考虑使用旋转来解决,观察发现此时是RR型的旋转,因此我们通过左旋来解决:

        左旋之后,我们需要将新的父亲结点变为黑色,原来的爷爷结点变为红色就完成了:

        继续插入下一个结点34:

        此时违反了红黑树不能有两个连续红结点的性质,并且对新插入的结点34来讲,它的叔叔结点是红色的,因此我们需要对将父亲叔叔变为黑色,爷爷变为红色:

        然后继续将爷爷结点18作为新插入结点继续向上判定,发现他不符合根结点是黑色结点的性质,因此我们将根节点18变为黑色即可:

        向上判定到了根节点就结束了, 我们继续插入下一个结点.

        继续插入下一个结点27:

        发现此时新插入结点27和它的父亲结点34违反了不能有两个相同红结点的规则,通过观察,我们发现他没有叔叔结点, 又因为是RL型,因此我们选择右左双旋来解决这个问题:

        旋转好后,再对旋转后的根节点27和祖父结点23进行变色:

        变色完成,我们的红黑树也就插入成功了.

        继续插入下一个结点15:

        发现并没有破坏红黑树的任何性质, 继续插入下一个结点.

        继续插入下一个结点9:

        发现新插入的9和其父亲结点15违反了不能有两个连续红结点的性质,同时其叔叔结点也不存在,通过观察是LL型旋转,因此我们选择右旋来解决这个问题:

        右旋完成后,我们更改旋转后的根节点15和爷爷结点17进行变色,就调整好了:

        继续插入下一个结点6:

        发现新插入的6和其父亲结点9违反了不能有两个连续红结点的性质,同时其叔叔是红色,因此我们选择将父亲结点叔叔结点和爷爷结点变色来解决这个问题:

        变色完成后,我们继续判断爷爷结点是否有违反红黑树的性质,发现没有,插入完成.

        继续插入下一个结点8:

        发现新插入的8和其父亲结点6违反了不能有两个连续红结点的性质,同时其叔叔结点也不存在,通过观察是LR型旋转,因此我们选择左右双旋来解决这个问题:

        旋转完成后,我们再对旋转后的根节点8,和爷爷结点9进行变色, 既可完成插入:

        继续插入下一个结点5:

        发现新插入的5和其父亲结点6违反了不能有两个连续红结点的性质,同时其叔叔是红色,因此我们选择将父亲结点叔叔结点和爷爷结点变色来解决这个问题:

        变色完成后,我们继续判断爷爷结点8是否有违反红黑树的性质,发现结点8和其父亲结点15违反了不能有两个连续红结点的性质,同时其叔叔结点27是黑色,通过观察是LL型旋转,因此我们选择右旋来解决这个问题:

        右旋完成后,我们更改旋转后的根节点15和爷爷结点18进行变色,就调整好了:

        继续插入最后一个结点25:

        发现新插入的25和其父亲结点23违反了不能有两个连续红结点的性质,同时其叔叔34是红色,因此我们选择将父亲结点叔叔结点和爷爷结点变色来解决这个问题:

        变色之后,继续判断爷爷结点27是否违反红黑树性质,发现结点27和它的父亲结点18违反了不能有两个连续红结点的性质,同时其叔叔结点8是红色,因此我们选择将父亲结点18叔叔结点8和爷爷结点15变色来解决这个问题:

        变色之后,继续判断新的爷爷结点15是否违反红黑树性质,发现他违反了根节点必须为黑的性质,因此我们将他变黑,又因为已经判断到根节点, 插入操作完成.

        将所有元素插入进红黑树后,我们显示出所有的空结点,验证红黑树的性质,发现是符合红黑树的性质的:


🎏红黑树的删除操作

        红黑树和AVL树一样,都是要在二叉搜索树的删除插入基础上然后保持其树本身的特性.

红黑树的删除难点主要在于删除叶子黑节点

        因为有孩子结点时我们只需要按二叉搜索树的逻辑让孩子结点代替它,并让孩子结点变黑即可。

        对于叶子红结点呢,因为删除它不会影响任何红黑树的性质,所以直接删除即可, 但是对于删除叶子黑节点就非常复杂,我放一张红黑树的删除操作逻辑图和二叉搜索树的删除逻辑在这里,有兴趣的朋友可以参考研究一下,这里就不详细展开了:



结语

希望这篇关于 红黑树(RB-Tree) 的博客能对大家有所帮助,欢迎大佬们留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

相关文章推荐

【数据结构】什么是平衡二叉搜索树(AVL Tree)?

【C++】STL标准模板库容器map

【C++】STL标准模板库容器set

【C++】模拟实现二叉搜索(排序)树

【数据结构】C语言实现链式二叉树(附完整运行代码)

【数据结构】什么是二叉搜索(排序)树?

【C++】模拟实现priority_queue(优先级队列)

【C++】模拟实现queue

【C++】模拟实现stack

【C++】模拟实现list

【C++】模拟实现vector

【C++】标准库类型vector

【C++】模拟实现string类

【C++】标准库类型string

【C++】构建第一个C++类:Date类

【C++】类的六大默认成员函数及其特性(万字详解)

【C++】什么是类与对象?


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

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

相关文章

codetop标签树刷题(四)!!暴打面试官!!!!

用于个人复习 1.二叉树的右视图2.二叉树最大宽度3.二叉树的最大深度4.N叉树的最大深度5.二叉树的最小深度6.子树的最大平均值7.求根节点到叶节点的数字之和8.另一棵树的子树9.对称二叉树 1.二叉树的右视图 给定一个二叉树的根节点root,想象自己站在它的右侧&#x…

TypeScript 封装 Axios 1.7.7

随着Axios版本的不同,类型也在改变,以后怎么写类型? yarn add axios1. 封装Axios 将Axios封装成一个类,同时重新封装request方法 重新封装request有几个好处: 所有的请求将从我们定义的requet请求中发送&#xff…

setTimeout,setInterval ,requestAnimationFrame定时器

setTimeout,setInterval ,requestAnimationFrame定时器 定时器函数通常用于执行定时任务,也就是说你做了一个功能放在定时器函数里,它可以在特定的时间去执行你的指令,或者说隔多长时间(单位时间内—毫秒为…

Centos Stream 9备份与恢复、实体小主机安装PVE系统、PVE安装Centos Stream 9

最近折腾小主机,搭建项目环境,记录相关步骤 数据无价,丢失难复 1. Centos Stream 9备份与恢复 1.1 系统备份 root权限用户执行进入根目录: cd /第一种方式备份命令: tar cvpzf backup.tgz / --exclude/proc --exclu…

计算机系统基础概述

什么是计算机? 计算机是一种利用电子技术进行信息处理的设备,它能够接收、存储、处理和提供数据。计算机通过执行一系列预定义的指令来处理数据,这些指令通常被称为程序。计算机的核心功能包括算术运算、逻辑判断、数据存储和信息检索 计算…

STM32 通用定时器

一、概述 STM32内部集成了多个定时/计数器,根据型号不同,STM32系列芯片最多包含8个定时/计数器。其中,TIM6、TIM7为基本定时器,TIM2~TIM5为通用定时器,TIM1、TIM8为高级控制定时器。 1.定时器的类型 基本定时器通用定…

微信小程序-npm支持-如何使用npm包

文章目录 1、在内建终端中打开2、npm init -y3、Vant Weapp4、通过 npm 安装5、构建 npm 1、在内建终端中打开 Windows PowerShell 版权所有 (C) Microsoft Corporation。保留所有权利。尝试新的跨平台 PowerShell https://aka.ms/pscore6PS C:\Users\dgq\WeChatProjects\minip…

python泵站设备运行预警信息管理系统

目录 功能介绍具体实现截图技术栈和环境说明python语言解决的思路性能/安全/负载方面核心代码部分展示详细视频演示源码获取方式 功能介绍 用户端 注册登录:用户可以注册账号并登录系统。 西电泵站简介:提供泵站的历史、功能和重要性等详细介绍。 泵站…

余承东直播论道智能驾驶:激光雷达不可或缺,华为ADS 3.0引领安全创新

华为余承东:激光雷达,智能驾驶安全性的关键 9月29日,华为消费者业务集团CEO余承东在一场引人注目的直播中,与知名主持人马东就智能驾驶技术的最新进展进行了深入交流。在这场直播中,余承东针对激光雷达在智能驾驶中的必要性问题,发表了明确且深刻的观点,引发了业界和公众…

在Docker中运行微服务注册中心Eureka

1、Docker简介: 作为开发者,经常遇到一个头大的问题:“在我机器上能运行”。而将SpringCloud微服务运行在Docker容器中,避免了因环境差异带来的兼容性问题,能够有效的解决此类问题。 通过Docker,开发者可…

角色动画——RootMotion全解

1. Unity(2022)的应用 由Animtor组件控制 在Animation Clip下可进行详细设置 ​ 官方文档的介绍(Animation选项卡 - Unity 手册) 上述动画类型在Rag选项卡中设置: Rig 选项卡上的设置定义了 Unity 如何将变形体映射到导入模型中的网格,以便能够将其动画化。 对于人…

Linux驱动开发——LED驱动开发

文章目录 1 概述1.1 说明 2 基础知识2.1 地址映射2.1.1 ioremap函数2.1.2 iounmap函数 2.2 I/O内存访问函数2.2.1 读操作函数2.2.2 写操作函数 3 硬件原理图分析4 RK3568 GPIO驱动原理4.1 引脚复用设置4.2 引脚驱动能力配置4.3 GPIO输入输出设置4.4 GPIO引脚高低电平设置 5 实验…

【GeekBand】C++设计模式笔记5_Observer_观察者模式

1. “组件协作”模式 现代软件专业分工之后的第一个结果是“框架与应用程序的划分”,“组件协作”模式通过晚期绑定,来实现框架与应用程序之间的松耦合,是二者之间协作时常用的模式。典型模式 Template MethodStrategyObserver / Event 2.…

HarmonyOS/OpenHarmony 自定义弹窗页面级层级控制解决方案

关键词:CuntomDialog自定义弹窗、SubWindow子窗口、页面级、弹窗层级控制、鸿蒙、弹窗展示层级异常 问题存在API版本:API10 - API12(该问题已反馈,期望后续官方能增加页面级控制能力) 在正常的鸿蒙app开发过程中&…

aws(学习笔记第二课) AWS SDK(node js)

aws(学习笔记第二课) 使用AWS SDK(node js) 学习内容: 使用AWS SDK(node js) 1. AWS SDK(node js) AWS支持多种SDK开发(除了AWS CLI,还支持其他的SDK) AndroidPythonNode.js(Javas…

约数个数约数之和

好久没发文章了.......不过粉丝还是一个没少...... 今天来看两道超级恶心的数论题目! No.1 约数个数 No.2 约数之和 先来看第一道:约数个数 题目描述 给定 n 个正整数 ai​,请你输出这些数的乘积的约数个数,答案对 10^97 取模 输入格式 第一行包含…

五种IO模型与阻塞IO

一、前言 在网络中通信的本质其实是网络中的两台主机的进程间进行通信,而进程通信的本质就是IO。 IO分为输入(input)和输出(output)站在进程的角度讲,进程出去数据为输出,外部数据进入进程为输…

YOLOv8 基于NCNN的安卓部署

YOLOv8 NCNN安卓部署 前两节我们依次介绍了基于YOLOv8的剪枝和蒸馏 本节将上一节得到的蒸馏模型导出NCNN,并部署到安卓。 NCNN 导出 YOLOv8项目中提供了NCNN导出的接口,但是这个模型放到ncnn-android-yolov8项目中你会发现更换模型后app会闪退。原因…

[ComfyUI]Flux:太强了!任意扩图神器,小红书极致逼真风格出游打卡写实风

随着人工智能技术的不断发展,图像生成与反推技术已经成为了AI领域的一大热点。今天,我们就来为大家详细介绍一款由ComfyUI团队开发的超强图像反推工具——Flux,以及如何使用它实现任意扩图和极致逼真风格出游打卡写实风。 一、Flux&#xff…

【AI大模型】使用Embedding API

一、使用OpenAI API 目前GPT embedding mode有三种,性能如下所示: 模型每美元页数MTEB得分MIRACL得分text-embedding-3-large9,61554.964.6text-embedding-3-small62,50062.344.0text-embedding-ada-00212,50061.031.4 MTEB得分为embedding model分类…