AVLTree 旋转笔记(根据平衡因子插入的公式,贼好理解)
平衡因子
avltree是一棵每个节点的左右子树的高度差不超过1的二叉树搜索树,对于avltree最重要的就是对平衡因子的控制。
对于旋转我们重点要注意的是三个节点,以左旋举例,需要注意的就是parent,subr,subrl。而旋转的方式有四种,我们只需要根据对应的平衡因子来去判断该怎样旋转就行。
左旋
对于左旋, 我们可以用一张图来概括
这里的h是指高度>=0的avl树,这里只适用于parent平衡因子为2,subr平衡因子为1的情况。
我们需要注意这三者关系的变化,以及对应平衡因子的更新。
根据这几点我们就能写出对应的旋转代码:
void rotateL(avltnode*parent){//获得对应节点avltnode* subr = parent->_right;avltnode* subrl = subr->_left;avltnode* parentParent = parent->_parent;// 更新parent的右parent->_right = subr->_left;//更新subr的右节点subr->_left = parent;//更新parent的父节点parent->_parent = subr;//判断subrl是否为空节点,如果不为空就更新subrl的父节点if (subrl)subrl->_parent = parent;//判断parentParent节点是否为空if (parentParent == nullptr){//为空说明走到了最上面的节点subr->_parent = nullptr;_node = subr;}else{//如果没有则判断是要放在左边还是右边。if (parentParent->_left == parent)parentParent->_left = subr;else if (parentParent->_right = parent)parentParent->_right = subr;subr->_parent = parentParent;}//更新平衡因子subr->_bf = parent->_bf = 0;}
右旋
右旋也是可以用一张图来概括
这里的h是指高度>=0的avl树,这里只适用于parent平衡因子为-2,subl平衡因子为-1的情况。
逻辑跟左旋差不了多少,代码注释也不过多赘述。
代码:
//右旋void rotateR(avltnode* parent){avltnode* subl = parent->_left;avltnode* sublr = subl->_right;avltnode* parentParent = parent->_parent;subl->_right = parent;parent->_parent = subl;parent->_left = sublr;//判断sublr是否为空if (sublr) sublr->_parent = parent;//判断parentParent是否为空if (parentParent == nullptr){subl->_parent = nullptr;_node = subl;}else{if (parentParent->_left == parent){parentParent->_left = subl;}else{parentParent->_right = subl;}subl->_parent = parentParent;}subl->_bf = parent->_bf = 0;}
右左双旋
subl,sublr写错了,该市subr,subrl
这里只是一种情况
先将 subr 右旋,再将parent左旋,这里只适用于parent平衡因子为2,subr平衡因子为-1的情况。
这里的平衡因子更新其实是要根据subrl来定的:
因为subr为-1时subrl肯定是不为空的,这里也有一个总结,当然可以当一个公式记住就行。
代码:
void rotateRL(avltnode* parent)
{avltnode* subr=parent->_right;avltnode* subrl = subr->_left;int bf = subrl->_bf;rotateR(subr);rotateL(parent);//判断平衡因子if (bf == 0){subr->_bf = subrl->_bf = parent->_bf = 0;}else if (bf == 1){subr->_bf = subrl->_bf = 0;parent->_bf = -1;}else if (bf == -1){subr->_bf = 1;subrl->_bf = parent->_bf = 0;}else//如果都不属于就报错{assert(false);}
}
左右双选

这里只适用于parent平衡因子为-2,subl平衡因子为1的情况
也就类似于右左双旋
代码:
void rotateLR(avltnode*parent){avltnode* subl = parent->_left;avltnode* sublr = subl->_right;int bf = sublr->_bf;rotateL(subl);rotateR(parent);if (bf == 0){subl->_bf = parent->_bf = sublr->_bf = 0;}else if (bf == -1){subl->_bf = sublr->_bf = 0;parent->_bf = 1;}else if (bf == 1){subl->_bf = -1;sublr->_bf = parent->_bf = 0;}}
总结
其实说avl树很难,但是当你根据公式来写这棵树,其实他也并不是很复杂。但是最终我们还是要去理解avl树为什么要这样旋转。
相关文章:
AVLTree 旋转笔记(根据平衡因子插入的公式,贼好理解)
平衡因子 avltree是一棵每个节点的左右子树的高度差不超过1的二叉树搜索树,对于avltree最重要的就是对平衡因子的控制。 对于旋转我们重点要注意的是三个节点,以左旋举例,需要注意的就是parent,subr,subrl。而旋转的方…...
STM32(十八):SPI通信
SPI通信: SPI(Serial Peripheral Interface)是由Motorola公司开发的一种通用数据总线 四根通信线:SCK(Serial Clock)、MOSI(Master Output Slave Input)主机输出从机输入、MISO&…...
Redis持久化机制(RDBAOF详解)
目录 一、Redis持久化介绍二、Redis持久化方式1、RDB持久化(1) 介绍(2) RDB持久化触发机制(3) RDB优点和缺点(4) RDB流程 2、AOF(append only file)持久化(1) 介绍(2) AOF优点和缺点(3) AOF文件重写(4) AOF文件重写流程 三、AOF和RDB持久化注意事项 一、Redis持久化介绍 Redis…...
蛋白质结构中pdbx_strand_id和entity_id相互转化
在蛋白质结构中,entity_id 和 pdbx_strand_id 表示的是不同的概念,涉及到不同层次的信息。 1. entity_id (实体 ID): 定义:entity_id 标识蛋白质结构中的一个“实体”(entity)。一个实体可以是一个多肽链、DNA 链、RNA 链,或者某些小分子(如辅因子、配体等)。特点:每…...
【父子线程传值TransmittableThreadLocal使用踩坑-及相关知识拓展】
文章目录 一.业务背景二.TransmittableThreadLocal是什么?三.问题复现1.定义注解DigitalAngel2.定义切面3.TransmittableThreadLocal相关4.线程池配置信息5.Controller6.Service7.测试结果8.问题分析9 解决办法及代码改造10.最终测试: 四.与 ThreadLocal…...
03 快乐树
快乐树 我们由题可以得出结论:一共有三种情况,但实际中第三中情况不存在。 证明第三中情况不存在: 我敲的代码 public boolean isHappy(int n) {int slown;int fastn;while(true) {int sum0;while(slow!0) {sum(slow%10)*(slow%10);slow/1…...
springboot+react实现移动端相册(上传图片到oss/ 批量删除/ 查看图片详情等功能)
相册页面及功能展示: react前端结构及代码: Java后端结构及代码 数据库结构: photo: user 这是首个利用AI自有知识构建的简易相册系统,项目是react构造前端spring boot构造后端。 前端有四个主要页面࿱…...
Python、R语言Lasso、Ridge岭回归、XGBoost分析Airbnb房屋数据:旅游市场差异、价格预测|数据分享...
全文链接:https://tecdat.cn/?p37839 分析师:Kefan Yu 在大众旅游蓬勃发展的背景下,乡村旅游已成为推动乡村经济、社会和文化发展的关键力量。当前,乡村旅游接待设施主要以招待所、小宾馆和农家乐等形式存在。然而,一…...
Spring Boot驱动的交互式作业管理系统:师生共评功能实现
1系统概述 1.1 研究背景 如今互联网高速发展,网络遍布全球,通过互联网发布的消息能快而方便的传播到世界每个角落,并且互联网上能传播的信息也很广,比如文字、图片、声音、视频等。从而,这种种好处使得互联网成了信息传…...
基于SSM的旅游网站【附源码】
基于SSM的旅游网站(源码L文说明文档) 目录 4 系统设计 4.1 系统概要设计 4.2 系统功能结构设计 4.3 数据库设计 4.3.1 数据库E-R图设计 4.3.2 数据库表结构设计 5 系统实现 5.1 管理员功能介绍 5.1.1 用户管理 5.1.2 …...
Python实现将目标文本批量存入Word,并将文本段落的开头进行缩进处理(11)
前言 本文是该专栏的第11篇,后面会持续分享Python办公自动化干货知识,记得关注。 在用python对目标文本进行批量自动化操作的时候,你可能会遇到这样的需求——“现有大批量的文本内容,需要通过python将其批量存入docx(word)文档中,而且每个段落的开头需要进行缩进处理”…...
el-select 下拉框选项文字过长解决方案
首先给下拉框设置类名,即popper-class属性,并且给el-option增加title属性 <el-selectv-model"item.portrayalItem"v-loadmore"{ method: lazyItemList, item, index }"multiplefilterableremotepopper-class"dropDown-sele…...
C语言基础语法——类型转换
数据有不同的类型,不同类型数据之间进行混合运算时涉及到类型的转换问题。 转换的方法有两种: 自动类型转换(隐式转换):遵循一定的规则,由编译系统自动完成强制类型转换(显示转换)…...
来电无通话界面问题分析
1、问题描述 场测反馈,无法接到电话,被叫失败。 2、Log分析 从Modem log看,空口确实有上报到有相关通话信息 排查AT相关Log,确实有上报AT< EAIC相关命令 查看相关AT指令 /* * EAIC: <call_id>,<number>,<type…...
物理学基础精解【70】
文章目录 加速度平均加速度和瞬时加速度一、定义二、性质三、数学原理与公式四、例子例题例题一例题二 曲线运动中加速度速率(速度大小)与曲线运动加速度方向与曲线运动总结 加速度和角加速度加速度与角加速度的基本定义圆周运动中的关系其他运动类型中的…...
HCIP--以太网交换安全(三)MAC地址漂移防止与检测
MAC地址漂移防止与检测 一、MAC地址漂移防止与检测知识点 1.1MAC地址漂移的概述 MAC地址漂移是指交换机上一个vlan内有两个端口学习到同一个MAC地址,后学习到的MAC地址表项覆盖原MAC地址表项的现象。 1.2.MAC地址漂移的防止方法 (1)配置…...
CSS3--美若天仙!?
免责声明:本文仅做分享~ 目录 CSS引入方式 选择器 盒子尺寸和背景色 文字控制属性 单行文字 垂直居中 字体族 font复合属性 文本对齐方式 文本修饰线 color 文字颜色 ----- 复合选择器 伪类选择器 超链接伪类 CSS特性 继承性 层叠性 优先级 Emmet …...
详细版的Jsoncpp的使用,包括在VS环境下配置
目录 准备环境VS 环境下配置编译使用 基础概述Json 数组Json 对象 Jsoncpp 的使用ValueFastWriterReader示例 如果想要 Json 部署在 Linux 上 参考: https://blog.csdn.net/2303_76953932/article/details/142703683?spm1001.2014.3001.5502 C中原生不支持 Json,所…...
开发指南070-3d模型
平台集成了应用于3d展示场景的相关底层,支持fbx和gltf两种模型格式。 样例如下: <div class"fullcontainer"> <div style"width:80%"> <iframe :src"url" width"100%" height"…...
问卷调查毕设计算机毕业设计投票系统SpringBootSSM框架
目录 一、引言 二、需求分析 用户角色: 功能需求: 非功能需求: 三、系统设计 技术选型: 数据库设计: 界面设计: 四、实现步骤 后端实现: …...
突破Windows多显示器显示壁垒:SetDPI重新定义显示体验
突破Windows多显示器显示壁垒:SetDPI重新定义显示体验 【免费下载链接】SetDPI 项目地址: https://gitcode.com/gh_mirrors/se/SetDPI 在当今多设备协同工作的时代,显示器已成为我们与数字世界交互的重要窗口。然而,当程序员小李将笔…...
立知-lychee-rerank-mm效果展示:汽车配置单与实拍图一致性验证
立知-lychee-rerank-mm效果展示:汽车配置单与实拍图一致性验证 1. 引言:多模态重排序的实用价值 在日常工作和生活中,我们经常遇到这样的场景:看到一份产品配置单,但不确定实际产品是否真的符合描述;或者…...
ESFT-gate-law-lite:法律文本智能分析新工具
ESFT-gate-law-lite:法律文本智能分析新工具 【免费下载链接】ESFT-gate-law-lite ESFT-gate-law-lite是基于HuggingFace的深度学习模型,专为法律领域定制。源自deepseek-ai团队,继承ESFT-vanilla-lite优势,强大而轻量,…...
【adb端口5555】烽火hg680系列安卓9线刷全攻略:告别强制升级与花屏困扰
1. 烽火HG680系列机顶盒的痛点与解决方案 最近在折腾烽火HG680-GY和HG680-GC这两款机顶盒的朋友应该都深有体会,官方系统用着用着就会弹出强制升级提示,有时候还会莫名其妙出现花屏问题。作为一个折腾过不下20台烽火盒子的老玩家,我太理解这种…...
Quartus-II 9.0实战:从半加器到4位加法器的数字逻辑设计全流程解析
1. 半加器设计:数字逻辑的起点 半加器是数字电路设计中最基础的加法单元,理解它的工作原理对后续学习全加器和多位加法器至关重要。半加器之所以称为"半",是因为它只能处理两个1位二进制数的相加,不考虑来自低位的进位输…...
Next AI Draw.io:从自然语言到专业图表,AI如何重塑技术绘图工作流
1. 当技术绘图遇上AI:一场效率革命 上周三凌晨两点,我还在为一个客户紧急赶制系统架构图。传统绘图工具里反复拖拽调整的机械操作,让我的咖啡消耗量达到了平日的三倍。直到偶然发现Next AI Draw.io这个神器——用一句"生成包含负载均衡和…...
BilibiliDown:你的专属B站视频管家,轻松下载与管理海量内容
BilibiliDown:你的专属B站视频管家,轻松下载与管理海量内容 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader 😳 项目地址: https://gitcode.…...
符号回归的工程化实践:基于深度学习的物理定律自动发现与工业部署
1. 符号回归:当深度学习遇见物理定律发现 第一次接触符号回归时,我被它的"反套路"特性惊艳到了——大多数深度学习模型都在努力变得更复杂,而它却在追求用最简单的数学公式解释世界。三年前我在化工厂做反应釜监控项目时࿰…...
网络舆情分析毕业设计:从数据采集到情感识别的技术实现与避坑指南
最近在帮学弟学妹们看网络舆情分析相关的毕业设计,发现大家普遍在几个地方卡壳:要么爬虫被封IP,数据拿不到;要么文本预处理一团糟,模型效果差;要么整个系统耦合在一起,改一处动全身,…...
Llama-3.2V-11B-cot惊艳效果:多对象遮挡场景下的因果关系链推演
Llama-3.2V-11B-cot惊艳效果:多对象遮挡场景下的因果关系链推演 1. 视觉推理新标杆 在计算机视觉领域,多对象遮挡场景下的因果关系推演一直是个技术难题。传统方法往往只能识别可见部分,而无法理解遮挡背后的逻辑关系。Llama-3.2V-11B-cot的…...
