介绍：
在计算机科学中，AVL树是最先发明的自平衡二叉查找树。
在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。
查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。
特点：
AVL树本质上还是一棵二叉搜索树，它的特点是：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
节点数：
高度为 h 的 AVL 树，节点数 N 最多2^h − 1； 最少N(h)=N(h− 1) +N(h− 2) + 1。
最少节点数n 如以斐波那契数列可以用数学归纳法证明：
即:
N(0) = 0 (表示 AVL Tree 高度为0的节点总数）
N(1) = 1 （表示 AVL Tree 高度为1的节点总数）
N(2) = 2 （表示 AVL Tree 高度为2的节点总数）
N(h)=N(h− 1) +N(h− 2) + 1 （表示 AVL Tree 高度为h的节点总数）
节点的平衡因子是它的左子树的高度减去它的右子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
操作：
假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先结点），