平衡二叉树
1.特点
具有以下性质：
- 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
- 这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
- 但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
2.不平衡的情况
平衡二叉树不平衡的情形：
把需要重新平衡的结点叫做α，由于任意两个节点最多只有两个儿子，因此高度不平衡时，α节点的两颗子树的高度相差2。
容易看出，这种不平衡可能出现在下面4中情况中：
- 对α的左儿子的左子树进行一次插入
- 对α的左儿子的右子树进行一次插入
- 对α的右儿子的左子树进行一次插入
- 对α的右儿子的右子树进行一次插入
情形1和情形4是关于α的镜像对称，情形2和情形3也是关于α的镜像对称，因此理论上看只有两种情况，但编程的角度看还是四种情形。
3.调整
第一种情况是插入发生在“外边”的情形（左左或右右--1、4），该情况可以通过一次单旋转完成调整；
第二种情况是插入发生在“内部”的情形（左右或右左--2、3），这种情况比较复杂，需要通过双旋转来调整。
3.1 单旋转
上图是左左的情况，节点6不满足平衡性，它的左子树3比右子树7深两层，3子树中更深的是3的左子树1，因此属于左左情况。
为了恢复平衡，我们把3上移一层，并把7下移一层，但此时实际已经超出了AVL树的性质要求。
为此，重新安排结点以形成一颗等价的树。为使树恢复平衡，我们把3变成这棵树的根节点，因为6大于3，把6置于3的右子树上，而原本在3右子树的4大于3，小于6，就把4置于6的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。
这种情况称为单旋转。
3.2 双旋转
对于左右和右左两种情况，单旋转不能解决问题，要经过两次旋转。
对于上图情况，为使树恢复平衡，我们需要进行两步：
- 把2作为根，进行一次右右旋转，旋转之后就变成了左左情况；
- 再进行一次左左旋转，最后得到了一棵以4为根的平衡二叉树。
4. 删除一个节点
删除分为以下几种情况：
首先在整个二叉树中搜索要删除的结点，如果没搜索到直接返回不作处理，否则执行以下操作：
1.要删除的节点是当前根节点T。
如果左右子树都非空。在高度较大的子树中实施删除操作。
分两种情况：
(1)、左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前根节点，然后删除左子树中元素值最大的那个节点。
(1)、左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。
如果左右子树中有一个为空，那么直接用那个非空子树或者是NULL替换当前根节点即可。
2、要删除的节点元素值小于当前根节点T值，在左子树中进行删除。
递归调用，在左子树中实施删除。
这个是需要判断当前根节点是否仍然满足平衡条件，
如果满足平衡条件，只需要更新当前根节点T的高度信息。
否则，需要进行旋转调整：
如果T的左子节点的左子树的高度大于T的左子节点的右子树的高度，进行相应的单旋转。否则进行双旋转。
3、要删除的节点元素值大于当前根节点T值，在右子树中进行删除。