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

红黑树的删除

news 2026/2/10 16:42:34

文章目录

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

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别，但在其他电脑上正常工作时，问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤，帮助你快速找到故障原因： 背景： 一个M-pard（铭豹）扩展坞的网卡突然无法识别了，扩展出来的三个USB接口正常。…...

编程新知 2026/2/9 16:05:07

iOS 26 携众系统重磅更新，但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

编程新知 2026/2/8 20:41:56

stm32G473的flash模式是单bank还是双bank？

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

编程新知 2026/2/8 20:41:51

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

编程新知 2026/2/5 4:25:15

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

编程新知 2026/2/7 17:31:44

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

编程新知 2026/2/2 21:52:33

逻辑回归：给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

编程新知 2025/10/27 21:25:04

（二）TensorRT-LLM | 模型导出（v0.20.0rc3）

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

编程新知 2026/1/24 6:44:11

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

编程新知 2026/1/30 12:10:19

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

编程新知 2025/10/31 5:18:02