Java数据结构与算法（树）——平衡二叉树（AVL树）
一、定义
平衡二叉查找树（Balanced Binary Sort Tree，BBST）简称平衡二叉树，是一种高度平衡的二叉树，由苏联数学家 Adele - Veliki 和 Landis 在 1962 年提出，故又命名为 AVL 树。
平衡二叉树的性质：首先是一种二叉查找树，并且其中每个节点的左子树和右子树的高度相差至多等于 1。
平衡因子BF（Balance Factor）——将二叉树上节点的左子树高度减去右子树高度的值称为平衡因子。平衡二叉树上，所有节点的平衡因子只可能是 -1，0，1。
最小不平衡子树——距离插入节点最近的，且平衡因子的绝对值大于 1 的节点为根的子树。以下图为例，左图是一棵平衡二叉树，当插入节点 1 时，节点 4 的 BF = 2（左子树高度 - 右子树高度 = 2 - 0 = 2），则以节点 4 为根节点的子树即为最小不平衡子树。
二、构建平衡二叉树及不平衡情况的处理方法
构建平衡二叉树的基本思想就是在构建二叉搜索树的过程中，每当插入一个新节点时，先检查是否因插入而破坏了树的平衡性，若是，则在保持二叉搜索树特性的前提下，调整最小不平衡子树中各节点之间的链接关系，进行相应的旋转调整，使之成为新的平衡二叉树。
注意：
不平衡的情况其实千变万化，比如左边深度为一万，右边深度为 0。但是我们考虑的是，在平衡二叉树中修改一个节点以后引起的不平衡，所以，左右子树的差的绝对值只能为 2。
旋转的情况：
（1）单旋：
最小不平衡子树的根节点的 BF 与它的子树的 BF 符号相同时，需要一次旋转。最小不平衡子树的根节点的 BF 大于 1 时，右旋；小于 -1 时，左旋。
（2）双旋：
最小不平衡子树的根节点的 BF 与它的子树的 BF 符号相反时，需要两次旋转，即先对子树进行一次旋转后使得 BF 符号相同之后，再反向旋转一次完成平衡。
1、左左（右旋）
插入节点 1 时，原平衡二叉树失衡，右旋过程图示如下：
最小不平衡子树的根节点 6 的 BF = 2，左子树根节点 4 的 BF = 1，同号且大于 1，右旋。具体操作：
- 当前根节点的左子树的右子树变成当前根节点的左子树（因为它满足大于左子树且小于根节点的要求）；
- 原根节点的左子树变成新的根节点；
- 原根节点变成新根节点的右子树。
2、右右（左旋）
插入节点 8 时，原平衡二叉树失衡，左旋过程图示如下：
最小不平衡子树的根节点 4 的 BF = -2，右子树根节点 6 的 BF = -1，同号且小于 -1，左旋。具体操作：
- 当前根节点的右子树的左子树变成当前根节点的右子树；
- 原根节点的右子树变成新的根节点；
- 原根节点变成新根节点的左子树。
3、双旋
如下图，插入节点 8 时，最小不平衡子树的根节点 9 的 BF = 2，左子树根节点 6 的 BF = -1，反号，仅一次单旋不能解决问题。
解决方法：
双旋：最小不平衡子树的左子树根节点 6 的 BF = -1，先左旋最小不平衡子树的左子树，再右旋最小不平衡子树。如下图所示：
先右旋再左旋的情况类似。