🌈感谢阅读East-sunrise学习分享——[进阶数据结构]AVL树博主水平有限，如有差错，欢迎斧正🙏感谢有你码字不易，若有收获，期待你的点赞关注💙我们一起进步🚀🌈我们上一篇博客分享了搜索二叉树，在文中也铺垫了搜索二叉树的一些结构局限性而今天分享的一种特殊的搜索二叉树——AVL树，便是一种结构优异的搜索二叉树🎄那么我们就开始吧🚀🚀🚀目录一、AVL树的概念二、AVL树结点的定义三、AVL树的插入四、AVL树的旋转1.左单旋2.右单旋3.左右双旋4.右左双旋五、最终代码展示一、AVL树的概念二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中
文章目录AVL树的概念AVL树结点的定义AVL树的插入AVL树的旋转左单旋右单旋左右双旋右左双旋AVL树的验证AVL树的查找AVL树的修改AVL树的删除AVL树的性能AVL树的概念二叉搜索树虽然可以提高我们查找数据的效率，但如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可
文章目录AVL树的概念AVL树结点的定义AVL树的插入AVL树的旋转左单旋右单旋左右双旋右左双旋AVL树的验证AVL树的查找AVL树的修改AVL树的删除AVL树的性能AVL树的概念二叉搜索树虽然可以提高我们查找数据的效率，但如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可
🔥🔥欢迎来到小林的博客！！ 🛰️博客主页：✈️小林爱敲代码 🛰️文章专栏：✈️小林的C++之路 🛰️欢迎关注：👍点赞🙌收藏✍️留言 AVL树是一个平衡二叉搜索，相比于红黑树，它更平衡。但是相比于插入删除的操作，红黑树更优。因为旋转有消耗，而红黑树的旋转明显要比AVL树少的多。所以这篇文章给大家带来了平衡二叉树的插入和查找操作，全程动图讲解！千万不要错过！至于删除操以后有机会为大家更新。 每日一句:即使道路坎坷不平，车轮也要前进；即使江河波涛汹涌，船只也航行。目录AVL树的概念AVL树的节点创建AVL类创建AVL树的插入检查AVL
🔥🔥欢迎来到小林的博客！！ 🛰️博客主页：✈️小林爱敲代码 🛰️文章专栏：✈️小林的C++之路 🛰️欢迎关注：👍点赞🙌收藏✍️留言 AVL树是一个平衡二叉搜索，相比于红黑树，它更平衡。但是相比于插入删除的操作，红黑树更优。因为旋转有消耗，而红黑树的旋转明显要比AVL树少的多。所以这篇文章给大家带来了平衡二叉树的插入和查找操作，全程动图讲解！千万不要错过！至于删除操以后有机会为大家更新。 每日一句:即使道路坎坷不平，车轮也要前进；即使江河波涛汹涌，船只也航行。目录AVL树的概念AVL树的节点创建AVL类创建AVL树的插入检查AVL
阅读本文前，请确保您已经了解了二叉搜索树的相关内容（如定义、增删查改的方法以及效率等）。否则，建议您先学习二叉搜索树。本文假定您对二叉搜索树有了足够的了解。效率？众所周知，在平衡条件下，对二叉搜索树中的元素进行增删查改，时间效率为\(O(log(n))\)。然而，理想很丰满，现实很骨感，实际上，二叉搜索树并不总是能够保持平衡状态。最极端的情况就是，除了叶节点之外，每个节点只有一个子节点，如图所示：这种情况下二叉搜索树已经退化成一个链表，时间复杂度达到了\(O(n)\)，二叉搜索树在时间效率上的优势并没有发挥出来。要想解决这个问题，我们就要在每次动态操作（插入、删除）之后，采取某种措施，使二叉搜
阅读本文前，请确保您已经了解了二叉搜索树的相关内容（如定义、增删查改的方法以及效率等）。否则，建议您先学习二叉搜索树。本文假定您对二叉搜索树有了足够的了解。效率？众所周知，在平衡条件下，对二叉搜索树中的元素进行增删查改，时间效率为\(O(log(n))\)。然而，理想很丰满，现实很骨感，实际上，二叉搜索树并不总是能够保持平衡状态。最极端的情况就是，除了叶节点之外，每个节点只有一个子节点，如图所示：这种情况下二叉搜索树已经退化成一个链表，时间复杂度达到了\(O(n)\)，二叉搜索树在时间效率上的优势并没有发挥出来。要想解决这个问题，我们就要在每次动态操作（插入、删除）之后，采取某种措施，使二叉搜
⚠本笔记前置知识:二叉搜索(排序)树及其插入操作。本文主要围绕AVL树的平衡因子、纸上做题思路、失衡类型(LL/RR/LR/RL)、失衡调整方法、插入后回溯这几部分知识点展开。注:本笔记中的平衡二叉树规定所有左子树都小于其父节点，所有右子树都大于其父节点。本笔记中的平衡因子计算方法是左子树高度-右子树高度。目录简单介绍一下下平衡因子简述平衡二叉树的插入操作什么是失衡节点纸上快速做题思路程序中定义树节点失衡类型-LL型失衡举例调整方法-右旋转程序实现失衡类型-RR型失衡举例调整方法-左旋转程序实现失衡类型-LR型失衡举例调整方法-先左旋转再右旋转程序实现失衡类型-RL型失衡举例调整方法-先右旋转
⚠本笔记前置知识:二叉搜索(排序)树及其插入操作。本文主要围绕AVL树的平衡因子、纸上做题思路、失衡类型(LL/RR/LR/RL)、失衡调整方法、插入后回溯这几部分知识点展开。注:本笔记中的平衡二叉树规定所有左子树都小于其父节点，所有右子树都大于其父节点。本笔记中的平衡因子计算方法是左子树高度-右子树高度。目录简单介绍一下下平衡因子简述平衡二叉树的插入操作什么是失衡节点纸上快速做题思路程序中定义树节点失衡类型-LL型失衡举例调整方法-右旋转程序实现失衡类型-RR型失衡举例调整方法-左旋转程序实现失衡类型-LR型失衡举例调整方法-先左旋转再右旋转程序实现失衡类型-RL型失衡举例调整方法-先右旋转
基本概念结合二叉查找树的特性，以及AVL树自身的特性，AVL树具有以下特性：若任意结点的左子树不为空，则左子树上所有结点的值均小于它的根结点的值若任意结点的右子树不为空，则右子树上所有结点的值均大于或等于它的根结点的值任意结点的左、右子树也分别为二叉查找树任意结点的子树的高度差都小于等于1上述的前三项是二叉查找树的特性，第四项是AVL树自平衡的特性。实现原理为了保证二叉树的平衡，AVL树引入了监督机制，就是在树的某一部分的不平衡度超过一个阈值后触发相应的平衡操作，保证树的平衡度在可以接受的范围内。既然引入了监督机制，则必然需要一个监督指标，以此来判断是否需要进行平衡操作，这个监督指标被称为平衡
