一、概念
平衡二叉树
（Self-Balancing Banary Search Tree 或者 Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。
AVL 树
两位俄罗斯数学家G.M.Adelson-Velskii 和E.M.Landis 在1962年共同发明一种解决平衡二叉树的算法，所以不少资料这样的平衡二叉树为 AVL树。可以看出它是一种高度平衡的二叉排序树。
平衡因子
我们将二叉树上左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor）。
最小不平衡子树
当向一棵树插入结点，距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。
举例如下：
符合平衡二叉树
不符合的如下：
- 第一张图是因为并非升序。
- 第二张图：虽然其他姐都都比较平衡，但是结点6的左子树深度3，右子树0，差别为3，不符合每一个结点的左子树和右子树高度差至多等于1。
最小不平衡树示意图，插入新结点5后，树原本的平衡被打破，结点4 的左右子树深度为，左3 - 右 1 = 2，大于1。称为了非平衡结点。此时从结点5开始以下的子树为最小不平衡子树。
