初识C++ · AVL树(2)
目录
前言:
1 左右旋
2 右左旋
3 部分细节补充
3.1 单旋和插入
3.2 部分小函数
前言:
AVL树作为一种结构,理解树的本身是不大难的,难的在于,树旋转之后的连接问题,写AVL树的代码大部分都是在旋转部分,所以连接问题是比较需要细心的,那么这里来说呢,把细心做好,变量的位置放好,连接的次序连接对,就成功了。
1 左右旋
前文提及,什么情况下需要左右旋?即不是纯粹的左边高或者是右边高,那么使用到左右旋的情况如下:
如果我们固执的以为在b 或者 c插入数据之后,90的平衡因子变为了-2,右旋就能解决问题的话就完蛋啦,这里我们直接对90右旋之后,结果就是镜像的,树还是没有平衡,那么我们再左旋,相当于旋转回来了,整个树的结果是没有变的。
此时就需要左旋转后再右旋转,可能有人会问,这个图是什么意思,我们使用的是抽象图来介绍,这样更加方便,长方形代表的就是高度为多少的子树。
选择b c作为例子,当我们往b c插入数据的时候,90的平衡因子变为了-2,此时parent就是90,那么我们需要一个操作让该树变成完全的左子树高,这样再右旋转,才可以保持平衡,那么如何变成完全的左子树高呢?
记住那两个线,30 -90 30 -60的这两条线,只要60在30和90的中间就是完全的左子树高,所以我们需要对30进行左旋,所以现在已知的操作就是先左旋再右旋,要记得参数不是一样的。
旋转的问题很好解决,旋转中的问题可不止旋转,这里还有平衡因子的问题,我们不难发现,在b 或者 c插入数据之后平衡因子的改变不是一样的,甚至来说如果h = 1,即60是新插入的,平衡因子的改变也是不一样的。
所以平衡因子的变化可以分为三个情况,一是b插入,二是c插入,三是60是新插入的,其中平衡因子的变化就留给读者自己发现啦,这是比较简单的,所以代码就可以出来了:
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 = -1;subLR->_bf = 0;parent->_bf = 0;}else if(bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}//60自己就是新插入的节点else if(bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}
我们知道,以某个节点作为平衡节点,平衡之后该节点的父节点平衡因子必定为0,所以我们可以把subLR = 0直接提取出来。所以双旋来说是很简单,甚至比单旋都简单。
2 右左旋
有了左右旋的基础,这里直接就给代码了:
void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//旋转完成RotateR(subR);RotateL(parent);//更新平衡因子subRL->_bf = 0;//RL必平衡if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;}else{assert(false);}}
3 部分细节补充
是不是以为AVL树到这里就要结束了?
错辣!还有许多细节要注意!
3.1 单旋和插入
单旋这里除了要注意旋转的时候的连接问题,还要注意变量的声明次序问题:
Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;Node* pparent = parent->_parent;parent->_parent = subL;
以右旋为例子,当parent节点不是根节点,势必涉及到parent的父节点的连接问题,所以我们先声明了pparent,如果我们在这个if里面声明:
if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (parent == pparent->_left){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}
在此之前pparent的值就已经变为了subL,所以pparent一定要在parent->_parent = subL之前声明了。
其次,插入这里:
//更新平衡因子
cur->_parent = parent;
while (parent)
{if (parent->_left == cur){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){//右单旋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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{//理论而言不可能出现这种情况assert(false);}
}
为什么旋转之后就要break了呢?按道理来说,比如双旋之后,parent的位置必然改变,可能直接变成了叶子节点,如果再走循环,平衡因子必然改变,此时树的结构就被破坏了,所以一定要break了。
现在解释上文说的,为什么旋转之后,比如单旋,平衡因子一定变为0了?这里我们就借助抽象图来理解,具象图没有那么好理解:
以这个图作为例子,c插入数据之后,n成为了新的根节点,此时左子树的高度是 h(m) + h = h + 1,右子树的高度是h + 1,1是新插入的数据,所以平衡因子必定为0,该结论在左右双旋里面也有体现。
3.2 部分小函数
这里的函数就是用来测试的函数,没有什么值得特别注意的:
void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}// 顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}
测试代码:
void TestAVLTree1()
{int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t1;for (auto e : arr){if (e == 13){int i = 0;}t1.Insert({ e,e });cout << "Insert:" << e << "->" << t1.IsBalance() << endl;}t1.InOrder();cout << t1.IsBalance() << endl;
}void TestAVLTree2()
{const int N = 100000000;vector<int> v;v.reserve(N);srand((unsigned)time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));cout << "Insert:" << e << "->" << t.IsBalance() << endl;}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值for (auto e : v){t.Find(e);}//随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}
下场剧透~因为AVL树的查找实在太快,但是对于平衡因子的控制要求太严格了,所以红黑树出现了,红黑树是一种近似平衡的结构~
感谢阅读!
相关文章:
初识C++ · AVL树(2)
目录 前言: 1 左右旋 2 右左旋 3 部分细节补充 3.1 单旋和插入 3.2 部分小函数 前言: AVL树作为一种结构,理解树的本身是不大难的,难的在于,树旋转之后的连接问题,写AVL树的代码大部分都是在旋转部分…...
LLM:归一化 总结
一、Batch Normalization 原理 Batch Normalization 是一种用于加速神经网络训练并提高稳定性的技术。它通过在每一层网络的激活值上进行归一化处理,使得每一层的输入分布更加稳定,从而加速训练过程,并且减轻了对参数初始化的依赖。 公式 …...
蓝桥杯 2024 年第十五届省赛真题 —— 最大异或结点
目录 1. 最大异或结点1. 问题描述2. 输入格式3. 输出格式4. 样例输入5. 样例输出6. 样例说明7. 评测用例规模与约定 2. 解题思路1. 解题思路2. AC_Code 1. 最大异或结点 1. 问题描述 小蓝有一棵树,树中包含 N N N 个结点,编号为 0 , 1 , 2 , ⋯ , N − 1 0,1,2,…...
AV1技术学习:Loop Restoration Filter
环路恢复滤波器(restoration filter)适用于64 64、128 128 或 256 256 像素块单元,称为 loop restoration units (LRUs)。每个单元可以独立选择是否跳过滤波、使用维纳滤波器(Wiener filter)或使用自导滤波器&#…...
如何使用python实现自动化办公?干货满满!
Python作为一种简单而强大的编程语言,不仅在数据科学和软件开发领域广受欢迎,还在办公自动化方面发挥了巨大作用。通过Python,我们可以编写脚本来自动执行各种重复性任务,从而提高工作效率并减少错误。在本文中,我们将…...
QT Creator下载安装详细教程(保姆级教程)
qt下载安装 1.下载网址 通过清华大学开源软件镜像站进行下载:链接: https://mirrors.tuna.tsinghua.edu.cn/qt/development_releases/online_installers/ 这里我选的是4.4版本的,也可以选择4.7版本,问题不大。 根据电脑系统选择下载linux…...
无人机公司销售需要什么资质
国家民航局于2024年1月1日实施了《无人驾驶航空器飞行管理暂行条例》,根据这个管理条例里面的 第十一条 使用除微型以外的民用无人驾驶航空器从事飞行活动的单位应当具备下列条件,并向国务院民用航空主管部门或者地区民用航空管理机构申请取得民用无人驾…...
代码自动化重构工具OpenRewrite介绍
OpenRewrite 是一个用于大规模自动化代码重构的开源框架,它极大地提升了开发人员的研发效率,通过自动化地进行代码重构和转换,帮助开发人员消除代码库中的技术债务。 通过 LST、访问器和配方的结合,OpenRewrite 能够实现准确的代…...
Win11安装Docker
下载Docker Desktop for Windows 下载 下载连接:Install Docker Desktop on Windows | Docker Docs 地址在国外,需要科学上网。也可使用我提供的,百度网盘:https://pan.baidu.com/s/1232TTkkzLsoZyFjC3bmgiQ 安装 下载完成之后…...
Windows电脑如何启动RTSP服务实现本地摄像头数据共享
技术背景 提起Windows共享本地摄像头,好多人想到的是通过ffmepg或vlc串流到服务器,实际上,用轻量级RTSP服务更简单,本文就介绍下,如何用大牛直播SDK的Windows轻量级RTSP服务,采集摄像头,生成本…...
探索 Spring WebFlux:构建响应式 Web 应用
探索 Spring WebFlux:构建响应式 Web 应用 随着互联网的发展,传统的同步编程模型已经难以应对高并发和高吞吐量的需求。为了解决这些问题,响应式编程逐渐成为主流。Spring WebFlux 是 Spring 5 引入的一个响应式 Web 框架,它基于…...
C# 植物大战僵尸
Winform 版本开发 高效率、流畅植物大战僵尸 git地址:冯腾飞/植物大战僵尸...
css 作业 2
文章目录 前言第四题第五题第六题第七题第八题第九题第十题(子标签) 前言 昨天写了前面三次作业,今天把剩下的七个作业写完 第四题 http://127.0.0.1:5500/index1.html,就用这个网址查看代码在网页的展示效果 代码评测过不了&…...
axios在vue中的使用
文章目录 一、axios是什么?二、使用步骤2.1 下载2.2 引入2.3 使用Get请求Post请求Forms 三、封装 一、axios是什么? Axios 是一个基于 promise 网络请求库,作用于node.js 和浏览器中。 它是 isomorphic 的(即同一套代码可以运行在浏览器和no…...
FastAPI(七十七)实战开发《在线课程学习系统》接口开发-- 课程编辑和查看评论
源码见:"fastapi_study_road-learning_system_online_courses: fastapi框架实战之--在线课程学习系统" 课程编辑 先来看下课程编辑 1.判断是否登录 2.判断课程是否存在 3.是否有权限(只有自己可以修改自己的课程) 4.名称是否重复…...
【JavaEE初阶】线程的概念及创建
目录 📕 前言 📕 认识线程(Thread) 🚩 概念 😊线程是什么 🙂 为啥要有线程 😭 进程和线程的区别(面试题重点) 🤭 Java的线程和操作系统线程…...
0727,学什么学,周六就应该休息!!!!!
周六就应该休息,一天就忙了两小时也不是我的错喵 目录 UDP的小总结 01:使用select实现一个基于UDP的一对一即时聊天程序。 1.0 复读机服务器和树洞客户端 2.0 byby不了一点的敬业服务器!!! 今天到此为止&#x…...
【C#】获取DICOM图像像素的像素值
8位像素深度的像素值 public byte GetGreyValue(int x, int y) {x Math.Min(x, m_nWidth - 1);y Math.Min(y, m_nHeight - 1);unsafe{byte* greyValue (byte*)m_pDicomData.ToPointer() y * m_nWidth x;return *greyValue;} } 16位像素深度的像素值 public ushort GetG…...
k8s多集群管理工具kubecm
文章目录 一、概述二、安装1、官网链接2、各平台安装2.1、MacOS2.2、Linux2.3、Windows 三、实例1、验证2、配置kubecm自动补全(选做)2.1、Bash2.2、Zsh2.3、fish2.4、PowerShell 3、创建存放kubeconfig文件的目录4、添加到 $HOME/.kube/config4.1、kube…...
通过 WSL 2 在Windows 上挂载 Linux 磁盘
原文查看 曾为了传输或者共享不同系统的文件频繁地在 Windows 和 Linux 系统之间切换,效率过低,所以尝试通过 WSL 2 在Windows 上挂载 Linux 磁盘。 先决条件 需要在Windows 10 2004 及更高版本(Build 19041 及更高版本)或 Win…...
【C#】在一个给定的宽、高范围内,获取到该多边形内部的所有坐标集合?
问题点 使用C#语言在一个给定的宽、高范围内,获取到该多边形内部的所有坐标集合? 这个多边形可能存在交叉及互相重叠部分 图像的宽、高可以定义为:2000*2000 多边形坐标集合:Point[] polygon_points new Point[] { new Point…...
json的数据结构
JSON 的数据结构 JSON 由两种数据结构组成:对象(字典)和数组。 一、对象 对象(object)是由键值对组成的无序集合。 键是字符串,值可以是任何类型,包括对象和数组;对象由一对花括…...
html-docx-js和file-saver实现html导出word
依赖html-docx-js,file-saver,html2canvas import { asBlob } from html-docx-js/dist/html-docx; import { saveAs } from file-saver; import html2Canvas from html2canvas;const handleImageToBase64 (cloneEle) > {let imgElements cloneEle.…...
三维影像系统PACS源码,图像存储与传输系统,应用于医院中管理医疗设备如CT,MR等产生的医学图像的信息系统
PACS,即图像存储与传输系统,是应用于医院中管理医疗设备如CT,MR等产生的医学图像的信息系统。目标是支持在医院内部所有关于图像的活动,集成了医疗设备,图像存储和分发,数字图像在重要诊断和会诊时的显示&a…...
Golang | Leetcode Golang题解之第292题Nim游戏
题目: 题解: func canWinNim(n int) bool {return n%4 ! 0 }...
Redis在SpringBoot中配置
lettuce redis的使用方法有两种,jedis和lecttuce,jedis用的不是很多,下面讲解用lettuce的使用方法。 首先导包: <!--redis依赖--> <dependency><groupId>org.springframework.boot</groupId><artif…...
linux 网络子系统
__netif_receive_skb_core 是 Linux 内核网络子系统中一个非常重要的函数,它负责将网络设备驱动层接收到的数据包传递到上层协议栈进行处理。以下是对该函数的一些关键点的详细解析: 一、函数作用 __netif_receive_skb_core 函数是处理接收到的网络数据…...
JVM:垃圾回收器演进
文章目录 一、演进二、Shenandoah三、ZGC 一、演进 二、Shenandoah Shenandoah是由Red Hat开发的一款低延迟的垃圾收集器,Shenandoah并发执行大部分GC工作,包括并发的整理,堆大小对STW的时间基本没有影响。 三、ZGC ZGC是一种可扩展的低延…...
全新微软语音合成网页版源码,短视频影视解说配音网页版系统-仿真人语音
源码介绍 最新微软语音合成网页版源码,可以用来给影视解说和短视频配音。它是TTS文本转语言,API接口和PHP源码。 这个微软语音合成接口的源码,超级简单,就几个文件搞定。用的是官方的API,试过了,合成速度…...
大语言模型-对比学习-Contrastive Learning
一、对比学习概念 对比学习是一种特殊的无监督学习方法。 旨在通过拉近相关样本的距离并且推远不相关样本的距离,来学习数据表示。 通常使用一种高自由度、自定义的规则来生成正负样本。在模型预训练中有着广泛的应用。 二、对比学习小案例 对比学习主要分为三个…...
C++ 封装的用法
C(七)封装 封装,可以达到,对外提供接口,屏蔽数据,对内开放数据。 权限控制 struct 中所有行为和属性都是 public 的(默认),此举也是为了 C兼容 C 语言, 因为 C 语言中没有权限的概念。 C中的 class 可以…...
【C++11:异常】
目录 抛异常标准书写格式 抛异常如何执行? 指定抛出异常类型: noexcept 关键字:throw 抛异常标准书写格式 抛异常如何执行? 当212行的异常被抛出,程序会重新返回函数func中,在函数中去寻找catch 语句的…...
Dify中HTTP请求节点的常见操作
HTTP节点包括API请求类型(GET、POST、HEAD、PATCH、PUT、DELETE),鉴权类型(无、API-Key基础、API-Key Bearer、API-Key自定义),HEADERS键值设置,PARAMS键值设置,BODY(non…...
《大语言模型(赵鑫)》知识框图
...
【Android】性能实践—编码优化与布局优化学习笔记
编码优化 使用场景 如果需要拼接字符串,优先使用StringBuffer和StringBuilder进行凭借,他们的性能优于直接用加号进行拼接,因为使用加号连接符会创建多余的对象一般情况下使用基本数据类来代替封装数据类型(比如int优于Integer&…...
如何合规与安全地利用专业爬虫工具,构建企业数据竞争优势
摘要: 本文深入探讨了在当今大数据时代,企业如何通过合规且安全的方式运用专业爬虫工具,有效收集并分析海量信息,进而转化为企业独有的数据优势。我们不仅会介绍最佳实践,还会讨论关键技术和策略,帮助企业…...
自动驾驶三维车道线检测系列—OpenLane数据集介绍
文章目录 1. 背景介绍2. OpenLane数据集详细描述2.1 数据集特点2.2 坐标系定义 3. 使用方法4. 结论 1. 背景介绍 自动驾驶技术的发展日新月异,而3D车道感知是其核心之一。本文将深入介绍OpenLane数据集——迄今为止规模最大、最接近真实世界的3D车道数据集。我们将…...
CMakeList学习笔记
设置项目:project project(planning VERSION 1.0.0 LANGUAGES CXX) # 项目的名字 版本 1.1.0 编程语言 CXX 设置包含目录:include_directories、targer_include_directories 设置编译类型:add_executable、add_library add_executable(demo d…...
将git默认的编辑器设置为vin
git默认编辑器现状 如下,很多linux发行版,未加修改的情况下,git的默认编辑器使用起来不太方便 Signed-off-by: root <rootxxx.COM># Please enter the commit message for your changes. Lines starting # with # will be ignored, a…...
ros2_control 6 自由度机械臂
系列文章目录 前言 ros2_control 是一个实时控制框架,专为普通机器人应用而设计。标准的 c 接口用于与硬件交互和查询用户定义的控制器命令。这些接口增强了代码的模块化和与机器人无关的设计。具体的应用细节,例如使用什么控制器、机器人有多少个关节以…...
Python 在自动化中的实际应用:用 Python 简化繁琐任务
文章目录 1、概述2、自动化文件和目录管理3.数据处理与分析4.网页爬虫5. 系统管理6。定时任务7.结语 1、概述 这篇文章将深入探讨Python在自动化中的实际应用,帮助您用Python简化繁琐任务。 我们将从多个方面入手,展示如何利用Python进行文件管理、数据…...
解释 Spring 框架的核心模块(如 IoC 容器、AOP )及其工作原理。描述如何使用 Spring Boot 快速搭建一个 RESTful Web服务?
Spring框架是一个广泛使用的Java企业级应用程序开发框架,它提供了一系列的模块来帮助开发者构建健壮、可测试、可维护的应用程序。 其中,最核心的模块包括IoC容器和AOP(Aspect Oriented Programming,面向切面编程)。 …...
数据分析详解
一、数据分析教程 1. 入门教程 在线课程:如Coursera、Udemy、网易云课堂等平台提供了大量数据分析的入门课程,涵盖统计学基础、Python/R语言编程、数据可视化等内容。书籍推荐:《Python数据分析实战》、《R语言实战》等书籍是数据分析入门的…...
SpringCloud之@FeignClient()注解的使用方式
FeignClient介绍 FeignClient 是 Spring Cloud 中用于声明一个 Feign 客户端的注解。由于SpringCloud采用分布式微服务架构,难免在各个子模块下存在模块方法互相调用的情况。比如订单服务要调用库存服务的方法,FeignClient()注解就是为了解决这个问题的…...
20.rabbitmq插件实现延迟队列
问题 前面谈到基于死信的延迟队列,存在的问题:如果第一个消息延时时间很长,而第二个消息延时时间很短,第二个消息并不会优先得到执行。 下载插件 地址:https://github.com/rabbitmq/rabbitmq-delayed-message-excha…...
TS如何处理js模块的类型?
现在很多插件都直接用ts开发了,本身包含了类型定义常见的第三方插件,都有’types/xxx’包,安装即可使用其他的,可通过declare module定义类型 比如: // someModule.js export function greet(name) {return Hello, $…...
GPS定位系统(VUE框架)
源码下载:小宅博客网 博主之前写的《GPS定位系统(MVC框架)》版本,并没有做到前后端分离,不太适合多人协作开发,这边博主分享一个基于asp.net web api vue3的GPS定位系统框架,本框架继承了MVC框…...
分布式光伏并网AM5SE-IS防孤岛保护装置介绍——安科瑞 叶西平
产品简介 功能: AM5SE-IS防孤岛保护装置主要适用于35kV、10kV及低压380V光伏发电、燃气发电等新能源并网供电系统。当发生孤岛现象时,可以快速切除并网点,使本站与电网侧快速脱离,保证整个电站和相关维护人员的生命安全。 应用…...
神奇的方法解决Navicat闪退
原因 打开Navicat操作上面的工具等就会闪退,原因竟然是屏幕划词!!! 解决方法 看别人提到有道词典的划词功能的原因 我没有安装有道词典,但我安装豆包,它也有划词翻译的功能,关闭即可...
openmv学习笔记(24电赛笔记)
感光元件 openmv采用小孔摄像模式,将图像映射到感光原件上面,来传递图片,通过图片快速的刷新行成视频,在IDE中通过对感光原件的编辑可以控制视频的效果。 重置感光元件到默认状态 import sensor #导入感光元件这个库sensor.res…...