【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://www.rhkb.cn/news/377349.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

[Vulnhub] Simple CuteNews-CMS+Kernel权限提升

[Vulnhub] Simple CuteNews-CMS+Kernel权限提升

信息收集 IP AddressOpening Ports192.168.8.104TCP:80 $ nmap -p- 192.168.8.104 --min-rate 1000 -sC -sV PORT STATE SERVICE VERSION 80/tcp open http Apache httpd 2.4.7 ((Ubuntu)) |_http-title: Please Login / CuteNews |_http-server-header: Apache/2.4.7…
阅读更多...
a-table 表格 根据序号展示不同的颜色

a-table 表格 根据序号展示不同的颜色

、 代码如下&#xff1a; :row-class-name"(_record, index) > (index % 2 1 ? table-striped : null)" 样式 .table-striped { background-color: #F6F9FA !important; } .table-striped .ant-table-cell-fix-right { background-color: #F6F9FA !important; …
阅读更多...
第一百六十五节 Java IO教程 - Java标准输入/输出/错误流

第一百六十五节 Java IO教程 - Java标准输入/输出/错误流

Java IO教程 - Java标准输入/输出/错误流 我们可以使用System.out和System.err对象引用&#xff0c;只要我们可以使用OutputStream对象。 我们可以使用System.in对象&#xff0c;只要我们可以使用InputStream对象。 System类提供了三个静态设置器方法setOut()&#xff0c;set…
阅读更多...
flutter 列表下拉框加搜索

flutter 列表下拉框加搜索

1.使用控件搜索加下拉框dropdown_search: ^0.4.9和获取中文拼音lpinyin: ^1.1.1 2.加入中文查询和首字查询 在当中找到相应的packages&#xff0c;再在SelectDialog.dart当中加入引入拼音搜索 import package:lpinyin/lpinyin.dart; 更改匹配方法manageItemsByFilter使其可…
阅读更多...
第一个AI应用（文心智能体平台）

第一个AI应用（文心智能体平台）

第一个AI应用&#xff08;文心智能体平台&#xff09; 官网&#xff1a;https://agents.baidu.com/ 平台简介&#xff1a;https://agents.baidu.com/docs/ 部分内容由AI生成&#xff0c;注意甄别 一、什么是AI应用及其功能 AI应用&#xff0c;即人工智能应用&#xff0c;是利用…
阅读更多...
Instagram品牌账号运营：从零到一的全攻略

Instagram品牌账号运营：从零到一的全攻略

Instagram是一个分享日常生活的平台&#xff0c;同时也是品牌与消费者建立联系和进行互动的场所。拥有超过10亿月活跃用户的Instagram&#xff0c;为品牌提供了与消费者进行深入沟通和建立联系的绝佳机会。本文将为您揭示如何从零开始&#xff0c;一步步构建并优化您的Instagra…
阅读更多...
银河麒麟高级服务器操作系统V10加固操作指南

银河麒麟高级服务器操作系统V10加固操作指南

1：检查系统openssh安全配置： 2：检查是否设置口令过期前警告天数： 3：检查账户认证失败次数限制： 修改/etc/pam.d/system-auth文件中deny的参数即可 4：检查是否配置SSH方式账户认证失败次数限制：
阅读更多...
CSS【详解】边框 border，边框-圆角 border-radius，边框-填充 border-image，轮廓 outline

CSS【详解】边框 border，边框-圆角 border-radius，边框-填充 border-image，轮廓 outline

边框 border border 是以下三种边框样式的简写&#xff1a; border-width 边框宽度 —— 数值 px&#xff08;像素&#xff09;,thin&#xff08;细&#xff09;,medium&#xff08;中等&#xff09;,thick&#xff08;粗&#xff09;border-style 边框线型 —— none【默认值…
阅读更多...
数据结构(4.4)——求next数组

数据结构(4.4)——求next数组

next数组的作用:当模式串的第j个字符失配时&#xff0c;从模式串的第next[j]的继续往后匹配 求模式串的next数组(手算) next[1] 任何模式串都一样&#xff0c;第一个字符不匹配时&#xff0c;只能匹配下一个子串&#xff0c;因此&#xff0c;往后&#xff0c;next[1]都无脑写…
阅读更多...
51单片机6（P0P1P2P3结构框架图）

51单片机6（P0P1P2P3结构框架图）

一、GPIO结构框架图与工作原理 1、接下来我们介绍一下这个GPIO结构框图和工作原理&#xff0c;我们使用51单片机的GPIO分为了P0&#xff0c;P1&#xff0c;P2&#xff0c;P3这四组端口&#xff0c;下面我们就分别来介绍这四组端口它的一个内部结构&#xff0c;只有了解了内部的…
阅读更多...
排序相关算法--3.选择排序

排序相关算法--3.选择排序

之前涉及的堆排序就是选择排序的一种&#xff0c;先进行选择。 基本选择排序&#xff1a; 最简单&#xff0c;也是最没用的排序算法&#xff0c;时间复杂度高并且还是不稳定的排序方法&#xff0c;项目中很少会用。 过程&#xff1a; 在一个长度为 N 的无序数组中&#xff0c;…
阅读更多...
Python使用策略模式和openpyxl库创建Excel文件并追加内容

Python使用策略模式和openpyxl库创建Excel文件并追加内容

from openpyxl import load_workbook# 数据数组 data [[1, 2, 3],[4, 5, 6],[7, 8, 9] ]# 打开现有的 Excel 文件 excel_file sheetApend_example.xlsx wb load_workbook(excel_file)# 选择要追加数据的工作表 sheet_name test_Sheet2 # 指定要追加数据的工作表名称 sheet…
阅读更多...
最值得推荐的10款Windows软件！

最值得推荐的10款Windows软件！

AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频播放量破百万https://aitools.jurilu.com/1.音乐播放器——Dopamine Dopamine是一款音乐播放器&#xff0c;设计简洁美观。它支持多种音频格式&#xff0c;包括wav、mp3、ogg…
阅读更多...
爬虫管理解决方案：让数据收集变得高效且合规

爬虫管理解决方案：让数据收集变得高效且合规

一、为何数据收集的效率与合规性同等重要&#xff1f; 随着大数据技术的飞速发展&#xff0c;数据收集已成为企业决策与市场洞察的核心驱动力。然而&#xff0c;在信息海洋中精准捕捞的同时&#xff0c;如何确保这一过程既高效又不触碰法律的红线&#xff0c;是每个数据实践者…
阅读更多...
“金山-讯飞”杯2024年武汉理工大学程序设计竞赛 A. Mobiusp败走***（思维题-点双连通分量、连通性）

“金山-讯飞”杯2024年武汉理工大学程序设计竞赛 A. Mobiusp败走***（思维题-点双连通分量、连通性）

题目 思路来源 官方题解 题解 手玩发现&#xff0c;能换的话&#xff0c;当且仅当.和1在一个环里&#xff0c;而这就是点双连通分量 所以最优策略是先把.换到(x,y)的位置&#xff0c;然后判断.和1在不在一个环里 也就是&#xff1a; 1. 判断删掉1时&#xff0c;.和(x,y)联…
阅读更多...
C++客户端Qt开发——信号和槽

C++客户端Qt开发——信号和槽

三、信号和槽 1.信号和槽概述 在Qt中&#xff0c;用户和控件的每次交互过程称为一个事件。比如"用户点击按钮”是一个事件&#xff0c;"用户关闭窗口”也是一个事件。每个事件都会发出一个信号&#xff0c;例如用户点击按钮会发出"按钮被点击"的信号&…
阅读更多...
基于JavaEE 的影视创作论坛的设计与实现

基于JavaEE 的影视创作论坛的设计与实现

点击下载源码 基于Javaee的影视创作论坛的设计与实现 摘 要 随着时代的发展&#xff0c;互联网的出现&#xff0c;给传统影视行业带来的最大便利就是&#xff0c;方便了影视从业人员以及爱好者的交流和互动&#xff0c;而为用户提供一个书写影评&#xff0c;阅读影评以及回复…
阅读更多...
Centos7 安装Redis6.2.6 gcc报错问题解决

Centos7 安装Redis6.2.6 gcc报错问题解决

Redis 报错信息 make: *** [all] 错误 2 安装gcc 修改yum源,在安装更新rpm包时获得比较理想的速度&#xff0c;走阿里云镜像通道 发现报错信息如下: 正在解析主机 mirrors.aliyun.com (mirrors.aliyun.com)… 失败&#xff1a;未知的名称或服务。 wget: 无法解析主机地址 “mi…
阅读更多...
9.5 栅格图层符号化多波段彩色渲染

9.5 栅格图层符号化多波段彩色渲染

文章目录 前言多波段彩色渲染QGis设置为多波段彩色二次开发代码实现多波段彩色 总结 前言 介绍栅格图层数据渲染之多波段彩色渲染说明&#xff1a;文章中的示例代码均来自开源项目qgis_cpp_api_apps 多波段彩色渲染 以“3420C_2010_327_RGB_LATLNG.tif”数据为例&#xff0c…
阅读更多...
【C++】初识C++（下）

【C++】初识C++（下）

前言 本篇博客继续总结一下C入门的一些小知识 &#x1f493; 个人主页&#xff1a;小张同学zkf ⏩ 文章专栏&#xff1a;C 若有问题 评论区见&#x1f4dd; &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐文章 ​ 目录 1.引用 1.1引用的概念 1.2const引用 1.3指针和引用的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发