平衡二叉树（AVL树）
平衡二叉树是啥我就不多说了，本篇博客只讲原理与方法。
首先引入平衡因子的概念。平衡因子（Balance Factor），以下简称bf。
bf = 右子树深度 - 左子树深度。平衡结点的平衡因子可为：-1，0，1。除此之外的结点都需要调整。
如下图：
AVL树的基础创建
创建AVL树的基本架构与二叉搜索树的创建基本一样，不同是为了方便后续的旋转与平衡因子的改变，多引入bf与parent记录结点的平衡因子与该结点的父节点，形成三叉链。
AVL树的旋转
右单旋
新节点插入较高左子树的左侧
以上过程可以简单的看作是30的右子树变成60的左子树，60变成30的右子树。其中h高度可以取值为0。
这是两种不同的情况。不同点在于30的右子树为NULL，此时并不需要更新其子树的parent结点的指向。每个结点的bf统统归零。
左单旋
新节点插入较高右子树的右侧
以上过程可简单看成，60的左变成30的右，30变成60的左。其中60的左可以为空。
和右单旋同理。
先左单旋再右单旋（LR）
新节点插入较高左子树的右侧
路径可以形象的看作“<”先左后右（LR）
将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再
考虑平衡因子的更新。
平衡因子的更新
情况一：如上图在b处插入后60结点的bf=-1，最终平衡树的平衡因子为60：0，30：0，90：1。
情况二：
在c处插入后60结点的bf=1,最终平衡因子为30：-1，60：0，90：0。
情况三：
插入60结点，60结点bf=1，最终平衡因子为30：0，60：0，90：0。
先右单旋再左单旋（RL）
新节点插入较高右子树的左侧
路径可以形象看作“>’，先右后左（RL）。
将双旋变成单旋后再旋转，即：先对90进行左单旋，然后再对30进行右单旋，旋转完成后再
考虑平衡因子的更新。
平衡因子讨论和LR类似。
代码
#pragma once
#include <iostream>
#include <stdlib.h>
using namespace std;template <class K,class V>
struct AVLtreeNode {AVLtreeNode<K, V>* _right;AVLtreeNode<K, V>* _left;AVLtreeNode<K, V>* _parent;AVLtreeNode(const pair<K,V>& kv):_right(nullptr),_left(nullptr),_parent(nullptr),_kv(kv),_bf(0){}int _bf; //平衡因子pair<K, V> _kv;
};
template <class K,class V>
class AVLtree {typedef AVLtreeNode<K,V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent){if (cur == parent->_right){parent->_bf++;}else{parent->_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){//parnet所在的子树出现不平衡，需要旋转if (parent->_bf == 2){if (cur->_bf == 1){RotateL(parent);}else if (cur->_bf == -1){RotateRL(parent);}}else if (parent->_bf == -2){if (cur->_bf == -1){RotateR(parent);}else if(cur->_bf==1){RotateLR(parent);}}break;}}return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;subR->_left = parent;Node* node = parent->_parent;parent->_parent = subR;//1、原来parent是这棵树的根，现在subR是根//2、parent不是根，parent还有他自己的_parent，现在让_parent指向subRif (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (node->_left == parent){node->_left = subR;}else{node->_right = subR;}subR->_parent = node;}parent->_bf = subR->_bf = 0;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subL->_right;Node* node = parent->_parent;subL->_right = parent;if (subLR) subLR->_parent = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parent == node->_left){node->_left = subL;}else{node->_right = subL;}subL->_parent = node;}subL->_bf = parent->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == 0){subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first <<" : " << root->_kv.second << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}int Height(Node* root){if (root == nullptr) return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;}bool _IsBalance(Node*root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return abs(leftHeight - rightHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);}bool IsBalance(){return _IsBalance(_root);}private:Node* _root=nullptr;
};void TestAVLTree()
{int a[] = { 16,3,7,11,9,26,18,14,15 };AVLtree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsBalance() << endl;
}相关文章：
平衡二叉树（AVL树）
平衡二叉树是啥我就不多说了，本篇博客只讲原理与方法。 首先引入平衡因子的概念。平衡因子（Balance Factor），以下简称bf。 bf 右子树深度 - 左子树深度。平衡结点的平衡因子可为：-1，0，1。除此…...
SSM架构 +java后台 实现rtsp流转hls流，在前端html上实现视频播放
序言：书接上文，我们继续 SSM架构 NginxFFmpeg实现rtsp流转hls流，在前端html上实现视频播放 步骤一：把rtsp流转化为hls流，用Java代码进行转换 package com.tools;import java.io.BufferedReader; import java.io.IOExc…...
贪心算法--
1.柠檬水找零 link:860. 柠檬水找零 - 力扣（LeetCode） code class Solution { public:bool lemonadeChange(vector<int>& bills) {// 贪心算法， 优先花出大面额bill， 尽可能保护小面额billint five 0, ten 0;// 不…...
【从0到1搞懂大模型】神经网络的实现：数据策略、模型调优与评估体系（3）
一、数据集的划分 （1）按一定比例划分为训练集和测试集 我们通常取8-2、7-3、6-4、5-5比例切分，直接将数据随机划分为训练集和测试集，然后使用训练集来生成模型，再用测试集来测试模型的正确率和误差，以验证…...
CTF工具集合-持续更新
工具地址https://github.com/huan-cdm/ctf_tools工具介绍： 1.ARCHPR：压缩包密码破解工具 2.StegSolve-1.4.jar：隐写图片查看工具 3.ctf_decrypt_tool.rar：随波逐流CTF编码工具 4.010_Editor_All_Versions_For_Windows_CracKed.…...
小方摄像头接入本地服务器的方法
最早众筹时买了几个小方摄像头，后来嫌弃分辨率，就淘汰吃灰好几年，最近想折腾个摄像头识别的小项目，秉着不投入先凑合跑起来的原则，想到了尘封已久的小方，想看看能不能通过网络拉取数据流。 搜索了下&#x…...
取反符号~
取反符号 ~ 用于对整数进行按位取反操作。它会将二进制表示中的每一位取反，即 0 变 1，1 变 0。 示例 a 5 # 二进制表示为 0000 0101 b ~a # 按位取反，结果为 1111 1010（补码表示） print(b) # 输出 -6解释 5 的二…...
Jenkins实现自动化构建与部署：上手攻略
一、持续集成与Jenkins核心价值 1.1 为什么需要自动化构建？ 在现代化软件开发中，团队每日面临以下挑战： 高频代码提交：平均每个开发者每天提交5-10次代码。多环境部署：开发、测试、预发布、生产环境需频繁同步。复杂…...
爱普生温补晶振 TG5032CFN高精度稳定时钟的典范
在科技日新月异的当下，众多领域对时钟信号的稳定性与精准度提出了极为严苛的要求。爱普生温补晶振TG5032CFN是一款高稳定性温度补偿晶体振荡器（TCXO）。该器件通过内置温度补偿电路，有效抑制环境温度变化对频率稳定性的影响&#x…...
【Java 面试 八股文】计算机网络篇
操作系统篇 1. 什么是HTTP? HTTP 和 HTTPS 的区别?2. 为什么说HTTPS比HTTP安全? HTTPS是如何保证安全的？3. 如何理解UDP 和 TCP? 区别? 应用场景?3.1 TCP 和 UDP 的特点3.2 适用场景 4. 如何理解TCP/IP协议?5. DNS协议 是什么？说说DNS 完整的查询…...
OpenHarmony5.0分布式系统源码实现分析—软总线
一、引言 OpenHarmony 作为一款面向万物互联的操作系统，其分布式软总线（Distributed SoftBus）是实现设备间高效通信和协同的核心技术之一。分布式软总线通过构建一个虚拟的总线网络，使得不同设备能够无缝连接、通信和协同工作。本…...
Spring Boot/Spring Cloud 整合 ELK（Elasticsearch、Logstash、Kibana）详细避坑指南
我们在开发中经常会写日志，所以需要有个日志可视化界面管理，使用ELK可以实现高效集中化的日志管理与分析，提升性能稳定性，满足安全合规要求，支持开发运维工作。 下述是我在搭建ELK时遇到的许许多多的坑，希望…...
云原生周刊：Istio 1.25.0 正式发布
开源项目推荐 Dstack Dstack 是一个开源的 AI 计算管理平台，旨在简化 AI 任务的部署和管理。它支持本地和云端运行 AI 工作负载，并提供自动化的 GPU 资源调度，使开发者能够更高效地利用计算资源。Dstack 兼容 K8s，可以无缝集成到…...
微前端如何拯救大型项目
前言 在前端开发的世界中，我们经常会遇到这样的问题：一个大型项目往往由多个团队共同开发，每个团队负责一部分功能。然而，随着项目的不断扩大和复杂化，前端代码库变得越来越庞大和难以维护。这时，微前端&a…...
RabbitMQ 高级特性：从 TTL 到消息分发的全面解析 （下）
RabbitMQ高级特性 RabbitMQ 高级特性解析：RabbitMQ 消息可靠性保障 （上）-CSDN博客 RabbitMQ 高级特性：从 TTL 到消息分发的全面解析 （下）-CSDN博客 引言 RabbitMQ 作为一款强大的消息队列中间件ÿ…...
OpenManus-通过源码方式本地运行OpenManus，含踩坑及处理方案
前言：最近 Manus 火得一塌糊涂啊，OpenManus 也一夜之间爆火，那么作为程序员应该来尝尝鲜 1、前期准备 FastGithub：如果有科学上网且能正常访问 github 则不需要下载此软件，此软件是提供国内直接访问 githubGit&#…...
Ubuntu22.04修改root用户并安装cuda
由于本人工作原因，经常会遇到需要给ubuntu打显卡驱动的问题，虽然说不难吧，但是耐不住机器多，重复多次也就烦了，于是抽出了一点时间，并且在deepseek的帮助之下，写了一个自动安装驱动的脚本&#…...
Java LeetCode 热题 100 回顾38
干货分享，感谢您的阅读！LeetCode 热题 100 回顾_力code热题100-CSDN博客 一、哈希部分 1.两数之和 （简单） 题目描述 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两…...
MySQL复习笔记
文章目录 1.MySQL1.1什么是数据库1.2 数据库分类1.3 MySQL简介1.4连接数据库 2. 操作数据库2.1 操作数据库2.2 数据库的列类型2.3 数据库的字段属性（重点）2.4 创建数据库表（重点）2.5 数据表的类型2.6 修改数据表 3. MySQL 数据管理…...
解释 TypeScript 中的类型系统，如何定义和使用类型？
1. 类型系统的核心作用 TypeScript类型系统本质上是JavaScript的静态类型增强方案，提供三个核心价值： 开发阶段类型检查（类似编译时eslint）更清晰的API文档（类型即文档）更好的IDE自动补全支持 代码示例&…...
安裝do時出現log file support is not available
“log file support is not available (press RETURN)” 这个提示信息表明日志文件支持不可用，让你按回车键继续。出现这种情况可能是因为 Odoo 的日志相关配置存在问题或者一些必要的依赖没有正确安装配置。以下是一些可以尝试的解决办法： 1. 检查 Odo…...
知识基础)
[HTTP协议]应用层协议HTTP从入门到深刻理解并落地部署自己的云服务(1)知识基础
[HTTP协议]应用层协议HTTP从入门到深刻理解并落地部署自己的云服务(1)知识基础 水墨不写bug 文章目录 (一)概念梳理1.什么是协议?2.什么是应用层?3. 为什么要进行分层？ （二）HTTP协议2.1 初识HTTP协议2.2HTTP协议的URL2.2.1域名2.2.2端口号2…...
机票改签请求
示例代码： tool def update_ticket_to_new_flight(ticket_no: str, new_flight_id: int) -> str:"""Update the users ticket to a new valid flight.Args:ticket_no (str): The ticket number to be updated.new_flight_id (int): The ID of th…...
linux下文件读写操作
Linux下，文件I/O是操作系统与文件系统之间进行数据传输的关键部分。文件I/O操作允许程序读取和写入文件，管理文件的打开、关闭、创建和删除等操作。 1. 文件描述符 在Linux中，每个打开的文件都由一个文件描述符来表示。文件描述符是一个非负…...
命名管道的创建和通信实现
目录 命名管道的创建 使用函数创建命名管道的通信 预备创建 makefile设计 server.hpp设计 clent.hpp设计 comm.hpp设计 server.cc设计 clent.cc设计 测试运行 今天我们来学习命名管道 由于匿名管道（pipe()）无法在两个毫不相干的进程之间进行通…...
C++和OpenGL实现3D游戏编程【连载24】——父物体和子物体之间的坐标转换
欢迎来到zhooyu的C++和OpenGL游戏专栏，专栏连载的所有精彩内容目录详见下边链接： 🔥C++和OpenGL实现3D游戏编程【总览】 父子物体的坐标转换 1、本节要实现的内容 前面章节我们了解了父物体与子物体的结构，它不仅能够表示物体之间的层次关系，更重要的一个作用就是展示物…...
)
21.HarmonyOS Next CustomSlider组件步长控制教程(三)
温馨提示：本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦！ 文章目录 1. 步长控制概述2. 步长基本概念2.1 什么是步长？2.2 步长的作用 3. 设置步长3.1 基本参数3.2 代码示例 4. 步长与范围的关系4…...
小白学习：rag向量数据库
学习视频： https://www.bilibili.com/video/BV11zf6YyEnT/?spm_id_from333.337.search-card.all.click 例子： 用户提出问题 客服机器人基于rag回答用户问题 过程拆解： 客户问题 – 转化为向量表示 – 在向量数据库中进行相似性搜索 – 系…...
STM32 CAN模块原理与应用详解
目录 概述 一、CAN模块核心原理 1. CAN协议基础 2. STM32 CAN控制器结构 3. 波特率配置 二、CAN模块配置步骤（基于HAL库） 1. 初始化CAN外设 2. 配置过滤器 3. 启动CAN通信 三、数据收发实现 1. 发送数据帧 2. 接收数据帧（中断方式…...
)
NO.29十六届蓝桥杯备战|string九道练习|reverse|翻转|回文(C++)
P5015 [NOIP 2018 普及组] 标题统计 - 洛谷 #include <bits/stdc.h> using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s;getline(cin, s);int sz s.size();int cnt 0;for (int i 0; i < sz; i){if (isspace(s[i]))continue…...
最新版本TOMCAT+IntelliJ IDEA+MAVEN项目创建（JAVAWEB）
前期所需： 1.apache-tomcat-10.1.18-windows-x64（tomcat 10.1.8版本或者差不多新的版本都可以） 2.IntelliJ idea 24年版本 或更高版本 3.已经配置好MAVEN了（一定先配置MAVEN再搞TOMCAT会事半功倍很多） 如果有没配置…...
MAC-禁止百度网盘自动升级更新
通过终端禁用更新服务（推荐） 此方法直接移除百度网盘的自动更新组件，无需修改系统文件。 步骤： 1.关闭百度网盘后台进程 按下 Command + Space → 输入「活动监视器」→ 搜索 BaiduNetdisk 或 UpdateAgent → 结束相关进程。 2.删除自动更新配置文件 打开终端…...
Unity DOTS从入门到精通之EntityCommandBufferSystem
文章目录 前言安装 DOTS 包ECBECB可以执行的指令示例： 前言 DOTS（面向数据的技术堆栈）是一套由 Unity 提供支持的技术，用于提供高性能游戏开发解决方案，特别适合需要处理大量数据的游戏，例如大型开放世界游…...
【AIGC系列】6：HunyuanVideo视频生成模型部署和代码分析
AIGC系列博文： 【AIGC系列】1：自编码器（AutoEncoder, AE） 【AIGC系列】2：DALLE 2模型介绍（内含扩散模型介绍） 【AIGC系列】3：Stable Diffusion模型原理介绍 【AIGC系列】4࿱…...
【Linux】使用问题汇总
#1 ssh连接的时候报Key exchange failed 原因：服务端版本高，抛弃了一些不安全的交换密钥算法，且客户端版本比较旧，不支持安全性较高的密钥交换算法。 解决方案： 如果是内网应用，安全要求不这么高…...
nnUNet V2修改网络——全配置替换MultiResBlock模块
更换前，要用nnUNet V2跑通所用数据集，证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构，初步了解要修改的网络，知己知彼，修改起来才能游刃有余。 MultiRes Block 是 MultiResUNet 中核心组件之一，旨在解决传统 U-Net 在处理多尺度医学图像时的局…...
Git合并工具在开发中的使用指南
在团队协作开发中，Git 是最常用的版本控制工具，而代码合并（Merge）是多人协作不可避免的环节。当多个开发者同时修改同一文件的相同区域时，Git 无法自动完成合并，此时需要借助合并工具（Merge Too…...
AutoDL平台租借GPU，创建transformers环境，使用VSCode SSH登录
AutoDL平台租借GPU，创建transformers环境，使用VSCode SSH登录 一、AutoDl平台租用GPU 1.注册并登录AutoDl官网：https://www.autodl.com/home 2.选择算力市场，找到需要的GPU： 我这里选择3090显卡 3.这里我们就选择P…...
listen EACCES: permission denied 0.0.0.0:811
具体错误 npm run serve> bige-v0.0.0 serve > viteThe CJS build of Vites Node API is deprecated. See https://vitejs.dev/guide/troubleshooting.html#vite-cjs-node-api-deprecated for more details. error when starting dev server: Error: listen EACCES: per…...
OpenAI API模型ChatGPT各模型功能对比，o1、o1Pro、GPT-4o、GPT-4.5调用次数限制附ChatGPT订阅教程
本文包含OpenAI API模型对比页面以及ChatGPT各模型功能对比表 - 截至2025最新整理数据：包含模型分类及描述；调用次数限制； 包含模型的类型有： Chat 模型（如 GPT-4o、GPT-4.5、GPT-4）专注于对话，…...
)
六十天前端强化训练之第十五天React组件基础案例：创建函数式组件展示用户信息(第15-21天：前端框架（React）)
欢迎来到编程星辰海的博客讲解 我们已经学了14天了，再坚持坚持，马上我们就可以变得更优秀了，加油，我相信大家，接下来的几天，我会给大家更新前端框架（React），看完可以给一…...
北大一二三四版全套DeepSeek教学资料
DeepSeek学习资料合集：https://pan.quark.cn/s/bb6ebf0e9b4d DeepSeek实操变现指南：https://pan.quark.cn/s/76328991eaa2 你是否渴望深入探索人工智能的前沿领域？是否在寻找一份能引领你从理论到实践，全面掌握AI核心技术的学习…...
计算机网络：计算机网络的组成和功能
计算机网络的组成： 计算机网络的工作方式： 计算机网络的逻辑功能; 总结： 计算机网络的功能： 1.数据通信 2.资源共享 3.分布式处理:计算机网络的分布式处理是指将计算任务分散到网络中的多个节点（计算机或设备&…...
管理网络安全
防火墙在 Linux 系统安全中有哪些重要的作用？ 防火墙作为网络安全的第一道防线，能够根据预设的规则，对进出系统的网络流量进行严格筛选。它可以阻止未经授权的外部访问，只允许符合规则的流量进入系统，从而保护系统免受…...
音频进阶学习十九——逆系统（简单进行回声消除）
文章目录 前言一、可逆系统1.定义2.解卷积3.逆系统恢复原始信号过程4.逆系统与原系统的零极点关系 二、使用逆系统去除回声获取原信号的频谱原系统和逆系统幅频响应和相频响应使用逆系统恢复原始信号整体代码如下 总结 前言 在上一篇音频进阶学习十八——幅频响应相同系统、全…...
Redis7系列：设置开机自启
前面的文章讲了Redis和Redis Stack的安装，随着服务器的重启，导致Redis 客户端无法连接。原来的是Redis没有配置开机自启。此文记录一下如何配置开机自启。 1、修改配置文件 前面的Redis和Redis Stack的安装的文章中已经讲了redis.config的配置…...
word甲烷一键下标
Sub 甲烷下标()甲烷下标 宏Selection.Find.ClearFormattingSelection.Find.Replacement.ClearFormattingWith Selection.Find.Text "CH4".Replacement.Text "CHguoshao4".Forward True.Wrap wdFindContinue.Format False.MatchCase False.MatchWhole…...
SSH 连接中主机密钥验证失败问题的解决方法
问题描述 在尝试通过 SSH 建立连接时，出现以下错误信息： WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY! Someone could be eavesdropping on you right now (man-in-the-middle attack…...
)
网络安全工具nc(NetCat)
NetCat是一个非常简单的Unix工具，可以读、写TCP或UDP网络连接(network connection)。它被设计成一个可靠的后端(back-end)工具，能被其它的程序程序或脚本直接地或容易地驱动。同时，它又是一个功能丰富的 网络调试和开发工具，因为它…...
探索在生成扩散模型中基于RAG增强生成的实现与未来
概述 像 Stable Diffusion、Flux 这样的生成扩散模型，以及 Hunyuan 等视频模型，都依赖于在单一、资源密集型的训练过程中通过固定数据集获取的知识。任何在训练之后引入的概念——被称为 知识截止——除非通过 微调 或外部适应技术（如 低秩适…...