为什么需要AVL树？
在二叉搜索树专题讲过二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，依据此序列构造的二叉搜索树为右斜树或者左斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。
例如假设有一组数[1, 2, 3, 4, 5, 6]如果我们以顺序添加到二叉搜索树中, 那么这颗二叉搜索树就会退化成一个链表。
二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。因此就有了AVL树。
AVL树也算是一种特殊的儿二叉搜索树，这里不讲AVL树的搜索与查找，因为都比较简单，主要讲的是AVL树的插入与删除，因为修改可能会导致重新平衡。
定义
它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1。AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。
4的左子树高度是0，右子树高度是0，高度差0
5的左子树高度1，右子树高度0，高度差1
8的左子树高度2，右子树高度1，高度差1
12的左子树高度3，右子树高度2，高度差1
18的左子树高度1，右子树高度0，高度差1
平衡因子
某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。当平衡因子的绝对值大于 1 时，就会触发树的重新平衡。
插入与删除
删除操作与二叉搜索树一样，只不过删除一个节点需要检查树是否平衡，如果平衡因子绝对值大于 1 时，就需要重新平衡，若平衡二叉树种某个结点的左子树和右子树的高度相差大于1，该树就是失衡了，该结点称为失衡点，先找到失衡点，接下来的操作就和插入时需要平衡一样了，所以这里只需要讲失衡点是怎么平衡的就可以。
会有四种情况导致失衡：
-
LL型
当新插入的结点为左子树的左子结点时，我们需要进行右旋操作来保证此部分子树继续处于平衡状态。
下面看一个比较复杂的情况:插入一个节点20
-
RR型
当新插入的结点为右子树的右子结点时，我们需要进行左旋操作来保证此部分子树继续处于平衡状态。
-
LR型
对于LR型的情况，要使用先对失衡点的左孩子进行左旋，然后再对失衡点进行右旋来解决。
复杂情况：
-
RL型
对于RL型的情况，要使用先对失衡点的右孩子进行右旋，然后再对失衡点进行左旋来解决。
复杂情况：
总结：
AVL是历史上出现的第一种平衡二叉树，它现在的很多应用都已经被红黑树代替。主要原因是它的平衡限制比较红黑树严格，在插入或者删除节点的时候很容易违反平衡限制条件，造成频繁的树结构调整和重新平衡。AVL限制对每个节点左子树和右子树的高度相差不超过一，所以它是高度平衡的二叉树，因而在进行查找的时候效率很高。而红黑树的平衡限制比AVL要弱，甚至左右子树的高度差等于2倍，所以红黑树的查找效率比AVL要低。但是，红黑树不需要频繁重平衡(得益于其宽松的限制条件)，所以在插入删除较频繁的环境中红黑树胜出。
