1. 平衡二叉树（AVL树）

1.1 定义

平衡二叉树（Self-Balancing Binary Search Tree，Height-Balancd Binary Search Tree），是一种二叉排序树，其中每个节点的左子树和右子树的高度差不超过1.

有两名俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年共同发明了一种解决平衡二叉树的算法，因此平衡二叉树也被称为AVL树。下图是平衡二叉树的示例，其中左边的平衡二叉树还是一个满二叉树。

1.2 平衡因子BF（Balance Factor）

上图平衡二叉树中每个节点旁边还有一个数字，这个数字代表当前节点的深度。我们将二叉树上节点的左子树深度减去右子树深度的值称为该节点的平衡因子（Balance Factor）。比如上图中右边的平衡二叉树中，节点10的深度为3，其左子树深度为1，右子树深度为2，因此节点10的平衡因子为-1；类似地，节点8的BF值为0。

1.3 最小不平衡子树

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

比如下图中，左图中节点6的BF值为-1，如果此时插入8，如右图所示，那么节点6的BF值将变为-2，此时以6为根的子树就称为最小不平衡子树。

                             

2. 平衡二叉树的实现原理

2.1 左旋和右旋

• 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如下图所示。

• 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

2.2 平衡二叉树的实现

通过左旋右旋实现平衡二叉树的原理：

1. 插入新节点之后，如果最小不平衡子树根节点的平衡因子BF大于1时（说明此时该节点的左子树深度大于右子树深度），就右旋（向右旋转可以减少左子树深度，增加右子树深度）。
2. 插入新节点之后，如果最小不平衡子树根节点的平衡因子BF小于-1时（说明此时该节点的左子树深度小于右子树深度），就左旋（向左旋转可以减少右子树深度，增加左子树深度）。
3. 需要注意，如果插入节点后，最小不平衡子树的BF与它的子树的BF符号相反时，需要先对节点进行一次按照前两条规则的转向的相反方向旋转，使得符号相同。等到二者符号相同时，再正常判断进行左旋或者右旋操作。

如下例：当插入节点9之后，最小不平衡子树的根节点是7，其BF值为-2（如图（a）），按照上述1、2条的判断，应该进行左旋操作，但是执行完左旋操作之后，变成了图（b），并没有称为平衡二叉树。

此时就需要根据上述第三条原则，对其进行相反的旋转操作，如下图所示，先对10节点进行右旋，得到下图（b），然后再按照规则1、2进行旋转操作即可。

下面的视频演示了平衡二叉树的工作过程。

3. 平衡二叉树的特点

平衡二叉树必须满足“所有节点的左右子树高度差不超过1”。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，因此对树的旋转操作比较多，因此平衡二叉树适合用于插入与删除次数比较少，但查找多的情况。

后面会提到另一种局部平衡二叉树——红黑树，红黑树只保证左右子树中黑色节点的个数相等，同时由于不能存在连续两个红色节点，因此实际可以保证左右子树的深度在2倍关系内（即右子树没有红色节点，左子树每个黑色节点之间都有一个红色节点的情况），这种局部最优的二叉搜索树，即保证了二叉树的相对平衡，又不需要很大的开销去维持这种平衡（相对于平衡二叉树来说），因此广泛得到了应用，C++的STL中很多地方都使用到了红黑树，地图、集、hashmap等都用到了红黑树这种数据结构。

参考资料：《大话数据结构》程杰【著】， 数据结构可视化工具（可以生成平衡二叉树，红黑树等，功能强大，旧金山大学开发的）