AVL搜索树
一、介绍
高度平衡的搜索二叉树，保证每个节点的左右子树高度差不超过1，降低搜索树的高度以提高搜索效率。
通过平衡因子和旋转来保证左右子树高度差不超过1
二、插入节点
1、插入规则
（1）搜按索树规则插入节点
（2）更新父节点平衡因子
插入左边就 --，插入右边就 ++
（3）保证父节点平衡因子不超过1
平衡因子是0：表示插入节点之后以父节点为子树的树高度没变，所以插入合法直接跳出。
平衡因子是正负1：以父节点为子树的树高度增大或者减小了1，虽然当前的父节点依旧合法，但是由于高度变了还要向上更新平衡因子。
平衡因子是正负2：要旋转使以父节点为子树的树平衡因子合法。合法后直接挑出。
2、旋转逻辑实现
（1）左高右低 右单旋
旋转前：
旋转后：
大逻辑：把 subLR 给 parent，把 parent 给 subL
右单旋代码实现逻辑和注意点：
a、标记三个节点：subL，subLR，ppNode（保存 parent 的父亲，为了最后更新 subL 的父节点）
b、先 subLR 作 parent 的左子树，注意更新subLR 父节点时 subLR == nullptr 情况
c、再 parent 作 subL 的右子树，注意更新 parent 的父节点
d、利用 ppNode 更新subL 的位置和父节点，注意一开始父节点是根的情况
e、更新 subL 和 parent 的平衡因子为0
右单旋代码：
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* ppNode = parent->_parent;parent->_left = subLR;if(subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){subL->_parent = ppNode;ppNode->_left = subL;}else{subL->_parent = ppNode;ppNode->_right = subL;}}parent->_bf = subL->_bf = 0;
}（2）右高左低 左单旋
旋转前：
旋转后：
分析过程和右单旋类似，代码如下：
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* ppNode = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;subR->_parent = ppNode;}else{ppNode->_right = subR;subR->_parent = ppNode;}}parent->_bf = subR->_bf = 0;
}（3）左高右高 左右双旋
旋转图：
左右双旋的本质就是把 subLR 的左子树给 subL，右子树给 parent
通过本质就可以知道三种不同情况的平衡因子：
| 插入前 subLR 平衡因子 | 插入后平衡因子 | ||
| subLR | subL | parent | |
| -1（新节点插在 subLR 的左子树） | 0 | 0 | 1 |
| 1（新节点插在 subLR 的右子树） | 0 | -1 | 0 |
| 0（新节点就是 subLR） | 0 | 0 | 0 |
左右双旋代码：
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == 0){subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}elseassert(false);
}（4）右高左高 右左双旋
旋转图：
右左双旋的本质就是把 subRL 的左子树给 parent，右子树给 subR
通过本质就可以知道三种不同情况的平衡因子：
| 插入前 subRL 平衡因子 | 插入后平衡因子 | ||
| subRL | subR | parent | |
| -1（新节点插在 subRL 的左子树） | 0 | 1 | 0 |
| 1（新节点插在 subRL 的右子树） | 0 | 0 | -1 |
| 0（新节点就是 subRL） | 0 | 0 | 0 |
右左双旋代码：
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 0){subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}elseassert(false);
}3、插入代码展示
bool insert(const pair<K, V> kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = cur;// 1.像搜索二叉树一样插入节点curwhile (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;// 2.更新平衡因子while (parent){if (cur == parent->_left)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0)break;else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 左高右低右单旋if (parent->_bf == -2 && cur->_bf == -1)RotateR(parent);// 右高左低左单旋else if (parent->_bf == 2 && cur->_bf == 1)RotateL(parent);// 左高右高左右双旋else if (parent->_bf == -2 && cur->_bf == 1)RotateLR(parent);// 右高左高右左双旋elseRotateRL(parent); break;}elseassert(false);}return true;
}三、删除节点
这里只了解删除逻辑，具体如何旋转不考虑。
删除规则
按搜索树删除
删除并更新平衡因子
删除左边就 ++，删除右边就 --
保证父节点平衡因子不超过1
平衡因子是0：表示删除结点之前是正负1，删除后高度改变，所以要向上继续更新。
平衡因子是正负1：表示删除结点之前是0，删除后高度不变，所以跳出。
平衡因子是正负2：要旋转使以父节点为子树的树平衡因子合法。合法后直接跳出。
相关文章：
AVL搜索树
一、介绍 高度平衡的搜索二叉树，保证每个节点的左右子树高度差不超过1，降低搜索树的高度以提高搜索效率。 通过平衡因子和旋转来保证左右子树高度差不超过1 二、插入节点 1、插入规则 （1）搜按索树规则插入节点 （…...
ELK模块封装starter
文章目录 1.combinations-elk-starter1.目录结构2.log4j2-spring.xml 从环境变量读取host和port3.ELKProperties.java 两个属性4.ELKAutoConfiguration.java 启用配置类5.ELKEnvironmentPreparedListener.java 监听器从application.yml中获取属性值6.spring.factories 注册监听…...
C# 与.NET 日志变革：JSON 让程序“开口说清话”
一、引言：日志新时代的开启 在软件开发的漫长旅程中，日志一直是我们不可或缺的伙伴。它就像是应用程序的 “黑匣子”，默默地记录着程序运行过程中的点点滴滴，为我们在调试、排查问题以及性能优化时提供关键线索。在早期ÿ…...
Ubuntu 系统，如何使用双Titan V跑AI
要在Ubuntu系统中使用双NVIDIA Titan V GPU来运行人工智能任务，你需要确保几个关键组件正确安装和配置。以下是基本步骤： 安装Ubuntu操作系统： 下载最新版本的Ubuntu服务器或桌面版ISO文件。使用工具如Rufus（Windows）或…...
CSDN的历史
CSDN（中国开发者网络，China Software Developer Network）是中国最具影响力的IT技术社区之一，其历史可追溯至1999年。以下是其发展历程和关键节点： --- **一、创立背景（1999年）** - **创始人**：蒋涛（国内知名技术人，曾参与金山软件早期开发）。 - **初衷**：为国内程…...
使用Pygame制作“贪吃蛇”游戏
贪吃蛇 是一款经典的休闲小游戏：玩家通过操控一条会不断变长的“蛇”在屏幕中移动，去吃随机出现的食物，同时要避免撞到墙壁或自己身体的其他部分。由于其逻辑相对简单，但可玩性和扩展性都不错，非常适合作为新手练习游戏…...
【详细教程】如何在Mac部署Deepseek R1？
DeepSeek是目前最火的国产大模型，官方App用户太多服务经常出现卡顿，部署一个本地DeepSeek R1可以方便使用。 1.系统最低要求 macOS 11 Big Sur 或更新 2.下载ollama https://ollama.com/ 3.安装DeepSeek R1 打开终端 运行命令 ollama run deepseek-…...
方法：使用与原理详解)
Java中的getInterfaces()方法：使用与原理详解
在Java中，反射（Reflection）是一个强大的工具，它允许程序在运行时动态地获取类的信息并操作类的属性和方法。getInterfaces()方法是Java反射API中的一个重要方法，用于获取类或接口直接实现的接口。本文将深入探讨getInt…...
PT站点自动签到
在站点下载一些视频电影资源，站点需要长期维护，每天自动签到。 两种方式： 一、保持浏览器登录状态，打开默认用户文件， 模拟点击签到（点击按钮自行设置：根据href名称） log日志 首次…...
计算机网络一点事（23）
传输层 端口作用：标识主机特定进程，TCP，UDP协议 端口号分类：服务器：0-1023，熟知 1024-49151 登记 客户端：49152-65535 功能：实现端到端，进程到进程的通信，…...
vim操作简要记录
操作容易忘记，记录一下基本使用的 :wq保存退出 :w :q :q! :wq! i I a A 方向键 h左 j下 k上 l右 dd删除方行（这其实是剪切行操作，不过一般用作删除，长按可删除，不过按.执行上一次操作删除更快） .执行上…...
DeepSeek大模型技术深度解析：揭开Transformer架构的神秘面纱
摘要 DeepSeek大模型由北京深度求索人工智能基础技术研究有限公司开发，基于Transformer架构，具备卓越的自然语言理解和生成能力。该模型能够高效处理智能对话、文本生成和语义理解等复杂任务，标志着人工智能在自然语言处理领域的重大进展。 关…...
Carla-ModuleNotFoundError: No module named ‘agents.navigation‘
解决办法： You need to make sure that _agents _ is in your (PYTHON)PATH variable or your working dictionary. Setting your working dictionary to <CARLA_ROOT>/PythonAPI/carla would fix it as agents is a sub dictionary. Similarly adding the c…...
1.Template Method 模式
模式定义 定义一个操作中的算法的骨架（稳定），而将一些步骤延迟（变化)到子类中。Template Method 使得子类可以不改变（复用）一个算法的结构即可重定义（override 重写）该算法的某些特…...
腾讯云开发提供免费GPU服务
https://ide.cloud.tencent.com/dashboard/web 适用于推理场景，每个月10000分钟免费时长 166 小时 40 分钟 自带学术加速，速度还是不错的 白嫖 Tesla T4 16G 算力 显存：16GB 算力：8 TFlops SP CPU：8 核 内存&#…...
11.QT控件：输入类控件
1. Line Edit(单行输入框) QLineEdit表示单行输入框，用来输入一段文本，但是不能换行。 核心属性： 核心信号： 2. Text Edit(多行输入框) QTextEdit表示多行输入框，也是一个富文本 & markdown编辑器。并且能在内容超…...
想学习Python编程,应该如何去学习呢
学习Python编程是一个循序渐进的过程，以下是一个详细的学习路径和建议： 一、基础入门 安装Python环境： 从Python官方网站下载并安装适合你操作系统的Python版本。确保将Python添加到系统路径中，以便在命令行中方便地访问。 学习…...
Java知识速记：深拷贝与浅拷贝
Java知识速记：深拷贝与浅拷贝 什么是浅拷贝？ 浅拷贝指的是创建一个新对象，但新对象的属性值是对原对象属性值的引用。当原对象的属性是基本类型时，浅拷贝能够直接复制其值；当属性是对象时，仅复制引用&…...
I2C基础知识
引言 这里祝大家新年快乐！前面我们介绍了串口通讯协议，现在我们继续来介绍另一种常见的简单的串行通讯方式——I2C通讯协议。 一、什么是I2C I2C 通讯协议（Inter-Integrated Circuit）是由Phiilps公司在上个世纪80年代开发的&#…...
智慧园区平台系统在数字化转型中的作用与应用前景探究
内容概要 在当前快速变化的商业环境中，数字化转型已经成为企业发展的重要趋势，而智慧园区平台系统则是这一转型的核心工具之一。这种系统集成了多种现代技术，能够有效提升园区的管理效率、优化资产使用，并提升整体服务水平。智慧…...
19 压测和常用的接口优化方案
高并发的平台应用，项目上线前离不开一个重要步骤就是压测，压测对于编码中的资源是否问题的排查，性能的调优都是离不开的。测试还要做测试报告，出具了测试报告给到运维团队才能上线。 压测的测试报告主要有以下几个方面:1.响应时间…...
buuuctf_秘密文件
题目： 应该是分析流量包了，用wireshark打开 我追踪http流未果，分析下ftp流 追踪流看看 用户 “ctf” 使用密码 “ctf” 登录。 PORT命令用于为后续操作设置数据连接。 LIST命令用于列出 FTP 服务器上目录的内容，但在此日志中未…...
前端学习-事件委托（三十）
目录 前言 课前思考 for循环注册事件 语法 事件委托 1.事件委托的好处是什么? 2.事件委托是委托给了谁，父元素还是子元素 3.如何找到真正触发的元素 示例代码 总结 前言 才子佳人，自是白衣卿相 课前思考 1.如果同时给多个元素注册事件&…...
工具的应用——安装copilot
一、介绍Copilot copilot是一个AI辅助编程的助手，作为需要拥抱AI的程序员可以从此尝试进入，至于好与不好，应当是小马过河，各有各的心得。这里不做评述。重点在安装copilot的过程中遇到了一些问题，然后把它总结下&…...
OPENGLPG第九版学习
文章目录 一、OpenGL概述二、着色器基础三、OpenGL绘制方式四、颜色、像素和片元五、视口变换、裁减、剪切与反馈六、纹理与帧缓存七、光照与阴影八、程序式纹理 skip九、细分着色器 skip十、几何着色器 skip十一、内存十二、计算着色器 skip附录 A 第三方支持库附录 B OpenGL …...
C++中常用的十大排序方法之1——冒泡排序
成长路上不孤单😊😊😊😊😊😊 【😊///计算机爱好者😊///持续分享所学😊///如有需要欢迎收藏转发///😊】 今日分享关于C中常用的排序方法之——冒泡排序的相关…...
算法总结-哈希表
文章目录 1.赎金信1.答案2.思路 2.字母异位词分组1.答案2.思路 3.两数之和1.答案2.思路 4.快乐数1.答案2.思路 5.最长连续序列1.答案2.思路 1.赎金信 1.答案 package com.sunxiansheng.arithmetic.day14;/*** Description: 383. 赎金信** Author sun* Create 2025/1/22 11:10…...
文件上传功能（一）
总说 过程参考黑马程序员SpringBoot3Vue3全套视频教程，springbootvue企业级全栈开发从基础、实战到面试一套通关_哔哩哔哩_bilibili 目录 总说 一、功能实现 1.1 Controller层 二、优化 一、功能实现 1.1 Controller层 在contoller层，创建一个File…...
【LeetCode 刷题】二叉树-二叉树的属性
此博客为《代码随想录》二叉树章节的学习笔记，主要内容为二叉树的属性相关的题目解析。 文章目录 101. 对称二叉树104.二叉树的最大深度111.二叉树的最小深度222.完全二叉树的节点个数110.平衡二叉树257. 二叉树的所有路径404.左叶子之和513.找树左下角的值112. 路…...
Redisson
Redisson快速入门 将原先逻辑修改 Redis代金卷(优惠卷)秒杀案例-多应用版-CSDN博客...
回顾生化之父三上真司的游戏思想
1. 放养式野蛮成长路线，开创生存恐怖类型 三上进入capcom后，没有培训，没有师傅手把手的指导，而是每天摸索写策划书，老员工给出不行的评语后，扔掉旧的重写新的。 然后突然就成为游戏总监，进入开…...
汽车网络信息安全-ISO/SAE 21434解析（中）
目录 第七章-分布式网络安全活动 1. 供应商能力评估 2. 报价 3. 网络安全职责界定 第八章-持续的网络安全活动 1. 网路安全监控 2. 网络安全事件评估 3. 漏洞分析 4. 漏洞管理 第九章-概念阶段 1. 对象定义 2. 网路安全目标 3. 网络安全概念 第十章 - 产品开发 第十…...
Tailwind CSS - Tailwind CSS 引入（安装、初始化、配置、引入、构建、使用 Tailwind CSS）
一、Tailwind CSS 概述 Tailwind CSS 是一个功能优先的 CSS 框架，它提供了大量的实用类（utility classes），允许开发者通过组合这些类来快速构建用户界面 Tailwind CSS 与传统的 CSS 框架不同（例如，Bootstr…...
Python-基于PyQt5,pdf2docx,pathlib的PDF转Word工具
前言：日常生活中，我们常常会跟WPS Office打交道。作表格，写报告，写PPT......可以说，我们的生活已经离不开WPS Office了。与此同时，我们在这个过程中也会遇到各种各样的技术阻碍，例如部分软件的PDF转Word需要收取额外费用等。那么，可不可以自己开发一个小工具来实现PDF转…...
FreeRTOS学习 --- 中断管理
什么是中断？ 让CPU打断正常运行的程序，转而去处理紧急的事件（程序），就叫中断 中断执行机制，可简单概括为三步： 1，中断请求 外设产生中断请求（GPIO外部中断、定时器中断…...
【小鱼闪闪】单片机开发工具——米思齐软件下载安装（图文）
浏览器打开网址 mixly.org, 在软件平台选择mixly离线版。 最新版本为3.0，会支持audinio， ESP32、ESP8266 ， 可以选择下载安装器或者完整版。 这里选择下载安装器，下载后运行“一键更新.bat”，即可自动下载最新版本的M…...
HarmonyOS：创建应用静态快捷方式
一、前言 静态快捷方式是一种在系统中创建的可以快速访问应用程序或特定功能的链接。它通常可以在长按应用图标，以图标和相应的文字出现在应用图标的上方，用户可以迅速启动对应应用程序的组件。使用快捷方式，可以提高效率，节省了查…...
企业微信远程一直显示正在加载
企业微信远程一直显示正在加载 1.问题描述2.问题解决 系统：Win10 1.问题描述 某天使用企业微信给同事进行远程协助的时候，发现一直卡在正在加载的页面，如下图所示 2.问题解决 经过一番查找资料后，我发现可能是2个地方出了问题…...
FireFox | Google Chrome | Microsoft Edge 禁用更新 final版
之前的方式要么失效，要么对设备有要求，这次梳理一下对设备、环境几乎没有要求的通用方式，universal & final 版。 1.Firefox 方式 FireFox火狐浏览器企业策略禁止更新_火狐浏览器禁止更新-CSDN博客 这应该是目前最好用的方式。火狐也…...
【C++】类和对象（5）
目录 一、构造函数补充1、初始化列表 二、类型转换三、static成员四、友元1、友元函数2、友元类 五、内部类六、匿名对象 一、构造函数补充 对于之前讲解的构造函数，还有一些更深层次的内容要进行补充，接下来进行补充内容的讲解。 1、初始化列表 在我…...
芸众商城小程序会员页面部分图标不显示问题解决办法
我遇到的问题 如下图所示，会员中心这里的图标在小程序端显示异常。但是在网页端又是能够正常显示的。 小程序端截图： 网页端截图： 我的解决方法 检查使用的小程序版本，比如这里使用的是1.2.238版本的小程序，最后…...
Spring Web MVC基础第一篇
目录 1.什么是Spring Web MVC？ 2.创建Spring Web MVC项目 3.注解使用 3.1RequestMapping（路由映射） 3.2一般参数传递 3.3RequestParam（参数重命名） 3.4RequestBody（传递JSON数据） 3.5Pa…...
Privacy Eraser，电脑隐私的终极清除者
Privacy Eraser 是一款专为保护用户隐私而设计的全能型软件，它不仅能够深度清理计算机中的各类隐私数据，还提供了多种系统优化工具，帮助用户提升设备的整体性能。通过这款软件，用户可以轻松清除浏览器历史记录、缓存文件、Cookie、…...
编程题-三数之和（中等）
题目： 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ，同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三…...
mysql中in和exists的区别？
大家好，我是锋哥。今天分享关于【mysql中in和exists的区别？】面试题。希望对大家有帮助； mysql中in和exists的区别？ 在 MySQL 中，IN 和 EXISTS 都是用于子查询的操作符，但它们在执行原理和适用场景上有所不…...
ThinkPHP 8 操作JSON数据
【图书介绍】《ThinkPHP 8高效构建Web应用》-CSDN博客 《2025新书 ThinkPHP 8高效构建Web应用 编程与应用开发丛书 夏磊 清华大学出版社教材书籍 9787302678236 ThinkPHP 8高效构建Web应用》【摘要 书评 试读】- 京东图书 使用VS Code开发ThinkPHP项目-CSDN博客 编程与应用开…...
深入剖析 Docker 的镜像分层存储机制
目录 一、基本原理 镜像构成 UnionFS 二、工作方式 镜像构建时 容器启动时 三、优势 共享与复用 高效存储和传输 快速镜像构建 可追溯性和可维护性 四、相关命令 查看镜像分层 基于已有镜像创建新镜像 Docker 凭借其卓越的性能和极高的灵活性，已然成为众多开发者…...
本地部署DeepSeek
1、打开ollama,点击“Download” Ollamahttps://ollama.com/ 2、下载完成后，安装ollama.exe 3、安装完成后，按"windowsR",输入"cmd” 4、输入“ollama -v”，查看版本，表示安装成功 5、返回ollama网页，…...
10.5 LangChain Model I/O 深度解析：如何用标准化接口打通大模型开发的“任督二脉”？
LangChain Model I/O 深度解析：如何用标准化接口打通大模型开发的“任督二脉”？ 关键词： LangChain Model I/O、大模型抽象、LLM标准化调用、多模型支持、流式响应 一、为什么需要标准化的大模型抽象？ 1. 大模型开发的现实困境 厂商锁定风险：代码深度耦合特定API（如Op…...
使用Pygame制作“俄罗斯方块”游戏
1. 前言 俄罗斯方块（Tetris） 是一款由方块下落、行消除等核心规则构成的经典益智游戏： 每次从屏幕顶部出现一个随机的方块（由若干小方格组成），玩家可以左右移动或旋转该方块，让它合适地堆叠在…...