平衡二叉排序树查找是对普通二叉排序树查找的改进。其名称——AVL——取自其发明者，G. M. Adelson-Velsky 和 E. M. Landis.
在普通的二叉排序树查找中，查找的比较次数取决于目标点和根结点的距离，即目标点在树的第几层（从根结点算起）。层数越高，比较的次数越多。处于底层的点，查找效率最低，比较次数等于树的深度。
我们希望树的深度越小越好。
想象一棵树如果是左倾（左边深度大于右边深度）或者右倾的，在同样的结点数量下，倾斜幅度越大，树的深度就越大。极端情况，若所有的结点都只有左子树（或只有右子树），树就变成了一个没有分支的线性表。也就不具备了二叉排序树的查找优势。
因而，我们希望树是平衡的，即每个结点的左子树深度和右子树深度近似。
AVL 树的核心思想就是在每次二叉排序树的结构发生变化时，对其平衡性进行检查和调整。这一揽子检查和调整的方法颇为复杂，倒也成体系，为此，我们需要先引入一些概念。
-
平衡因子
结点的左子树深度减去右子树深度。
-
平衡树
若一棵树满足二叉平衡树的定义，且树中所有结点的平衡因子的绝对值都不大于 1，则这棵树是一棵平衡树。
-
最小不平衡子树
当我们向树中插入一个新结点后，距离新结点最近的平衡因子绝对值大于 1 的结点为根的子树为最小不平衡子树。
基本操作 #
我们调整平衡性的操作都是对最小不平衡子树进行的。
接下来我们来分析几种最小不平衡子树的场景及对应的操作。
右旋 #
如图所示，根结点的平衡因子为 2，其绝对值大于 1，并且是正值，因而这是一棵左倾（左高右低）的最小不平衡子树。我们需要对其做右旋处理。
右旋之后，树平衡了。
从上图来看，似乎右旋操作只是简单地将3号结点变成了2号结点的右孩子，2号结点成了新的根结点。
然而，上图只是一个极度简化的情况，实际情况可能比这复杂。
如上图，真实情况下，各个结点都是有子树的。图中圆形代表结点，三角形代表子树。
在 N 结点插入前，L 结点的平衡因子为 0，P 结点的平衡因子为 1，树是平衡的。（由于在 AVL 算法中，每次树结构发生变化，我们都会调整其平衡性，因而在新结点插入前，树必然是平衡的，我们无需考虑不平衡状态下的插入。）
N 结点插入后，L 结点的平衡因子变为 1，P 结点平衡因子变为 2，树失衡了。（实际上，P 结点上面可能还有父结点，但是在 AVL 算法中，我们只需要对最小不平衡子树做处理，因而对 P 的父结点及其以上的结点就无需关注了。）
可以看到，由于子树的存在，一个完整的右旋操作可以归纳为以下几个步骤：
- L 的右子树变为 P 的左子树。
- P 变为 L 的右子树。
- L 变为新的根。
- 调整平衡因子，P、L 的平衡因子均变为 0。
左旋 #
通过右旋的类比，我们可以容易地理解左旋操作。二者呈对称关系。
