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

红黑树删除的实现与四种情况的证明

news 来源：原创 2025/8/3 4:34:14

🧭 学习重点

删除节点的三种情况
红黑树如何恢复性质
四种修复情况
完整可运行的 C++ 实现

一、红黑树删除的基础理解

红黑树删除比插入复杂得多，因为：

删除的是黑节点可能会破坏“从根到叶子黑节点数相等”的性质。
删除红节点无需修复，直接删。
删除黑节点，要么借黑色、要么旋转重构。

二、删除节点的三种基本情况（和 BST 类似）

无子节点（叶子节点）：直接删。
有一个子节点：用子节点替代。
有两个子节点：找到中序后继，用其值替换被删节点，然后删除后继。

注意：红黑树中处理的是“颜色破坏”，不是结构本身。

三、红黑树删除修复目标

恢复五大性质（尤其是黑高一致性）
使用双黑节点表示“临时多了一层黑色”
四种修复方式：兄弟红、兄弟黑侄红、兄弟黑侄黑、旋转变色

四、四种删除修复情况（核心）

设 x 为“被提上来”的节点（可能是 NIL）

✅ Case 1：`x` 的兄弟是红色

P(B)                   S(B)
/    \      =>         /   \
x(B)   S(R)             P(R)  Sr(B)
/  \            /   \
Sl   Sr         x(B)  Sl

父变红，兄变黑，左旋父节点，变成 Case 2~4。

✅ Case 2：`x` 的兄弟是黑色，且两个侄子都是黑色

P(?)
/   \
x(B)  S(B)
/  \
B     B

把 S 变红，x = p，向上传递双黑

✅ Case 3：兄弟黑，近侄子红，远侄子黑

P(?)
/   \
x(B)  S(B)
/
R

先右旋 S，再变成 Case 4

✅ Case 4：兄弟黑，远侄子红

P(?)
/   \
x(B)  S(B)
\
R

左旋 p，交换 p 和 s 颜色，把远侄子设为黑，修复完毕

五、完整 C++ 实现：红黑树删除

我们先定义红黑树结构（含旋转、插入、删除等）：

✅ 树结构和节点定义

#include <iostream>
using namespace std;enum Color { RED, BLACK };struct Node {
int val;
Color color;
Node *left, *right, *parent;Node(int val): val(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

✅ 左旋操作

void leftRotate(Node*& root, Node* x) {Node* y = x->right;x->right = y->left;if (y->left) y->left->parent = x;y->parent = x->parent;if (!x->parent) root = y;else if (x == x->parent->left) x->parent->left = y;else x->parent->right = y;y->left = x;x->parent = y;
}

✅ 右旋操作

void rightRotate(Node*& root, Node* y) {Node* x = y->left;y->left = x->right;if (x->right) x->right->parent = y;x->parent = y->parent;if (!y->parent) root = x;else if (y == y->parent->left) y->parent->left = x;else y->parent->right = x;x->right = y;y->parent = x;
}

✅ 找到最小节点（用于后继替换）

Node* minimum(Node* node) {while (node->left) node = node->left;return node;
}

✅ 删除修复函数

void deleteFixUp(Node*& root, Node* x) {while (x != root && (!x || x->color == BLACK)) {if (x == x->parent->left) {Node* w = x->parent->right;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;leftRotate(root, x->parent);w = x->parent->right;}if ((!w->left || w->left->color == BLACK) &&(!w->right || w->right->color == BLACK)) {w->color = RED;x = x->parent;} else {if (!w->right || w->right->color == BLACK) {if (w->left) w->left->color = BLACK;w->color = RED;rightRotate(root, w);w = x->parent->right;}w->color = x->parent->color;x->parent->color = BLACK;if (w->right) w->right->color = BLACK;leftRotate(root, x->parent);x = root;}} else {// 对称处理Node* w = x->parent->left;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rightRotate(root, x->parent);w = x->parent->left;}if ((!w->left || w->left->color == BLACK) &&(!w->right || w->right->color == BLACK)) {w->color = RED;x = x->parent;} else {if (!w->left || w->left->color == BLACK) {if (w->right) w->right->color = BLACK;w->color = RED;leftRotate(root, w);w = x->parent->left;}w->color = x->parent->color;x->parent->color = BLACK;if (w->left) w->left->color = BLACK;rightRotate(root, x->parent);x = root;}}}if (x) x->color = BLACK;
}

✅ 删除操作主函数

void rbDelete(Node*& root, Node* z) {Node* y = z;Node* x;Color yOriginalColor = y->color;if (!z->left) {x = z->right;transplant(root, z, z->right);} else if (!z->right) {x = z->left;transplant(root, z, z->left);} else {y = minimum(z->right);yOriginalColor = y->color;x = y->right;if (y->parent == z) {if (x) x->parent = y;} else {transplant(root, y, y->right);y->right = z->right;y->right->parent = y;}transplant(root, z, y);y->left = z->left;y->left->parent = y;y->color = z->color;}if (yOriginalColor == BLACK)deleteFixUp(root, x);
}

✅ 替换子树辅助函数

void transplant(Node*& root, Node* u, Node* v) {if (!u->parent) root = v;else if (u == u->parent->left) u->parent->left = v;else u->parent->right = v;if (v) v->parent = u->parent;
}

六、总结与练习建议

删除是红黑树最复杂操作，逻辑较多但结构稳定
建议多画图分析每种情况
自己实现一棵树，从插入到删除，打印中序遍历验证

红黑树删除的实现与四种情况的证明

🧭 学习重点删除节点的三种情况红黑树如何恢复性质四种修复情况完整可运行的 C 实现一、红黑树删除的基础理解红黑树删除比插入复杂得多，因为： 删除的是黑节点可能会破坏“从根到叶子黑节点数相等”的性质。删除红节点无需修复&#xf…...

编程日记 2025/8/3 4:34:14

FHE与后量子密码学

1. 引言近年来，关于后量子密码学（PQC, Post-Quantum Cryptography） 的讨论愈发热烈。这是因为安全专家担心，一旦有人成功研发出量子计算机，会发生什么可怕的事情。由于 Shor 算法的存在，量子计算机将能够…...

编程日记 2025/7/29 19:34:32

使用FastAPI和React以及MongoDB构建全栈Web应用04 MongoDB快速入门

一、NoSQL 概述 1.1 了解关系数据库的局限性 Before diving into NoSQL, it’s essential to understand the challenges posed by traditional Relational Database Management Systems (RDBMS). While RDBMS have been the cornerstone of data management for decades, th…...

编程日记 2025/7/29 19:34:31

C++：this指针

class date { public:void f(int i){} } 以上是我们定义的一个简单的类，这个类里面含有一个简单的成员函数，成员函数看似只有一个参数，实际上是两个参数，除了参数i以外，还有一个指向调用该函数的对象的指针——this指…...

编程日记 2025/7/29 12:05:23

如何在postman使用时间戳

1. 使用 Pre-request Script 动态转换在发送请求前，将日期字符串转为时间戳并存储为环境变量/全局变量。示例代码 // 将日期字符串（如 "2023-10-01"）转为时间戳（毫秒） const dateString "2…...

编程日记 2025/7/29 1:30:20

OCP开闭原则

OCP，software entities(modules,classes,functions,etc.)should be openfor extension, but closed for modification. 软件实体（模块、类和方法等）应该对扩展开发，对修改关闭。 OCP特点提高可扩展性：新功能通过添…...

编程日记 2025/7/26 12:01:06

计算机网络：什么是Mesh组网以及都有哪些设备支持Mesh组网？

Mesh组网技术详解与实现工具推荐 Mesh组网是一种通过多个节点路由器协同工作，形成覆盖全屋的无线网络的技术。它通过动态路径调整、无缝漫游和自愈能力，解决传统单一路由器覆盖不足的问题，尤其适合大户型、多层住宅或复杂户型环境。以下是Mesh组网的核心原理、实现方式及推…...

编程日记 2025/8/3 1:16:03

STM32f103 标准库零基础学习之点灯

前提：你已经下好了标准外设库，如果没有可以去找找教程 ST官网上可以下载目录前提：你已经下好了标准外设库，如果没有可以去找找教程 ST官网上可以下载点灯逻辑 1. 定义 GPIO 初始化结构体 2. 开启GPIOA的时钟…...

编程日记 2025/8/1 16:57:38

uniapp使用ui.request 请求流式输出

正文： 在现代Web开发中，实时数据流和长时间运行的请求变得越来越常见，尤其是在处理大量数据或进行实时通信时。在这种情况下，uniapp 提供的 ui.request 请求方法可以帮助我们轻松实现流式输出请求。本文将介绍如何使用 uni.reques…...

编程日记 2025/7/29 21:51:12

MATLAB安装常见问题及解决方案详解（含代码示例）

MATLAB作为科学计算和工程分析的核心工具，其安装过程可能因操作系统版本、硬件配置或网络环境等因素而出现各种问题。本文基于MATLAB官方文档和社区经验，系统总结了安装过程中常见的问题，并提供详细的解决方案和代码示例，帮助用户…...

编程日记 2025/7/29 5:43:53

【Java ee初阶】网络编程 UDP socket

网络编程 socket api 是传输层提供的api。 UDP 无连接，不可靠传输，面向数据报，全双工。 TCP 有链接，可靠传输，面向字节流，全双工。 UDP socket api 数据报 DatagrammSocket 代表了操作系统中的socket文…...

编程日记 2025/7/30 21:51:40

BeanPostProcessor和AOP

BeanPostProcessor Spring中有一个接口Oredr的getOrder()方法，这个方法返回值是一个int类型，Spring容器会根据这个方法的返回值对容器的多个Processor对象从小到大排序，创建Bean时候依次执行他们的方法，也就是说getOrder()方法的…...

编程日记 2025/7/31 16:17:47

django的权限角色管理(RBAC)

在 Django 中，User、Group 和 Permission 是权限系统的核心组件。下面通过代码示例演示它们的 CRUD（创建、读取、更新、删除） 操作： 一、User 模型 CRUD from django.contrib.auth.models import User# 创建用户 user User.obje…...

编程日记 2025/7/29 21:51:01

vue vite 无法热更新问题

一、在vue页面引入组件CustomEmployeesDialog，修改组件CustomEmployeesDialog无法热更新引入方式： import CustomEmployeesDialog from ../dialog/customEmployeesDialog.vue 目录结构： 最后发现是引入import时，路径大小写与目…...

编程日记 2025/7/31 1:37:41

IBM BAW（原BPM升级版）使用教程第八讲

续前篇！ 一、流程开发功能模块使用逻辑和顺序前面我们已经对流程、用户界面、公开的自动化服务、服务、事件、团队、数据、性能、文件各个模块进行了详细讲解，现在统一进行全面统一讲解。在 IBM Business Automation Workflow (BAW) 中，…...

编程日记 2025/7/29 21:50:57

202534 ｜ KafKa简介+应用场景+集群搭建+快速入门

Apache Kafka 简介一、什么是 Kafka？ Apache Kafka 是一个高吞吐量、分布式、可扩展的流处理平台，用于构建实时数据管道和流应用程序。它最初由 LinkedIn 开发，并于 2011 年开源，目前由 Apache 软件基金会进行维护。 Kafka 具备…...

编程日记 2025/8/1 8:31:45

[思维模式-25]：《本质思考力》-6- 马克思主义哲学的五对基本哲学范畴，以及在计算机领域的体现

一、马克思主义哲学的五对基本哲学范畴， 马克思主义哲学的五对基本哲学范畴是内容与形式、现象与本质、原因与结果、必然性与偶然性、可能性与现实性，以下为具体分析： 内容与形式：组成元素 VS 组成结构内容指构成事物内在要素的…...

编程日记 2025/7/29 21:50:52

6. 存储池配置与CephFS创建 ceph version 14.2.22

6. 存储池配置与CephFS创建 6.1 CRUSH规则管理6.2 纠删码配置6.3 为SSD和HDD创建专用CRUSH规则6.4 创建CephFS存储池6.5 验证存储池配置记录OSD盘符所有节点都执行 7. 客户端挂载CephFS7.1 Ubuntu客户端配置7.2 使用内核驱动挂载7.3 设置开机自动挂载说明：配置Cep…...

编程日记 2025/7/29 21:50:50

RocketMQ Kafka区别

架构 ZooKeeper：管理 Broker 注册、分区 Leader 选举及消费者组状态。Broker：存储 Partition数据，每个 Partition 为独立日志文件。Producer/Consumer：通过 ZooKeeper获取路由信息，实现消息分发与消费。 NameServer&am…...

编程日记 2025/7/29 21:50:48

linux和linux 、linux和windows实现文件复制笔记

前提：两设备得在同一局域网下,且启用了ssh 一、linux和linux实现文件复制从 Ubuntu B 复制文件夹到 Ubuntu A 在 Ubuntu A 上打开终端，执行： scp -r userBubuntuB_IP:/home/userB/folder_to_copy /home/userA/destination/ 二、linux和…...

编程日记 2025/8/2 3:41:25

Flink 运维监控与指标采集实战

一、引言：实时任务为什么必须监控？在实时任务中，任务失败、数据延迟、资源瓶颈往往并非由明显的代码异常引发，而是隐蔽地潜藏在： Kafka 积压无告警 Flink Checkpoint 卡顿却无人知晓反压、TaskManager 内存 OOM 未实时感知为了保障业务 SLA、高可用与可观测性，构建完…...

编程日记 2025/8/3 1:12:05

linux 开发小技巧之git增加指令别名

众所周知，git的指令执行时都得敲好几个字符才能补充上来，比如常用的git status，是不是要将全部的字符一个个地在键盘敲上来，有没有更懒惰点办法，可以将经常用到的git命令通过其他的别名的方式填充，比如刚刚…...

编程日记 2025/7/30 22:19:42

【八股消消乐】项目中如何优化JVM内存分配？

😊你好，我是小航，一个正在变秃、变强的文艺倾年。 🔔本专栏《八股消消乐》旨在记录个人所背的八股文，包括Java/Go开发、Vue开发、系统架构、大模型开发、机器学习、深度学习、力扣算法等相关知识点，期待与你…...

编程日记 2025/8/2 0:47:16

操作系统实验习题解析上篇

孤村落日残霞，轻烟老树寒鸦，一点飞鸿影下。青山绿水，白草红叶黄花。 ————《天净沙秋》白朴【元】目录实验一： 代码： 解析： 运行结果： 实验二： 代码解析 1. 类设计 …...

编程日记 2025/8/3 0:17:36

Yocto中`${B}`变量的作用

在Yocto项目中，${B}是一个关键路径变量，用于指定构建目录（Build Directory），其作用是存放编译过程中生成的中间文件（如Makefile、目标文件、日志等），从而将构建产物与源码目录分离，保持源码环境的独立性^1。具体解析：定义与默认路径默认情况下，${B}的路径为${TM…...

编程日记 2025/7/31 1:36:43

JDBC执行sql过程

1. 加载数据库驱动 JDBC 通过驱动（Driver） 实现与不同数据库的通信。驱动需提前加载到 JVM： 手动加载（JDBC 4.0 前）： Class.forName("com.mysql.cj.jdbc.Driver"); // MySQL 驱…...

编程日记 2025/7/31 14:19:25

python如何提取Chrome中的保存的网站登录用户名密码？

很多浏览器都贴心地提供了保存用户密码功能，用户一旦开启，就不需要每次都输入用户名、密码，非常方便。作为python脚本，能否拿到用户提前保存在浏览器中的用户名密码，用以自动登录呢？必须有，小爬…...

编程日记 2025/8/1 18:39:04

【数据结构入门训练DAY-30】数的划分

文章目录前言一、题目二、解题思路结语前言本次训练内容训练DFS。训练解题思维。一、题目将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n7，k3，下面三种分法被认为是相同的。 {1&a…...

编程日记 2025/8/1 4:58:57

CD37.【C++ Dev】string类的模拟实现(上)

目录 1.string基本知识的回顾 2.简单的模拟实现准备操作代码实现成员变量构造函数 C风格构造的函数无参构造函数 C风格构造的函数与无参构造函数合二为一析构函数 c_str() size() operator[ ] 可读可写只可读 iterator(指针版) begin()和end() 编辑…...

编程日记 2025/7/31 21:04:21

Java代理

一、代理的基本定义 1.什么是Java代理模式:给目标对象提供一个代理对象，并且由代理对象控制对目标对象的引用。 2.类是构建对象的模板下面是最简单的代理实现（这只是一个演示会报错） package 代理;public class xiaoming {public static…...

编程日记 2025/7/29 21:50:23

源码示例：使用SpringBoot+Vue+ElementUI+UniAPP技术组合开发一套小微企业ERP系统

目录一、系统架构设计 1、技术分层 2、开发环境二、快速开发实践 1、后端搭建（Spring Boot） 2、前端管理端（VueElementUI） 3、移动端开发（UniAPP） 三、关键集成方案 1、统一接口处理 2、跨平台…...

编程日记 2025/7/29 21:50:20

.Net Mqtt协议-MQTTNet（一）简介

一、MQTTNet 简介 MQTTnet 是一个高性能的MQTT类库，支持.NET Core和.NET Framework。二、MQTTNet 原理 MQTTnet 是一个用于.NET的高性能MQTT类库，实现了MQTT协议的各个层级，包括连接、会话、发布/订阅、QoS（服务质量&#xff0…...

编程日记 2025/7/29 21:50:17

路由策略和策略路由的区别以及配置案例

区别路由策略：路由策略是通过ACL等方式控制路由发布，让对方学到适当路由条目，比如有20条路由，只想让某个路由器学到10条，可以通过路由策略进行过滤。策略路由：策略路由是通过定义策略和应用&#xff0c…...

编程日记 2025/7/30 9:21:31

【Debian】关于LubanCat-RK3588s开发板安装Debian的一些事

琐碎的事问题不少，甚至一度让我以为核心坏了按照指引烧录完Debian11-gnome镜像后启动，此时输出的分辨率不一定匹配显示器，进而导致黑屏，此时需要使用MobaXterm的串口终端以运行一些指令，下载链接用xrandr指令查看显示…...

编程日记 2025/7/29 21:50:13

vmware环境ORACLE RAC环境数据库节点1无法启动问题分析处理

近期在一个客户数据库巡检时发现ORACLE RAC环境数据库一节点故障，只有二节点在运行。 RAC环境正常安装完成后，后期典型的节点无法启动问题就是私网异常、共享存储异常等，检查机器日志可以快速定位问题；本次问题就是因为心跳网络问…...

编程日记 2025/7/29 21:50:11

前端性能优化全攻略：从基础体验到首屏加载的深度实践

在移动互联网时代，用户体验已成为产品竞争力的核心要素。本文将从基础交互优化和首屏加载专项两个维度，系统梳理前端性能优化的关键策略。（对应图片1的整体框架设计） 一、基础性能优化四维模型 1. 首次打开加速方案 • 资源压缩…...

编程日记 2025/8/2 13:39:24

选对第三方软件测试公司，项目验收成功率提升90%

在当今数字化浪潮中，软件质量已成为企业竞争力的核心要素。然而，软件开发团队往往因资源有限或视角局限，难以全面发现潜在问题。这时，第三方软件测试公司凭借其独立性和专业性，成为企业确保软件质量的关键伙伴。尤其在…...

编程日记 2025/7/29 21:50:05

golang常用库之-protojson 库（json.Marshal 和 protojson.Marshal 序列化对比）

文章目录 golang常用库之-protojson 库（json.Marshal 和 protojson.Marshal 序列化对比）什么是protojson 库什么情况需要用 protojson？ json.Marshal 和 protojson.Marshal 序列化对比简单示例json.Marshal 的潜在问题 (对于 Protobuf 结构体…...

编程日记 2025/7/29 21:50:03

嵌入式学习笔记 - 运算放大器的共模抑制比

一定义共模抑制比（Common Mode Rejection Ratio, ‌CMRR‌）是衡量差分放大器（或差分电路）抑制共模信号能力的关键指标。它在电子工程中尤为重要，特别是在需要处理微弱信号或对抗环境噪声的场景中。核心概念 ‌共…...

编程日记 2025/8/1 15:14:13

Taccel：一个高性能的GPU加速视触觉机器人模拟平台

触觉感知对于实现人类水平的机器人操作能力至关重要。而视觉触觉传感器（VBTS）作为一种有前景的解决方案，通过相机捕捉弹性凝胶垫的形变模式来感知接触的方式，为视触觉机器人提供了高空间分辨率和成本效益。然而，这些传…...

编程日记 2025/8/1 22:55:29

高效Python开发：uv包管理器全面解析

目录 uv简介亮点与 pip、pip-tools、pipx、poetry、pyenv、virtualenv 对比安装uv快速开始uv安装pythonuv运行脚本运行无依赖的脚本运行有依赖的脚本创建带元数据的 Python 脚本使用 shebang 创建可执行文件使用其他package indexes锁定依赖提高可复现性指定不同的 Python 版本…...

编程日记 2025/7/29 21:49:56

PyTorch 线性回归模型构建与神经网络基础要点解析

笔记 1 PyTorch构建线性回归模型 1.1 创建数据集 import torch from torch.utils.data import TensorDataset # 创建x和y张量数据集对象 from torch.utils.data import DataLoader # 创建数据集加载器 import torch.nn as nn # 损失函数和回归函数 from torch.optim impo…...

编程日记 2025/7/31 1:32:26

PyTorch API 2 - 混合精度、微分、cpu、cuda、可视化

文章目录自动混合精度包 - torch.amp自动类型转换参数说明梯度缩放自动转换操作符参考操作符适用性CUDA 操作特定行为可自动转换为 float16 的 CUDA 运算可自动转换为 float32 的 CUDA 运算提升至最宽输入类型的 CUDA 操作优先使用 binary_cross_entropy_with_logits 而非 bi…...

编程日记 2025/8/1 11:12:13

window 显示驱动开发-AGP 类型伸缩空间段

AGP 类型的伸缩空间段类似于线性光圈空间段。但是，内核模式显示微型端口驱动程序（KMD）不会通过 AGP 类型的伸缩空间段公开 dxgkDdiBuildPagingBuffer 回调函数的DXGK_OPERATION_MAP_APERTURE_SEGMENT和DXGK_OPERATION_UNMAP_APERTURE_SEGMEN…...

编程日记 2025/8/1 17:44:06

异地多活单元化架构下的微服务体系

治理服务间的跨IDC调用，而数据库层面还是要跨IDC 服务注册中心拆开、金融要求，距离太远，异地备库，如果延迟没读到数据就可能有资损，IDC3平时不能用，IDC1挂了还是有数据同步问题，IDC3日常维护…...

编程日记 2025/8/1 11:11:47

LinkedList源码解析

添加元素方法 add方法详解 /*E:创建LinkedList对象时泛型中设置好的数据类型e: 传递的参数boolean： 添加成功即为true，添加失败即为false */public boolean add(E e) {// 在链表最后一个结点后面插入新结点(根据待插入元素封装的结点) linkLast(e);/…...

编程日记 2025/7/31 10:57:04

Android 13 使能user版本进recovery

在 debug 版本上，可以在关机状态下，同时按电源键和音量加键进 recovery 。 user 版本上不行。参考使用 build 变体 debug 版本和 user 版本的差别之一就是 ro.debuggable 属性不同。顺着这个思路追踪，找到 bootable/recovery/reco…...

编程日记 2025/7/29 21:49:44

Docker 使用总结及完整示例介绍

以下是一份详细的 Docker 使用总结及完整示例介绍，涵盖基础概念、常用命令和实际应用场景： 一、Docker 核心概念镜像 (Image) 只读模板，用于创建容器。例如：ubuntu:22.04, nginx:alpine 容器 (Container) 镜像的运行实例&#x…...

编程日记 2025/8/1 11:12:21

[Linux]多线程（二）原生线程库---pthread库的使用

[Linux]多线程（二）原生线程库—pthread库的使用水墨不写bug 文章目录一、pthread原生线程库的使用1. pthread_create全面的看待线程返回值2. pthread_join3. pthread_exit对比理解线程退出？1、return退出2、调用C库函数exit()退出3、调用pt…...

编程日记 2025/7/29 21:49:39

1.短信登录

1.0 问题记录 1.0.1 redis 重复 token 问题每次用户登录时，后端会创建一个新的 token 并存入 Redis，但之前登录的 token 还没有过期。这可能会导致以下问题： 1. Redis 中存在大量未过期但实际已不使用的 token2. 同一用户可能有多个有效 …...

编程日记 2025/8/1 11:26:36