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

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

news 2025/8/4 5:26:06

二叉搜索树：【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.lryc.cn/news/400392.html

相关文章：

  • px,em,rem之间的关系换算
  • HTTP——POST请求详情
  • 外包干了1个月，技术明显退步。。。
  • LeetCode加油站(贪心算法/暴力，分析其时间和空间复杂度)
  • 5.1 软件工程基础知识-软件工程概述
  • HttpUtil工具
  • 并发编程-锁的分类
  • K8S系列-Kubernetes基本概念及Pod、Deployment、Service的使用
  • 在VSCode上创建Vue项目详细教程
  • Go语言入门之流程控制简述
  • 接口测试框架基于模板自动生成测试用例！
  • C++ STL stable_sort用法
  • YOLO v8进行目标检测的遇到的bug小结
  • FastAPI -- 第二弹(响应模型、状态码、路由APIRouter、后台任务BackgroundTasks)
  • 案例 | 人大金仓助力山西政务服务核心业务系统实现全栈国产化升级改造
  • 如何用python写接口
  • 轻量级可扩展易航网址引导系统源码V2.45
  • 解决ESLint和Prettier冲突的问题
  • C判断一个点在三角形上
  • 物业系统自主研发接口测试框架
  • 手机和电脑通过TCP传输
  • Git 在commit后，撤销commit
  • 多模态大模型 - MM1
  • FPGA设计之跨时钟域（CDC）设计篇（2）----如何科学地设计复位信号？
  • GPS北斗标准时钟同步服务器结构是什么？安徽京准
  • 9.5 栅格图层符号化多波段彩色渲染
  • 力扣第九题
  • 鞭炮插画：成都亚恒丰创教育科技有限公司
  • python 循环
  • 映美精黑白相机IFrameQueueBuffer转halcon的HObject