AVL树是最先发明的自平衡二叉查找树。在AVL树中任何结点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）
在这个网站可以看到AVL树的可视化：AVL Tree Visualization
【1】概念介绍
二叉查找树只限制了结点值大小：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
那么在极端情况下，可能出现如下情况，此时查找的时间复杂度从O(logN)退化为O(N)
我们理想的情况是如下所示，只需要O(logN)就可以查找到结点(N是总结点个数)。
这就是为什么引入AVL树。相对于二叉查找树，其维护了平衡：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
总结其特点如下：
本身首先是一棵二叉搜索树(二叉查找树)。
左右子树也是AVL树
带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1
如果它有n个结点，其高度可保持在logn ，搜索时间复杂度O(logn)
AVL树好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
树高的证明
设 fn为高度为 n 的 AVL 树所包含的最少结点数，则有:
显然 fn 是一个斐波那契数列。众所周知，斐波那契数列是以指数的速度增长的，因此 AVL 树的高度为O(logn)
【2】插入时四种旋转操作
为了位置平衡，那么AVL树在插入和删除时需要重新调整结构，这里可能会发生旋转动作。
这里先引入一个概念：平衡因子。
平衡因子：将二叉树上结点的左子树高度减去右子树高度的值称为该结点的平衡因子BF(Balance Factor)。
对于平衡二叉树，BF的取值范围为[-1,1]。如果发现某个结点的BF值不在此范围，则需要对树进行调整。
如下图所示，平衡因子我们这里取了绝对值。
如果这时插入结点5，那么就会触发左旋，根结点平衡因子并未发生变化。
插入一个结点，只会影响根结点到插入结点的父结点上这条路径上所有结点的平衡因子。
二叉树的平衡化有两大基础操作： 左旋和右旋。左旋，即是逆时针旋转；右旋，即是顺时针旋转。这种旋转在整个平衡化过程中可能进行一次或多次，这两种操作都是从失去平衡的最小子树根结点开始的(即离插入结点最近且平衡因子超过1的祖结点)。
下面我们总结四种场景的旋转。
① 左旋(RR调整)
这个如前面所示，当再次插入结点5时，就会触发左旋操作。总结就是插入了较高右子树的右侧结点。
如果插入一个结点后，插入结点的父结点的平衡因子变成了0，则说明插入结点后树的高度没有发生变化，则只影响了父结点的平衡因子。
如果继续插入结点6呢？这时会导致父结点(2)的平衡因子变成2 ，那么就会触发父结点的左旋，使结点4变成新的父结点。
如果插入一个结点后，该结点的父结点的平衡因子的绝对值大于等于1，在向上更新过程中如果某一个结点的平衡因子变成了0则停止更新，最坏情况下一直要更新到根结点。
② 右旋(LL调整)
与RR调整相对的是，LL调整也就是在较高左侧子树插入左侧结点。
如下所示，插入结点2，那么会导致父结点4的平衡因子变为2，这时需要进行右旋。右旋之后根结点5的平衡因子变为了1(无需调整)，调整结束。
如果继续插入结点1呢？按照平衡二叉树的规则，这时会插入到结点2的左侧。这时会打破根结点的平衡因子，发生根结点的变化。
- 调整原先根结点(5)的左侧结点(3)为新的根结点(3)
- 旧的根结点作为新的根结点的右子结点
- 原先左侧结点(3)的右侧结点(4)作为旧的根结点(5)的左侧结点(4)
总结来看，根结点进行变化的前提条件是左子树(右子树)没有办法经过调整维持原先的树高度。比如左子树(右子树)已经是一棵满二叉树(或者是不存在没有兄弟结点的叶子结点)，那么此时再在左子树(右子树)插入新的结点，只能通过修改根结点来调整平衡。
③ 先左旋后右旋(LR调整)
也就是插入较高左侧子树的右孩子结点。
如下图所示，这里首先对34进行左旋调整4为3的父结点，然后对整体进行右旋，提升4为新的根结点，原先的根结点5降为4的右结点。
④ 先右旋再左旋(RL调整)
也就是插入较高右侧子树的左侧结点。
如下图所示，这里首先对67进行右旋调整6为7的父结点，然后对整体进行左旋，提升6为新的根结点，原先的根结点5降为6的左结点。
关于插入的总结
AVL树也是一颗二叉搜索树，因此它在插入数据时也需要先找到要插入的位置然后再将结点插入。不同的是，AVL树插入结点后需要对结点的平衡因子进行调整(自底向上折回调整)，如果插入结点后平衡因子的绝对值大于1,则还需要对该树进行旋转，旋转成为一颗高度平衡的二叉搜索树。
【3】删除操作
首先这里我们回顾一下二叉查找树的前驱和后继结点。
① 前驱结点
某结点的前驱结点就是小于该结点中的最大结点。
主要有③个场景：
① 如果某个结点存在左子结点，那么左子结点（子树）下中的最大 key 值结点即是前驱。比如结点4的前驱是2。
② 如果某个结点没有左子结点，而且如果该结点为其父结点的右子结点，那么该结点的父结点即为该结点的前驱。比如结点3的前驱是2.
- ③ 如果某个结点没有左子结点，而且如果该结点为其父结点的左子结点，那么就往顶端寻找，直到找到第一个结点A并且A是其父结点的右子结点，结点A的父结点就是要找的前驱。
比如结点7的前驱是6
② 后继结点
某结点的后继就是大于该结点的所有结点中最小的那个结点。
仍旧以下图为例：
同样有3种场景
① 如果某个结点存在右子结点，那么右子结点（子树）下中的最小 key 值结点即是后继。比如结点6的后继是7
② 如果某个结点没有右子结点，而且如果该结点为其父结点的左子结点，那么该结点的父结点即为该结点的后继。比如结点7的后继是8
③ 如果某个结点没有右子结点，而且如果该结点为其父结点的右子结点，那么就往顶端寻找，直到找到第一个结点A且A是其父结点的左子结点，A的父结点就是要找的后继。比如3的后继是4，结点A是2.
③ AVL的结点删除
AVL的结点删除和 BST 类似，将结点与后继交换后再删除。删除会导致树高以及平衡因子变化，这时需要沿着被删除结点到根的路径来调整这种变化。如何调整变化？其实就是类似插入时的“旋转操作”。
如下所示，我们删除结点4：
那么第一步则是将结点4与后继(结点5)交换，然后删除结点4：
这时可以看到左侧结点5的平衡因子是2，打破了AVL树的性质，典型的LR结构，那么我们进行先左旋再右旋的调整。
整体来看，AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。
