[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
左单旋
左单旋适合的情况:
右树插入新的节点,导致祖先节点不平衡
操作:
- 将右节点的左子树变为祖先节点的右子树
- 将祖先节点变为父节点的左子树
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树插入的模拟实现
前言 紧接着上一篇文章,我们来模拟实现一下set的底层结构 引入 对于BSTree,虽然可以缩短查找的效率,但如果数据有序它将退化为单支树 我们可以用AVL树来解决这个问题。 概念 AVL树: 它的每个结点的左右子树高度之差的绝对值…...

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

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

kali apt update报错
错误信息: 获取:http:/dl.google.com/几inux/chrome/.deb stable InRelease 错误:http:/dl.google.com/linux/chrome/deb stable InRelease 由于没有公钥,无法验证下列签名:NO_PUBKEY4EB27DB2A3B88B8B 命中:…...
7-1 图图图
某城市有n个景点,部分景点之间有巴士免费来回接送。(1) 给定某个景点x,如果从这个景点出发坐一次免费巴士,可以到达多少个不同的景点?(2) 判断景点a是否可以通过免费巴士(可换乘)到达景点b;(3) …...
Java(多线程)
取水: 主部分: 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大神器,效率飞起!
我们都知道程序员在工作时,会经常遇到任务繁重的情况,为了提高效率,程序员们也会借助一些软件,那么哪些软件可以帮助程序员们提高工作效率呢? 整理不易,关注一波!! 1. Xftp 7 Xft…...

揭秘文件加密利器:24年度最值得信赖的5大加密软件评测
数据安全与隐私保护已成为我们每个人都必须面对的重要问题。 文件加密软件作为保障数据安全的关键工具,其重要性不言而喻。 在众多的加密软件中,哪些软件能够在保障数据安全的同时,又具备良好的易用性和稳定性呢? 本文将为您揭秘…...

【仪酷LabVIEW AI工具包案例】使用LabVIEW AI工具包+YOLOv5结合Dobot机械臂实现智能垃圾分类
🏡博客主页: virobotics(仪酷智能):LabVIEW深度学习、人工智能博主 🎄所属专栏:『仪酷LabVIEW AI工具包案例』 📑上期文章:『【YOLOv9】实战二:手把手教你使用TensorRT实现YOLOv…...
鸿蒙应用开发系列 EX篇:HarmonyOS应用开发者基础认证
文章目录 系列文章背景认证考试题库参考注意:题库会不定时的进行具备调整甚至整体轮换,此为2024.5月版本注意:题库中题目的选项每次都会随机顺序,请参考内容判断题单选题多选题系列文章 鸿蒙应用开发系列 篇一:鸿蒙系统概述 鸿蒙应用开发系列 篇二:鸿蒙系统开发工具与环…...

基于Linux中的 进程相关知识 综合讲解
目录 一、进程的基本概念 二、pid,ppid,fork函数 三、进程的状态讲解 四、进程的优先级 五、完结撒❀ 一、进程的基本概念 概念: ● 课本概念:程序的一个执行实例,正在执行的程序等 ● 内核观点:担当…...

前端高频面试题 5.08
事件委托 事件委托是前端开发中常用的一种优化性能和代码可维护性的方法,它基于DOM的事件冒泡机制。当一个元素触发事件时,这个事件会按照从顶层到底层的顺序传播,直到最底层的元素(通常是文档的根节点)。事件委托利用…...
python 的继承、封装和多态
1. 继承(Inheritance) 继承是面向对象编程中的一个重要概念,它允许一个类(子类)继承另一个类(父类)的属性和方法。子类可以重用父类的代码,同时也可以扩展或修改父类的行为。 常用…...

数智结合,智慧合同让法务管理发挥内在价值
在当今这个信息化、数字化飞速发展的时代,数据已成为企业重要的战略资源。法务管理作为企业内部控制和风险防范的重要环节,其重要性不言而喻。然而,传统的法务管理模式往往存在效率低下、信息孤岛、反应迟缓等问题。在这样的背景下࿰…...
Ubuntu 安装docker
1: 卸载旧版本 如果你曾经安装过旧版本的 Docker,首先需要卸载它们: sudo apt-get remove docker docker-engine docker.io containerd runc2: 安装依赖工具 安装一些必要的工具,以便后续的安装过程能够顺利进行: sudo apt-ge…...

【北京迅为】《iTOP-3588开发板快速烧写手册》-第8章 TF启动
RK3588是一款低功耗、高性能的处理器,适用于基于arm的PC和Edge计算设备、个人移动互联网设备等数字多媒体应用,RK3588支持8K视频编解码,内置GPU可以完全兼容OpenGLES 1.1、2.0和3.2。RK3588引入了新一代完全基于硬件的最大4800万像素ISP&…...
Helm 模板流程控制
Helm 的模板语言提供了多种控制结构,以允许模板作者根据条件逻辑生成模板内容。以下是 Helm 模板控制结构的核心内容总结: 控制结构 Helm 模板支持以下控制结构: if/else:用于创建条件语句,根据给定的条件包含或排除…...

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

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

《QT实用小工具·五十一》带动画的 CheckBox
1、概述 源码放在文章末尾 该项目实现了带动画效果的多选框,鼠标放在上面或者选中都会呈现炫酷的动画效果,demo演示如下: 项目部分代码如下所示: #ifndef LINEARCHECKBOX_H #define LINEARCHECKBOX_H#include <QCheckBox> …...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...

Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...

CMS内容管理系统的设计与实现:多站点模式的实现
在一套内容管理系统中,其实有很多站点,比如企业门户网站,产品手册,知识帮助手册等,因此会需要多个站点,甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录
#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...