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

手撕红黑树的 左旋 与 右旋

news 来源：原创 2025/8/5 5:29:31

一、为什么需要旋转？

在红黑树中，插入或删除节点可能会破坏其五条性质，比如高度不平衡或连续红节点。

为了恢复红黑性质，我们采用局部旋转来“调整树形结构”，保持平衡。

二、旋转本质是“局部变形”

  • 左旋和右旋不会破坏中序遍历结果（即元素仍是有序的）
  • 旋转只是在三到四个节点之间调整指针结构

三、🔄 左旋（Left Rotation）

目的：把某个节点往上提，把右子节点放下来

对节点 x 做左旋，即把 x 的右子节点 y 转换为其父节点，y 的左子树转为 x 的右子树。

✅ 前提：
  • 节点 x 有一个右子节点 y
📌 结构变化图：
原始结构：             旋转后结构：x                      y
\                    /
y       -->        x
/                      \
T1                      T1
🔧 伪代码（C++ 风格）：
Node* leftRotate(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;return y;
}

四、🔁 右旋（Right Rotation）

目的：把某个节点往上提，把左子节点放下来

对节点 y 做右旋，即把 y 的左子节点 x 转换为其父节点，x 的右子树转为 y 的左子树。

✅ 前提：
  • 节点 y 有一个左子节点 x
📌 结构变化图：
原始结构：             旋转后结构：y                    x
/                      \
x         -->           y
\                    /
T1                T1
🔧 伪代码（C++ 风格）：
Node* rightRotate(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;return x;
}

五、动手建议

手动画出下面结构并旋转：

         10\20\30

此时你对 10 进行左旋，会得到：

         20/  \10    30

六、应用场景提示

  • 左旋和右旋是红黑树维护性质的唯一“结构性操作”
  • 接下来我们讲：插入时的三种情况 + 旋转修复方式

✅ 小测试

  1. 红黑树为什么旋转后仍能保持 BST 的性质？
  2. 左旋后，原节点的右子节点发生了什么变化？
  3. 红黑树旋转是否会破坏红黑性质？

相关文章：

手撕红黑树的 左旋 与 右旋

一、为什么需要旋转？ 在红黑树中，插入或删除节点可能会破坏其五条性质，比如高度不平衡或连续红节点。 为了恢复红黑性质，我们采用局部旋转来“调整树形结构”，保持平衡。 二、旋转本质是“局部变形” 左旋和右旋不会…...

编程日记 2025/8/5 5:29:31

Java——反射

目录 5 反射 5 反射 类信息：方法、变量、构造器、继承和实现的类或接口。反射：反射是 Java 中一项强大的特性，它赋予了程序在运行时动态获取类的信息，并能够调用类的方法、访问类的字段以及操作构造函数等的能力。通过反射&#…...

编程日记 2025/8/5 5:26:57

一文了解Python中的requests库：网络交互的基础

目录 1. 前言 2. requests库的基本概念 3. requests库的适应场景 4. requests库的基本使用 4.1 安装requests 4.2 发送第一个请求 4.3 常见HTTP请求方法 4.4 响应对象的属性 4.5 发送带参数的请求 4.6 处理请求和响应 5. 高级功能 5.1 文件上传 5.2 会话对象 5.3…...

编程日记 2025/7/31 11:28:34

基于大模型预测的足月胎膜早破行阴道分娩全流程研究报告

目录 一、引言 1.1 研究背景与意义 1.2 研究目的与方法 1.3 研究创新点 二、胎膜早破（足月）行阴道分娩概述 2.1 胎膜早破定义与分类 2.2 足月胎膜早破行阴道分娩的现状与挑战 2.3 大模型预测引入的必要性 三、大模型预测原理与技术 3.1 大模型介绍 3.2 数据收集与…...

编程日记 2025/8/5 5:26:56

ISP流程介绍(Raw格式阶段)

一、ISP之DPC DPC(Defective Pixel Correction)也就是坏点矫正，在sensor接收光信号，并做光电转换之后。 这一步设计的意义在于：摄像头sensor的感光元件通常很多会存在一些工艺缺陷缺陷，让图像上某些像素无法正常收集到需要的光信号…...

编程日记 2025/8/5 5:23:06

Codeforces Round 1023 (Div. 2)

Dashboard - Codeforces Round 1023 (Div. 2) - Codeforces 一个构造问题&#xff0c;我把最大的数放在一个数组&#xff0c;其余数放在另一个数组&#xff0c;就能保证gcd不同 来看代码&#xff1a; #include <bits/stdc.h> using namespace std;int main() {int t;ci…...

编程日记 2025/8/5 1:57:57

按位宽提取十六进制值

需求&#xff1a;给出一个十六进制值&#xff0c;要求提取high和low位之间的值。比如16ha0f0&#xff0c;这是一个16bit宽的十六进制数0xa0f0&#xff0c;提取[15:12]范围内的值。 def extract_bits(value, high, low):"""从 value 中提取 [high:low] 位的值:p…...

编程日记 2025/7/31 11:28:24

Android设备序列号获取方式全解析

Android设备序列号获取方式全解析 前言 在Android开发中&#xff0c;获取设备序列号&#xff08;SN&#xff09;是设备管理类应用常见的需求。但不同厂商设备获取方式存在差异&#xff0c;且Android系统版本升级也带来了API变化。本文将系统梳理7种主流序列号获取方式&#x…...

编程日记 2025/7/31 13:36:03

Spring框架（1）

Spring框架是Java企业级开发中最受欢迎的框架之一&#xff0c;它通过简化开发流程、降低耦合度&#xff0c;让开发者能够更专注于业务逻辑的实现。本文将带你了解Spring框架的核心概念和基本用法。 一、Spring框架简介 Spring是一个轻量级的开源Java开发框架&#xff0c;由Ro…...

编程日记 2025/7/31 11:28:21

软件安全（二）优化shellcode

我们在上一节课中所写的shellcode&#xff0c;其中使用到的相关的API是通过写入其内存地址来实现调用。这种方法具有局限性&#xff0c;如切换其他的操作系统API的内存地址就会发生变化&#xff0c;从而无法正常调用。 所谓的shellcode不过是在目标程序中加一个区段使得程序可…...

编程日记 2025/7/31 11:28:18

前端使用腾讯地图api实现定位功能

1.配置key 申请地址&#xff1a; https://lbs.qq.com/dev/console/key/manage 2.在项目中引入jssdk <script type"text/javascript" src"https://apis.map.qq.com/tools/geolocation/min?keykey&referermyapp"></script>使用 const g…...

编程日记 2025/7/31 11:28:16

单片机-STM32部分：10、串口UART

飞书文档https://x509p6c8to.feishu.cn/wiki/W7ZGwKJCeiGjqmkvTpJcjT2HnNf 串口说明 电平标准是数据1和数据0的表达方式&#xff0c;是传输线缆中人为规定的电压与数据的对应关系&#xff0c;串口常用的电平标准有如下三种&#xff1a; TTL电平&#xff1a;3.3V或5V表示1&am…...

编程日记 2025/7/31 11:28:13

STM32外设-串口UART

STM32外设-串口UART 一&#xff0c;串口简介二&#xff0c;串口基础概念1&#xff0c;什么是同步和异步/UART与USART对比2&#xff0c;串行与并行3&#xff0c;波特率 (Baud Rate)4&#xff0c;数据帧 (Data Frame)5&#xff0c;TX 和 RX 三&#xff0c;硬件连接1&#xff0c;u…...

编程日记 2025/7/31 8:19:42

《工业计算机硬件技术支持手册》适用于哪些人群？

《工业计算机硬件技术支持手册》于2024年出版&#xff0c;主要讲当前正在应用的最新计算硬件技术。包括计算机各种功能接口、扩展总线、各种国际通行的板型规格等等。书中引用的数据&#xff0c;全部来自国际行业技术规范&#xff0c;书中还融入了作者几十年的工作经验和操作技…...

编程日记 2025/7/31 11:28:09

element-ui时间线样式修改

element-ui时间线样式修改 前两天公司给了一个需求 要求如下图所示 需求是时间在步骤条左边,看了element-ui的文档 发现并没有参数可以设置时间在步骤条的左边 那没办法 只能自己想一想办法了 首先想到的是用样式直接改变 活不多说 直接搞 第一步 选中时间这个元素 发现了这个类…...

编程日记 2025/7/31 11:28:05

动态规划之背包问题：组合优化中的经典NP挑战

背包问题概念&#xff1a; 背包问题是一种经典的组合优化的NP问题&#xff0c;在计算机科学、运筹学等领域有着广泛的应用。 问题可以简单的描述为&#xff1a; 假设有一个容量为C的背包和n个物品&#xff0c;每个物品i都有重量w[i]和价值v[i]。目标是选择一些物品放入背包&…...

编程日记 2025/8/2 3:28:57

JavaScript 基础

JS概念 JS基础概念 JS是一种运行在客户端(浏览器)的编程语言, 实现人机交换结果 作用: 网页特效表单验证数据交互服务端编程(node.js) JS的组成 ECMAScript—javaScript语言基础Web APIs—(DOM: 页面文档对象模型)(BOM: 浏览器对象模型) JS书写 位置 内部: 写到< /body…...

编程日记 2025/7/31 11:27:53

Vibe Coding: 优点与缺点

如果你最近在开发圈子里，你很可能听说过这个新趋势"vibe coding"（氛围编程）。 我只能说我对此感受复杂。以下是原因。 优势 在构建新项目时，靠着氛围编程达到成功感觉很自由！但对于遗留代码来说情况就不同了，尽管也不是不可能。 实时反馈和快速迭代 Cursor（…...

编程日记 2025/7/31 13:36:01

小动物听力评价系统基本原理简析

小动物听力评价系统是用于评估小动物听力功能的专业设备&#xff0c;以下从系统组成、工作原理、评价方法等方面为你介绍&#xff1a; 一 系统组成 声音刺激模块&#xff1a;能产生不同频率、强度和类型的声音信号&#xff0c;如纯音、啭音、短声等&#xff0c;以刺激小动物的听…...

编程日记 2025/8/2 23:32:41

spark缓存-persist

存储级别指定 persist&#xff1a;可以通过传入 StorageLevel 参数来指定不同的持久化级别。常见的持久化级别有&#xff1a; MEMORY_ONLY&#xff1a;将 RDD 以 Java 对象的形式存储在 JVM 的内存中。若内存不足&#xff0c;部分分区将不会被缓存&#xff0c;需要时会重新计算…...

编程日记 2025/7/31 10:30:42

树初步 #1（插排串联 - 辽宁省2024CCPC）

树初步 数的基础内容可以看看树基础 - OI Wiki里面的讲解&#xff0c;对一些操作的基础概念介绍的很清楚&#xff1b; 下面直接来看例题&#xff1a; 插排串联 - 辽宁省CCPC 题目大意 给定一个n1个节点的有根数&#xff1b; 根节点&#xff08;0号&#xff09;是插座&…...

编程日记 2025/7/31 10:30:41

CDGP重点知识梳理（82个）

目 录 考点分布 考试要求 第一章 数据管理-5%...

编程日记 2025/8/2 2:21:35

shell脚本基础详细学习（更新中）

shell简单介绍 Shell不仅仅是充当用户与UNIX或者localhost交互的角色&#xff0c;还可以作为一种程序设计 语言来使用。通过Shell编程&#xff0c;可以实现许多非常实用的功能&#xff0c;提高系统管理的自动化水平。 如果有一系列经常需要使用的命令&#xff0c;把它存储在一…...

编程日记 2025/7/31 10:30:37

记录一下学习kafka的使用以及思路

下面这是kafka的依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-stream-kafka</artifactId></dependency> 我在学习的时候直接导入是没有导入成功的&#xff0c;我猜测大概的原因是我本…...

编程日记 2025/7/31 10:30:35

AT9880B北斗单模卫星定位SOC芯片

AT9880B是一款高性能北斗单模卫星导航接收机SOC单芯片&#xff0c;芯片集成射频前端和数字基带、北斗多频卫星信号处理引擎、电源管理功能。芯片支持接收中国北斗二号和北斗三号&#xff0c;支持接收B1I、B1C、B2I、B3I、B2a和 B2b等频点信号。 主要特性&#xff1a; 支持北斗…...

编程日记 2025/7/31 10:30:33

李沐《动手学深度学习》 | 多层感知机

文章目录 感知机模型《深度学习入门》的解释训练感知机损失函数的选择感知机的收敛定理&#xff1a;什么时候能够停下来&#xff0c;是不是真的可以停下来感知机的不足 多层感知模型案例引入隐藏层从线性到非线性单隐藏层-单分类案例多隐藏层 激活函数softmax函数溢出的问题 多…...

编程日记 2025/8/4 15:58:49

vue数据可视化开发常用库

一、常用数据可视化库 1. ECharts 特点&#xff1a;功能强大&#xff0c;支持多种图表类型&#xff0c;社区活跃。适用场景&#xff1a;复杂图表、大数据量、3D 可视化。安装&#xff1a;npm install echarts示例&#xff1a;<template><div ref"chart" c…...

编程日记 2025/7/31 10:30:28

CAN转ModbusTCP网关：破解电池生产线设备协议壁垒，实现全链路智能互联

在电池生产的现代工艺中&#xff0c;自动化和信息化水平的提高是提升产能、保障品质与安全的关键。CAN 协议作为一种广泛应用于汽车、工业控制等领域的串行通信协议&#xff0c;它以其高可靠性和强实时性而受到企业的青睐。而在众多工业通讯协议中&#xff0c;ModbusTCP作为一种…...

编程日记 2025/7/31 10:30:26

更新 / 安装 Nvidia Driver 驱动 - Ubuntu - 2

如果按更新 / 安装 Nvidia Driver 驱动 - Ubuntu-CSDN博客中的步骤操作后问题依旧&#xff0c;则查看过程中的提示信息。 如果发现有“Use sudo apt autoremove to remove them.”&#xff0c;则执行&#xff1a; #sudo apt autoremove #nvidia-smi...

编程日记 2025/7/31 10:30:24

技术分享 | 如何在2k0300（LoongArch架构）处理器上跑通qt开发流程

近期迅为售后团队反馈&#xff0c;许多用户咨询&#xff1a;2K0300处理器采用了LA264处理器核&#xff0c;若要在该处理器上运行Qt程序&#xff0c;由于架构发生了变化&#xff0c;其使用方法是否仍与ARM平台保持一致&#xff1f; 单纯回答‘一致’或‘不一致’缺乏说服力&…...

编程日记 2025/7/31 13:35:59

ubuntu 24.04 error: cannot uninstall blinker 1.7.0, record file not found. hint

最近在打python3.12的镜像&#xff0c;安装browser-gym的核心库&#xff0c;编译一个使用browswer agents的环境&#xff0c;然后出现了下面的问题&#xff1a; error: cannot uninstall blinker 1.7.0, record file not found. hint: the package was installed by debian.系…...

编程日记 2025/7/31 13:35:57

学习记录：DAY28

DispatcherController 功能完善与接口文档编写 前言 没什么动力说废话了。 今天来完善 DispatcherController 的功能&#xff0c;然后写写接口文档。 日程 早上&#xff1a;本来只有早八&#xff0c;但是早上摸鱼了&#xff0c;罪过罪过。下午&#xff1a;把 DispatcherContro…...

编程日记 2025/7/31 13:35:54

C# 的异步任务中, 如何暂停, 继续,停止任务

namespace taskTest {using System;using System.Threading;using System.Threading.Tasks;public class MyService{private Task? workTask;private readonly SemaphoreSlim semaphore new SemaphoreSlim(0, 1); // 初始为 0&#xff0c;Start() 启动时手动放行private read…...

编程日记 2025/7/31 6:22:17

html object标签介绍（用于嵌入外部资源通用标签）（已不推荐使用deprecated，建议使用img、video、audio标签）

文章目录 HTML <object> 标签详解基本语法与核心属性关键属性解析1. **data**2. **type**3. **width & height**4. **name** 嵌入不同类型的资源1. **嵌入图像**2. **嵌入音频**3. **嵌入视频**4. **嵌入 PDF** 参数传递与回退内容**参数&#xff08;<param>&a…...

编程日记 2025/8/1 15:37:40

专题练习1

优化: 找101-200的质数: 开发验证码: 解密数字 抽奖 优化 彩票...

编程日记 2025/7/31 13:35:48

Uniapp编写微信小程序，使用canvas进行绘图

一、canvas文档&#xff1a; https://developer.mozilla.org/zh-CN/docs/Web/API/Canvas_API/Tutorial 二、数据绘制&#xff08;单位是像素&#xff09;&#xff1a; 1、绘制文本&#xff1a; 文字的长度超过设置的最大宽度&#xff0c;文字会缩在一起 ① 填充文本&#xf…...

编程日记 2025/7/31 13:35:45

Java高频基础面试题

Java高频基础面试题 Java基础 Java的特点是什么&#xff1f; 面向对象平台无关性&#xff08;“一次编写&#xff0c;到处运行”&#xff09;支持多线程自动内存管理&#xff08;垃圾回收&#xff09;安全性丰富的类库 JDK、JRE和JVM的区别 JDK (Java Development Kit): Java…...

编程日记 2025/8/3 15:20:36

U9C-SQL-采购订单视图

U9C-SQL-采购订单视图 SELECTpo.ID,CONVERT ( VARCHAR ( 10 ), po.CreatedOn, 23 ) AS 签订日期,org.Name AS 甲方,po.DocNo AS 单号,item.Code AS 料号,item.Name AS 品名,item.SPECS AS 规格,item.DescFlexField_PrivateDescSeg1 AS 图号,item.DescFlexField_PrivateDescSeg2…...

编程日记 2025/7/31 13:35:41

HTML字符串转换为React元素实现

HTML字符串安全转换为React元素的实现 一、背景介绍 介绍HTML字符串在Web开发中的常见场景。说明React中直接使用HTML字符串的局限性。提出将HTML字符串转换为React元素的需求。 二、首先必备的两个npm库&#xff1a;html-react-parser和dompurify 导入&#xff1a; pnpm i…...

编程日记 2025/7/31 13:35:39

全局异常未能正确捕获到对应的异常

自定义Validation验证器遇到的问题 抛出的异常没有能被指定的TaskValidException.class方法拦截到。故写这个原因 全局异常拦截只能拦截相同的异常。只能通过解析转入自定义的异常。自定义的异常继承的异常要是一家子的。如TaskValidException和ValidationException。这样就能在…...

编程日记 2025/7/31 13:35:37

LeetCode 解题思路 47（最长回文子串、最长公共子序列）

解题思路&#xff1a; dp 数组的含义&#xff1a; dp[i][j] 是否为回文子串。递推公式&#xff1a; dp[i][j] s.charAt(i) s.charAt(j) && dp[i 1][j - 1]。dp 数组初始化&#xff1a; 单字符 dp[i][i] true&#xff0c;双字符 dp[i][i 1] s.charAt(i) s.charA…...

编程日记 2025/7/31 13:35:35

P11369 [Ynoi2024] 弥留之国的爱丽丝（操作分块，DAG可达性trick）

真的神仙题。感觉学到了很多。 题意&#xff1a; 给你一张 n n n 个结点 m m m 条边的有向图&#xff0c;点编号为 1 , 2 , … , n 1,2,\dots,n 1,2,…,n。每条边的颜色为黑色或白色。一开始所有 m m m 条边都是黑色的。 你需要进行 q q q 次操作&#xff0c;有两种操作…...

编程日记 2025/7/31 13:35:33

NAT穿越

概述 IPSec协商是通过IKE完成--->ISAKMP协议完成--->由UDP封装&#xff0c;源目端口均为500。 NAT--->NAPT&#xff0c;同时转换IP和端口信息。 对端设备会查验收到的数据报文中的源IP和源端口&#xff0c;其中源IP可以设定为NAT转换后的IP&#xff0c;但是源端口无法…...

编程日记 2025/7/31 13:35:31

不黑文化艺术学社首席艺术家孙溟㠭浅析“雪渔派”

孙溟㠭浅析“雪渔派” 何震 字主臣 &#xff0c;长卿&#xff0c;号雪渔&#xff0c;安徽婺源&#xff08;今江西&#xff09;人&#xff0c;是明代著名的篆刻家和书法家&#xff0c;与文彭独树一帜&#xff0c;实现书法与刀法的统一。 云中白鹤 笑谭间气吐霓虹 边款 其篆刻吸…...

编程日记 2025/7/31 13:35:29

【Linux操作系统】第一弹——Linux基础篇

文章目录 &#x1f4a1; 一. Linux的基本常识&#x1fa94; 1.1 linux网络连接三种方式&#x1fa94;1.2 虚拟机的克隆&#x1fa94;1.3 虚拟机的快照&#x1fa94;1.4 虚拟机的迁移和删除&#x1fa94;1.5 vmtools工具 &#x1f4a1;二. Linux的目录结构&#x1fa94;2.1 Linu…...

编程日记 2025/7/31 13:35:27

“ES7+ React/Redux/React-Native snippets“常用快捷前缀

请注意&#xff0c;这是一个常用的列表&#xff0c;不是扩展提供的所有前缀。最完整和最新的列表请参考扩展的官方文档或在 VS Code 中查看扩展的详情页面。 React (通常用于 .js, .jsx, .ts, .tsx): rfce: React Functional Component with Export Defaultrafce: React Arro…...

编程日记 2025/7/31 13:35:25

selenium替代----playwright

安装 好处特点&#xff1a;这个东西不像selenium需要固定版本的驱动 pip config set global.index-url https://mirrors.aliyun.com/pypi/simplepip install --upgrade pippip install playwright playwright installplaywright install ffmpeg (处理音视频的)验证&#x…...

编程日记 2025/7/31 13:35:23

2025年社交APP安全防御指南：抵御DDoS与CC攻击的实战策略

2025年&#xff0c;社交APP的用户规模与业务复杂度持续增长&#xff0c;但随之而来的DDoS与CC攻击也愈发隐蔽和智能化。攻击者通过AI伪造用户行为、劫持物联网设备&#xff0c;甚至利用区块链漏洞发起混合攻击&#xff0c;对平台稳定性与用户数据安全构成严峻挑战。本文将结合最…...

编程日记 2025/7/31 13:35:21

PHP会话技术

第十六章-PHP会话技术 PHP会话技术是构建动态、个性化Web应用的核心机制之一&#xff0c;它通过跟踪用户在网站上的连续操作状态&#xff0c;实现了网页间的数据持久化交互。无论是电商平台的购物车信息保存、社交媒体的用户登录状态维持&#xff0c;还是表单数据的跨页面传递…...

编程日记 2025/7/31 13:35:19

QT聊天项目DAY10

1.封装redis操作类 头文件 #ifndef REDISMANAGE_H #define REDISMANAGE_H#include "Singletion.h" #include "GlobalHead.h"class RedisManage : public Singletion<RedisManage> {friend class Singletion<RedisManage>; public:~RedisMana…...

编程日记 2025/8/4 23:21:07