当前位置： 首页 > news >正文

红黑树的删除

news 文章来源：https://blog.csdn.net/2301_77838258/article/details/142252912 2025/5/17 17:52:09

文章目录

  • 前言
  • 一.删除的节点左子树右子树都有
  • 二.删除的节点只有左/右子树
    • 删除调整操作
  • 三.删除的节点没有孩子
    • 1.删除的节点为红色
    • 2.删除的节点为黑色
      • 1).兄弟节点为黑色
        • (1).兄弟节点至少有一个红色的孩子节点
          • LL型
          • RR型
          • RL型
          • LR型
        • (2).兄弟节点没有孩子或所有孩子为黑色
      • 2).兄弟节点为红色
  • 完整删除示例

前言

    在之前我们已经学习了红黑树的插入插入操作, 现在我们来学习删除操作, 删除操作比起插入操作更复杂

一.删除的节点左子树右子树都有

    根据二叉搜索树的删除, 找到删除节点的前驱和后继替代删除即可, 替代后就可以转化为后面两种情况, 这里不再详细介绍了

二.删除的节点只有左/右子树

    根据红黑树的特性, 每条路径的黑色节点相同, 不存在连续的红色节点, 所以对于红黑树, 这种删除情况只可能是这样几种, 并且只有一个孩子
在这里插入图片描述
在这里插入图片描述

删除调整操作

    只需让孩子节点替代删除节点, 再变黑即可
比如上图删除后
在这里插入图片描述
在这里插入图片描述

三.删除的节点没有孩子

1.删除的节点为红色

    直接删除即可, 不会破坏红黑树的规则
在这里插入图片描述
删除后
在这里插入图片描述

2.删除的节点为黑色

    删除一个黑色节点, 那么经过这条路径的黑色节点都会少一个, 破坏了黑路同的规则, 这时需要进行调整, 我们需要补上一个黑色节点, 假设当前删除位置有一个黑色节点, 那么现在这棵树还是满足红黑树的规则, 现在我们需要考虑将这个"借"的黑色节点调整
比如

在这里插入图片描述
在这里插入图片描述

1).兄弟节点为黑色

(1).兄弟节点至少有一个红色的孩子节点

    让兄弟节点的孩子的颜色变成兄弟节点的颜色, 兄弟节点的颜色变成父节点的颜色, 父节点变黑, 再根据兄弟节点的位置进行旋转操作

LL型

比如

删除后"借"一个

在这里插入图片描述
变色

在这里插入图片描述
右旋并归还"借"节点
在这里插入图片描述

RR型

在这里插入图片描述
删除后"借"节点
在这里插入图片描述
变色旋转
在这里插入图片描述

RL型

在这里插入图片描述

将兄弟节点的孩子和父节点变色旋转
在这里插入图片描述

LR型

在这里插入图片描述
变色旋转
在这里插入图片描述

(2).兄弟节点没有孩子或所有孩子为黑色

    直接将兄弟节点变红, 然后之前"借"的节点的位置向上移动
比如
在这里插入图片描述
兄弟节点变红, "借"节点上移
在这里插入图片描述
因为"借"节点为根节点, 直接归还
在这里插入图片描述

2).兄弟节点为红色

    兄弟节点为红色, 将兄弟节点和父节点的颜色交换, 相当于向父节点借一个黑色节点, 然后向之前"借"的节点方向旋转

比如在这里插入图片描述
删除后, "借"一个黑色节点保持红黑树规则
在这里插入图片描述

变色
在这里插入图片描述

向"借"的节点方向旋转
在这里插入图片描述

继续调整

在这里插入图片描述

完整删除示例

以下面这颗红黑树举例
在这里插入图片描述

  1. 删除25 是黑色节点, "借"一个节点
    在这里插入图片描述
    发现兄弟节点是黑色并且有一个孩子, 变色旋转调整

在这里插入图片描述
2. 删除15 转化为删除它的直接后继
在这里插入图片描述
删除一个黑色节点, 它的兄弟节点为红色, 兄弟节点和父节点变色, 向删除节点方向旋转

在这里插入图片描述
此时"借"节点兄弟为黑色, 且没有孩子, 变红色, 然后将"节点"向上移
在这里插入图片描述
"借"节点遇到红色节点直接变黑
在这里插入图片描述
3. 删除6
在这里插入图片描述
兄弟节点为黑, 并且有孩子, 变色调整
在这里插入图片描述
4. 删除13
在这里插入图片描述
兄弟节点为黑, 且没有孩子 变色,"借"节点向上调整

在这里插入图片描述
"借"节点兄弟节点为黑,且孩子都为黑色, 变色并调整"借"节点
在这里插入图片描述
归还"借"节点
在这里插入图片描述
5. 删除37在这里插入图片描述
兄弟节点为黑, 且有红色孩子节点
在这里插入图片描述
6. 删除27 转化为删除后继
在这里插入图片描述
"借"节点直接变黑
在这里插入图片描述
7. 删除17 转化为删除后继
在这里插入图片描述
直接删除
在这里插入图片描述
8. 删除34 兄弟节点为黑, 且有红色孩子节点
变色旋转
在这里插入图片描述

  1. 删除9
    兄弟节点为黑色, 且无孩子
    在这里插入图片描述
  2. 删除10
    孩子节点顶上
    在这里插入图片描述

相关文章：

红黑树的删除

文章目录 前言一.删除的节点左子树右子树都有二.删除的节点只有左/右子树删除调整操作 三.删除的节点没有孩子1.删除的节点为红色2.删除的节点为黑色1).兄弟节点为黑色(1).兄弟节点至少有一个红色的孩子节点LL型RR型RL型LR型 (2).兄弟节点没有孩子或所有孩子为黑色 2).兄弟节点…...

编程日记 2024/9/15 6:16:51

Vue3+setup实现父子组件单表增删改查写法模板

父组件写法 <el-card><!-- el-card 头部插槽 显示列表名和新增按钮 --><template #header><div class"table-header-container"><i class"fas fa-th" />角色列表&#xff08;100&#xff09;<span style"flex-grow…...

编程日记 2024/9/15 6:15:51

jmeter 录制APP脚本

一、手机 1、修改网络 代理选择手动→填写服务器主机名&#xff08;电脑IP&#xff0c;如&#xff1a;192.1xx.x.xx&#xff09;→服务器端口&#xff08;任意未被占用端口&#xff0c;如&#xff1a;8888&#xff09; 2、安装证书 手机浏览器访问服务器主机名:服务器端口&a…...

编程日记 2024/9/15 6:14:50

C++类与对象深度解析（一）：从抽象到实践的全面入门指南

文章目录 C 类与对象——详细入门指南前言1. 类的定义1.1 类定义的基本格式示例代码解释 1.2 访问限定符示例代码解释 1.3 类域示例代码解释 1.4 成员命名规范常见的命名约定&#xff1a;示例&#xff1a;拓展&#xff1a; 1.5 class与struct的默认访问权限示例&#xff1a; 2.…...

编程日记 2024/9/15 6:13:49

docker拉取 jdk 8

docker pull openjdk:8docker run -d -it --name java-8 openjdk:8docker run -d -it --name java-8 openjdk:8 –name java-8 容器名&#xff0c;自定义的 openjdk:8 镜像名&#xff1a;标签名 &#xff0c; 使用 docker images 查看 2、查看已运行的容器实例&#xff1a; doc…...

编程日记 2024/9/15 6:12:48

机器学习VS深度学习

机器学习&#xff08;Machine Learning, ML&#xff09;和深度学习&#xff08;Deep Learning, DL&#xff09;是人工智能&#xff08;AI&#xff09;的两个子领域&#xff0c;它们有许多相似之处&#xff0c;但在技术实现和应用范围上也有显著区别。下面从几个方面对两者进行区…...

编程日记 2024/9/15 6:10:45

基于vue框架的宠物交流平台1n2n3（程序+源码+数据库+调试部署+开发环境）系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;会员,宠物信息,宠物类型,团队信息,申请领养,团队申请,领养宠物 开题报告内容 基于Vue框架的宠物交流平台开题报告 一、项目背景 随着现代生活节奏的加快与人们情感需求的日益增长&#xff0c;宠物已成为众多家庭不可或缺的重要成员。…...

编程日记 2024/9/15 6:09:45

Rust 所有权 借用与引用

文章目录 发现宝藏1. 所有权&#xff08;Ownership&#xff09;2. 引用&#xff08;References&#xff09;2.1 不可变引用2.2 可变引用2.3 引用的规则 3. 悬垂引用&#xff08;Dangling References&#xff09;4. 借用&#xff08;Borrowing&#xff09;结论 发现宝藏 前些天…...

编程日记 2024/9/15 6:07:43

构建智能电商新生态：深度解析京东商品详情API的力量

在当今数字化浪潮中&#xff0c;智能电商系统已成为推动零售业转型升级的重要引擎。作为电商行业的领军者之一&#xff0c;京东凭借其庞大的商品数据库和先进的技术架构&#xff0c;为开发者与商家提供了丰富的API接口&#xff0c;其中商品详情API无疑是构建智能电商系统的关键…...

编程日记 2024/9/15 6:06:42

Golang | Leetcode Golang题解之第398题随机数索引

题目&#xff1a; 题解&#xff1a; type Solution []intfunc Constructor(nums []int) Solution {return nums }func (nums Solution) Pick(target int) (ans int) {cnt : 0for i, num : range nums {if num target {cnt // 第 cnt 次遇到 targetif rand.Intn(cnt) 0 {ans …...

编程日记 2024/9/15 6:05:41

使用注意力机制可以让你的模型更加灵活，但是需要额外的计算资源。rnn lstm bilstm attension

确实&#xff0c;使用注意力机制可以使模型更加灵活&#xff0c;但也确实需要额外的计算资源。注意力机制允许模型在处理序列数据时&#xff0c;能够动态地关注不同位置的重要性&#xff0c;从而更好地捕捉长依赖关系。下面是一个简单的注意力机制实现示例&#xff0c;可以帮助…...

编程日记 2024/9/15 6:04:40

git命令大全

简介&#xff1a;个人学习分享&#xff0c;如有错误&#xff0c;欢迎批评指正 一、Git操作流程 1、代码提交和同步代码 第零步: 工作区与仓库保持一致第一步: 文件增删改&#xff0c;变为已修改状态第二步: git add &#xff0c;变为已暂存状态 $ git status $ git add --al…...

编程日记 2024/9/15 6:03:39

【数据仓库】数据仓库常见的数据模型——范式模型

目录 一、范式 1、第一范式 2、第二范式 3、第三范式 4、进一步范式化&#xff1a;BCNF、4NF 和 5NF 简介 &#xff08;1&#xff09;Boyce-Codd 范式&#xff08;BCNF&#xff09; &#xff08;2&#xff09;第四范式&#xff08;4NF&#xff09; &#xff08;5&#x…...

编程日记 2024/9/15 6:02:38

【LeetCode每日一题】——LCR 078.合并 K 个升序链表

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目注意】六【题目示例】七【题目提示】八【解题思路】九【时间频度】十【代码实现】十一【提交结果】 一【题目类别】 优先队列 二【题目难度】 困难 三【题目编号】 LCR 078.合并 K 个升序链表 …...

编程日记 2024/9/15 6:00:37

代码随想录算法训练营第五十九天 | dijkstra（堆优化版）精讲

目录 dijkstra&#xff08;堆优化版&#xff09;精讲 思路 堆优化细节 方法一&#xff1a; 最小堆优化 dijkstra&#xff08;堆优化版&#xff09;精讲 题目链接&#xff1a;卡码网&#xff1a;47. 参加科学大会 文章讲解&#xff1a;代码随想录 小明是一位科学家&#x…...

编程日记 2024/9/15 5:58:10

go语言后端开发学习(七)——如何在gin框架中集成限流中间件

一.什么是限流 限流又称为流量控制&#xff08;流控&#xff09;&#xff0c;通常是指限制到达系统的并发请求数。 我们生活中也会经常遇到限流的场景&#xff0c;比如&#xff1a;某景区限制每日进入景区的游客数量为8万人&#xff1b;沙河地铁站早高峰通过站外排队逐一放行的…...

编程日记 2024/9/15 5:57:09

SpringBoot2：web开发常用功能实现及原理解析-整合EasyExcel实现Excel导入导出功能

1、工程包结构 主要是这5个Java类 2、导入EasyExcel包 这里同时贴出其他相关springboot的基础包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId></dependency><depend…...

编程日记 2024/9/15 5:56:08

CTFShow-信息搜集

Web1&#xff1a; ​ 题目描述&#xff1a;开发注释未及时删除 。 ​ 打开题目后提示web1:where is flag? ​ ctrlu读取源码。 Web2&#xff1a; ​ 题目描述&#xff1a;js前台拦截 无效操作 ​ 打开题目后显示&#xff1a;无法查看源代码 ​ 右键无法用&#xff0c;…...

编程日记 2024/9/15 5:53:02

Facebook的虚拟现实功能简介：社交网络的新前沿

在科技飞速发展的今天&#xff0c;虚拟现实&#xff08;VR&#xff09;已经从科幻小说中的梦想变成了触手可及的现实。作为全球领先的社交平台&#xff0c;Facebook&#xff08;现已更名为Meta&#xff09;正大力推动虚拟现实技术的发展&#xff0c;以重新定义用户的社交体验。…...

编程日记 2024/9/15 5:52:01

Redis embstr 编码

embstr 编码 是 Redis 中一种优化存储小型字符串的编码方式。它是 Redis 内部存储字符串的多种方式之一&#xff0c;特别适用于存储长度不超过 44 字节的小字符串。...

编程日记 2024/9/15 5:51:00

【Elasticsearch系列二】安装 Kibana

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

编程日记 2024/9/15 5:49:59

中国电子学会202403青少年软件编程（Python）等级考试试卷（三级）真题与解析

202403Python 三级真题 一、选择题 1.在 Python 中，hex(2023)的功能是？（ ） A.将十进制数 2023 转化为十六进制数 B.将十进制数 2023 转化为八进制数 C.将十六进制数 2023 转化为十进制数 D.将八进制数 2023 转化为十进制数 2.下列表达式的值与其他三个选项不相…...

编程日记 2024/9/15 5:48:58

k8s 资源管理

文章目录 ResourceQuota什么是资源配额定义一个ResourceQuotaResourceQuota的使用 LimitRangeLimitRange的用途示例1&#xff1a;配置默认的requests和limits示例2&#xff1a;配置requests和limits的范围 QoS什么是服务质量保证示例1&#xff1a;实现QoS为Guaranteed的Pod示例…...

编程日记 2024/9/15 5:47:57

演示：基于WPF的自绘的中国地铁轨道控件

一、目的&#xff1a;演示一个基于WPF的自绘的中国地铁轨道控件 二、效果演示 北京地铁 成都地铁 上海地铁 深圳地铁 南京地铁 长春地铁 哈尔滨地铁 武汉地铁 厦门地铁 香港地铁 三、功能 支持平移、缩放等操作 鼠标悬停显示线路信息和站点信息 按表格显示&#xff0c;按纸张…...

编程日记 2024/9/15 5:46:56

设计模式（Design Patterns）

设计模式&#xff08;Design Patterns&#xff09;是软件开发人员在软件设计过程中面临的一般性问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。设计模式的目的是为了提高代码的可重用性、可维护性、可读性、可靠性以及灵活性。设…...

编程日记 2024/9/15 5:44:55

C++：opencv生成结构元素用于膨胀腐蚀等cv::getStructuringElement

cv::getStructuringElement 是 OpenCV 库中用于生成结构元素的函数。结构元素在形态学操作中&#xff08;如膨胀、腐蚀、开运算、闭运算等&#xff09;扮演着关键角色。这个函数可以创建不同形状和尺寸的结构元素&#xff0c;以适应不同的图像处理需求。 函数原型 cv::Mat cv…...

编程日记 2024/9/15 5:43:54

最大余额法，解决百分比计算相加不等于100%(扇形/饼图百分比使用的此算法)

在开发项目的过程中有时候需要进行计算百分比&#xff0c;例如计算饼状图百分比。有时候在计算的过程中常规四舍五入计算会发生所有计算的值相加不等于100%的情况 这是 get_percent_value 函数的 JavaScript 版本&#xff1a; /*** 最大余额法&#xff0c;解决百分比计算相加不…...

编程日记 2024/9/15 5:39:51

哈希表简单介绍

概念 在顺序结构以及平衡树中&#xff0c;元素关键字与他们存储的位置并没有直接的映射关系&#xff0c;从而会影响查找关键字的效率&#xff0c;顺序结构中查找关键字的时间复杂度为O&#xff08;N&#xff09;&#xff0c;平衡树查找关键字的时间复杂度为O&#xff08;log2^…...

编程日记 2024/9/15 5:38:50

kafka 之 本地部署单机版

安装JDK 查看你选择的版本需要安装哪一个版本的jdk 网址 下载 JDK下载 注&#xff1a;如果网页不允许下载&#xff0c;使用wget命令下载即可&#xff0c;下载之后安装。 建议使用rpm安装&#xff0c;之后使用 update-alternatives --config java 控制当前环境使用Java的版…...

编程日记 2024/9/15 5:37:47

开发一款通过蓝牙连接控制水电表的微信小程序

增强软硬件交互 为了更好的解决师生生活中的实际问题&#xff0c;开发蓝牙小程序加强了和校区硬件的交互。 比如通过蓝牙连接控制水电表&#xff0c;减少实体卡片的使用。添加人脸活体检测功能&#xff0c;提高本人认证效率&#xff0c;减少师生等待时间。 蓝牙水电控展示 蓝…...

编程日记 2024/9/15 5:35:46