当前位置: 首页 > news >正文

初识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)

目录 前言&#xff1a; 1 左右旋 2 右左旋 3 部分细节补充 3.1 单旋和插入 3.2 部分小函数 前言&#xff1a; AVL树作为一种结构&#xff0c;理解树的本身是不大难的&#xff0c;难的在于&#xff0c;树旋转之后的连接问题&#xff0c;写AVL树的代码大部分都是在旋转部分…...

LLM:归一化 总结

一、Batch Normalization 原理 Batch Normalization 是一种用于加速神经网络训练并提高稳定性的技术。它通过在每一层网络的激活值上进行归一化处理&#xff0c;使得每一层的输入分布更加稳定&#xff0c;从而加速训练过程&#xff0c;并且减轻了对参数初始化的依赖。 公式 …...

蓝桥杯 2024 年第十五届省赛真题 —— 最大异或结点

目录 1. 最大异或结点1. 问题描述2. 输入格式3. 输出格式4. 样例输入5. 样例输出6. 样例说明7. 评测用例规模与约定 2. 解题思路1. 解题思路2. AC_Code 1. 最大异或结点 1. 问题描述 小蓝有一棵树,树中包含 N N N 个结点&#xff0c;编号为 0 , 1 , 2 , ⋯ , N − 1 0,1,2,…...

AV1技术学习:Loop Restoration Filter

环路恢复滤波器&#xff08;restoration filter&#xff09;适用于64 64、128 128 或 256 256 像素块单元&#xff0c;称为 loop restoration units (LRUs)。每个单元可以独立选择是否跳过滤波、使用维纳滤波器&#xff08;Wiener filter&#xff09;或使用自导滤波器&#…...

如何使用python实现自动化办公?干货满满!

Python作为一种简单而强大的编程语言&#xff0c;不仅在数据科学和软件开发领域广受欢迎&#xff0c;还在办公自动化方面发挥了巨大作用。通过Python&#xff0c;我们可以编写脚本来自动执行各种重复性任务&#xff0c;从而提高工作效率并减少错误。在本文中&#xff0c;我们将…...

QT Creator下载安装详细教程(保姆级教程)

qt下载安装 1.下载网址 通过清华大学开源软件镜像站进行下载&#xff1a;链接: https://mirrors.tuna.tsinghua.edu.cn/qt/development_releases/online_installers/ 这里我选的是4.4版本的&#xff0c;也可以选择4.7版本&#xff0c;问题不大。 根据电脑系统选择下载linux…...

无人机公司销售需要什么资质

国家民航局于2024年1月1日实施了《无人驾驶航空器飞行管理暂行条例》&#xff0c;根据这个管理条例里面的 第十一条 使用除微型以外的民用无人驾驶航空器从事飞行活动的单位应当具备下列条件&#xff0c;并向国务院民用航空主管部门或者地区民用航空管理机构申请取得民用无人驾…...

代码自动化重构工具OpenRewrite介绍

OpenRewrite 是一个用于大规模自动化代码重构的开源框架&#xff0c;它极大地提升了开发人员的研发效率&#xff0c;通过自动化地进行代码重构和转换&#xff0c;帮助开发人员消除代码库中的技术债务。 通过 LST、访问器和配方的结合&#xff0c;OpenRewrite 能够实现准确的代…...

Win11安装Docker

下载Docker Desktop for Windows 下载 下载连接&#xff1a;Install Docker Desktop on Windows | Docker Docs 地址在国外&#xff0c;需要科学上网。也可使用我提供的&#xff0c;百度网盘&#xff1a;https://pan.baidu.com/s/1232TTkkzLsoZyFjC3bmgiQ 安装 下载完成之后…...

Windows电脑如何启动RTSP服务实现本地摄像头数据共享

技术背景 提起Windows共享本地摄像头&#xff0c;好多人想到的是通过ffmepg或vlc串流到服务器&#xff0c;实际上&#xff0c;用轻量级RTSP服务更简单&#xff0c;本文就介绍下&#xff0c;如何用大牛直播SDK的Windows轻量级RTSP服务&#xff0c;采集摄像头&#xff0c;生成本…...

探索 Spring WebFlux:构建响应式 Web 应用

探索 Spring WebFlux&#xff1a;构建响应式 Web 应用 随着互联网的发展&#xff0c;传统的同步编程模型已经难以应对高并发和高吞吐量的需求。为了解决这些问题&#xff0c;响应式编程逐渐成为主流。Spring WebFlux 是 Spring 5 引入的一个响应式 Web 框架&#xff0c;它基于…...

C# 植物大战僵尸

Winform 版本开发 高效率、流畅植物大战僵尸 git地址&#xff1a;冯腾飞/植物大战僵尸...

css 作业 2

文章目录 前言第四题第五题第六题第七题第八题第九题第十题&#xff08;子标签&#xff09; 前言 昨天写了前面三次作业&#xff0c;今天把剩下的七个作业写完 第四题 http://127.0.0.1:5500/index1.html&#xff0c;就用这个网址查看代码在网页的展示效果 代码评测过不了&…...

axios在vue中的使用

文章目录 一、axios是什么&#xff1f;二、使用步骤2.1 下载2.2 引入2.3 使用Get请求Post请求Forms 三、封装 一、axios是什么&#xff1f; Axios 是一个基于 promise 网络请求库&#xff0c;作用于node.js 和浏览器中。 它是 isomorphic 的(即同一套代码可以运行在浏览器和no…...

FastAPI(七十七)实战开发《在线课程学习系统》接口开发-- 课程编辑和查看评论

源码见&#xff1a;"fastapi_study_road-learning_system_online_courses: fastapi框架实战之--在线课程学习系统" 课程编辑 先来看下课程编辑 1.判断是否登录 2.判断课程是否存在 3.是否有权限&#xff08;只有自己可以修改自己的课程&#xff09; 4.名称是否重复…...

【JavaEE初阶】线程的概念及创建

目录 &#x1f4d5; 前言 &#x1f4d5; 认识线程&#xff08;Thread&#xff09; &#x1f6a9; 概念 &#x1f60a;线程是什么 &#x1f642; 为啥要有线程 &#x1f62d; 进程和线程的区别&#xff08;面试题重点&#xff09; &#x1f92d; Java的线程和操作系统线程…...

0727,学什么学,周六就应该休息!!!!!

周六就应该休息&#xff0c;一天就忙了两小时也不是我的错喵 目录 UDP的小总结 01&#xff1a;使用select实现一个基于UDP的一对一即时聊天程序。 1.0 复读机服务器和树洞客户端 2.0 byby不了一点的敬业服务器&#xff01;&#xff01;&#xff01; 今天到此为止&#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自动补全&#xff08;选做&#xff09;2.1、Bash2.2、Zsh2.3、fish2.4、PowerShell 3、创建存放kubeconfig文件的目录4、添加到 $HOME/.kube/config4.1、kube…...

通过 WSL 2 在Windows 上挂载 Linux 磁盘

原文查看 曾为了传输或者共享不同系统的文件频繁地在 Windows 和 Linux 系统之间切换&#xff0c;效率过低&#xff0c;所以尝试通过 WSL 2 在Windows 上挂载 Linux 磁盘。 先决条件 需要在Windows 10 2004 及更高版本&#xff08;Build 19041 及更高版本&#xff09;或 Win…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...