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

红黑树的删除

news 2025/8/23 13:42:02

文章目录

  • 前言
  • 一.删除的节点左子树右子树都有
  • 二.删除的节点只有左/右子树
    • 删除调整操作
  • 三.删除的节点没有孩子
    • 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

Python｜GIF 解析与构建（5）：手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

编程新知 2025/6/27 2:57:24

MPNet：旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块（MBFM） 2.2 残差注意力金字塔模块（RAPM） 2.2.1 空间金字塔注意力（SPA） 2.2.2 金字塔残差块（PRBlock） 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

编程新知 2025/8/20 19:23:33

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

编程新知 2025/8/5 22:19:11

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

编程新知 2025/8/11 10:05:03

CMake基础：构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

编程新知 2025/8/22 4:15:28

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

编程新知 2025/8/22 3:59:16

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持，SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库（解决显示问题） sudo apt install fonts-wqy…...

编程新知 2025/6/19 4:31:50

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件，或者在构建过程中仍然引用了旧的路…...

编程新知 2025/8/22 4:52:59

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

编程新知 2025/8/22 5:18:11

Netty从入门到进阶（二）

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

编程新知 2025/8/22 5:22:57