文章目录1、AVL树(平衡二叉树)的定义1.1、平衡因子) Balance Factor，bf ) 1.2、学习计算各节点的高度和平衡因子1.3、平衡二叉树2、区分是否为AVL树的作用(3、AVL树的基本操作) 3.1、平衡因子右转具体步骤)3.1.2、右转动画演示)3.1.3、右转左右两次旋转步骤：3.2.2、左右旋转示例： 3.3、——插入右模左转： 3.3
1、AVL树(平衡二叉树)的定义
二叉树的全称叫平衡二叉搜索(排序)树，简称AVL树。 英文： Balancedbinarytree(BBT )，注：双叉搜索树(BST ) )。
AVL 什么意思 ？
AVL是大学教授G.M. Adelson-Velsky和E.M. Landis名称的缩写，是他们提出的平衡二叉树的概念，为了纪念他们，把平衡二叉树称为AVL树。
AVL树本质上是二叉树，但具有以下特征。
那就是天空树或者左右两个子的高度差绝对值在1以下，左右两个子的树也是平衡的二叉树。 在AVL树中，任何节点的两个子树的最大高度差为1，因此也称为平衡二叉树。
1.1、平衡因子(Balance Factor，简称bf )平衡因子) bf )节点左子树深度减去右子树深度。
即结点的平衡因子 = 左子树的高度 - 右子树的高度
在 AVL树中，所有节点的平衡因子都必须满足： -1=bf=1;
1.2、学习计算各节点高度和平衡因子的下图二叉树，计算各节点高度和平衡因子。 该图标如下所示：
从AVL树的定义中可以看出，上面的两个图都不是AVL树(平衡二叉树)。
1.3、区分是否平衡二叉树下面是平衡二叉树与非平衡二叉树的对比图：
2、AVL树的作用：我们知道，对于一般的二叉树搜索树(Binary Search Tree )，其期望高度(也就是在一棵平衡木的情况下)为log2n，其各操作的时间复杂度o ) log2n )也同时决定然而，在极端的情况下，例如，如果插入的序列是规则的，则两股搜索树退化为近似的链或链，其中，其操作的时间复杂度退化为线性，即o(n )。 通过随机化建立二叉树可以尽量避免这种情况，但经过多次操作后，在删除时，总是选择在要删除的节点后替换其本身，使得右侧节点的数量总是减少，树向左变重。 同时，树木失去了平衡，操作的时间复杂度提高。
例如，在空的双修树和AVL树中依次插入一组数据1、2、3、4、5和6，如下图所示。
由上图可知，即使是同一个节点，根据插入的方法不同，树的高度也不同。 特别是在带插入节点数量多且为正序的情况下，二叉树的高度为o[n]，但在AVL树中没有这种情况，树的高度总是O(lgN )。 高度越小，对树的一些基本操作的时间复杂度越小。 这是我们引入AVL树的原因。
3、AVL树的基本操作AVL树的操作基本上和二叉搜索树相同，这里我们关注的是两个变化很大的操作。 插入和删除。
我知道AVL树不仅是双股搜索树，还有其他性质。 如果是通常的双叉搜索树的插入方法，AVL树有可能失去平衡。 同样，删除时也有可能破坏树的平衡，所以要进行包括单圈和双圈在内的特殊处理
3.1、——左旋插入：
由上图可知，插入前的树是AVL树，但插入节点后，t左右部分树的高度差的绝对值不再为=1，AVL树失去平衡，将要旋转。
对节点t的3358www.Sina.com/的左结点（L）进行了插入元素的操作的情况称为左子树（L），应该右转。
左左型T代表平衡因子(bf )大于1的节点。
3.1.1、右转具体步骤： t右转成为L的右节点l的右节点y放置在t的左孩子身上，旋转中心为根节点t的左节点(l )。
这样就可以得到新的AVL树。 旋转过程的图示如下。
3.1.2、右转动画演示：
3.1.3、右转例：注：
在左情况下，在插入新数据1时，进行右转操作：
示例1：
插入节点2后，向右旋转。
3.2、插入——左右模左右旋转：
/p>由上图可知，我们在T结点的左结点的右子树上插入一个元素时，会使得根为T的树的左右子树高度差的绝对值不再 <= 1，如果只是进行简单的右旋，得到的树仍然是不平衡的。
在结点T的 左结点（L） 的 右子树（R） 上做了插入元素的操作，我们称这种情况为 左右型 ，我们应该进行左右旋。
注： T 表示 平衡因子(bf)大于1的节点。
3.2.1、左右旋的两次旋转步骤：第1次是左旋转：
L节点 左旋转，成为R的左节点R的左节点（Y1） 左旋转，成为 L的右节点（即左子节点左转）第2次是右旋转：
T节点 右旋转，成为R的右节点R的右节点（Y2）右旋转，成为T的左节点（即右子节点右转）旋转中心是根节点 T 的左节点（R）。
3.2.2、左右旋转的示例：一定要先把上面的左左型、左右型的旋转搞明白了， 下面的右右型、右左型的旋转就容易理解了。
3.3、插入——右右型的左旋：由上图可知：在插入之前树是一颗AVL树，而插入新结点之后，T的左右子树高度差的绝对值不再 <+ 1，此时AVL树的平衡性被破坏，我们要对其进行旋转。
在结点T的 右结点（R） 的 右子树（R） 上做了插入元素的操作，我们称这种情况为 右右型 ，我们应该进行左旋转。
注： T 表示 平衡因子(bf)大于1的节点。
3.3.1、左旋的具体步骤： T向左旋转成为R的左结点R的左节点Y放到T的右孩子上旋转中心是根节点T的右节点（R）。
这样即可得到一颗新的AVL树，旋转过程图如下：
3.3.2、动画演示： 3.3.3、左旋举例：示例1：
右右情况下，插入新数据时，左旋操作：
示例2：
由上图可知，我们在T结点的右结点的左子树上插入一个元素时，会使得根为T的树的左右子树高度差的绝对值不再 < 1，如果只是进行简单的左旋，得到的树仍然是不平衡的。
在结点T的 右结点（R） 的 左子树（L） 上做了插入元素的操作，我们称这种情况为 右左型 ，我们应该进行右左旋。
注： T 表示 平衡因子(bf)大于1的节点。
3.4.1、右左旋的两次旋转步骤：第1次是右旋转：
R 节点 右旋转，成为L的右节点L的右节点（Y2） 右旋转，成为R的左节点（即右子节点右转）第2次是左旋转：
T 节点 左旋转，成为L的左节点L的左节点（Y1）左旋转，成为T的右节点 （即左子节点左转）旋转中心是根节点 T 的右节点（L）。
3.4.2、右左旋的的示例 4、总结：在插入的过程中，会出现一下四种情况破坏AVL树的特性，我们可以采取如下相应的旋转。
插入位置状态操作在结点T的左结点（L）的 左子树（L） 上做了插入元素左左型右旋在结点T的左结点（L）的 右子树（R） 上做了插入元素左右型左右旋在结点T的右结点（R）的 右子树（R） 上做了插入元素右右型左旋在结点T的右结点（R）的 左子树（L） 上做了插入元素右左型右左旋注意：
T 表示 平衡因子(bf)大于1的节点。
不知道大家发现规律没，这个规则还是挺好记，下面来个图示：
5、参考文章https://www.cnblogs.com/idreamo/p/8308336.html
https://segmentfault.com/a/1190000006123188
https://blog.csdn.net/sjg_sjk/article/details/80332151
https://blog.csdn.net/FreeeLinux/article/details/52204851