【计算机基础——数据结构——红黑树】

1. 红黑树(RBTree)

为什么HashMap不直接使用AVL树,而是选择了红黑树呢?

由于AVL树必须保证左右子树平衡,Max(最大树高-最小树高) <= 1,所以在插入的时候很容易出现不平衡的情况,一旦这样,就需要进行旋转以求达到平衡。正是由于这种严格的平衡条件,导致AVL需要花大量时间在调整上,故AVL树一般使用场景在于查询场景, 而不是 增加删除 频繁的场景。

红黑树(rbt)做了什么优化呢?

红黑树(rbt)继承了AVL可自平衡的优点,同时, 红黑树(rbt)在查询速率和平衡调整中寻找平衡,放宽了树的平衡条件,从而可以用于增加删除 频繁的场景。在实际应用中,红黑树的使用要多得多。

与AVL树相比,红黑树牺牲了部分平衡性,以换取插入/删除操作时较少的旋转操作,整体来说性能要优于AVL树。虽然RBTree是复杂的, 但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的:

1.1 红黑树的特性(5条原则)

口诀:根黑叶黑,非红即黑,红黑相连,黑数相等

  • 节点非黑即红
  • 根节点一定是黑色
  • 叶子节点(nil)一定是黑色
  • 每个红色节点的两个子节点都为黑色。(等价于每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点。

RBT有点属于一种空间换时间类型的优化
在avl的节点上,增加了 颜色属性的 数据,相当于 增加了空间的消耗。 通过颜色属性的增加, 换取,后面平衡操作的次数 减少。

  • 红色属性 说明,红色节点的孩子,一定是黑色。 但是,RBTree 黑色节点的孩子,可以是红色,也可以是黑色。
  • 叶子属性 说明, 叶子节点可以是空nil ,AVL的叶子节点不是空的,具体如下图。
    在这里插入图片描述

基于上面的原则,我们一般在插入红黑树节点的时候,会将这个节点设置为红色,

原因参照最后一条原则: 红色破坏原则的可能性最小,如果是黑色, 很可能导致这条支路的黑色节点比其它支路的要多1,破坏了平衡。

1.2 黑色完美平衡

红黑树并不是一颗AVL平衡二叉搜索树,从图上可以看到,根节点P的左子树显然比右子树高

根据 红黑树的特性5,从任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点, 说明:

rbt 的 左子树和右子树的黑节点的层数是相等的
红黑树的平衡条件,不是以整体的高度来约束的,而是以黑色节点的高度,来约束的。

在这里插入图片描述
去掉 rbt中的红色节点,会得到 一个四叉树, 从根节点到每一个叶子,高度相同,就是rbt的root到叶子的黑色路径长度。

1.3 红黑树的恢复平衡过程的三个操作

一旦红黑树5个原则有不满足的情况,我们视为平衡被打破,如何恢复平衡?

1.3.1 变色

节点的颜色由红变黑或由黑变红。(这个操作很好了解)

1.3.2 左旋

以某个结点作为支点(pivot),其父节点(子树的root)旋转为自己的左子树(左旋),pivot的原左子树变成 原root节点的 右子树,pivot的原右子树保持不变。
在这里插入图片描述

1.3.3 右旋

以某个结点作为支点(pivot),其父节点(子树的root)旋转为自己的右子树(右旋),pivot的原右子树变成 原root节点的 左子树,pivot的原左子树保持不变。
在这里插入图片描述

2. 红黑树插入节点情况分析

默认新插入的节点为红色,因为父节点为黑色的概率较大,插入新节点为红色,可以避免颜色冲突。

2.1 红黑树为空树

直接把插入结点作为根节点就可以了。
另外:根据红黑树性质 2根节点是黑色的。还需要把插入节点设置为黑色。

2.2 插入节点的Key已经存在

更新当前节点的值,为插入节点的值。
在这里插入图片描述

2.3 插入节点的父节点为黑色

由于插入的节点是红色的,当插入节点的父节点是黑色时,不会影响红黑树的平衡,所以: 直接插入无需做自平衡(因为每个节点自带两个Nil黑色节点)。
在这里插入图片描述

2.4 插入节点的父节点为红色

根据性质2:根节点是黑色。

如果插入节点的父节点为红色节点,那么该父节点不可能为根节点,所以插入节点总是存在祖父节点(三代关系)。

根据性质4:每个红色节点的两个子节点一定是黑色的。不能有两个红色节点相连。
此时会出现两种状态:

  • 父亲和叔叔为红色
  • 父亲为红色,叔叔为黑色

在这里插入图片描述

2.4.1 父亲和叔叔为红色节点

根据性质4:红色节点不能相连 ==》祖父节点肯定为黑色节点:
父亲为红色,那么此时该插入子树的红黑树层数的情况是:黑红红。
因为不可能同时存在两个相连的红色节点,需要进行 变色, 显然处理方式是把其改为:红黑红

变色处理:黑红红 ==> 红黑红

  1. 将F和V节点改为黑色
  2. 将P改为红色
  3. 将P设置为当前节点,进行后续处理

在这里插入图片描述
可以看到,将P设置为红色了,如果P的父节点是黑色,那么无需做处理;
但如果P的父节点是红色,则违反红黑树性质了,所以需要将P设置为当前节点,继续插入操作, 做自平衡处理,直到整体平衡为止。

2.4.2 叔叔为黑色,父亲为红色,并且父亲节点是祖父节点的左子节点

在这里插入图片描述

2.4.2.1 插在父亲的左节点(LL型失衡)

细分场景 1: 新插入节点,为其父节点的左子节点(LL红色情况), 插入后 就是LL 型失衡
在这里插入图片描述

  1. 变颜色:将F设置为黑色,将P设置为红色
  2. 对F节点进行右旋
    在这里插入图片描述
2.4.2.2 插在父亲的右节点(LR型失衡)

细分场景 2: 新插入节点,为其父节点的右子节点(LR红色情况), 插入后 就是LR 型失衡
在这里插入图片描述

  1. 对F进行左旋
  2. 将F设置为当前节点,得到LL红色情况
  3. 按照LL红色情况处理(1.变色 2.右旋P节点)

在这里插入图片描述

2.4.3 叔叔为黑节点,父亲为红色,并且父亲节点是祖父节点的右子节点

在这里插入图片描述

2.4.3.1 RR型失衡

新插入节点,为其父节点的右子节点(RR红色情况)
在这里插入图片描述
自平衡处理:
1.变色:将F设置为黑色,将P设置为红色
2.对P节点进行左旋
在这里插入图片描述

2.4.3.2 RL型失衡

新插入节点,为其父节点的左子节点(RL红色情况)
在这里插入图片描述
自平衡处理:

  1. 对F进行右旋
  2. 将F设置为当前节点,得到RR红色情况
  3. 按照RR红色情况处理(1.变色 2.左旋 P节点)
    在这里插入图片描述

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

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

相关文章

【MatLab手记】 --从0到了解超超超详过程!!!

文章目录 MatLab笔记一、命令行窗口二、变量命名规则三、数据类型1. 数字2. 字符与字符串3. 矩阵3.1 矩阵创建3.2 矩阵的修改和删除3.3 矩阵的拼接与重构重排3.4 矩阵的运算方法3.5 矩阵的下标 4. 元胞数组&#xff08;类似数据容器&#xff09;5. 结构体 四、逻辑与流程控制五…

Qt_day5_常用类

常用类 目录 1. QString 字符串类&#xff08;掌握&#xff09; 2. 容器类&#xff08;掌握&#xff09; 2.1 顺序容器QList 2.2 关联容器QMap 3. 几种Qt数据类型&#xff08;熟悉&#xff09; 3.1 跨平台数据类型 3.2 QVariant 统一数据类型 3.3 QStringList 字符串列表 4. QD…

【THM】linux取证 DisGruntled

目录 0x00 房间介绍 0x01 连接并简单排查 0x02 让我们看看做没做坏事 0x03 炸弹已埋下。但何时何地&#xff1f; 0x04 收尾 0x05 结论 0x00 房间介绍 嘿&#xff0c;孩子&#xff01;太好了&#xff0c;你来了&#xff01; 不知道您是否看过这则新闻&#xff0c;我…

MFC中Excel的导入以及使用步骤

参考地址 在需要对EXCEL表进行操作的类中添加以下头文件&#xff1a;若出现大量错误将其放入stdafx.h中 #include "resource.h" // 主符号 #include "CWorkbook.h" //单个工作簿 #include "CRange.h" //区域类&#xff0c;对Excel大…

智能化温室大棚控制系统设计(论文+源码)

1 系统的功能及方案设计 本次智能化温室大棚控制系统的设计其系统整体结构如图2.1所示&#xff0c;整个系统在器件上包括了主控制器STC89C52&#xff0c;温湿度传感器DHT11&#xff0c;LCD1602液晶&#xff0c;继电器&#xff0c;CO2传感器&#xff0c;光敏电阻&#xff0c;按…

一篇文章教会你使用Linux的‘sed‘基础命令

Linux sed 命令详解 Linux sed 命令详解1、基本语法2、常用命令2.1 替换2.2 删除行2.3 查找并打印行2.4 插入与追加2.5 多命令组合 3、高级用法3.1 替换并保存结果到新文件3.2 在范围内替换3.3 正则表达式匹配 4、小结 Linux sed 命令详解 sed 是 Linux 系统中非常强大的流编辑…

集群化消息服务解决方案

目录 集群化消息服务解决方案项目概述架构图使用说明服务端通过API接口推送消息给客户端调用方式 请求参数返回参数 客户端推送消息连接websocket或发送消息 接收消息项目地址作者信息 集群化消息服务解决方案 项目概述 集群化消息服务解决方案是一种用于处理大量消息的高可用…

elementUI 点击弹出时间 date-picker

elementUI的日期组件&#xff0c;有完整的UI样式及弹窗&#xff0c;但是我的页面不要它的UI样式&#xff0c;点击的时候却要弹出类似的日期选择器&#xff0c;那怎么办呢&#xff1f; 以下是elementUI自带的UI风格&#xff0c;一定要一个输入框来触发。 这是我的项目中要用到的…

【go从零单排】go中的三种数据类型array、slices、maps

Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 array数组 package mainimport "fmt"func main() {var a [5]int //var关键字定义数组&#xff0c;[5]表…

科技改变阅读习惯:最新研究揭示电子阅读器的普及趋势

据QYResearch调研团队最新报告“全球电子阅读器市场报告2023-2029”显示&#xff0c;预计2029年全球电子阅读器市场规模将达到6.9亿美元&#xff0c;未来几年年复合增长率CAGR为0.4%。 如上图表/数据&#xff0c;摘自QYResearch最新报告“全球电子阅读器市场研究报告2023-2029.…

解决 VSCode 中 C/C++ 编码乱码问题的两种方法

解决 VSCode 中 C/C 编码乱码问题的两种方法 在中国地区&#xff0c;Windows 系统中的 cmd 和 PowerShell 默认编码是 GBK&#xff0c;但 VSCode 默认使用 UTF-8 编码。这种编码不一致会导致在 VSCode 终端中运行 C/C 程序时出现乱码。以下介绍两种方法来解决这一问题。 方法…

UE5遇到问题记录

问题描述&#xff1a; 在让敌人自动追踪玩家的时候一开始运行就会播放攻击的动画 解决方法&#xff1a; 这样是因为敌人一开始就检测到自己了&#xff0c;所以触发动画。 方式一&#xff1a;加一个条件 方式二&#xff1a;改一下碰撞预设

内网对抗-信息收集篇SPN扫描DC定位角色区域定性服务探针安全防护凭据获取

知识点&#xff1a; 1、信息收集篇-网络架构-出网&角色&服务&成员 2、信息收集篇-安全防护-杀毒&防火墙&流量监控 3、信息收集篇-密码凭据-系统&工具&网站&网络域渗透的信息收集&#xff1a; 在攻防演练中&#xff0c;当完成边界突破后进入内…

基于Matlab 疲劳驾驶检测

Matlab 疲劳驾驶检测 课题介绍 该课题为基于眼部和嘴部的疲劳驾驶检测。带有一个人机交互界面GUI&#xff0c;通过输入视频&#xff0c;分帧&#xff0c;定位眼睛和嘴巴&#xff0c;通过眼睛和嘴巴的张合度&#xff0c;来判别是否疲劳。 二、操作步骤 第一步&#xff1a;最…

11.11 代码块

一 java 1.代码块 1&#xff09; 理解 使用构造器时&#xff1a;先默认 调用代码块内容 再调用 构造器内容【代码块 > 构造器】 1.1 细节 1&#xff09;静态代码块 只能加载一次 2&#xff09;先调用父类代码块 再子类代码块 3&#xff09;静态代码块是随着类加载而执行…

在gitlab,把新分支替换成master分支

1、备份master分支&#xff0c;可以打tag 2、删除master分支 正常情况下&#xff0c;master分支不允许删除&#xff0c;需要做两个操作才能删除 a、变更项目默认分支为非master分支&#xff0c;可以先随便选择 b、取消master为非保护分支 操作了上述两步&#xff0c;就可以删…

在使用element中的抽屉<el-drawer>页签<el-tabs/>组合时,echarts图表宽度显示异常问题

类似这种情况&#xff0c;宽度异常 原因&#xff1a;在展示出抽屉时&#xff0c;图表的组件一件初始化了&#xff0c;导致他的宽度提前设定好了&#xff08;我默认的style"width: 100%; height: 300px;"&#xff09;&#xff0c;我得解决方法有2个&#xff1a; 1、第…

《大模型应用开发极简入门》笔记

推荐序 可略过不看。 初识GPT-4和ChatGPT LLM概述 NLP的目标是让计算机能够处理自然语言文本&#xff0c;涉及诸多任务&#xff1a; 文本分类&#xff1a;将输入文本归为预定义的类别。自动翻译&#xff1a;将文本从一种语言自动翻译成另一种语言&#xff0c;包括程序语言。…

Unicode字符集(万国码)

1.三种编码方式&#xff1a; UTF-16&#xff1a;16个bit位&#xff08;2个字节&#xff09;存储 UTF-32&#xff1a;32个bit位&#xff08;4个字节&#xff09;存储 UTF-8&#xff1a;可变长度字符编码。1-4个字节存储&#xff0c;只需记住&#xff1a;英文字母1个字节表示&…

支持 Win10 的网络环境模拟(丢包,延迟,带宽)

升级 Windows 10 以后&#xff0c;原来各种网络模拟软件都挂掉了&#xff0c;目前能用的就是只有 clumsy&#xff1a; 唯一问题是不支持模拟带宽&#xff0c;那么平时要模拟一些糟糕的网络情况的话&#xff0c;是不太方便的&#xff0c;而开虚拟机用 Linux tc 或者设置个远程 l…