平衡二叉树（Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个节点的左子树和右子树的高差至多等于1。

    有两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年共同发明一种解决平衡二叉树的算法，所以也称平衡二叉树为AVL树。

    平衡二叉树，是一种高度平衡的二叉排序树。要么是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor）。则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子绝对值大于1，则该二叉树就是不平衡的。

    距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称之为最小不平衡子树。

8.7.1 平衡二叉树实现原理

    平衡二叉树构建的基本思想是：在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

    假设有一个数组a[10]={3,2,1,4,5,6,7,10,9,8}需要构建二叉排序树。在不考虑平衡情况下，会构建成如下图1的样子；但这棵二叉树高度为8，对于查找很不利（二叉排序树的查找时间复杂度与深度与有）。希望能构建成如图2的样子，高度只有4。

    对于数组a[10]的前两位3和2，正常构建，到第3个数1时，发现根结点的平衡因子变成了2（左深度2-右深度0），此时整棵树都成了最小不平衡子树，因此需要调整。如下图1。因为平衡因子BF值为正，因此将整个树进行右旋（顺时针旋转），此时结点2成了根结点，3成了2的右孩子，这样三个结点的BF值均为0，非常平衡。

    然后再增加结点4，平衡因子没有发生改变，如图3。增加结点5时，结点3的BF值为-2，说明要旋转了。由于BF是负值，所以对这棵最小平衡子树进行左旋（逆时针旋转），如图4.

    继续增加结点6时，发现根结点的BF值变成了-2，如图6。所以左旋转，注意此时本来结点3是4的左孩子，但由于旋转后需要满足二叉排序树特性，因此它成了结点2的右孩子，如图7，增加结点7，同样要左旋，如图8和9。

    当增加结点10时，结构无变化，如图10。再增加结点9，此时结点7的BF变成了-2，理论上只需要旋转最小不平衡子树7、9、10即可，但如果左旋转后结点9就成了10的右孩子，不符合二叉排序树的特性（左子孙比根结点小，右子孙比根结点大）。不能简单的右旋转。

    根本原因在于结点7的BF是-2，而结点10的BF是1。也即一正一负，符号不统一，而之前的旋转无论转旋右旋，根与子结点的平衡因子符号都是相同的。

    不统一，就先旋转为统一。于是先对结点9和结点10进行右旋，使得结点10成为9的右子树，结点9的BF为-1，此时就与结点7的BF值符号统一了。如图12所示。

    这样再以结点7为最小不平衡子树进行左旋，得到图13，接着插入8，情况下刚才类似，结点6的BF是-2，而它的右孩子9的BF是1，如图14，因此以9为根结点，进行右旋，得到图15，此时结点6和结点7的符号都是负，于是以6为根结点左旋，最终得到平衡二叉树。