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

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

    从平衡二叉树的英文名字，你也可以体会到，它是一种高度平衡的二叉排序树。那什么叫做高度平衡呢？意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor），那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

    看图8-7-2，为什么图1是平衡二叉树，而图2却不是呢？这里就是考查我们对平衡二叉树的定义的理解，它的前提首先是一棵二叉排序树，右上图的59比58大，却是58的左子树，这是不符合二叉排序树的定义的。图3不是平衡二叉树的原因就在于，结点58的左子树高度为3，而右子树为空，二者差大于了绝对值1，因此它也不是平衡的。而经过适当的调整后的图4，它就符合了定义，因此它是平衡二叉树。
    image.png
    距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。图8-7-3，当新插入结点37时，距离它最近的平衡因子绝对值超过1的结点是58（即它的左子树高度3减去右子树高度1），所以从58开始以下的子树为最小不平衡子树。
    image.png