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

【C++进阶】AVL树

news 来源：原创 2024/9/21 11:00:10

0.前言

前面我们已经学习过二叉搜索树了，但如果我们是用二叉搜索树来封装map和set等关联式容器是有缺陷的，很可能会退化为单分支的情况，那样效率就极低了，那么有没有方法来弥补二叉搜索树的缺陷呢？

那么AVL树就出现了，通过AVL树的右单旋、左单旋、左右单旋，右左单旋等操作来防止二叉搜索树退化为单分支的情况出现。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树也是以这两位大佬名字的首字母来命名的。

1.AVL树的概念

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树是AVL树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
     

我们这里使用的平衡因子是右子树高度 - 左子树高度。 

 

2.AVL树节点的定义

代码如下：

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;	//该节点的左孩子AVLTreeNode<K, V>* _right;	//该节点的右孩子AVLTreeNode<K, V>* _parent;	//该节点的双亲pair<K, V>  _kv;	//该节点的key和valueint _bf; //balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv)	//该节点初始化:_left(nullptr)  , _right(nullptr), _parent(nullptr), _kv(kv)  , _bf(0){}
};

3.AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子
     

插入思路：

 1.按照搜索树规则插入

2.更新插入节点的祖先节点的平衡因子

        a.插入父亲的右边，父亲的平衡因子--

        b.插入父亲的左边，父亲的平衡因子++

        c.父亲平衡因子 == 0， 父亲所在子树高度不变，不再继续往上更新。插入结束

        d.父亲平衡因子 == 1 or -1， 父亲所在子树高度变了，继续往上更新。

        e.父亲平衡因子 == 2 or -2， 父亲所在子树已经不平衡了，需要旋转处理。

更新中不可能出现其他值，插入之前树是AVL树，平衡因子要么是1 -1 0， ++ --

最多就是c/d/e三种情况。

 代码如下：

	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;}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){//右单旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//左单旋RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//左右双旋RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左双旋//RotateRL(parent);}break;}else{//理论上不会出现这种情况，但仍要判断，大佬都不能保证自己的代码没有bugassert(false);}}return true;}

4.AVL树的旋转

4.1 右单旋

插入新节点要插入较高左子树的左侧（左左）-》右单旋

图形解析：

 实现代码如下：

	void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能为空，不为空时才能调整subLR的父节点subLR->_parent = parent;subL->_right = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}

4.2 左单旋

插入新节点要插入较高右子树的右侧（右右）-》左单旋

图形解析：

 代码如下：

	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能为空，不为空时才能调整subRL的父节点subRL->_parent = parent;subR->_left = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;}

4.3 左右双旋

插入新节点要插入较高左子树的右侧（左右）-》左右双旋

图形解析：

对于插入的位置根据h的高度和插入的位置时的平衡因子出现的最终的结果可分为三种情况：

1.h == 0

        60自己就是新增节点。bf == 0

此时的平衡因子为，30 60 90节点都为0。

2.h > 0

        a.新增节点插入的是60的左子树中 bf == -1

此时的平衡因子为，30节点为0,90为0,60为1

        b.新增节点插入的是60的右子树中bf == 1

此时的平衡因子为，30节点为-1,90为0,60为0

代码如下：

 

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{//理论上不会出现的情况assert(false);}}

4.4 右左双旋

插入新节点要插入较高右子树的左侧（右左）-》右左双旋

与左右双旋类似

代码如下：

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{//理论上不会出现的情况assert(false);}}


总结：
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时，执行左单旋
当pSubR的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是，执行右单旋
当pSubL的平衡因子为1时，执行左右双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。
 

5.AVL树的验证

5.1 验证其是否为二叉搜索树

给一个序列进行一次中序遍历，看是否有序，有序即为二叉搜索树。

void TestAVLTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();
}

5.2 验证其是否为平衡树

	bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->right);}

6.AVL树的删除（了解）

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

7.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即logN。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

 8.AVL树的整体模拟代码实现

#pragma once
#include<iostream>
using namespace std;
#include<assert.h>template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;	//该节点的左孩子AVLTreeNode<K, V>* _right;	//该节点的右孩子AVLTreeNode<K, V>* _parent;	//该节点的双亲pair<K, V>  _kv;	//该节点的key和valueint _bf; //balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv)	//该节点初始化:_left(nullptr)  , _right(nullptr), _parent(nullptr), _kv(kv)  , _bf(0){}
};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;}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){//右单旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//左单旋RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//左右双旋RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左双旋RotateRL(parent);}break;}else{//理论上不会出现这种情况，但仍要判断，大佬都不能保证自己的代码没有bugassert(false);}}return true;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能为空，不为空时才能调整subLR的父节点subLR->_parent = parent;subL->_right = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能为空，不为空时才能调整subRL的父节点subRL->_parent = parent;subR->_left = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_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 == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{//理论上不会出现的情况assert(false);}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{//理论上不会出现的情况assert(false);}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}
private:int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr){return 0;}return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;
};void TestAVLTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();
}
void TestAVLTree2()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();cout << t1.IsBalance() << endl;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • MySQL-笔记-02.关系模型基本理论
  • Android四大组件 Broadcast广播机制
  • 微信小程序毕业设计-智慧旅游平台系统项目开发实战(附源码+演示视频+LW)
  • CentOS-7安装教程
  • 缓存IO与直接IO
  • 基于51单片机的数字频率计(电路图+pcb+论文+仿真+源码)
  • hyperf 多对多关联模型
  • 智能化让幼儿园管理更加规范
  • world machine学习笔记（3）
  • 方正畅享全媒体新闻采编系统 binary.do SQL注入漏洞复现
  • 智能家居6 -- 配置 ini文件优化设备添加
  • 【C++】详解AVL树——平衡二叉搜索树
  • 电商公司需不需要建数字档案室呢
  • 下一代Docker会让部署更丝滑吗
  • 说些什么好呢
  • 深入了解以太坊
  • 《网管员必读——网络组建》（第2版）电子课件下载
  • 【159天】尚学堂高琪Java300集视频精华笔记（128）
  • 【个人向】《HTTP图解》阅后小结
  • angular学习第一篇-----环境搭建
  • mysql 数据库四种事务隔离级别
  • Mysql优化
  • node 版本过低
  • npx命令介绍
  • Protobuf3语言指南
  • ucore操作系统实验笔记 - 重新理解中断
  • vue-cli3搭建项目
  • 阿里云Kubernetes容器服务上体验Knative
  • 成为一名优秀的Developer的书单
  • 浮现式设计
  • 腾讯优测优分享 | Android碎片化问题小结——关于闪光灯的那些事儿
  • ​必胜客礼品卡回收多少钱，回收平台哪家好
  • # 达梦数据库知识点
  • #pragma预处理命令
  • #每天一道面试题# 什么是MySQL的回表查询
  • （C）一些题4
  • （pytorch进阶之路）扩散概率模型
  • (void) (_x == _y)的作用
  • （博弈 sg入门）kiki's game -- hdu -- 2147
  • （不用互三）AI绘画：科技赋能艺术的崭新时代
  • （附源码）ssm航空客运订票系统 毕业设计 141612
  • （附源码）ssm学生管理系统 毕业设计 141543
  • (三)模仿学习-Action数据的模仿
  • (四) 虚拟摄像头vivi体验
  • （一）utf8mb4_general_ci 和 utf8mb4_unicode_ci 适用排序和比较规则场景
  • (原創) 如何動態建立二維陣列(多維陣列)? (.NET) (C#)
  • .bat批处理（八）：各种形式的变量%0、%i、%%i、var、%var%、!var!的含义和区别
  • .net core 管理用户机密
  • .NET Core 项目指定SDK版本
  • .Net Core/.Net6/.Net8 ，启动配置/Program.cs 配置
  • .NET 中使用 Mutex 进行跨越进程边界的同步
  • .NET国产化改造探索（三）、银河麒麟安装.NET 8环境
  • .NET周刊【7月第4期 2024-07-28】
  • []串口通信 零星笔记
  • [20161214]如何确定dbid.txt