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

[C++][数据结构]AVL树插入的模拟实现

前言

紧接着上一篇文章,我们来模拟实现一下set的底层结构

引入

对于BSTree,虽然可以缩短查找的效率,但如果数据有序它将退化为单支树

我们可以用AVL树来解决这个问题。

概念

AVL树:

  • 它的每个结点的左右子树高度之差的绝对值不超过1
  • 它的左右子树都是AVL树

在这里插入图片描述对于10来说,左右子树高度差为2,所以不满足

实现

基本结构

template<class K, class V>
struct AVLTreeNode
{using Node = AVLTreeNode<K, V>;Node* _left;	//左节点Node* _right;	//右节点Node* _parent	//父节点int _bf;		//平衡因子//计算方式:右树高度减去左树高度pair<K, V> _kv;	//用pair封起来的键值对AVLTreeNode(const pair<K, V>& kv):_kv(kv),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

插入

和搜索树的插入规则前半部分是相同的,具体细节可以看注释

	bool Insert(const pair<K, V>& kv){//1.按照搜索树规则插入:先找到合适的位置,然后链接if (_root == nullptr){_root = new Node(kv);return true;}//如果树为空,特殊判断Node* parent = nullptr;//父节点//方便记录父节点原来的子树Node* cur = _root;while (cur != nullptr){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;}}//查找完再判断是父节点的左树还是右数//标记为Acur = new Node(kv);if (parent->kv.first > kv.first){parent->_right = cur;}else{parent->_right = cur;}cur->_parent = parent;//2.更新平衡因子,根据AVL的规则,进行旋转调整//	- 插入因子会影响自己所有的祖先节点//	- 更新原则://		1.修改_bf//			- cur是_parent左边,_parent->_bf--//			- cur是_parent右边,_parent->_bf++//		2.根据_parent->_bf是否为0来判断是否修改祖先的_bf,//			- _bf == 0 在更新前_bf是-1或1,更新后左右平衡了,所以不会影响祖先//			- _bf == 1/-1 更新前平衡因子为0,更新后左右不平衡了,所以祖先也要更新//		3._bf == 2/-2 插入后出现问题,要进行旋转while(parent){if (parent->_right == cur){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == 1){cur = cur->_parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if(parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else{RotateRL(parent);}break;//因为旋转完就是全都平衡了,所以直接结束循环}else{throw("false");}}return true;}

旋转

旋转也是插入的一部分,只是因为比较重要,所以单独拎出来写

变量说明:

  • h表示树的高度
  • a、b、c是树的名字
  • 30,60是_value

左单旋

在这里插入图片描述
左单旋适合的情况:
右树插入新的节点,导致祖先节点不平衡

操作:

  1. 将右节点的左子树变为祖先节点的右子树
  2. 将祖先节点变为父节点的左子树
void RotateL(Node* parent)			//右单旋
{Node* subR = parent->_right;	//subR是parent的右节点Node* subRL = subR->_left;		//subRL是subR的左节点parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (parent->_parent->_left == parent){parent->_parent->_left = subR;}else{parent->_parent->_right = subR:}subR->_parent = parent->_parent;}parent->_bf = 0;subR->_bf = 0;
}

右单旋

和上面的逻辑相同,只是新增节点放在了左子树,要向右旋转

	void RotateR(Node* parent)			//右单旋{Node* subL = parent->_left;		//subL是parent的左节点Node* subLR = subL->_right;		//subLR是subL的右节点parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (parent->_parent->_left == parent){parent->_parent->_left = subL;}else{parent->_parent->_right = subL:}subL->_parent = parent->_parent;}parent->_bf = 0;subL->_bf = 0;}

左右双旋

旋转的代码相同,就是对于平衡因子的处理需要注意
分四种情况考虑

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{throw("false");}}

右左双旋

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}

判断是否平衡

我们再写一个接口来判断给的树是否平衡

	int _Height(Node* root){if (root == nullptr){return 0;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool _IsBlance(Node* root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (abs(leftHeight - rightHeight) >= 2){throw("不平衡");}if (rightHeight - leftHeight != root->_bf){throw("平衡因子异常");}return _IsBlance(root->_left)&& _IsBlance(root->_right);}

优化:求高度

我们可以发现,这段代码还可以优化,因为每一次的高度都是要重新求的,有很多重复工作。

所以,我们可以增加一个参数,

bool _IsBlance(Node* root, int& height);

这样树的高度就会再函数调用结束后被传出来,并且不用修改返回值

	bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout <<root->_kv.first<<"不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first <<"平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}bool IsBalance(){int height = 0;return _IsBalance(_root, height);}

结语

AVL树比搜索树要更优秀,但具体逻辑(指旋转)要更复杂,希望对你有帮助!!

相关文章:

[C++][数据结构]AVL树插入的模拟实现

前言 紧接着上一篇文章&#xff0c;我们来模拟实现一下set的底层结构 引入 对于BSTree&#xff0c;虽然可以缩短查找的效率&#xff0c;但如果数据有序它将退化为单支树 我们可以用AVL树来解决这个问题。 概念 AVL树&#xff1a; 它的每个结点的左右子树高度之差的绝对值…...

力扣每日一题108:将有序数组转换为二叉搜索树

题目 简单 给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 平衡 二叉搜索树。 示例 1&#xff1a; 输入&#xff1a;nums [-10,-3,0,5,9] 输出&#xff1a;[0,-3,9,-10,null,5] 解释&#xff1a;[0,-10,5,null,-3,null,9] 也…...

保护公司机密:避免员工带着数据说拜拜

公司的核心资产之一就是数据。无论是客户信息、研发代码、内部决议、财务报告、商业合同、设计图纸等都是公司的重要资产。如果这些数据在员工离职时被带走&#xff0c;或在员工在职期间不当行为导致数据泄露&#xff0c;将给公司带来重大损失。 然而&#xff0c;保护这些数据…...

kali apt update报错

错误信息&#xff1a; 获取&#xff1a;http:/dl.google.com/几inux/chrome/.deb stable InRelease 错误&#xff1a;http:/dl.google.com/linux/chrome/deb stable InRelease 由于没有公钥&#xff0c;无法验证下列签名&#xff1a;NO_PUBKEY4EB27DB2A3B88B8B 命中&#xff1a…...

7-1 图图图

某城市有n个景点&#xff0c;部分景点之间有巴士免费来回接送。(1) 给定某个景点x&#xff0c;如果从这个景点出发坐一次免费巴士&#xff0c;可以到达多少个不同的景点&#xff1f;(2) 判断景点a是否可以通过免费巴士&#xff08;可换乘&#xff09;到达景点b&#xff1b;(3) …...

Java(多线程)

取水&#xff1a; 主部分&#xff1a; package a0506.Test3;import java.util.Random;public class Test3 {public static void main(String[] args) {Well2 well2new Well2(10);WellThread Zsnew WellThread("------张三------",well2,new Random().nextInt(5));W…...

程序员必备的7大神器,效率飞起!

我们都知道程序员在工作时&#xff0c;会经常遇到任务繁重的情况&#xff0c;为了提高效率&#xff0c;程序员们也会借助一些软件&#xff0c;那么哪些软件可以帮助程序员们提高工作效率呢&#xff1f; 整理不易&#xff0c;关注一波&#xff01;&#xff01; 1. Xftp 7 Xft…...

揭秘文件加密利器:24年度最值得信赖的5大加密软件评测

数据安全与隐私保护已成为我们每个人都必须面对的重要问题。 文件加密软件作为保障数据安全的关键工具&#xff0c;其重要性不言而喻。 在众多的加密软件中&#xff0c;哪些软件能够在保障数据安全的同时&#xff0c;又具备良好的易用性和稳定性呢&#xff1f; 本文将为您揭秘…...

【仪酷LabVIEW AI工具包案例】使用LabVIEW AI工具包+YOLOv5结合Dobot机械臂实现智能垃圾分类

‍‍&#x1f3e1;博客主页&#xff1a; virobotics(仪酷智能)&#xff1a;LabVIEW深度学习、人工智能博主 &#x1f384;所属专栏&#xff1a;『仪酷LabVIEW AI工具包案例』 &#x1f4d1;上期文章&#xff1a;『【YOLOv9】实战二&#xff1a;手把手教你使用TensorRT实现YOLOv…...

鸿蒙应用开发系列 EX篇:HarmonyOS应用开发者基础认证

文章目录 系列文章背景认证考试题库参考注意:题库会不定时的进行具备调整甚至整体轮换,此为2024.5月版本注意:题库中题目的选项每次都会随机顺序,请参考内容判断题单选题多选题系列文章 鸿蒙应用开发系列 篇一:鸿蒙系统概述 鸿蒙应用开发系列 篇二:鸿蒙系统开发工具与环…...

基于Linux中的 进程相关知识 综合讲解

目录 一、进程的基本概念 二、pid&#xff0c;ppid&#xff0c;fork函数 三、进程的状态讲解 四、进程的优先级 五、完结撒❀ 一、进程的基本概念 概念&#xff1a; ● 课本概念&#xff1a;程序的一个执行实例&#xff0c;正在执行的程序等 ● 内核观点&#xff1a;担当…...

前端高频面试题 5.08

事件委托 事件委托是前端开发中常用的一种优化性能和代码可维护性的方法&#xff0c;它基于DOM的事件冒泡机制。当一个元素触发事件时&#xff0c;这个事件会按照从顶层到底层的顺序传播&#xff0c;直到最底层的元素&#xff08;通常是文档的根节点&#xff09;。事件委托利用…...

python 的继承、封装和多态

1. 继承&#xff08;Inheritance&#xff09; 继承是面向对象编程中的一个重要概念&#xff0c;它允许一个类&#xff08;子类&#xff09;继承另一个类&#xff08;父类&#xff09;的属性和方法。子类可以重用父类的代码&#xff0c;同时也可以扩展或修改父类的行为。 常用…...

数智结合,智慧合同让法务管理发挥内在价值

在当今这个信息化、数字化飞速发展的时代&#xff0c;数据已成为企业重要的战略资源。法务管理作为企业内部控制和风险防范的重要环节&#xff0c;其重要性不言而喻。然而&#xff0c;传统的法务管理模式往往存在效率低下、信息孤岛、反应迟缓等问题。在这样的背景下&#xff0…...

Ubuntu 安装docker

1: 卸载旧版本 如果你曾经安装过旧版本的 Docker&#xff0c;首先需要卸载它们&#xff1a; sudo apt-get remove docker docker-engine docker.io containerd runc2: 安装依赖工具 安装一些必要的工具&#xff0c;以便后续的安装过程能够顺利进行&#xff1a; sudo apt-ge…...

【北京迅为】《iTOP-3588开发板快速烧写手册》-第8章 TF启动

RK3588是一款低功耗、高性能的处理器&#xff0c;适用于基于arm的PC和Edge计算设备、个人移动互联网设备等数字多媒体应用&#xff0c;RK3588支持8K视频编解码&#xff0c;内置GPU可以完全兼容OpenGLES 1.1、2.0和3.2。RK3588引入了新一代完全基于硬件的最大4800万像素ISP&…...

Helm 模板流程控制

Helm 的模板语言提供了多种控制结构&#xff0c;以允许模板作者根据条件逻辑生成模板内容。以下是 Helm 模板控制结构的核心内容总结&#xff1a; 控制结构 Helm 模板支持以下控制结构&#xff1a; if/else&#xff1a;用于创建条件语句&#xff0c;根据给定的条件包含或排除…...

Kansformer?变形金刚来自过去的新敌人

​1.前言 多层感知器(MLPs),也被称为全连接前馈神经网络,是当今深度学习模型的基础组成部分。 MLPs在机器学习中扮演着至关重要的角色,因为它们是用于近似非线性函数的默认模型,这得益于通用近似定理所保证的表达能力。然而,MLPs真的是我们能构建的最佳非线性回归器吗?尽管ML…...

今晚 19:00 | 从这两个问题入手,带你了解数据要素相关税务问题

五一假期已经结束&#xff0c;返工后当然是继续劳动啦~数据要素系列直播《星光对话》第三期也将在今晚19:00&#xff0c;继续跟大家见面。 本期直播&#xff0c;依然由 星光数智咨询总监 刘靖 主讲&#xff0c;带来&#xff1a;《数据要素相关税务问题解读》。 主要围绕两个问题…...

《QT实用小工具·五十一》带动画的 CheckBox

1、概述 源码放在文章末尾 该项目实现了带动画效果的多选框&#xff0c;鼠标放在上面或者选中都会呈现炫酷的动画效果&#xff0c;demo演示如下&#xff1a; 项目部分代码如下所示&#xff1a; #ifndef LINEARCHECKBOX_H #define LINEARCHECKBOX_H#include <QCheckBox> …...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...