【C++进阶学习】第七弹——AVL树——树形结构存储数据的经典模块

二叉搜索树：【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客

目录

一、AVL树的概念

二、AVL树的原理与实现

AVL树的节点

AVL树的插入

AVL树的旋转

AVL树的打印

AVL树的检查

三、实现AVL树的完整代码

四、总结

前言：

在前面我们学习二叉搜索树的时候，虽然大部分情况下二叉搜索树的效率都是很高的，但是如果是一组相对有序的数字，我们用二叉搜索树来排序就会显得比较麻烦了，因此，AVL树就出现了，下面就让我们一起来学习以下AVL树的相关知识

一、AVL树的概念

AVL树实际上就是特殊的二叉搜索树，是对二叉搜索树的改进，我们在用树形结构来查找或操作数据的时候，一般都是要从树根一层一层往下找，所以树高越低，效率越高，但是二叉搜索树在有些场景下比较麻烦，比如一个相对有序的数组{2，1，3，4，5，6}

这样一个数组如果通过二叉搜索树处理就会显得层数太多，效率很低

所以人们也就有了这样一种思考：我们可不可以通过某种操作让左右子树的高度差不超过1，这样就能极大的提高效率，这就是AVL树的概念

AVL树中任何节点的左右子树的高度差（平衡因子）绝对值不超过1。这意味着树始终保持平衡，避免了二叉搜索树在节点插入或删除后可能出现的退化现象。

二、AVL树的原理与实现

了解了AVL树的基本内容之后，接下来我们就来一步一步学习以下AVL树的原理到底是什么以及如何实现一个AVL树：

AVL树的节点

template<class K,class V>   
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;    //左子树AVLTreeNode<K, V>* _right;   //右子树AVLTreeNode<K, V>* _parent;  //父亲pair<K, V> _kv;       //存放节点值的int _bf;    //平衡因子（通过这个可以直到左右子树存在情况）//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0)     //平衡因子起始值是0，当左子树插入一个节点时-1，右子树插入一个节点时+1{}
};

AVL树的节点操作与二叉搜索树还是比较相似的，都有左子树右子树和父亲节点的叉式结构，比较不同的是加入了一个平衡因子

AVL树的插入

实现AVL树的重点就是解决AVL树的插入问题，而解决插入问题最关键的就是要做到如何让左右子树高度的绝对值适合不大于1，我们是通过合理的旋转来实现的，而且需要旋转的情况也是分为四种的：

RR型：左旋

LL型：右旋

RL型：先右旋，再左旋

LR型：先左旋，再右旋

下面我们来看这样几个例子：

1、RR型（左旋）

2、LL型（右旋）

3、LR型（先左旋，再右旋）

4、RL型（先右旋，再左旋）

操作与3正好相反，不过多赘述

下面就让我们看一下插入的代码：

	bool Insert(const pair<K,V>& kv)    //插入节点{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//管控平衡while (parent)    //当为根时，停止{if (cur == parent->_left){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){//左单旋RotateL(parent);break;}else if (parent->_bf == -2 && cur->_bf == -1){//右单旋RotateR(parent);break;}else if (parent->_bf == 2 && cur->_bf == -1){//RL型RotateRL(parent);break;}else if (parent->_bf == -2 && cur->_bf == 1){//LR型RotateLR(parent);break;}}else{assert(false);}}return true;}

AVL树的旋转

	void RotateL(Node* parent)   //左单旋（RR型）{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;subR->_left = parent;if(subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_parent = subR;parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent)   //右单旋（LL型）{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;parent->_left = subLR;subL->_right = parent;if (subLR){subLR->_parent = parent;}if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_parent = subL;subL->_bf = parent->_bf = 0;}void RotateRL(Node* parent)      //先右单旋，再左单旋（RL型）{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){//subRL自己就是新增点parent->_bf = subR->_bf = 0;}else if (bf == -1){//subRL的左子树上新增parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){//subRL的右子树上新增parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent)      //先左单旋，再右单旋（LR型）{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){//subLR自己就是新增点parent->_bf = subL->_bf = 0;}else if (bf == -1){//subLR的左子树上新增parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){//subLR的右子树上新增parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}}

AVL树的打印

AVL树的打印与二叉搜索树一致，都是中序打印，我们就直接来看代码了

	//中序打印void Inorder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}

AVL树的检查

检查是否为AVL树，一方面我们可以通过打印的结果先来判断一下它是不是二叉搜索树，然后我们可以通过比较左右子树的高度差来判断它是否为AVL树（根据前面可知AVL树左右子树高度差最大为1）

	//检查是否为AVL树bool IsBalance(){return _IsBalance(_root);}int _High(Node* root){if (root == nullptr)return 0;int LeftHigh = _High(root->_left);int RightHigh = _High(root->_right);return LeftHigh > RightHigh ? LeftHigh + 1 : RightHigh + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int LeftHigh = _High(root->_left);int RightHigh = _High(root->_right);if (RightHigh - LeftHigh != root->_bf){cout << _root->_kv.first << "当前节点平衡因子有问题" << endl;return false;}return abs(LeftHigh- RightHigh) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}

三、实现AVL树的完整代码

AVLTree.h

template<class K,class V>   
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;    //左子树AVLTreeNode<K, V>* _right;   //右子树AVLTreeNode<K, V>* _parent;  //父亲pair<K, V> _kv;       //存放节点值的int _bf;    //平衡因子（通过这个可以直到左右子树存在情况）//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0)     //平衡因子起始值是0，当左子树插入一个节点时-1，右子树插入一个节点时+1{}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K,V>& kv)    //插入节点{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//管控平衡while (parent)    //当为根时，停止{if (cur == parent->_left){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){//左单旋RotateL(parent);break;}else if (parent->_bf == -2 && cur->_bf == -1){//右单旋RotateR(parent);break;}else if (parent->_bf == 2 && cur->_bf == -1){//RL型RotateRL(parent);break;}else if (parent->_bf == -2 && cur->_bf == 1){//LR型RotateLR(parent);break;}}else{assert(false);}}return true;}void RotateL(Node* parent)   //左单旋（RR型）{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;subR->_left = parent;if(subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_parent = subR;parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent)   //右单旋（LL型）{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;parent->_left = subLR;subL->_right = parent;if (subLR){subLR->_parent = parent;}if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_parent = subL;subL->_bf = parent->_bf = 0;}void RotateRL(Node* parent)      //先右单旋，再左单旋（RL型）{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){//subRL自己就是新增点parent->_bf = subR->_bf = 0;}else if (bf == -1){//subRL的左子树上新增parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){//subRL的右子树上新增parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent)      //先左单旋，再右单旋（LR型）{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){//subLR自己就是新增点parent->_bf = subL->_bf = 0;}else if (bf == -1){//subLR的左子树上新增parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){//subLR的右子树上新增parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}}//中序打印void Inorder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}//检查是否为AVL树bool IsBalance(){return _IsBalance(_root);}int _High(Node* root){if (root == nullptr)return 0;int LeftHigh = _High(root->_left);int RightHigh = _High(root->_right);return LeftHigh > RightHigh ? LeftHigh + 1 : RightHigh + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int LeftHigh = _High(root->_left);int RightHigh = _High(root->_right);if (RightHigh - LeftHigh != root->_bf){cout << _root->_kv.first << "当前节点平衡因子有问题" << endl;return false;}return abs(LeftHigh- RightHigh) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}
private:Node* _root = nullptr;
};

test.c

//AVL树
#include"AVLTree.h"
int main()
{int a[] = { 16,3,7,11,9,26,18,14,15 };   AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.Inorder();cout << "输出1代表是AVL树，输出0代表不是：" << t.IsBalance() << endl;return 0;
}

运行结果：

四、总结

AVL树的理解和实现总体来说还是比较难的，思路一定要搞清楚，代码实现上尽力而为

感谢各位大佬观看，创作不易，还请各位大佬点一个小小的赞！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/3250109.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

前端轻松拿捏！最简全栈登录认证和权限设计！

前端轻松拿捏！最简全栈登录认证和权限设计！

本项目代码已开源&#xff0c;具体见&#xff1a; 前端工程&#xff1a;vue3-ts-blog-frontend 后端工程&#xff1a;express-blog-backend 数据库初始化脚本&#xff1a;关注公众号程序员白彬&#xff0c;回复关键字“博客数据库脚本”&#xff0c;即可获取。 前端走向全栈&am…
阅读更多...
宋仕强谈狼性营销与五看三定

宋仕强谈狼性营销与五看三定

宋仕强说余承东董宇辉联合宣传&#xff0c;他们的狼性营销我们要学习&#xff0c;我们金航标和萨科微要认真学习华为的先进理念和成功经验&#xff0c;和“五看三定”思维和工作模型&#xff0c;让管理团队深度思考&#xff0c;再不断实践。在产品定义和市场定位方面&#xff0…
阅读更多...
小程序js 把链接转换为二维码

小程序js 把链接转换为二维码

GitHub - Rookie-M/weapp-qrcode: weapp.qrcode.js 在 微信小程序 中&#xff0c;快速生成二维码 1.要下载上面地址的插件包 2.引用 import drawQrcode from ../../utils/weapp.qrcode.minonLoad(options) {let that thisconsole.log(JSON.parse(options.info))that.setData…
阅读更多...
Ubuntu 24.04 LTS 桌面安装MT4或MT5 (MetaTrader)教程

Ubuntu 24.04 LTS 桌面安装MT4或MT5 (MetaTrader)教程

运行脚本即可在 Ubuntu 24.04 LTS Noble Linux 上轻松安装 MetaTrader 5 或 4 应用程序&#xff0c;使用 WineHQ 进行外汇交易。 MetaTrader 4 (MT4) 或 MetaTrader 5 是用于交易外汇对和商品的流行平台。它支持各种外汇经纪商、内置价格分析工具以及通过专家顾问 (EA) 进行自…
阅读更多...
【BUG】已解决： KeyboardInterrupt

【BUG】已解决： KeyboardInterrupt

已解决&#xff1a; KeyboardInterrupt 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博主英杰&#xff0c;211科班出身&#xff0c;就职于医疗科技公司&#xff0c;热衷分享知识&#xff0c;武汉城市开发者社区主理人 擅长.net、C…
阅读更多...
折叠屏遇上Galaxy AI，三星新一代Galaxy Z系列开启移动终端新篇章

折叠屏遇上Galaxy AI，三星新一代Galaxy Z系列开启移动终端新篇章

作者 | 曾响铃 文 | 响铃说 随着换机周期的普遍延长以及智能手机行业内竞争态势的日益激烈&#xff0c;传统的硬件升级与参数比拼已难以全面满足消费者日益多元化的需求。面对这一挑战&#xff0c;行业迫切需要探索新的增长路径与发展方向。 折叠屏技术的兴起&#xff0c;无…
阅读更多...
npm install时报错 reason: certificate has expired

npm install时报错 reason: certificate has expired

在VS code中导入新项目&#xff0c;执行npm install时报错&#xff1a; npm warn old lockfile Could not fetch metadata for antv/g3.4.10 FetchError: request to https://registry.npm.taobao.org/antv%2fg failed, reason: certificate has expirednpm warn old lockfile …
阅读更多...
用DrissionPage过某里滑块分析

用DrissionPage过某里滑块分析

最近我又在找工作了&#xff0c;悲哀啊~&#xff0c;面试官给了一道题&#xff0c;要求如下&#xff1a; 爬虫机试&#xff1a;https://detail.1688.com/offer/643272204627.html 过该链接的滑动验证码&#xff0c;拿到正确的商品信息页html&#xff0c;提取出商品维度的信息&a…
阅读更多...
Notepad++换安装路径之后，右键打开方式报错：Windows无法访问指定设备、路径或文件。你可能没有适当的权限访问该项目。的处理方法

Notepad++换安装路径之后，右键打开方式报错：Windows无法访问指定设备、路径或文件。你可能没有适当的权限访问该项目。的处理方法

把Notepad添加到右键打开方式&#xff0c;可以参考下面的3篇文章添加&#xff1a; https://blog.csdn.net/xiaoerbuyu1233/article/details/88287747 https://blog.csdn.net/qq_44000337/article/details/120277317 https://www.cnblogs.com/zhrngM/p/12899026.html 这里主要是…
阅读更多...
docker安装mysql突然无法远程连接

docker安装mysql突然无法远程连接

docker安装mysql突然莫名其妙的无法远程连接 docker安装mysql突然无法远程访问问题背景发现问题排查问题解决问题总结 docker安装mysql突然无法远程访问 问题背景 大概一年前在服务器中通过docker安装mysql5.7端口映射关系是3308->3306 前期在服务器上开方了3308端口 fir…
阅读更多...
redis操作set时的性能分析y以及一系列问题

redis操作set时的性能分析y以及一系列问题

redis操作set时的性能分析y以及一系列问题 第一次测试 初始状态 第一次测试 第二次 初始状态 第二次测试 测试代码 Javapackage cn.only.hww; import redis.clients.jedis.Jedis; import java.util.*;/** * author…
阅读更多...
液氮罐搬运过程中的安全注意事项有哪些

液氮罐搬运过程中的安全注意事项有哪些

在液氮罐搬运过程中&#xff0c;安全性是至关重要的考虑因素。液氮是一种极低温的液体&#xff0c;其温度可达零下196摄氏度&#xff0c;在接触到人体或物体时会迅速引发严重的冷冻伤害。因此&#xff0c;正确的搬运和使用液氮罐是保障操作安全的关键。 液氮是一种无色、无味的…
阅读更多...
每日一题，力扣leetcode Hot100之128. 最长连续序列

每日一题，力扣leetcode Hot100之128. 最长连续序列

题目理解&#xff1a; 从示例1可以看出简单的连续数字就算&#xff0c;从示例2可以看出当有重复数字时&#xff0c;是不算长度的 解法一&#xff1a; 第一个想到的解法&#xff0c;就是对nums排序&#xff0c;然后双层循环遍历进行判断&#xff0c;当前一个和后一个相减等于…
阅读更多...
【鸿蒙学习笔记】位置设置・direction・容器内主轴方向上元素的布局

【鸿蒙学习笔记】位置设置・direction・容器内主轴方向上元素的布局

官方文档&#xff1a;位置设置 目录标题 direction・容器内主轴方向上元素的布局Row direction direction・容器内主轴方向上元素的布局 Row direction Row() {Text(1).height(50).width(25%).fontSize(16).backgroundColor(0xF5DEB3).textAlign(TextAlign.Center)Text(2)…
阅读更多...
NVidia 的 gpu 开源 Linux Kernel Module Driver 编译 安装 使用

NVidia 的 gpu 开源 Linux Kernel Module Driver 编译 安装 使用

见面礼&#xff0c;动态查看gpu使用情况&#xff0c;每隔2秒钟自动执行一次 nvidia-smi $ watch -n 2 nvidia-smi 1&#xff0c;找一台nv kmd列表中支持的 GPU 的电脑&#xff0c;安装ubuntu22.04 列表见 github of the kmd source code。 因为 cuda sdk 12.3支持最高到 ubu…
阅读更多...
[MySQL][索引][下][理解索引]详细讲解

[MySQL][索引][下][理解索引]详细讲解

目录 0.前期准备1.为何IO交互要是Page&#xff1f;2.理解单个Page3.理解多个Page4.页目录5.单页情况6.多页情况7.总结复盘8.InnoDB 在建立索引结构来管理数据的时候&#xff0c;其他数据结构为何不行&#xff1f;9.聚簇索引 vs 非聚簇索引 0.前期准备 建立测试表 create table …
阅读更多...
网站开发：使用VScode安装yarn包和运行前端项目

网站开发：使用VScode安装yarn包和运行前端项目

一、首先打开PowerShell-管理员身份运行ISE 输入命令&#xff1a; set-ExecutionPolicy RemoteSigned 选择“全是”&#xff0c;表示允许在本地计算机上运行由本地用户创建的脚本&#xff0c;没有报错就行了 二、接着打开VScode集成终端 输入 npm install -g yarn 再次输入以…
阅读更多...
2-38 基于matlab的蚁群算法优化无人机uav巡检

2-38 基于matlab的蚁群算法优化无人机uav巡检

基于matlab的蚁群算法优化无人机uav巡检&#xff0c;巡检位置坐标可根据需求设置&#xff0c;从基地出发&#xff0c;返回基地&#xff0c;使得路径最小。可设置蚁群数量&#xff0c;信息素系数。输出最佳路线长度。程序已调通&#xff0c;可直接运行。 2-38 蚁群算法优化无人…
阅读更多...
人工智能算法工程师(高级)课程1-单类目标识别之人脸检测识别技术MTCNN模型介绍与代码详解

人工智能算法工程师(高级)课程1-单类目标识别之人脸检测识别技术MTCNN模型介绍与代码详解

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能算法工程师(高级)课程1-单类目标识别之人脸检测识别技术MTCNN模型介绍与代码详解。本文深入探讨了基于PyTorch的人脸检测与识别技术&#xff0c;详细介绍了MTCNN模型、Siamese network以及center loss、sof…
阅读更多...
Linux/Windows 系统分区

Linux/Windows 系统分区

1. Windows 系统 1.1 系统分区 系统分区也叫做磁盘分区&#xff0c;即分盘&#xff1b; 举个例子&#xff0c;好比家里有一个大柜子&#xff0c;把衣服&#xff0c;鞋子&#xff0c;袜子都放在里面&#xff0c;由于没有隔断&#xff0c;找的时候非常麻烦&#xff0c;找是能找…
阅读更多...
最新文章

Copyright @ 2022~2023