平衡二叉树
##定义 二叉树的左子树的深度和右子树的深度差不超过2，左子树和右子树本身也是平衡二叉树
##结点的高度 本文假设二叉树的叶子结点的高度为1，父结点的高度等于较高子结点的高度加1，也就是如下公式:
我们用h(left)和h(right)表示结点左右子树的高度，h(b_left)表示b的左孩子结点的高度，如果左孩子结点为NULL,则返回0，其他表示类似。
##结点的旋转
- 左旋转
- 右旋转
- 旋转的意义
从上面两种旋转的图可以看到，旋转的会使左右子树的高度发生变化，以左旋转为例，旋转之前左右子树的高度为：
旋转之后左右子树的高度为：
通过公式可以看出，左子树的高度至少提升1，右子树的高度至少降低1，所以左旋会使右子树的高度降低，相反， 右旋会使左子树的高度降低。明白了这个道理，后面对于平衡二叉树的增加和删除结点后的再平衡，就很好处理了，因为二叉树的再平衡实际上就是调整左右子树的高度而已。但是有一种情况我们必须避免，就是h(left)- h(right)==2的情况经过旋转之后出现h(right)- h(left)==2，这样就没有达到再平衡的效果，只是从一个极端到另一个极端，下面我们分析下什么时候会出现这种情况，假设加入某结点导致某个结点的左右子树高度差等于2了。未旋转之前如下：
整理可以得到：
①
旋转之后的情况如下：
整理可以得到：
②
如果h(b_left) > h(b_right),等式①如下：
- h(b_left) = h(a_left) + 1 代入等式②， 如下：
- max(h(a_left) + 1, h(a_left)) = h(b_right) + 1 ==>h(a_left) + 1 = h(b_right) + 1
最终得到
③
如果h(b_left) <= h(b_right) 会得到如下等式
- max(h(b_left), h(a_left)) =h(a_left) + 2
可以看到如果h(b_left) > h(a_left) ==> h(b_left) - h(a_left) =2 这样导致添加结点前二叉树就不是一个平衡二叉树了，所以这种情况忽略；如果h(a_left) > h(b_left) ==> h(a_left) - h(a_left) =2， 这种个情况更不存在，所以最终我们得到等式③，如果最初的条件是h(right) - h(left) == 2， 我们还会得到下面的等式
④
所以在h(a_left) = h(b_right) 或者 h(b_left) = h(a_right)时会出现我们提到的极端情况，请记住③④公式，下面我们介绍平衡二叉树增删结点时会解释这两个公式的意义。
##平衡二叉树增加结点 我们先从最简单的平衡二叉树开始，最简单的平衡二叉树有如下两种形式，他们在插入结点时，可能导致二叉树失衡。
导致二叉树失衡不外乎下面四种情况：
图中的a结点都是失衡结点，a、b两种情况可以通过旋转失衡结点来达到再平衡的目的，而c、d却不行，其根本原因就是它符合我们上面得出的③④两个公式，导致直接旋转失衡结点不能达到再平衡的目的，简单的办法就是通过把c、d转化为a、b两种形式，再进行处理，仔细观察可以看到，通过旋转b结点可以分别将c、d转换为a、b两种形式，这样再旋转失衡结点a就可以达到再平衡的目的。至于做何种旋转，通过上面的分析很容易就可以得到：
- a情况当然是右旋转（右旋转可以降低左子树的高度，增加右子树的高度）
- b情况当然是左旋转 （左旋转可以降低右子树的高度，增加左子树的高度）
- c当然是要转换为a情况，所以要先把b结点左旋转，然后再处理a情况
- d当然是要转换为b情况，所以要先把b结点右旋转，然后再处理b情况
通过上面的分析，可以得到下面简单的伪代码
sub_tree = taller_child(unbalance_node) //taller_child表示获取结点的较高孩子结点sub_sub_tree = taller_child(sub_tree)if (sub_tree == left(unbalance_node) && sub_sub_tree == left(sub_tree)) //a情况 left_rotate(unbalance_node)else if (sub_tree == right(unbalance_node) && sub_sub_tree == right(sub_tree)) //b情况 right_rotate(unbalance_node)else if (sub_tree == left(unbalance_node) && sub_sub_tree == right(sub_tree)) //c情况 right_rotate(sub_tree) left_rotate(unbalance_node)else //d情况 left_rotate(sub_tree) right_rotate(unbalance_node)
##平衡二叉树删除结点
删除结点首先是按照二叉树删除结点的方法删除指定结点，然后从删除结点的父节点寻找失衡结点 按照增加结点处理失衡结点的方法处就可以了。