【平衡二叉搜索树（AVL）-- 旋转】

news/2024/11/8 14:43:38/

目录：

前言

打怪升级：第60天
在这里插入图片描述

AVLTree，也就是我们所说的：自平衡二叉搜索树，AVL命名由来是两位发明者的名字的首字母，并无其他含义。
AVL树有两个重要的特点：

  1. AVL树是一棵搜索树；
  2. AVL树左右子树的高度差的绝对值不大于1；
  3. AVL树的左右子树也是AVL树。
    高度差可取0,1,-1。

注：我们将左右子树的高度差称为平衡因子，简称为bf（Balance Factor）。

  • 既然AVL树是一棵搜索树它就需要满足搜索树的特征：
  1. 左子树不空，左子树上的值都小于根节点的值；
  2. 右子树不空，右子树上的值都大于根节点的值；
  3. 左右子树也都是二叉搜索树。
  • 既然要保持AVL树左右子树的高度差的绝对值不大于1，我们就需要记录以及修改它，这里我们采用的方法是旋转。

下面我们首先从二叉搜索树的插入开始引入AVL树的插入，以及之后的旋转操作，话不多说，大家上车。

1、二叉搜索树的插入

根据二叉搜索树的性质：左子树节点的值都小于根，右子树节点的值都大于根，我们可以在插入的时候进行一下判断即可，
需要注意的是：如果出现相同的值我们不进行插入。

	template<class K>struct BSTreeNode {BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}struct BSTreeNode* _left;struct BSTreeNode* _right;K _key;};bool Insert(const k& key){if (_root == nullptr) // 空树 -- 插入的节点作为根{_root = new Node(key);}else{Node* prev = nullptr; // cur的父节点 Node* cur = _root;while (cur)  // 小放左，大放右，同不加{if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{return false;}}if (key < prev->_key)  // 判断插入到prev的左边还是右边prev->_left = new Node(key);elseprev->_right = new Node(key);}return true;}

上面的操作就可以让我们实现二叉搜索树的插入，因为AVL树也是一棵二叉搜索树，他也需要符合二叉搜索树的性质，因此有了二叉搜索树的插入我们就可以很方便的写出AVL树的插入过程，
但是AVL树不仅有二叉搜索树的性质还有自己的一些特性：bf的绝对值不大于1，但是插入的过程中我们只考虑了搜索树的性质，因此在插入之后我们需要检查是否符合AVL树的特性，如果符合我们就不做修改，否则就需要进行旋转。

2、AVL树的旋转

bf的计算我们采用右子树高度 减去 左子树高度

我们来理一理什么时候需要进行旋转：

  1. 插入节点后该节点一定是叶子结点没有左右子树，因此bf为0，
    而插入节点后高度收到影响的就是它的所有祖先节点，因此我们需要从该节点开始往上检查它的祖先节点的bf；

  2. 如果插入之后该节点的祖先节点变成了1/-1， 说明该祖先节点原本是0，此时插入之后高度改变了，我们就需要继续往上更新其他祖先节点。

  3. 而如果插入之后该节点的祖先节点变成了0，说明该祖先节点之前是不平衡的（1/-1），插入之后变成了完全平衡，此时整棵树的高度并没有改变，那么我们就不需要往上更新了。

  4. 既然bf的绝对值不可以大于1，那么当插入一个新的节点后它的某个祖先节点的bf变成了±2，就说明出现了问题，我们需要进行旋转，
    在正常情况下当bf变成±2时我们就要进行旋转，因此不会出现bf绝对值大于2的情况。

在这里插入图片描述

因为插入节点之后我们需要从该节点出发往上检查它的祖先节点，此处我们采用三叉链。
插入的操作同二叉搜索树，下面我们来将上面的分析过程通过代码实现出来：

struct AVLTreeNode
{AVLTreeNode(const int& val):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_val(val){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent; // 指向父亲int _bf; // 平衡因子int _val; // 数据};// insert中的调整操作parent = cur->_parent;while (parent){if (cur == parent->_left) --parent->_bf;else ++parent->_bf;if (parent->_bf == 0) // 说明我们现在使得父亲的左右平衡了，整体h不变，结束调整{break;}else if (parent->_bf == 1 || parent->_bf == -1) // 父亲的h增加，继续向上调整{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2) // 对父亲进行旋转，之后结束调整{// 判断如何旋转if (parent->_bf == 2 && cur->_bf == 1) // 右右高，左单旋RotateL(parent);else if (parent->_bf == -2 && cur->_bf == -1) // 左左高，右单旋RotateR(parent);else if (parent->_bf == 2 && cur->_bf == -1) // 从下往上：左右高，先右旋再左旋RotateRL(parent);else if (parent->_bf == -2 && cur->_bf == 1) // 从下往上：右左高，先左旋再右旋RotateLR(parent);break;}else // 前面就出错了{assert(false);}}

旋转操作一共分为4种情况，上方是旋转操作的大框架，下面我们来对它们逐个击破。

（1）右单旋（LL）

右单旋：左子树高，将根节点向右旋转降低左子树的高度并且增加右子树的高度。
由下图我们可以看出 – 经过旋转后三个节点的bf都变为了0 – 根节点的变为了叶子结点，根节点的左子树变为了新的根并且右子树的高度+1。

这里是引用

那么通过上图我们是否可以尝试写出第一份代码？

	void RotateR(Node* parent) // 左高，右单旋{Node* nodeL = parent->_left;nodeL->_right = parent;parent->_parent = nodeL;_root = nodeL; // 更新根节点nodeL->parent=nullptr;parent->_bf = nodeL->_bf = 0;}

好像这样就结束了，也没有多复杂嘛，甚至，异常的简单？针对上面的情况我们的确解决了，但是我们来看一看下面的情况：

这里是引用
此时需要旋转的是中间的部分节点，既然是中间的部分，我们就需要链接旧根节点的父节点与新根节点。

在这里插入图片描述
此时需要旋转的部分确实是根节点，不过他好像很特殊，新根节点左右子树都有，我们想要将旧根节点作为新根节点的右子树，就需要先保存新根节点的右子树。

上方的就是我们右旋过程过程中会遇到的所以情况，下面我们对右旋的情况进行总结并且写出完整代码。
右旋的步骤：

  1. 旧根节点作为新根节点的右子树，因此我们需要保存新根节点的右子树；
  2. 新根节点的右子树作为旧根节点的左子树；
  3. 旧根节点改变，因此我们需要更改旧根节点的父亲节点，
  4. 通过上面的分析我们发现：最多有4个节点需要发生更改：旧根节点，旧根节点的父亲节点，旧根节点的左孩子（新根节点），新根节点的右孩子 ，而四个节点可以形成三组父子关系，因此我们在右旋时需要修改三组父子关系。

下图中的方块表示一颗颗子树，h为树的高度，希望朋友们可以自行尝试画一画h=0、1 、2。。。的情况，可以加深我们对右旋的理解。
在这里插入图片描述

	void RotateR(Node* parent) // 左高，右单旋{Node* nodeL = parent->_left;  // 旧根节点的左节点 -- 新根节点Node* nodeLR = nodeL->_right;  // 左子树的右子树Node* nodePP = parent->_parent; // 旧根节点的父节点parent->_left = nodeLR;if (nodeLR != nullptr) //  左子树的右子树不为空nodeLR->_parent = parent;nodeL->_right = parent;parent->_parent = nodeL;nodeL->_parent = nodePP;if (nodePP == nullptr) // 根{_root = nodeL;}else // 更新父节点的孩子{if (nodePP->_left == parent)nodePP->_left = nodeL;elsenodePP->_right = nodeL;}// 更新bfparent->_bf = nodeL->_bf = 0; }

动图图解:
在这里插入图片描述在这里插入图片描述在这里插入图片描述

（2）左单旋（RR）

左旋的步骤：

  1. 旧根节点作为新根节点的左子树，因此我们需要保存新根节点的左子树；
  2. 新根节点的左子树作为旧根节点的右子树；
  3. 旧根节点改变，因此我们需要更改旧根节点的父亲节点，
  4. 通过上面的分析我们发现：最多有4个节点需要发生更改：旧根节点，旧根节点的父亲节点，旧根节点的右孩子（新根节点），新根节点的左孩子 ，而四个节点可以形成三组父子关系，因此我们在右旋时需要修改三组父子关系。

同右单旋基本一样，下方给出统一图形以及代码解析：

这里是引用

	void RotateL(Node* parent) // 右高，左单旋 -- 或者说叫做右右高，左单旋{Node* nodeR = parent->_right;Node* nodeRL = nodeR->_left;Node* nodePP = parent->_parent;parent->_right = nodeRL;if (nodeRL) nodeRL->_parent = parent;nodeR->_left = parent;parent->_parent = nodeR;if (nodePP) // 不是根节点{if (parent == nodePP->_left)nodePP->_left = nodeR;elsenodePP->_right = nodeR;}else{_root = nodeR;}nodeR->_parent = nodePP;// 更改bfparent->_bf = nodeR->_bf = 0;}

（3）右左双旋（LR）

在左单旋和右单旋的情况下，我们遇到的都是：根节点和它的孩子节点都是同一边高，如下图：
左：parent与nodeL都是左子树高
右：parent与nodeR都是右子树高

这里是引用

下边这种情况：
parent右子树高，nodeR左子树高，此时如果单单使用一次左旋或者右旋无法解决我们不平衡问题。
在这里插入图片描述
这种父亲和孩子高度差不在同一边的情况下我们可以将nodeR的方向转换一下，将nodeR右旋之后parent与nodeR的高度差就达到了统一，
此时再对根节点进行一次左旋就可以达到平衡的目的。

在这里插入图片描述

我们实际上会遇到的情况一共有以下三种：

在这里插入图片描述

只是看图的话好像看不出来点什么，那么我们看一看平衡之后 parent 与 nodeR的bf，新的根节点的bf一定为0，而parent与nodeR的bf却是不断变化的，那么为什么会有出现这三种情况？
这与nodeR的左孩子的孩子有关，它是否有孩子，以及有的是左孩子还是右孩子都会出现不一样的结果，
而单纯的左旋与右旋之后都会将parent与nodeR设置为0，因此这里需要我们进行特殊处理，
我们可以nodeR的左孩子的bf来判断parent与nodeR的bf。
具体代码如下：

	void RotateRL(Node* parent) // 从下往上：左右高，先右旋再左旋{// 旋转Node* nodeR = parent->_right;Node* nodeRL = nodeR->_left;int bf = nodeRL->_bf;   // 用来判断RotateR(nodeR);       // 复用RotateL(parent);// 更改bfnodeRL->_bf = 0;if (bf == 1){parent->_bf = -1;nodeR->_bf = 0;}else if (bf == -1){parent->_bf = 0;nodeR->_bf = 1;}else if (bf == 0){parent->_bf = 0;nodeR->_bf = 0;}else  // 走到这一步说明在插入新节点之前就出问题了{assert(false);}}

在这里插入图片描述

（4）左右双旋（RL）

类比右左双旋。
注：小标题中的 RL指的是：nodeL的右子树高，parent的左子树高
左右双旋指的是：先左旋再右旋

	void RotateLR(Node* parent)  // 从下往上：右左高，先左旋再右旋{Node* nodeL = parent->_left;Node* nodeLR = nodeL->_right;int bf = nodeLR->_bf;// 旋转RotateL(nodeL);RotateR(parent);// 更改bfnodeLR->_bf = 0;if (bf == -1){nodeL->_bf = 0;parent->_bf = 1;}else if (bf == 1){nodeL->_bf = -1;parent->_bf = 0;}else if (bf == 0){nodeL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

完整插入代码以及打印验证

#pragma once
#include<iostream>
using namespace std;
#include<cassert>class AVLTree
{typedef AVLTreeNode Node;
public:AVLTree():_root(nullptr){}bool Insert(const int& p){// 插入 -- 找好位置后需要更新bfif (_root == nullptr){_root = new Node(p);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_val < p){parent = cur;cur = cur->_right;}else if (cur->_val > p){parent = cur;cur = cur->_left;}else  // 已经存在return false; }	cur = new Node(p);if (cur->_kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;// 开始向上调整bf，判断是否需要旋转 == 2/-2while (parent){if (cur == parent->_left) --parent->_bf;else ++parent->_bf;if (parent->_bf == 0) // 说明我们现在使得父亲的左右平衡了，整体h不变，结束调整{break;}else if (parent->_bf == 1 || parent->_bf == -1) // 父亲的h增加，继续向上调整{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2) // 对父亲进行旋转，之后结束调整{// 判断如何旋转if (parent->_bf == 2 && cur->_bf == 1) // 右右高，左单旋RotateL(parent);else if (parent->_bf == -2 && cur->_bf == -1) // 左左高，右单旋RotateR(parent);else if (parent->_bf == 2 && cur->_bf == -1) // 从下往上：左右高，先右旋再左旋RotateRL(parent);else if (parent->_bf == -2 && cur->_bf == 1) // 从下往上：右左高，先左旋再右旋RotateLR(parent);break;}else // 前面就出错了{assert(false);}}return true;}void InOrder(){_InOrder(_root);}
private:void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_val << ", \t" << root->_bf << endl;_InOrder(root->_right);}private:Node* _root = nullptr;
};

3、为什么需要AVL树

有的朋友会有疑问：既然我们已经有了搜索二叉树，而且查找效率也十分不错，为什么还要专门来一个平衡二叉搜索树，这样有必要吗，
嗯~答案肯定是有的，而且，十分有，
在存储数据方面我们有了单链表与数组就已经足够了，之所以更加费事地设计二叉树这种结构并不是因为它长得更优美好看，而是想要利用它，通过对它的存储方式进行限制来达到快速查询的效果 – 二叉搜索树，二叉树在设计之初就不是为了插入和删除。
但是，实际情况下二叉搜索树的形态与插入数据的顺序有很大关系，乱序插入更有利于形成“健康的”二叉搜索树，
如果我的插入的数据是一组接近有序序列，那么得到的二叉树就是一棵“歪脖子树”，甚至是单链表：
在这里插入图片描述

这时对数据的查找效率接近O(N),基本上是遍历一整颗树，因此，在插入过程中我们需要对它进行调整，保证它是一棵“健康的”二叉树，
这样才可以保证查询的高效性：在这里插入图片描述

总结

旋转是为了在保持平衡树性质的前提下降低树的高度，右子树高就左旋，左子树高就右旋。
如果你还有一些疑问未得到解答，可以查看完整代码部分的旋转情况判断，这一些判断条件可以给你很好的启发，配合上自己动手画图，我相信你一定掌握它。

文章中的动图来源：AVL Tree测试


http://www.ppmy.cn/news/56366.html

相关文章

用扩展方法来实现EventTrigger中事件的异步等待

用扩展方法来实现EventTrigger中事件的异步等待

一、什么是扩展方法&#xff1f; 扩展方法是一种C#语言提供的功能&#xff0c;允许我们向现有类型添加新的方法&#xff0c;而无需修改类型的源代码。扩展方法的优缺点如下&#xff1a; 二、它有什么优点&#xff1f; 1、不需要修改源类型的代码&#xff1a;使用扩展方法可以…
阅读更多...
Spring--AOP详细介绍--和详细代码演示证明理解

Spring--AOP详细介绍--和详细代码演示证明理解

目录 Spring--AOP详细介绍 基本介绍 代码演示—入门 需求说明 定义一个接口类Vehicle 定义一个实现接口类的Car类 定义一个实现接口类的Ship类 创建测试类Test.java 来思考一下&#xff0c; 解决方案-动态代理方式-2 修改 Car类 修改 Ship类 创建VehicleProxyProvid…
阅读更多...
Packet Tracer - 静态路由故障排除

Packet Tracer - 静态路由故障排除

Packet Tracer - 静态路由故障排除 地址分配表 设备 接口 IPv4 地址 子网掩码 默认网关 R1 G0/0 172.31.1.1 255.255.255.128 不适用 S0/0/0 172.31.1.194 255.255.255.252 不适用 R2 G0/0 172.31.0.1 255.255.255.0 不适用 S0/0/0 172.31.1.193 255.255…
阅读更多...
开源，点云处理及三维重建软件（Point Cloud Viewer, PCV）的设计与实现

开源，点云处理及三维重建软件（Point Cloud Viewer, PCV）的设计与实现

GitHub地址&#xff1a;point-cloud-viewer GitCode地址&#xff1a;point-cloud-viewer 文章目录 使用教程以及相关工具库Step 1 搭建环境Step 2 使用Cmake构建工程Step3 使用VS 编写code并编译执行 点云处理及三维重建软件(PCV)的设计与实现一&#xff0c; 软件总体设计1.1 软…
阅读更多...
Android 9.0 原生SystemUI下拉通知栏每条通知默认展开

Android 9.0 原生SystemUI下拉通知栏每条通知默认展开

1.前言 在9.0的系统rom原生开发中，在产品对SystemUI下拉通知栏做定制的时候，在下拉状态栏的时候，通知栏中 最后一条通知默认是收缩的 点击按钮 就会展开 原生系统systemui就是如此，为了更美观 所以要求最后一条通知也默认展开，显得更美观 最终效果图: 2.原生SystemUI下拉通…
阅读更多...
【id:58】【20分】C. 复数运算（友元函数）

【id:58】【20分】C. 复数运算（友元函数）

时间限制 1s 内存限制 128MB 题目描述 复数类的声明如下&#xff1a; class Complex { private: double real; // 实部 double imag; // 虚部 public: Complex(); Complex(double r, double i); // 友元函数&#xff0c;复数c1 c2(二参数对象相加) friend Complex addCom(co…
阅读更多...
【Linux】入门介绍

【Linux】入门介绍

&#x1f331;博客主页&#xff1a;大寄一场. &#x1f331;系列专栏&#xff1a;Linux &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注​ 目录 前言 Linux背景介绍 1.发展史 UNIX发展的历史 Linux发展历史 2. 开源 3. 官网 4. 企业应用现状 5. 发行版…
阅读更多...
如何理解自动化测试数据驱动与关键字驱动的区别?

如何理解自动化测试数据驱动与关键字驱动的区别?

一、关键字驱动KDT(Keyword-driven testing) 1、自动化测试框架发展的第三个阶段是关键字驱动测试框架阶段&#xff0c;它是当前比较流行的一种框架之一&#xff0c;并且现在的自动化测试工具已经将关键字驱动框架融入到工具中。在录制过程中自动化测试工具会将对象及操作属性保…
阅读更多...
最新文章

Copyright @ 2022~2023