1. AVL定义
AVL树是一种改进版的搜索二叉树。对于一般的搜索二叉树而言，如果数据恰好是按照从小到大的顺序或者从大到小的顺序插入的，那么搜索二叉树就对退化成链表，这个时候查找，插入和删除的时间都会上升到O(n)，而这对于海量数据而言，是我们无法忍受的。即使是一颗由完全随机的数据构造成的搜索二叉树，从统计角度去分析，在进行若甘次的插入和删除操作，这个搜索二叉树的高度也不能令人满意。这个时候大家就希望能有一种二叉树解决上述问题。这个时候就出现平衡搜索二叉树，它的基本原理就是在插入和删除的时候，根据情况进行调整，以降低二叉树的高度。平衡搜索二叉树典型代表就是AVL树和红黑树。
AVL树：任何一个节点的左子支高度与右子支高度之差的绝对值不超过1。需要我们注意的是，AVL树定义不是说从根节点到叶子节点的最短距离比最长短距离大1。
上图就是一颗AVL树，从根节点到叶子节点的最短距离是5，最长距离是9。
2. AVL插入操作
AVL树的插入操作首先会按照普通搜索二叉树的插入操作进行，当插入一个数据后，我们会沿着插入数据时所经过的的节点回溯，回溯的过程中会判回溯路径中的每个节点的左子支高度与右子支高度之差的绝对值是否超过1，如果超过1我们就进行调整，调整的目的是使得该节点满足AVL树的定义。调整的情况可以分为以下四旋转操作，旋转操作可以降低树的高度，同时不改变搜索二叉树的性质（即任何一个节点左子支中的全部节点小于该节点，右子支的全部节点大于该节点）。
2.1 情况1，节点D左子支比右子支高度大2，且插入的节点位于D的左孩子节点的左子支上
2.2 情况2，节点D右子支比左子支高度大2，且插入的节点位于节点D右孩子节点的右子支上
2.3 情况3，节点D左子支比右子支高度大2，且插入的节点位于节点D左孩子节点的右子支上
2.4 情况4, 节点D右子支比左子支高度大2，且插入的节点位于节点D右孩子节点的左子支上
延伸阅读
学习是年轻人改变自己的最好方式