一篇搞定AVL树+旋转【附图详解旋转思想】

2024-03-31 15:44
文章标签 详解 一篇 旋转 avl 思想 搞定 附图

本文主要是介绍一篇搞定AVL树+旋转【附图详解旋转思想】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
————————————————

一.AVL 树

1.1 AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。（上章提过）
所以就有人发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

AVL树的条件：
一棵AVL树可以是空树，是具有以下性质的二叉搜索树：
1.它的左右子树都是AVL树
2.左右子树高度之差(简称平衡因子)的绝对值不超过1 (-1/0/1)(如下图)（这里讨论的该节点的平衡因子=右子树高度-左子树高度）

注意: 下图的平衡因子=左子树高度-右子树高度
在这里插入图片描述
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)。

1.2 AVL树节点的定义

                                //树节点的定义
template<class K,class V>
struct AVLNode
{ AVLNode<K, V>* _left;        //存储左节点AVLNode<K, V>* _right;       //存储右节点AVLNode<K, V>* _parent;      //存储父亲pair<K,V> _kv;               //存储数据int _bl;                     //平衡因子AVLNode(pair<K, V>& kv)      //构造函数:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bl(0)     {}
};

1.3 AVL树的插入

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

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

平衡因子的处理方法：

Cur插入后，Parent的平衡因子一定需要调整，在插入之前，Parent 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

  1. 如果Cur插入到Parent的左侧，只需给Parent的平衡因子-1即可
  2. 如果Cur插入到Parent的右侧，只需给Parent的平衡因子+1即可

此时：Parent的平衡因子可能有三种情况：0，正负1， 正负2

  1. 如果Parent的平衡因子为0，说明插入之前Parent的平衡因子为正负1，插入后被调整成0，此时满足 AVL树的性质，插入成功。
  2. 如果Parent的平衡因子为正负1，说明插入前Parent的平衡因子一定为0，插入后被更新成正负1，此时以Parent为根的树的高度增加，需要继续向上更新。
  3. 如果Parent的平衡因子为正负2，则Parent的平衡因子违反平衡树的性质，需要对其进行旋转处理。

【旋转代码在下面讲解后】
实现代码：

bool insert(pair<K,V>& kv)
{if (_root == nullptr){_root = new Node(kv);}//找插入位置Node* parent = nullptr;   //记录插入位置的父亲，方便插入后链接Node* cur = _root;while (cur){if (cur->_kv > kv){parent = cur;cur = cur->_left;}else if (cur->_kv < kv){parent = cur;cur = cur->_right;}else{return false;}}//到这里就说明找到插入位置了，下面就开始插入了//判断插在父亲的左边还是右边if (cur == parent->left)             {cur = new Node(kv);      parent->_left = cur;cur->_parent = parent;cur->_parent->_bl--;       //如果是在左边插入，则--平衡因子}else if (cur == parent->right){cur = new Node(kv);parent->_right = cur;cur->_parent = parent;cur->_parent->_bl++;      //如果是在右边插入，则++平衡因子}//调节上面节点的平衡值while (parent){//情况1：插入节点后父亲的平衡因子改变if (parent->_bl == 1 || parent->_bl == -1){Node* grandfather = parent->_parent;if (parent = grandfather->_left){grandfather->_bl--;parent = grandfather;}else{grandfather->_bl++;parent = grandfather;}}//情况二：插入节点后父亲的平衡因子不改变else if (parent->_bl == 0){break;}//情况三：父亲的平衡因子已经不满足AVL树的条件//需要旋转处理else if (){/下面的旋转代码后面讲解后贴出//左单旋if (){}//右单旋else if (){}//左右双旋else if (){}//右左双旋else if (){}}}
}

1.4AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
单旋分为：左单旋与右单旋
双旋分为：左右双旋与右左双旋

单旋思想

如图
在这里插入图片描述
如上图，上面的左右单旋，要么是在parent的左子树高，并且左子树中左边高（左左高）
要么是parent的右子树高，并且右子树中右边高（右右高），这种及只需要旋转一边就可以解决不平衡的问题，哪边高，就往另一边旋转即可。

1.4.1左单旋

使用场景：
新节点插入较高右子树的右侧—右右：左单旋。

如图：长方形代表高度为h的子树。

在这里插入图片描述
具体例子：
在这里插入图片描述

解析：

含义解析：

pNodeR = parent->_right
pNodeRL = pNodeR->_left

思想解析：
如上图，右单旋是让pNodeRL节点成为parent的右孩子，然后parent自己变为pNodeR的左孩子，pNodeR变成这个子树的根。

平衡因子的调节：
单旋后pNodeR与parent的平衡因子都变为0；

注意：
在旋转过程中，有以下几种情况需要考虑：

  1. 50节点的左孩子可能存在，也可能不存在。
  2. 25可能是根节点，也可能是子树
    如果是根节点，旋转完成后，要更新根节点。
    如果是子树，可能是某个节点的左子树，也可能是右子树。

实现代码

//左单旋
void rotateL(Node* parent)
{Node* pparent = parent->_parent;  //记录所旋转根节点的父亲Node* pNodeR = parent->_right;   Node* pNodeRL = pNodeR->_left;if (pNodeRL)                //如果该旋转节点的右节点的左孩子存在parent->_right = pNodeRL;pNodeR->_left = parent;  //新的父节点的链接if (parent == _root)       //若parent是根节点{_root = pNodeR;pparent = nullptr;     }else                     //parent不是根节点{if (pparent->_left == parent){pparent->_left = pNodeR;}else{pparent->_right = pNodeR;}}pNodeR->_bl = 0;parent->_bl = 0;
}
1.4.2右单旋

使用场景：
新节点插入较高左子树的左侧—左左：右单旋

如图
在这里插入图片描述
具体例子：
在这里插入图片描述

解析：

含义解析

pNodeL = parent->_Left
pNodeLR = pNodeL->_right

思想解析

如上图，右单旋是让pNodeLR节点变为parent的左孩子，然后parent自己变为pNodeL的右孩子，pNodeL变成这个子树的根。

平衡因子的调节：
单旋后pNodeL与parent的平衡因子都变为0；

在旋转过程中，有以下几种情况需要考虑：

  1. 5节点的右孩子可能存在，也可能不存在。
  2. 8可能是根节点，也可能是子树
    如果是根节点，旋转完成后，要更新根节点。
    如果是子树，可能是某个节点的左子树，也可能是右子树。

代码实现

/右单旋void rotateR(Node* parent){Node* pparent = parent->_parent;Node* pNodeL = parent->_left;Node* pNodeLR = pNodeL->_right;if (pNodeLR)parent->_left = pNodeLR;pNodeL->_right = parent;if (parent == _root){_root = pNodeL;pparent = nullptr;}else{if (pparent->_left == parent){pparent->_left = pNodeL;}else{pparent->_right = pNodeL;}}pNodeL->_bl = 0;parent->_bl = 0;}
双旋思想

如图
在这里插入图片描述
如上图，如果parent的左子树高，并且左子树中的右子树高（左右高），或则是parent的右子树高，并且右子树的左子树高（右左高），则旋转一次不能解决问题，所以就有了双旋的思想。

1.4.3左右单双旋

使用场景：

新节点插入较高左子树的右侧—左右：先左单旋再右单旋

如图
在这里插入图片描述
具体例子：
在这里插入图片描述
解析：
因为是parent的左子树中的右子树高，所以只需要先将parent的左子树进行左旋，将parent的左子树变为左边高，则旋转后parent整个树就变为了左左高，再用上面单旋的思想，parent以旋转点进行右旋即可；

else if (parent->_bl == -2 && parent->_left->_bl == 1)
{int bl = parent->_left->_right->_bl;Node* pNodeL = parent->_left;Node* pNodeLR = pNodeL->_right;rotateL(pNodeL);     //左旋转rotateR(parent);    //右旋转if (-1 == bl)      //分情况调节平衡因子{pNodeLR->_bl = 0;pNodeL->_bl = 0;parent->_bl = 1;}else if (1 == bl){pNodeLR->_bl = 0;parent->_bl = 0;pNodeL->_bl = -1;}else{pNodeLR->_bl = 0;parent->_bl = 0;pNodeL->_bl = 0;}
}
1.4.4右左单旋

使用场景：
新节点插入较高右子树的左侧—右左：先右单旋再左单旋

如图
在这里插入图片描述
具体例子：
在这里插入图片描述

解析：

因为是parent的右子树中的左子树高，所以只需要先将parent的右子树进行右旋，将parent的右子树变为右边高，则旋转后parent整个树就变为了右右高，再用上面单旋的思想，parent以旋转点进行左旋即可；

代码实现

else if (parent->_bl == 2 && parent->_right->_bl == -1)
{Node* pNodeR = parent->_right;Node* pNodeRL = pNodeR->_left;int bl = pNodeRL->_bl;rotateR(pNodeR);   //先右旋rotateL(parent);   //再左旋pNodeRL->_bl = 0;    //分情况调节平衡因子if (1 == bl){parent->_bl = -1;pNodeR->_bl = 0;}else if (-1 == bl){parent->_bl = 0;pNodeR->_bl = 1;}else{parent->_bl = 0;pNodeR = 0;}
}
双旋后平衡因子的调节

我们从结果来看，忽略过程，从图中可以得到
在这里插入图片描述
解析：
实际上就是将60的左孩子给了30的右孩子，把60的有孩子给了90的左孩子。
所以可以得出：
平衡因子的改变与60的平衡因子有关（与它的左右孩子有关）。
情况分为3种：60的平衡因子为（1，0，-1）

下图解为：右左双旋
当为1时：
在这里插入图片描述
结论：

pNodeRL的平衡因子为0
parent–>-1
pNodeR–>0

当为0时：
在这里插入图片描述
结论：

pNodeRL的平衡因子为0
parent–>0
pNodeR–>0

当为-1时：
在这里插入图片描述
结论：

pNodeRL的平衡因子为0
parent–>0
pNodeR–>1

左右双旋的图解
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

旋转总结：

假如以Parent为根的子树不平衡，即Parent的平衡因子为2或者-2
分以下情况考虑：

  1. Parent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pNodeR 当pNodeR的平衡因子为1时，执行左单旋 当pNodeR的平衡因子为-1时，执行右左双旋
  2. Parent的平衡因子为-2，说明Parent的左子树高，设Parent的左子树的根为pNodeL 当pNodeL的平衡因子为-1是，执行右单旋 当pNodeL的平衡因子为1时，执行左右双旋
    旋转完成后，原Parent为根的子树个高度降低，已经平衡，不需要再向上更新。

1.5 AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

  1. 验证其为二叉搜索树
    如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
  2. 验证其为平衡树
    每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
    节点的平衡因子是否计算正确。

代码实现
方法一：

	int Hight(Node* root)    //计算该节点的高度{if (root == nullptr){return 0;}int Hightleft = Hight(root->_left);int Hightright = Hight(root->right);return Hightleft > Hightright ? Hightleft + 1 : Hightright + 1;  //返回左右子树高的那一个}bool _isbalance(Node* root){if(root==nullptr){return true;}int hightleft = Hight(root->_left);    //计算左右子树的高度int hightright = Hight(root->_right);if (abs(hightright - hightleft) >= 2)   //判断高度差{return flase;}if (hightright - hightleft !=root->_bl)    //判断计算结果是否与该节点的平衡因子相等{cout << root->_kv->first<<':' << "异常" << endl;return false;}return isbalance(root->_left) && isblance(root->_right);  //递归}

方法一有大量的重复计算（每一个节点都需要重新计算高度）
方法二更优

方法二：

	bool _isbalance(Node* root,int& height)   //height记录高度{if (root == nullptr){height = 0;return true;}if (!isbalance(root->_left，height) || !isblance(root->_right，height)){return false;}int heightleft = 0;int heightright = 0;if (abs(heightright - heightleft) >= 2)    //如果高度差超过1，则不平衡，返回false{return false;}if (heightright - heightleft != root->_bl)   //检查该节点的平衡因子是否正确{cout << root->_kv->first << ':' << "异常" << endl;return false;}height = heightleft > heightright ? heightleft + 1 : heightright + 1;   //计算height的值return true;}bool isbalance(){return _isbalance(_root);}

1.6 AVL树的性能分析

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

本章完~

这篇关于一篇搞定AVL树+旋转【附图详解旋转思想】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/864691。

相关文章

Python中的魔术方法__new__详解

Python中的魔术方法__new__详解

《Python中的魔术方法__new__详解》：本文主要介绍Python中的魔术方法__new__的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、核心意义与机制1.1 构造过程原理1.2 与 __init__ 对比二、核心功能解析2.1 核心能力2.2
阅读更多...
在PyCharm中安装PyTorch、torchvision和OpenCV详解

在PyCharm中安装PyTorch、torchvision和OpenCV详解

《在PyCharm中安装PyTorch、torchvision和OpenCV详解》：本文主要介绍在PyCharm中安装PyTorch、torchvision和OpenCV方式,具有很好的参考价值,... 目录PyCharm安装PyTorch、torchvision和OpenCV安装python安装PyTor
阅读更多...
SpringBoot条件注解核心作用与使用场景详解

SpringBoot条件注解核心作用与使用场景详解

《SpringBoot条件注解核心作用与使用场景详解》SpringBoot的条件注解为开发者提供了强大的动态配置能力,理解其原理和适用场景是构建灵活、可扩展应用的关键,本文将系统梳理所有常用的条件注... 目录引言一、条件注解的核心机制二、SpringBoot内置条件注解详解1、@ConditionalOn
阅读更多...
Qt spdlog日志模块的使用详解

Qt spdlog日志模块的使用详解

《Qtspdlog日志模块的使用详解》在Qt应用程序开发中,良好的日志系统至关重要,本文将介绍如何使用spdlog1.5.0创建满足以下要求的日志系统,感兴趣的朋友一起看看吧... 目录版本摘要例子logmanager.cpp文件main.cpp文件版本spdlog版本：1.5.0采用1.5.0版本主要
阅读更多...
Linux ls命令操作详解

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,：本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文
阅读更多...
MySQL中的交叉连接、自然连接和内连接查询详解

MySQL中的交叉连接、自然连接和内连接查询详解

《MySQL中的交叉连接、自然连接和内连接查询详解》：本文主要介绍MySQL中的交叉连接、自然连接和内连接查询,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、引入二、交php叉连接（cross join）三、自然连接（naturalandroid join）四
阅读更多...
Go 语言中的select语句详解及工作原理

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道（channel）操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1：监听多个通道示例 2：带
阅读更多...
mysql的基础语句和外键查询及其语句详解(推荐)

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》：本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键
阅读更多...
Spring Boot项目部署命令java -jar的各种参数及作用详解

Spring Boot项目部署命令java -jar的各种参数及作用详解

《SpringBoot项目部署命令java-jar的各种参数及作用详解》：本文主要介绍SpringBoot项目部署命令java-jar的各种参数及作用的相关资料,包括设置内存大小、垃圾回收... 目录前言一、基础命令结构二、常见的 Java 命令参数1. 设置内存大小2. 配置垃圾回收器3. 配置线程栈大小
阅读更多...
鸿蒙中@State的原理使用详解(HarmonyOS 5)

鸿蒙中@State的原理使用详解(HarmonyOS 5)

《鸿蒙中@State的原理使用详解(HarmonyOS5)》@State是HarmonyOSArkTS框架中用于管理组件状态的核心装饰器,其核心作用是实现数据驱动UI的响应式编程模式,本文给大家介绍... 目录一、@State在鸿蒙中是做什么的？二、@Spythontate的基本原理1. 依赖关系的收集2.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2