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

红黑树的删除

news 2026/5/17 6:10: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

【独家首发】ElevenLabs乌尔都语语音SDK逆向分析（v2.4.1）：提取未文档化emotion_intensity参数，实现新闻播报级庄严语调控制

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;ElevenLabs乌尔都语语音SDK逆向分析全景概览 ElevenLabs 官方未公开乌尔都语&#xff08;ur-PK&#xff09;的独立语音 SDK&#xff0c;但其 Web API 实际支持该语言的 TTS 合成。通过对官方 JS SDK&am…...

编程新知 2026/5/17 5:39:43

Lua-RTOS-ESP32：用脚本语言快速开发物联网硬件的实践指南

1. 项目概述&#xff1a;当Lua遇上RTOS&#xff0c;在ESP32上构建轻量级物联网开发新范式如果你是一名嵌入式开发者&#xff0c;或者对物联网&#xff08;IoT&#xff09;设备编程感兴趣&#xff0c;那么你一定对ESP32这颗明星芯片不陌生。它凭借强大的双核处理能力、丰富的无线…...

编程新知 2026/5/17 5:17:24

Carapace：统一跨Shell命令行补全的Go语言引擎

1. 项目概述&#xff1a;一个为Shell而生的全能补全引擎 如果你和我一样&#xff0c;每天有超过一半的工作时间是在终端里度过的&#xff0c;那你一定对命令行补全这件事又爱又恨。爱的是&#xff0c;一个恰到好处的补全能让你行云流水&#xff0c;效率倍增&#xff1b;恨的是…...

编程新知 2026/5/17 3:43:41

会话管理封装实践：构建安全可扩展的分布式会话系统

1. 项目概述&#xff1a;一个被低估的会话管理利器如果你是一名开发者&#xff0c;尤其是经常需要处理用户登录、权限校验、状态保持这类“脏活累活”的后端或全栈开发者&#xff0c;那么你一定对“会话管理”这四个字又爱又恨。爱的是&#xff0c;它是构建安全、有状态应用的基…...

编程新知 2026/5/17 3:22:25

渠道输水控制系统模型在环测试【附仿真】

✨ 长期致力于渠道输水、水动力数值模拟、控制系统、模型在环测试、胶东调水工程研究工作&#xff0c;擅长数据搜集与处理、建模仿真、程序编写、仿真设计。 ✅ 专业定制毕设、代码 ✅ 如需沟通交流&#xff0c;点击《获取方式》 &#xff08;1&#xff09;Preissmann四点隐式格…...

编程新知 2026/5/17 2:25:55

VTube Studio API完全指南：5个核心场景教你打造个性化虚拟主播互动

VTube Studio API完全指南&#xff1a;5个核心场景教你打造个性化虚拟主播互动 【免费下载链接】VTubeStudio VTube Studio API Development Page 项目地址: https://gitcode.com/gh_mirrors/vt/VTubeStudio 想要为你的虚拟主播形象添加更多互动功能&#xff0c;却不知道…...

编程新知 2026/5/17 1:56:54

2025最权威的AI辅助论文网站实际效果

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 在学术研究跟论文写作这个领域当中&#xff0c;人工智能工具的兴起给学者和学生带来了从来没…...

编程新知 2026/5/16 23:22:11

基于Kubernetes跑通第一个云原生应用【20260516】002篇

文章目录 📖 理论深潜：Kubernetes 架构与容器底层原理 1. 云原生与 K8s 核心概念 为什么需要 K8s？（从痛点出发） 深度解析：容器底层三大魔法 ① NameSpace（命名空间）：隔离的围墙 ② Cgroups（控制组）：资源的天花板 ③ UnionFS（联合文件系统）：分层的积木 2. K8s 架…...

编程新知 2026/5/16 23:05:38

Mac玩转老游戏：手把手教你用Wineskin配置RPG Maker游戏所需RTP环境

Mac玩转老游戏&#xff1a;手把手教你用Wineskin配置RPG Maker游戏所需RTP环境 在Mac上重温经典RPG游戏是许多怀旧玩家的梦想&#xff0c;但RPG Maker游戏往往依赖Windows特有的运行时包&#xff08;RTP&#xff09;&#xff0c;这让Mac用户望而却步。本文将带你深入探索如何利…...

编程新知 2026/5/16 22:22:24

终极指南：如何让苹果触控板在Windows上获得专业级体验

终极指南&#xff1a;如何让苹果触控板在Windows上获得专业级体验 【免费下载链接】mac-precision-touchpad Windows Precision Touchpad Driver Implementation for Apple MacBook / Magic Trackpad 项目地址: https://gitcode.com/gh_mirrors/ma/mac-precision-touchpad …...

编程新知 2026/5/16 21:47:27