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

AVL树 和 红黑树 的插入算法

news 来源：原创 2025/8/22 13:26:41

1.AVL树

按照二叉搜索树的规则找到要插入的位置并插入，插入过后看是父节点的左还是右孩子，然后把父节点的平衡因子-1或+1，调整后如果父节点的平衡因子是0，那就说明这颗子树的高度插入前后不变，上面的就不用调整平衡因子了，到此结束。如果调整后如果父节点的平衡因子是1或-1，那就说明该子树的高度变化了，那就往上走。走了之后看是左孩子还是右孩子，然后给父节点的平衡因子-1/+1，然后看调整后的结果，如果是0或+/-1那和上一次处理一样，不再多说，如果是+/-2，那就开旋~，记该节点为Parent

1.parent节点平衡因子+2

那说明右边高，那就看看右边怎么个事，看右孩子的平衡因子

a.右孩子subR的平衡因子是+1

那说明还是右边高，直接左旋parent节点，subR平衡因子是变成0，parent平衡因子变成0

b.右孩子sub的平衡因子是-1

这种情况要先变成完全不平衡那种，即先右旋subR节点，然后就变成了上面那种完全不平衡的样子，然后左旋parent节点，旋转很简单，平衡因子有点难调。我们要根据subRL，也就是subR的左孩子来调整平衡因子，

如果subRL的平衡因子是0，subRL=0  parent=0  subR=0

如果subRL的平衡因子是1，subRL=0  parent=-1  subR=0

如果subRL的平衡因子是-1，subRL=0  parent=0  subR=1

2.parent节点平衡因子-2

思考方式和+2一样

2.红黑树

按照二叉搜索树的方式找到要插入的位置并插入，节点默认应该是红色而不是黑色，因为红色插入的话不一定会破坏红黑树的规则，而黑色节点插入一定会破坏每条路径上黑色节点个数相同这个规则。插入红色节点后，如果父节点是黑色，那就什么规则都没破坏，结束了。如果父节点是红色，那不能有相邻红色节点，所以要调整，插入这个结点之前应该满足是红黑树，所以父节点是红色说明爷爷节点一定是黑色，这时的关键就是叔叔节点也就是爷爷结点的另一个子节点

1.叔叔节点是红色

那直接把父节点和叔叔节点变成黑色，爷爷节点变成红色，然后继续往上调整，爷爷节点就变成了新加入的红色节点，正如一开始的孙子节点一样

2.叔叔节点是黑色或不存在

这个时候要开旋了~

爷爷节点记为parent，

a.假如父节点是subL

也就是爷爷节点的左孩子，然后当前节点subLL，也就是父节点的左节点，那就右旋parent，然后parent变为红色，父节点变为黑色；当前节点是subLR，也就是当前节点是父节点的右孩子，那就先左旋subL，变成上一种情况那种样子，然后右旋parent，改parent为红色，subL为黑色

b.假如父节点是subR

然后分类当前节点如上

相关文章：

AVL树 和 红黑树 的插入算法

1.AVL树 按照二叉搜索树的规则找到要插入的位置并插入，插入过后看是父节点的左还是右孩子，然后把父节点的平衡因子-1或1，调整后如果父节点的平衡因子是0，那就说明这颗子树的高度插入前后不变，上面的就不用调整平衡因子…...

编程日记 2025/8/22 13:26:41

【项目】基于ArkTS的网吧会员应用开发（1）

一、效果图展示 二、界面讲解 以上是基于ArkTS的鸿蒙应用网吧会员软件的引导页，使用滑动组件滑动页面，至最后一页时，点击立即体验，进入登录页面。 三、代码演示 import promptAction from ohos.promptAction; import router fr…...

编程日记 2025/8/21 18:44:04

命令模式（Command Pattern）

非常好！现在我们来深入讲解行为型设计模式之一 —— 命令模式（Command Pattern）。 我将通过： ✅ 定义解释 🎯 使用动机 🐍 Python 完整调用代码（含注释） 🧭 清晰类图 …...

编程日记 2025/8/21 22:36:46

CMake基础介绍

1、CMake 概述 CMake 是一个项目构建工具，并且是跨平台的；关于项目构建目前比较流行的还有 Makefile(通过 Make 命令进行项目的构建)， 大多 IDE 软件都集成了 make,比如：VS 的 nmake、linux 下的 GNU make、Qt 的 qmake 等&…...

编程日记 2025/8/21 2:10:04

偷钱包行为检测数据集VOC+YOLO格式922张1类别有增强

有320张图片是原图剩余为增强图片 数据集格式：Pascal VOC格式YOLO格式(不包含分割路径的txt文件，仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)：922 标注数量(xml文件个数)：922 标注数量…...

编程日记 2025/8/22 8:42:09

C 语言比较运算符：程序如何做出“判断”？

各类资料学习下载合集 ​​https://pan.quark.cn/s/8c91ccb5a474​​ 在编写程序时，我们经常需要根据不同的条件来执行不同的代码。比如，如果一个分数大于 60 分，就判断为及格；如果用户的年龄小于 18 岁，就禁止访问某个内容等等。这些“判断”的核心，就依赖于程序能够比…...

编程日记 2025/8/21 6:08:20

Webug4.0靶场通关笔记16- 第20关文件上传(截断上传)

目录 第20关 文件上传(截断上传) 1.打开靶场 2.源码分析 （1）右键查看前端源码 （2）服务端源码分析 （3）渗透思路 3.渗透实战 （1）构建脚本 （2）bp抓包 …...

编程日记 2025/8/20 0:26:06

10 种最新的思维链（Chain-of-Thought, CoT）增强方法

防御式链式思维（Chain-of-Defensive-Thought） 该方法通过引入结构化、防御性的推理示例，提高大语言模型在面对被污染或误导信息时的稳健性。 📄 论文链接：https://arxiv.org/abs/2504.20769 混合链式思维（…...

编程日记 2025/8/20 0:26:05

力扣119题解

记录 2025.5.5 题目&#xff1a; 思路&#xff1a; 代码: class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> row new ArrayList<Integer>();row.add(1);for (int i 1; i < rowIndex; i) {row.add((int) ((long) row.get(i…...

编程日记 2025/8/22 13:25:28

NSOperation深入解析：从使用到底层原理

1. 基础概念与使用 1.1 NSOperation概述 NSOperation是Apple提供的一个面向对象的并发编程API&#xff0c;它基于GCD&#xff08;Grand Central Dispatch&#xff09;构建&#xff0c;但提供了更高层次的抽象和更丰富的功能。NSOperation允许开发者以面向对象的方式管理并发任…...

编程日记 2025/8/19 9:38:14

suna工具调用可视化界面实现原理分析（二）

这是一个基于React的浏览器操作可视化调试组件&#xff0c;主要用于在AI开发工具中展示网页自动化操作过程&#xff08;如导航、点击、表单填写等&#xff09;的执行状态和结果。以下是关键技术组件和功能亮点的解析&#xff1a; 一、核心功能模块 浏览器操作状态可视化 • 实时…...

编程日记 2025/8/20 0:26:01

【大模型面试每日一题】Day 9：BERT 的 MLM 和 GPT 的 Next Token Prediction 有什么区别？

【大模型面试每日一题】Day 9&#xff1a;BERT 的 MLM 和 GPT 的 Next Token Prediction 有什么区别&#xff1f; &#x1f4cc; 题目重现 &#x1f31f; 面试官&#xff1a;预训练任务中&#xff0c;BERT 的 MLM&#xff08;Masked Language Modeling&#xff09;和 GPT 的 …...

编程日记 2025/8/20 0:25:59

分析strtol(),strtoul()和strtod()三个函数的功能

字符串转换为数值部分和子字符串首地址的函数有strtol(),strtoul()和strtod()三个函数。 1、strtol()函数 long int strtol(const char *str, char **endptr, int base) //当base0时,若字符串不是以"0","0x"和"0X"开头,则将数字部分按照10进制…...

编程日记 2025/8/20 0:25:58

Spring Boot 加载application.properties或application.yml配置文件的位置顺序。

我换一种更通俗易懂的方式&#xff0c;结合具体例子来解释 Spring Boot 加载application.properties或application.yml配置文件的位置顺序。 生活场景类比 想象你要找一本书&#xff0c;你有几个可能存放这本书的地方&#xff0c;你会按照一定顺序去这些地方找&#xff0c;直…...

编程日记 2025/8/19 12:15:37

C++进阶之——多态

1. 多态的概念 多态是用来描述这个世界的 多态的概念&#xff1a;通俗来说&#xff0c;就是多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当不同的对象去完成时会 产生出不同的状态。 这里就很厉害了&#xff0c;能够实现特殊处理&#xff0c;本文章就是来仔细…...

编程日记 2025/8/20 0:25:54

第13项三期，入组1123例：默沙东启动TROP2 ADC+PD-1子宫内膜癌头对头临床

Umabs DB作为目前全球最全面的抗体药物专业数据库&#xff0c;收录全球近10000个从临床前到商业化阶段抗体药物&#xff0c;涉及靶点1600&#xff0c;涉及疾病种类2400&#xff0c;研发机构2900&#xff0c;覆盖药物蛋白序列、专利和临床等多种专业信息。Umabs DB药物数据库已正…...

编程日记 2025/8/20 0:25:52

政务服务智能化改造方案和案例分析

政务服务智能化改造方案和案例分析 一、引言 在数字化时代浪潮的推动下&#xff0c;政务服务智能化改造已成为提升政府服务效能、优化营商环境、增强民众满意度的关键举措。传统政务服务模式存在流程繁琐、信息孤岛、办理效率低等问题&#xff0c;难以满足现代社会快节奏发展和…...

编程日记 2025/8/21 14:26:41

15.日志分析入门

日志分析入门 第一部分&#xff1a;日志分析基础第二部分&#xff1a;日志分析方法与工具第三部分&#xff1a;日志分析实践总结 目标&#xff1a; • 理解日志分析在网络安全中的作用 • 掌握日志的基本类型和分析方法 • 通过实践初步体验日志分析的过程 第一部分&#xff…...

编程日记 2025/8/20 1:41:55

EPSG:3857 和 EPSG:4326 的区别

EPSG:3857 和 EPSG:4326 是两种常用的空间参考系统&#xff0c;主要区别在于坐标表示方式和应用场景。以下是它们的核心差异&#xff1a; 1. 坐标系类型 EPSG:4326&#xff08;WGS84&#xff09; 地理坐标系&#xff08;Geographic Coordinate System&#xff09;&#xff0c;基…...

编程日记 2025/8/20 1:41:50

Python Cookbook-7.2 使用 pickle 和 cPickle 模块序列化数据

任务 你想以某种可以接受的速度序列化和重建Python 数据结构&#xff0c;这些数据既包括基本Python 对象也包括类和实例。 解决方案 如果你不想假设你的数据完全由基本 Python 对象组成&#xff0c;或者需要在不同的 Python 版本之间移植&#xff0c;再或者需要将序列化后的…...

编程日记 2025/8/19 9:42:14

Java学习手册：Spring 多数据源配置与管理

在实际开发中&#xff0c;有时需要连接多个数据库&#xff0c;例如&#xff0c;一个系统可能需要从不同的数据库中读取和写入数据。Spring 提供了多种方式来配置和管理多数据源&#xff0c;以下将介绍常见的配置和管理方法。 一、多数据源配置 在 Spring 中&#xff0c;可以通…...

编程日记 2025/8/21 21:43:06

六、shell脚本--正则表达式：玩转文本匹配的“万能钥匙”

想象一下&#xff0c;你需要在一大堆文本&#xff08;比如日志文件、配置文件、网页代码&#xff09;里查找符合某种特定模式的字符串&#xff0c;而不是仅仅查找固定的单词。比如说&#xff1a; 找出所有的电子邮件地址 &#x1f4e7;。找到所有看起来像电话号码 &#x1f4d…...

编程日记 2025/8/20 1:41:37

Gradio全解20——Streaming：流式传输的多媒体应用（4）——基于Groq的带自动语音检测功能的多模态Gradio应用

Gradio全解20——Streaming&#xff1a;流式传输的多媒体应用&#xff08;4&#xff09;——基于Groq的带自动语音检测功能的多模态Gradio应用 本篇摘要20. Streaming&#xff1a;流式传输的多媒体应用20.4 基于Groq的带自动语音检测功能的多模态Gradio应用20.4.1 组件及配置1.…...

编程日记 2025/8/20 1:41:32

力扣hot100 （除自身以外数组的乘积）

238. 除自身以外数组的乘积 中等 给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除…...

编程日记 2025/8/20 1:41:29

LFU算法解析

文章目录 LFU缓存中关键变量的访问与更新机制1. min_freq - 最小频率访问时机更新时机更新示例 2. capacity - 缓存容量访问时机更新时机访问示例 3. key_to_node - 键到节点的映射访问时机更新时机更新示例 4. freq_to_dummy - 频率到链表哑节点的映射访问时机更新时机更新示例…...

编程日记 2025/8/20 1:41:24

RHCSA笔记2

RHCSA基础命令 &#xff08;一&#xff09;命令格式 &#xff08;1&#xff09;命令名【选项】【参数】 选项&#xff1a;决定命令执行的方式&#xff0c;通常有个-或--开头 参数&#xff1a;决定命令作用的目标&#xff08;目录&#xff0c;文件&#xff0c;磁盘&#xff…...

编程日记 2025/8/20 1:41:21

JavaSE核心知识点01基础语法01-02（基本数据类型、运算符、运算符优先级）

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 JavaSE核心知识点01基础语法01-02&#xff0…...

编程日记 2025/8/20 1:41:19

FOC算法开环控制基础

1. 为什么要有FOC算法 先看看从有刷电机到无刷电机的简单介绍&#xff0c;如下图1&#xff0c;通电螺线圈会产生磁场&#xff0c;这个磁场会产生N级和S级&#xff0c;然后这个电磁铁就可以吸引永磁体&#xff0c;S级吸引N级&#xff0c;N级吸引S级&#xff0c;通俗的来说&…...

编程日记 2025/8/20 1:41:15

进程间通信——管道

概念 进程间通信&#xff08;Inter-Process Communication&#xff0c;简称 IPC&#xff09;是指在不同进程之间进行数据交换和信息传递的机制。它的目的主要有4种&#xff1a; 数据传输&#xff1a;一个进程需要将它的数据发送给另一个进程资源共享&#xff1a;多个进程之间…...

编程日记 2025/8/20 1:41:12

五一作业-day02

文章目录 1. 每日基操2. 模拟故障2.1 **remove regular empty file 是否删除普通文件(空的)?**2.2 **is a directory xxx是一个目录**2.3 **xxx not a directory 不是一个目录**2.4 Cant open file for writing2.5 **No write since last change** 3. 习题4. **进阶习题** 1. …...

编程日记 2025/8/20 1:41:09

Springclound常用五大组件及其使用原理

注册中心Eureka Eureka-Server&#xff1a;就是服务注册中心&#xff08;可以是一个集群&#xff09;&#xff0c;对外暴露自己的地址。 提供者&#xff1a;启动后向Eureka注册自己信息&#xff08;地址&#xff0c;服务名称等&#xff09;&#xff0c;并且定期进行服务续约 …...

编程日记 2025/8/20 1:41:06

Qt 显示QRegExp 和 QtXml 不存在问题

QRegExp 和 QtXml 问题 在Qt6 中 已被弃用&#xff1b; 1&#xff09;QRegExp 已被弃用&#xff0c;改用 QRegularExpression Qt5 → Qt6 重大变更&#xff1a;QRegExp 被移到了 Qt5Compat 模块&#xff0c;默认不在 Qt6 核心模块中。 错误类型解决方法QRegExp 找不到改用 Q…...

编程日记 2025/8/22 12:13:41

开元类双端互动组件部署实战全流程教程（第4部分：后台配置系统与参数动态控制）

作者&#xff1a;曾经因为后台配置写错&#xff0c;导致全服进不去房的工程师 组件附带的后台管理系统为 PHP 编写&#xff0c;界面简洁但功能齐全。具备完整的模块划分与权限体系&#xff0c;支持动态参数下发、日志审计、行为数据统计等。 七、前端后台交互流程图与代码示例 …...

编程日记 2025/8/19 8:53:26

MySQL基础关键_008_DDL 和 DML（一）

目 录 一、DDL 1.创建表 &#xff08;1&#xff09;语法格式 &#xff08;2&#xff09;实例 2.查看建表语句 &#xff08;1&#xff09;语法格式 &#xff08;2&#xff09;实例 3.修改表名 &#xff08;1&#xff09;语法格式 &#xff08;2&#xff09;实例 4.新…...

编程日记 2025/8/20 1:41:00

基于SpringBoot + Vue 的火车票订票系统

包含&#xff1a; [1]源码✔ 数据库文件✔ [2]万字文档✔ [3]视频与图文配置教程✔ 功能描述&#xff1a; 本系统包含管理员、用户两个角色。 管理员&#xff1a;用户管理、新闻公告管理、车辆管理、车站及路线管理、留言建议管理、车次信息管理 用户&#xff1a;购票操作、查…...

编程日记 2025/8/21 22:22:50

飞致云开源社区月度动态报告（2025年4月）

自2023年6月起&#xff0c;中国领先的开源软件公司飞致云以月度为单位发布《飞致云开源社区月度动态报告》&#xff0c;旨在向广大社区用户同步飞致云旗下系列开源软件的发展情况&#xff0c;以及当月主要的产品新版本发布、社区运营成果等相关信息。 飞致云开源运营数据概览&…...

编程日记 2025/8/21 6:08:12

解决跨域的4种方法

00_跨域的概念 浏览器只允许请问具有相同的协议&#xff0c;域名&#xff0c;端口&#xff0c;进行请求&#xff0c;有一个不同&#xff0c;就会拒绝。 01.前后端协商jsonp //jsonp//jsonp 是 json with padding 的缩写&#xff0c;是一种通过 <script> 标签的 src 属性…...

编程日记 2025/8/22 8:41:58

C# 方法(局部函数和参数)

本章内容: 方法的结构 方法体内部的代码执行 局部变量 局部常量 控制流 方法调用 返回值 返回语句和void方法 局部函数 参数 值参数 引用参数 引用类型作为值参数和引用参数 输出参数 参数数组 参数类型总结 方法重载 命名参数 可选参数 栈帧 递归 局部函数 正如刚刚所解释的&…...

编程日记 2025/8/20 1:40:51

kotlin 02flow-sharedFlow 完整教程

一 sharedFlow是什么 SharedFlow 是 Kotlin 协程中 Flow 的一种 热流&#xff08;Hot Flow&#xff09;&#xff0c;用于在多个订阅者之间 共享事件或数据流。它适合处理 一次性事件&#xff08;如导航、弹窗、Toast、刷新通知等&#xff09;&#xff0c;而不是持续状态。 ✅ …...

编程日记 2025/8/22 1:25:47

数据库原理——E-R图的极速省流理解 例题解析

前言 数据库一节没听&#xff0c;一个小时看书给我大致看懂了 E-R概念模型极速省流版 E-R图的重点&#xff1a; 关系图&#xff0c;三要素——实体、属性、联系 图形标识——矩形、椭圆形、菱形 1.实体和属性也可以放一个框矩形框 2.菱形两层边&#xff1a;弱实体集的联…...

编程日记 2025/8/20 1:40:45

5.4 - 5.5Web基础+c语言拓展功能函数

StringBoot HTTP协议&#xff1a; 规定了浏览器与服务器之间数据传递的规则。 请求协议&#xff1a; 请求数据格式&#xff1a; 请求头和请求体之间有一个空行隔开 响应协议&#xff1a; 响应数据格式&#xff1a; 响应头和响应体之间存在空行隔开。 响应数据设置&#xff1…...

编程日记 2025/8/19 10:37:58

Java抽象类与接口详解

一、抽象类(Abstract Class) 1. 定义与基本使用 // 抽象类定义 public abstract class Animal {// 抽象方法(无实现)public abstract void makeSound();// 具体方法(有实现)public void sleep() {System.out.println("动物在睡觉");} }// 继承抽象类 class Dog ext…...

编程日记 2025/8/20 1:40:41

网络延时 第四次CCF-CSP计算机软件能力认证

就是求树的直径: 思路&#xff1a;函数代表当前根节点的最长距离 然后遍历保存当前树的所有孩子的最长距离 和次长距离 如果是叶子节点就返回0 在每次获得每个节点的次长距离和最长距离就更新全局直径 最后获得最长距离 Ac代码: #include <bits/stdc.h> using namespa…...

编程日记 2025/8/22 7:38:15

【C++进阶十】多态深度剖析

【C进阶十】多态深度剖析 1.多态的概念及条件2.虚函数的重写3.重写、重定义、重载区别4.C11新增的override 和final5.抽象类6.虚表指针和虚表6.1什么是虚表指针6.2指向谁调用谁&#xff0c;传父类调用父类&#xff0c;传子类调用子类 7.多态的原理8.单继承的虚表状态9.多继承的…...

编程日记 2025/8/22 5:04:16

网络传输中字节序

在小端字节序主机发送数据 0x1234 的情况下，（单字节没有字节序）我们可以分步骤来分析接收端如何解析这个数据： 1. 小端字节序主机的存储方式 在小端字节序中，低地址存储低字节，高地址存储高字节。 数据 0x1234 的字节表示为： 低字节：0x34 高字节：0x12 因此，在小端字…...

编程日记 2025/8/19 17:52:26

前端- ElementPlus入门

1.介绍 Element&#xff1a;是饿了么公司前端开发团队提供的一套基于 Vue3 的网站组件库&#xff0c;用于快速构建网页。 Element 提供了很多组件供我们使用。例如 超链接、按钮、图片、表格等等。 官方网站&#xff1a;一个 Vue 3 UI 框架 | Element Plus 2.步骤 1.安装E…...

编程日记 2025/8/20 1:40:29

AI Agent 要用到的技术

AI 发展是大趋势&#xff0c;以下是目前要用到的一些技术项 不论你从事哪个方向&#xff0c;这个技术栈都有必要学习 LangChainTransformersMicrosoft Semantic KernelLangflowLangGrphLangSmith 学习网站 以下是 LangChain、Transformers、Microsoft Semantic Kernel 的学习…...

编程日记 2025/8/20 1:40:26

# 从零构建一个简单的卷积神经网络：手写数字识别

从零构建一个简单的卷积神经网络&#xff1a;手写数字识别 在深度学习的世界里&#xff0c;卷积神经网络&#xff08;CNN&#xff09;是处理图像数据的强大工具。今天&#xff0c;我们将通过一个简单的例子&#xff0c;从零开始构建一个CNN模型&#xff0c;用于手写数字识别。…...

编程日记 2025/8/21 9:00:02

【RK3588嵌入式图形编程】-Cairo-Cairo图形库支持后端

Cairo图形库支持后端 文章目录 Cairo图形库支持后端1、PNG图像后端2、PDF文件后端3、SVG文件后端4、GTK窗口支持Cairo库支持多种后端。在本文中，我们使用Cairo创建PNG图像、PDF文件、SVG文件，并在GTK窗口上绘制。 1、PNG图像后端 在第一个示例中，我们创建一个 PNG 图像。 …...

编程日记 2025/8/21 7:24:08

LCD，LED

本文来源 &#xff1a; 腾讯元宝 LCD(Liquid Crystal Display)液晶显示器 LCD本身并不能发光&#xff0c;而是控制光的传输。 LCD内充满了棒状的液态分子&#xff08;液晶&#xff09;&#xff0c;这些分子可以形成扭转的螺旋线&#xff0c;弯曲来自显示器背后光源产生的光线或…...

编程日记 2025/8/19 7:09:17