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

红黑树的删除

news 2026/3/28 2:06:26

文章目录

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

【LAMMPS实战】从文献到模拟：精准定位与获取ReaxFF反应力场参数文件

1. 初识ReaxFF反应力场&#xff1a;为什么我们需要它&#xff1f; 第一次接触分子动力学模拟时&#xff0c;我完全被各种力场搞晕了。直到遇到需要模拟化学反应的情况&#xff0c;才发现普通的力场根本不够用。这时候ReaxFF反应力场就像救命稻草一样出现了。简单来说&#xff0…...

编程新知 2026/3/28 1:03:35

UniAppX项目数据可视化升级：用lime-echart + ECharts打造高性能图表（从Vue2/Vue3到uni-app-x全流程）

UniAppX高性能数据可视化实战&#xff1a;lime-echart与ECharts的深度整合指南 当移动端数据可视化需求遭遇性能瓶颈时&#xff0c;UniAppX框架与lime-echart的组合正在成为技术决策者的新选择。本文将揭示如何在不同技术栈中实现图表渲染性能的突破性提升&#xff0c;从原理剖…...

编程新知 2026/3/27 23:10:36

联想M920x黑苹果终极指南：从零构建完美macOS系统

联想M920x黑苹果终极指南&#xff1a;从零构建完美macOS系统 【免费下载链接】M920x-Hackintosh-EFI Hackintosh Opencore EFIs for M920x 项目地址: https://gitcode.com/gh_mirrors/m9/M920x-Hackintosh-EFI 你是否想让联想M920x这款紧凑型主机运行macOS系统&#xff…...

编程新知 2026/3/27 21:56:02

告别盲目搜索！Unity大版本升级时，系统化处理API变更的5个步骤

Unity大版本升级的系统化实践&#xff1a;从API变更管理到团队协作优化 当Unity 2023 LTS发布时&#xff0c;某中型游戏团队在升级过程中发现超过40%的脚本因API变更而报错&#xff0c;导致项目停滞两周。这种场景在技术迭代中并不罕见&#xff0c;但大多数团队仍采用"遇到…...

编程新知 2026/3/27 21:54:01

突破传统：用Arduino SI4735库打造全频段数字收音机方案

突破传统&#xff1a;用Arduino SI4735库打造全频段数字收音机方案 【免费下载链接】SI4735 SI473X Library for Arduino 项目地址: https://gitcode.com/gh_mirrors/si/SI4735 你是否曾梦想过亲手打造一台能接收全球广播的专业收音机&#xff1f;面对传统模拟电路的复杂…...

编程新知 2026/3/27 21:29:55

Dual-Tree Agent RAG：可控、可解释、可验证

从文本检索到方法推理的跃迁 传统RAG系统将文档切分为平面文本块&#xff0c;通过向量相似度检索来增强大模型生成。这种模式在简单事实问答中表现良好&#xff0c;却难以应对需要全局结构理解、跨章节整合和方法论复用的复杂创新任务。现有改进方案如RAPTOR&#xff08;层次摘…...

编程新知 2026/3/27 20:17:08

SEER‘S EYE模型辅助计算机组成原理教学：概念可视化与问答

SEERS EYE模型辅助计算机组成原理教学&#xff1a;概念可视化与问答 计算机组成原理这门课&#xff0c;对很多学生来说&#xff0c;就像在学一门“外星语”。CPU、寄存器、流水线、缓存……这些词听起来就够抽象的&#xff0c;更别说理解它们是怎么协同工作的了。传统的教学方…...

编程新知 2026/3/27 19:55:04

白城腾讯广告服务商

在白城&#xff0c;有不少企业想借助腾讯广告拓展业务&#xff0c;这就离不开靠谱的腾讯广告服务商。今天就和大家聊聊白城腾讯广告服务商的那些事儿&#xff0c;长春中网互联技术在这一领域表现就相当不错。白城腾讯广告服务商现状行业报告显示&#xff0c;近几年白城地区对腾…...

编程新知 2026/3/27 19:32:54

YOLOv11分割模型实战：用C++和ONNXRuntime解析‘output0’和‘output1’双输出，实现像素级颜色分析

YOLOv11分割模型实战&#xff1a;C与ONNXRuntime双输出解析与像素级颜色分析 在计算机视觉领域&#xff0c;目标检测与实例分割技术的结合正成为工业应用的新标准。YOLOv11作为YOLO系列的最新成员&#xff0c;不仅延续了其高效检测的特性&#xff0c;更通过双输出结构实现了精准…...

编程新知 2026/3/27 19:30:53

开源像素艺术大模型教程：Pixel Dream Workshop Windows/Mac双平台部署

开源像素艺术大模型教程&#xff1a;Pixel Dream Workshop Windows/Mac双平台部署 1. 像素幻梦创意工坊简介 Pixel Dream Workshop&#xff08;像素幻梦创意工坊&#xff09;是一款基于FLUX.1-dev扩散模型的像素艺术生成工具。它采用独特的16-bit像素风格界面设计&#xff0c…...

编程新知 2026/3/27 19:10:50