C++:探索AVL树旋转的奥秘
文章目录
- 前言 AVL树为什么要旋转?
- 一、插入一个值的大概过程
- 1. 插入一个值的大致过程
- 2. 平衡因子更新原则
- 3. 旋转处理的目的
- 二、左单旋
- 1. 左单旋旋转方式总处理图
- 2. 左单旋具体会遇到的情况
- 3. 左单旋代码总结
- 三、右单旋
- 1. 右单旋旋转方式总处理图
- 2. 右单旋具体会遇到的情况
- 3. 右单旋代码总结
- 四、双旋
- 1. 右左双旋旋转逻辑
- 2. 右左双旋可能会遇到的问题辨析
- 3. 右左双旋平衡因子的处理
- 4. 右左双旋代码总结
- 五、左右双旋
- 总结
前言 AVL树为什么要旋转?
AVL树需要旋转是为了保持平衡。当插入或删除节点后,某些子树的高度差超过1,就会破坏AVL树的平衡性。为了让树重新平衡,避免一边过高、一边过低的情况,旋转可以调整节点的位置,使树保持左右高度差不超过1。这样做的目的是确保查找、插入、删除操作的效率始终保持在 O(log₂ n)
。简单来说,旋转就是“调位置,让树站得更稳”。
一、插入一个值的大概过程
1. 插入一个值的大致过程
-
按照二叉搜索树规则插入:
插入的新节点位置依据二叉搜索树的性质确定,即小于当前节点放左子树,大于当前节点放右子树。 -
更新平衡因子:
新增节点后,只会影响其祖先节点的高度,可能导致部分祖先节点的平衡因子发生变化。从新增节点向根节点逐步更新平衡因子。如果在更新过程中某节点的平衡因子变为2或-2,说明该节点的子树已经不平衡,需要旋转处理;否则,插入结束。 -
检查平衡并调整:
- 如果更新平衡因子的过程中没有发现问题(平衡因子均为0、1或-1),插入操作完成。
- 如果出现不平衡,则对不平衡的子树进行旋转处理。旋转不仅恢复子树的平衡,还会降低子树的高度,确保不再影响其父节点的平衡因子,从而结束插入过程。
2. 平衡因子更新原则
-
平衡因子公式:
只有子树高度发生变化时,才会影响当前节点的平衡因子。
-
更新规则:
- 若新增节点在父节点的右子树,则父节点的平衡因子增加1(
+1
)。 - 若新增节点在父节点的左子树,则父节点的平衡因子减少1(
-1
)。
- 若新增节点在父节点的右子树,则父节点的平衡因子增加1(
-
更新停止条件:
- 平衡因子变为0:
父节点平衡因子从-1
变为0
或从1
变为0
,说明新增节点插入到高度较低的一侧,子树高度未改变,更新过程可以停止。 - 平衡因子变为1或-1:
父节点平衡因子从0
变为1
或从0
变为-1
,说明新增节点插入后子树高度增加,但仍符合平衡要求,需继续向上更新。 - 平衡因子变为2或-2:
父节点平衡因子从1
变为2
或从-1
变为-2
,说明子树高度过高,已失去平衡,需要进行旋转处理。
- 平衡因子变为0:
3. 旋转处理的目的
- 恢复平衡:
通过单旋转或双旋转调整节点位置,使当前子树符合平衡要求。 - 降低子树高度:
旋转后,子树高度恢复到插入前的水平,确保不会对更高层节点产生影响,插入过程结束。
二、左单旋
形成条件:parent->_bf == 2 && cur->_bf == 1
1. 左单旋旋转方式总处理图
-
失衡检测:
- 当插入的新节点导致父节点的平衡因子为
2
,并且新节点被插入到右子树的右侧时,发生右右失衡(RR失衡)。
- 当插入的新节点导致父节点的平衡因子为
-
旋转操作:
- 左单旋的核心目标是将父节点的右子树(即失衡节点的右子树根)提升为新的根节点,并将原来的父节点挂接到新根节点的左子树上。
parent->right = cur->left; // 将右子树的左子树挂接到父节点的右子树
cur->left = parent; // 将父节点挂接为右子树的左子树
-
处理父节点链接问题:
- 需要确保旋转后父节点的父节点(如果存在)正确地连接到新的根节点。
- 如果原父节点有父节点(即不是根节点),则要更新父节点的左右子树指向新的根节点。
- 如果原父节点是根节点,则更新树的根节点。
- 需要确保旋转后父节点的父节点(如果存在)正确地连接到新的根节点。
-
更新平衡因子:
- 旋转后,原父节点和新的根节点的平衡因子都应设置为
0
,因为旋转使得这两颗子树已经平衡。
- 旋转后,原父节点和新的根节点的平衡因子都应设置为
-
旋转结束:
- 完成旋转后,新的根节点成为子树的根,树恢复平衡。
- 完成旋转后,新的根节点成为子树的根,树恢复平衡。
2. 左单旋具体会遇到的情况
我们具体会遇到比如 h = 0, h = 1, h = 2 …无穷多种情况:
分析如下:
3. 左单旋代码总结
// 左单旋
void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;// 重新链接parent->_right = curleft;if (curleft) // 如果curleft存在{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left = parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}// 更改平衡因子parent->_bf = cur->_bf = 0;
}
三、右单旋
形成条件:parent->_bf == -2 && cur->_bf == -1
1. 右单旋旋转方式总处理图
右单旋处理的方式与左单旋是一致的,只不过是反过来了,就不多介绍了。
-
失衡检测:
- 当插入的新节点导致父节点的平衡因子为
-2
,并且新节点被插入到左子树的左侧时,发生左左失衡(LL失衡)。
- 当插入的新节点导致父节点的平衡因子为
-
旋转操作:
- 右单旋的核心目标是将父节点的左子树(即失衡节点的左子树根)提升为新的根节点,并将原来的父节点挂接到新根节点的右子树上。
parent->left = cur->right; // 将左子树的右子树挂接到父节点的左子树
cur->right = parent; // 将父节点挂接为左子树的右子树
-
处理父节点链接问题:
- 需要确保旋转后父节点的父节点(如果存在)正确地连接到新的根节点。
- 如果原父节点有父节点(即不是根节点),则要更新父节点的左右子树指向新的根节点。
- 如果原父节点是根节点,则更新树的根节点。
- 需要确保旋转后父节点的父节点(如果存在)正确地连接到新的根节点。
-
更新平衡因子:
- 旋转后,原父节点和新的根节点的平衡因子都应设置为
0
,因为旋转使得这两颗子树已经平衡。
- 旋转后,原父节点和新的根节点的平衡因子都应设置为
-
旋转结束:
- 完成旋转后,新的根节点成为子树的根,树恢复平衡。
2. 右单旋具体会遇到的情况
3. 右单旋代码总结
// 右单旋
void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;if (ppnode == nullptr){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}// 改变平衡因子parent->_bf = cur->_bf = 0;
}
四、双旋
1. 右左双旋旋转逻辑
形成条件:parent->_bf == 2 && cur->_bf == -1
这里是右左双旋的处理方式:
- 插入新节点
- 以cur进行右单旋
- 以parent进行左单旋
2. 右左双旋可能会遇到的问题辨析
h = 0 的情况:
h = 1 的情况:
h = 2 的情况:
3. 右左双旋平衡因子的处理
右左双旋的平衡因子与前面的单旋的平衡因子处理方式不同,单旋平衡因子再旋转过后全都是0,但是双旋的平衡因子不一样。
它分为以下三种情况:
- h = 0 的情况,
及curleft._bf = 0
,
结果——>parent._bf = 0,cur._bf = 0,curleft._bf = 0
- h > 0 的情况下,
及curleft._bf == 1
,
以以下C位置插入引发的旋转。
结果: parent._bf = -1,cur._bf = 0,curleft._bf = 0
- h > 0 的情况下,
及curleft._bf == -1
,
以以下B位置插入引发的旋转。
结果: parent._bf = 0,cur._bf = 1,curleft._bf = 0
4. 右左双旋代码总结
// 右左双旋
void RotateRL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;// 右旋RotateR(cur);// 左旋RotateL(parent);// 调整平衡因子if (bf == 0){parent->_bf = 0;cur->_bf = 0;curleft->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = 0;curleft->_bf = 0;}else if (bf == -1){parent->_bf = 0;cur->_bf = 1;curleft->_bf = 0;}else{assert(false);}
}
五、左右双旋
形成条件:parent->_bf == -2 && cur->_bf == 1
左右双旋与右左双旋类型,就是反过来的过程~
// 左右双旋
void RotateLR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}
}
总结
那么,到这里就结束啦!
通过学习AVL树的旋转机制,我们不仅掌握了数据结构平衡的重要性,更感受到了算法的巧妙与严谨。
如果对您有帮助的话,麻烦点一个一键三连,谢谢啦~😘😘😘😘
相关文章:

C++:探索AVL树旋转的奥秘
文章目录 前言 AVL树为什么要旋转?一、插入一个值的大概过程1. 插入一个值的大致过程2. 平衡因子更新原则3. 旋转处理的目的 二、左单旋1. 左单旋旋转方式总处理图2. 左单旋具体会遇到的情况3. 左单旋代码总结 三、右单旋1. 右单旋旋转方式总处理图2. 右单旋具体会遇…...

2. Django中的URL调度器 (自定义路径转换器)
在 Django 中,URL 路由通常使用路径转换器(path converters)来匹配和捕获 URL 中的特定模式,例如整数、字符串或 slug 等。默认情况下,Django 提供了一些内置的路径转换器,如 <int>、<str>、&l…...
深度学习:神经网络中线性层的使用
深度学习:神经网络中线性层的使用 在神经网络中,线性层(也称为全连接层或密集层)是基础组件之一,用于执行输入数据的线性变换。通过这种变换,线性层可以重新组合输入数据的特征,并将其映射到新…...
【刷题】算法设计题+程序设计题【2】2019-2024
11.202019年真题*2BST二叉排序树分裂、双向冒泡排序 2019 真题 【2019 1】编写算法,将一棵二叉排序树 分解成两棵二叉排序树 t1和t2,使得t1中的所有结点关键字的值都小于x,t2中所有结点关键字都大于x。 typedef struct BSTNode{int data;str…...
搭建es环境
centos7搭建elasticsearch环境 首先考虑使用 Docker 来安装 Elasticsearch、Kibana 和 Logstash。在安装过程中,可能会遇到一些问题,但通过适当的方法可以解决。 docker pull docker.elastic.co/elasticsearch/elasticsearch:8.14.3 首先创建一个网络&a…...
阿里云和七牛云对象存储区别和实现
七牛云对象存储操作(QiniuUtil) 配置:使用 com.qiniu.storage.Configuration 类来配置上传设置,如指定区域(Region)和分片上传版本。上传管理器:通过 UploadManager 类来处理文件上传。认证&am…...

uniapp微信小程序接入airkiss插件进行WIFI配网
本文可参考uniapp小程序插件 一.申请插件 微信公众平台设置页链接:微信公众平台 登录您的小程序微信公众平台,进入设置页,在第三方设置->插件管理->添加插件中申请AiThinkerAirkissforWXMini插件,申请的插件appId为【wx6…...

03 —— Webpack 自动生成 html 文件
HtmlWebpackPlugin | webpack 中文文档 | webpack中文文档 | webpack中文网 安装 npm install --save-dev html-webpack-plugin 下载html-webpack-plugin本地软件包 npm i html-webpack-plugin --save-dev 配置webpack.config.js让webpack拥有插件功能 const HtmlWebpack…...

Python毕业设计选题:基于python的豆瓣电影数据分析可视化系统-flask+spider
开发语言:Python框架:flaskPython版本:python3.7.7数据库:mysql 5.7数据库工具:Navicat11开发软件:PyCharm 系统展示 系统首页 个人中心 管理员登录界面 管理员功能界面 电影管理 用户管理 系统管理 摘要…...
抽象类能使用final修饰吗?
不能。 在java中,抽象类不能使用final修饰。原因是final修饰符用于类不能被继承,而抽象类的主要用途就是被继承以提供基础实现或定义抽象方法供子类实现。这两个互相矛盾,因此不能同时使用。 具体解释 abstract修饰符:用于定义一个抽象类&…...
C语言内存:我家大门常打开
C语言本着自由开放的理念,并不禁止程序访问非法内存。 什么是非法内存?就是那本不是你家的地,你却硬跑过去种庄稼。 或者,你在澡堂子里拿着自己的钥匙去捅别人的柜。 这种行为当然后果难料。 可能你捅了半天,火花冒…...

路由协议——iBGP与EBGP
一、适用场景 1、企业需要连接总部与分部,但总部与分部运行着不同的路由协议,总部到分部有自建的专线,端到端的设备支持BGP路由协议。 2、网络运营商,如电信、联通、移动等,各区域的ip路由表庞大,若要完成…...

【Linux】基础02
Linux编译和调试 VI编辑文件 vi : 进入文件编辑 是命令行模式 i :从光标处进入插入模式 dd : 删除光标所在行 n dd 删除指定行数 Esc : 退出插入模式 : 冒号进入末行模式 :wq : 保存退出 :q : 未修改文件可以退出 :q! …...
Elasticsearch面试内容整理-安全与权限管理
在 Elasticsearch 中,安全与权限管理至关重要,特别是当系统处理敏感数据时。Elasticsearch 提供了一套全面的安全机制来确保数据的机密性、完整性和可用性。以下是 Elasticsearch 安全与权限管理的详细介绍。 安全组件概述 Elasticsearch 的安全功能由 Elastic Stack 提供的一…...

【数据分享】中国汽车工业年鉴(1986-2023)
本年鉴是由工业和信息化部指导,中国汽车技术研究中心有限公司与中国汽车工业协会联合主办。《年鉴》是全面、客观记载中国汽车工业发展与改革历程的重要文献,内容涵盖汽车产业政策、标准、企业、市场以及全国各省市汽车工业发展情况,并调查汇…...

el-cascader 使用笔记
1.效果 2.官网 https://element.eleme.cn/#/zh-CN/component/cascader 3.动态加载(官网) <el-cascader :props"props"></el-cascader><script>let id 0;export default {data() {return {props: {lazy: true,lazyLoad (…...
代替Spinnaker 的 POINTGREY工业级相机 FLIR相机 Python编程案例
SpinnakerSDK_FULL_4.0.0.116_x64 是一个用于FLIR相机的SDK,主要用于图像采集和处理。Spinnaker SDK主要提供C接口,无法直接应用在python环境。本文则基于Pycharm2019python3.7的环境下,调用opencv,EasySpin,PySpin,的库实现POINTGREY工业级相…...

网络篇12 | SSH2协议应用,禁SFTP子模式实现文件传输
网络篇12 | SSH2的应用 解决的业务问题协议选定SSH2(Secure Shell 2,目前基本用这个)SSH1(Secure Shell 1)Telnet 代码实现落地方案1:ganymed-ssh2maven坐标关键源代码技术效果验证连接高版本OpenSSH报错分…...

MetaGPT实现多动作Agent
异步编程学习链接 智能体 LLM观察思考行动记忆 多智能体 智能体环境SOP评审路由订阅经济 教程地址 多动作的agent的本质是react,这包括了think(考虑接下来该采取啥动作)act(采取行动) 在MetaGPT的examples/write_…...
docker更新镜像源
常用的国内 Docker 镜像加速器 1. 阿里云镜像加速器:https://cr.console.aliyun.com/cn-hangzhou/instances/mirrors 2. 腾讯云镜像加速器:https://cloud.tencent.com/document/product/457/33221 3. 网易云镜像加速器:https://hub-mirror…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...

基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...

【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...