15二叉平衡树

# coding:uft-8

'''
平均查找长度ASL：
【 每一层的单个元素查找要多少次 * 这一层多少个元素 】所有层数求和/树的元素个数 = 平均查找长度
可以很明显的看出来，平衡二叉树的平均查找长度要比普通搜索二叉树小一些。

平衡因子BF：
BF = Hl - Hr 。左右子树高度差。  None 的高度 为 -1 ，一个结点的高度为0，两个结点高度为1。

平衡二叉树AV：
对于每一个结点来说  \BF\ <= 1 ,

完全二叉树的 h = log2（n）
高度为h 的平衡二叉树最少结点数：
n（h） = n（h-1）+n（h-2）+ 1
类似斐波那契数列。 但是 n1 与 F1 值不相等，且没有后面的 +1 ，
n（h） = F(h+2) - 1
数学推理，h = O(log2（n))
'''

'''
 平衡树的调整：
 插入破坏平衡的结点，重新构造树的结构，使之重新平衡。
 右子树下的右子树 下面插入 叫 RR 插入。
 RR 插入，需要 RR 旋转来重新平衡。
 RR 旋转 要将被破坏的结点的右子树拎上来，再将其其它结点位移或者不位移，保证其为搜索二叉树。

 LL 左左旋转同理，
 需要注意的是被破坏结点的位置别找错！

 如果一个插入后，同时出现两个结点被破坏，还是一次旋转，就能让两个结点都重新平衡。

 LR 插入 用LR旋转来 重新平衡。
 LR 旋转，将被破坏结点的左儿子的右儿子结点，拎上来，再将其其它结点位移或者不位移，保证其为搜索二叉树。

 RL 插入 和RL旋转 同理。
 需要注意的是被破坏结点的位置别找错！

 注意：
 旋转的 调整总是 在被破坏的结点往下的R L 三个结点 调整相对位置，其它结点适当移动保证搜索二叉树就行。

 有时候插入之后，树的结构不需要边，但是平衡因子一定会变。
'''