【高阶数据结构】AVL树（动图详解）

news/2025/1/15 18:18:50/

🌈欢迎来到数据结构专栏~~AVL树详解

  • (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
  • 目前状态：大三非科班啃C++中
  • 🌍博客主页：张小姐的猫~江湖背景
  • 快上车🚘，握好方向盘跟我有一起打天下嘞！
  • 送给自己的一句鸡汤🤔：
  • 🔥真正的大师永远怀着一颗学徒的心
  • 作者水平很有限，如果发现错误，可在评论区指正，感谢🙏
  • 🎉🎉欢迎持续关注！
    请添加图片描述

请添加图片描述

文章目录

  • 🌈欢迎来到数据结构专栏~~AVL树详解
    • 一. AVL树的概念
    • 二. AVL树结点的定义
    • 三. AVL树的插入
    • 四. AVL树的旋转
      • 🥑左单旋
      • 🥑右单旋（和左单旋高度相似）
      • 🔥左右单旋
      • 🔥右左单旋
    • 五. 验证AVL树
    • 六. AVL树的性能

请添加图片描述

一. AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

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

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

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称 平衡因子)的绝对值不超过1(-1/0/1)
  • 平衡因子= 右子树高度 - 左子树高度；非必须，也可以不要，只是方便我们实现的一种方式！

在这里插入图片描述
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O(log2n)O(log_2 n)O(log2​n)，搜索时间复杂度O(log2nlog_2 nlog2​n)

单支树的效率是O(N)O(N)O(N)，AVL树不一样，在10亿中只用找30次（可能多一点）

在这里插入图片描述

二. AVL树结点的定义

此处我们定义成三叉链结构 ，方便后序的操作；也在每个节点引入了平衡因子（右子树高度-左子树高度），还需要实现一下构造函数，左右子树以及父节点都是空，再把平衡因子设置为0即可

template<class K, class V>
struct AVLTreeNode
{//定义三叉链AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;//存储的键值对pair<K, V> _kv;//平衡因子(balance factor)int _bf;//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

注意：平衡因子不是必须的，只是我们实现高度平衡的一种方式，不用平衡因子也是可以实现的

三. AVL树的插入

插入节点有三个步骤

  1. 按照二叉搜索树的原理，找到待插入的位置
  2. 判断待插入的节点是在parent的左还是右，插入节点
  3. 更新平衡因子，如果发现不平衡，则要旋转

🔥因为AVL树本身就是一颗二叉搜索树，插入规则（比较节点大小即可）：

  • 插入的节点key值 > 当前位置的key值，插入到右子树
  • 插入的节点key值 < 当前位置的key值，插入到左子树
  • 插入的节点key值等于当前位置的key值，插入失败

🌈那判断完插入成功与否，是不是就要判断平衡因子的更新了

平衡因子是否更新取决于：该结点的左右子树的高度是否发生了变化，因此插入一个结点后，该结点的 祖先结点的平衡因子可能需要更新

在这里插入图片描述

🌏更新平衡因子的规则：

  • 新增在右，parent -> bf++；新增在左，parent -> bf --；

每更新完一个结点的平衡因子后，都需要进行以下判断：

  1. 如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子
  2. 如果parent的平衡因子等于0；表明无需往上更新平衡因子
  3. 如果parent的平衡因子等于-2或者2；就已经不平衡了，需要旋转处理
  4. 如果parent的平衡因子大于2或者小于-2；就说明之前插入的就不是AVL树了，赶紧去检查💥
更新后的平衡因子分析
-1 or 1说明parent插入前的平衡因子是0；左右子树高度相等，插入后有一边高，parent高度变了，则需要往上继续更新
0说明parent插入前的平衡因子是 -1 or 1；左右子树一边高一边低，插入后两边相等，插入的填上了矮的那一边，parent的高度不变，不需要继续往上更新
-2 or 2说明parent插入前的平衡因子是 -1 or 1；已经是平衡的临界值了；插入后变成-2 or 2 ；打破了平衡，parent所在的子树需要旋转处理

最坏的情况如下：一路更新到root根节点

在这里插入图片描述

那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，向上递归，直到parent为空的情况，以下逻辑是必须的

	cur = parent;parent = parent->_parent;

当平衡因子出现了2/-2的情况，要对子树进行旋转处理，但也要遵守原则

  • 旋转成平衡树
  • 保持搜索树的规则

而旋转有四种大情况，对此我们要进行分类：

  1. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋

  2. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋

  3. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋

  4. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋

注意：旋转过后无需再往上更新平衡因子了，因为高度已经没有发生变化了，也就不会影响父节点的平衡因子了

	//插入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)//插入节点值大于当前节点的key{parent = cur;cur = cur->_right;//往右走}else if (cur->_kv.first > kv.first)//插入节点值小于当前节点的key{parent = cur;cur = cur->_left;//往左走}else{//插入的节点key值等于当前位置的key值，插入失败return false;}}//开始插入cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else if (parent->_kv.first < kv.first){parent->_left = cur;}//连接parentcur->_parent = parent;//控制平衡//1、更新平衡因子while (parent){if (cur == parent->right){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == -1 || parent->_bf == 1)//也可以用abs{cur = parent;parent = parent->_parent;}else if (parent->_bf == 0){break;}else if (parent->_bf == -2 || parent->_bf == 2){//说明parent所在的子树已经不平衡了，需要旋转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){RotateLR(parent);//左右双旋}break;}else{assert(false);//在插入前树的平衡因子就有问题}}return true;}

四. AVL树的旋转

🥑左单旋

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

⚡动图展示：

请添加图片描述

抽象图过程解析：

在这里插入图片描述
其中h可以等于0、1、2等等，不过都可以归纳到这种大情况，处理情况都一样，都是引发parent 等于2，cur等于1

左单旋旋转步骤：

  1. subRL变成parent的右子树（subL和parent的关系，要注意🔥subL可能为空）
  2. parent成为subR的左子树（parent和subLR的关系）
  3. subR成为根节点（ppNode 和 subL关系，也要注意🔥parent是子树的根还是整棵树的根）
  4. 最后更新平衡因子

在这里插入图片描述

为什么要这样旋转？要符合二叉搜索树规则

  • subR的左子树的值本身就比parent的值要大，所以可以作为parent的右子树
  • parent及其左子树当中结点的值本身就比subR的值小，所以可以作为subR的左子树

平衡因子更新：

在这里插入图片描述

可以看见，左单旋后树的高度就平衡了，也就无需继续向上更新平衡因子了

代码实现如下：（详细注释）

	void RotateL(Node* parent){//三叉链Node* subR = parent->_right;Node* subLR = subR->_left;Node* ppNode = parent->_parent;//subR 和 parent之间的关系subR->_left = parent;parent->_parent = subR;//subRL 和 parent之间的关系subRL = parent->_right;if (subRL)subRL->parent = parent;//ppNode 和 subR的关系if (ppNode == nullptr){_root = subR;subR->_parent = nullptr;//没有父节点，所以为空}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}//更新平衡因子subR->_bf = parent->_bf = 0;}

🥑右单旋（和左单旋高度相似）

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

动图演示：

请添加图片描述抽象图过程解析：

在这里插入图片描述

右单旋旋转步骤：

与左单旋雷同，看上面就行

同样也要满足二叉搜索树的性质：也是和左单旋雷同，看上面就行

平衡因子更新如下：

在这里插入图片描述同样右单旋后，parent的平衡因子为0，左右子树高度相等，也就无需继续往上更新平衡因子了

话不多说上代码：

//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* ppNode = parent->_parent;//subL 和 parent的关系subL->_right = parent;parent->_parent = subL;//subLR 和 parent之间的关系parent->_left = subLR;if (subLR)subLR->_parent = parent;//ppNode 和 subL的关系if (ppNode == nullptr){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left == subL;}else{ppNode->_right == subL;}subL->_parent = ppNode;}//更新平衡因子subL->_bf = parent->_bf = 0;
}

🔥左右单旋

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

动图演示：
请添加图片描述

在b树或者c树中新增节点，均会引发左右双旋

旋转示意图如下：

1、插入新节点
在这里插入图片描述

2、以30为旋转点进行左单旋

在这里插入图片描述

3、以90为旋转点进行右单旋

在这里插入图片描述

左右单旋的步骤如下：

  1. 以subL为节点左单旋
  2. 以parent为节点右单旋
  3. 更新平衡因子（这才是重点）

左右双旋后满足二叉搜索树的性质：

实际上就是把subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根（看图理解）

  • subLR左子树的节点值比subL的值大，所以可以作为subL的右子树
  • subLR右子树的节点值比parent的值小，因此可以作为parent的左子树
  • 前两个步骤之后，subL以及子树的值，和parent的值均符合，所以可以当subLR的左右子树

重点来了：（以subLR为突破口）
左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：

  1. 当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0

在这里插入图片描述

  1. 当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0

在这里插入图片描述

  1. 当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0

在这里插入图片描述
经过左右双旋后，即树的高度没有发生变化，所以无需继续往上更新平衡因子

话不多说，代码实现一下吧：

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//subL节点左单旋RotateL(subL);//parent节点进行右单旋RotateR(parent);//更新平衡因子if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if(bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);//旋转前的平衡因子就出错了}}

🔥右左单旋

动图演示：

请添加图片描述

旋转图演示过程：

1、插入新节点

在这里插入图片描述

2、以subR的节点进行右单旋

在这里插入图片描述

3、以parent的节点进行右单旋

在这里插入图片描述

旋转步骤和左右双旋雷同

重点来了：（以subRL为突破口）
左右双旋后，平衡因子的更新随着subRL 原始平衡因子的不同分为三种情况分别对应subRL = 0、1、2情况，此处就不多赘述了，详细可以浏览左右双旋的，情况一样

代码实现

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//subR右单旋RotateR(subR);//parent进行左单旋RotateL(parent);if (bf == 1){subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subRL->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else{assert(false);}}

五. 验证AVL树

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

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

先验证是否为二叉搜索树

	void _InOrder(Node* root){if (root == nullptr){return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}

但中序遍历只能代表是二叉搜索树，不能代表是AVL树，为此还需要验证二叉树的平衡性，查平衡因子有一种监守自盗的感觉，因为平衡因子我们刚修改完，所以我们去查高度俩判断！

  • 如果是空树，证明平衡，是AVL树
  • 根高度差不大于2，并且递归子树的高度差都不大于2，即是AVL树
  • 特殊情况，平衡因子和该点的高度差对不上，要判断一下
	//是否平衡bool IsBalance(Node* root){if (root == nullptr){return true;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;if (diff ！ = root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}//小于2就为真 并且递归调用子树判断是否平衡return abs(diff) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}//后序查找int Height(Node* root){if (root == nullptr)return 0;int leftHT = Height(root->_left);int rightHT = Height(root->_right);return max(leftHT, rightHT) + 1;}

六. AVL树的性能

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


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

相关文章

vue组件之间的数据传递和组件的生命周期

vue组件之间的数据传递和组件的生命周期

一、组件之间的通信1、组件之间的关系&#xff1a;父子关系、兄弟关系、跨级关系2、父子组件之间的通信&#xff08;数据传递&#xff09;&#xff1a;&#xff08;1&#xff09;父组件 ——-> 子组件&#xff1a;使用propsA、第一步&#xff1a;在父组件中使用子组件时&…
阅读更多...
LeetCode：11. 盛最多水的容器

LeetCode：11. 盛最多水的容器

11. 盛最多水的容器1&#xff09;题目2&#xff09;思路3&#xff09;代码4&#xff09;结果1&#xff09;题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x …
阅读更多...
【java集合】HashMap源码解析（基于JDK1.8）

【java集合】HashMap源码解析（基于JDK1.8）

一、Hashmap简介 类继承关系图如下&#xff1a; HashMap实现了三个接口&#xff0c;一个抽象类。主要的方法都在Map接口中&#xff0c;AbstractMap抽象类实现了Map方法中的公共方法&#xff0c;例如&#xff1a;size(),containsKey(),clear()等,主要方法由子类自己实现。 Ha…
阅读更多...
接口的理解

接口的理解

文章目录一、接口匿名实现类、匿名对象练习1练习2JDK8接口的新特性一、接口 1、接口使用interface定义 2、Java中接口和类是并列结构 3、如何定义接口——定义接口中的成员 JDK7之前&#xff1a;只能定义全局常量和抽象方法 全局常量&#xff1a;public static final的&#x…
阅读更多...
1.c++环境配置及第一个环境运行

1.c++环境配置及第一个环境运行

开发IDE与环境 最好是使用ubuntu系统进行开发&#xff0c;如果没有的话&#xff0c;基于windows使用vs code 进行ssh连接到远程的ubuntu主机进行开发也可以。开发的过程跟本地差不多。 vs code IDE 插件的安装 1.变成中文菜单与提示,安装MS-CEINTL.vscode-language-pack-zh-…
阅读更多...
学习一下如何使用python实现一个超级卡哇伊的五角星吧

学习一下如何使用python实现一个超级卡哇伊的五角星吧

Hello呀朋友们~ 今天实在想不出要写啥了，但是前两天有朋友让我写一个五角星，这个好说呀，必须安排的妥妥当当的！！！！！ 在这里我就不多说了，这个也挺简单的，那就直接上代码吧！！！！ 当然颜色你可以自己改变，所有颜色都是可以的昂 我们先来讲一下关于颜色的一些知…
阅读更多...
C++入门（一）

C++入门（一）

目录 一. 关键字 二. 命名空间 三. 输入&输出 1.输出 2.输入 四. 缺省参数 1.全缺省参数 2.半缺省参数 五. 函数重载 1.类型 2.原理 一. 关键字 简单了解一下都有哪些关键字 二. 命名空间 在c语言的学习之中&#xff0c;我们知道&#xff0c;在同一…
阅读更多...
高通平台开发系列讲解（USB篇）USB调试手段汇总说明 - 视频课

高通平台开发系列讲解（USB篇）USB调试手段汇总说明 - 视频课

文章目录 一、USB AT数据流说明二、BUS Hound 工具说明三、sysfs相关USB调试节点四、USB usbmon工具使用五、USB usbmon日志解析六、UsbTreeView软件的使用七、视频讲解分享沉淀、分享、成长，让自己和他人都能有所收获！😄 📢 碰见USB AT不通怎么办？所以本篇章汇总了高通…
阅读更多...
最新文章

Copyright @ 2022~2023