平衡二叉树
——AVL，任意结点的平衡因子（左子树高度-右子树高度）的绝对值不超过一。
高度为h的最小平衡二叉树的结点数Nh？
Nh=Nh-1+Nh-2+1；已知Nh0=0；Nh1=1；
平衡二叉树的判断
利用递归的后序遍历过程
（1）判断左子树是一棵平衡二叉树
（2）判断右子树是一颗平衡二叉树
（3）判断以该结点为根的二叉树为平衡二叉树
判断条件
若左右子树均为平衡二叉树，且左子树与右子树高度差的绝对值小于等于1，则平衡。
平衡二叉树的插入
先按二叉排序树的标准插入元素再调整为平衡二叉树
每次调整的是最小不平衡子树——非常重要
LL平衡旋转（右单旋转）
原因：在结点A的左孩子的左子树上插入新的结点
调整方法：右旋操作：将A的左孩子B代替A，将A结点作为B的右子树根节点，而B的原有的右子树作为A的左子树。
RR平衡旋转（左单旋转）
原因：在结点A的右孩子的右子树上插入新的结点
调整方法：左旋操作：将A的右孩子B代替A，将A结点作为B的左子树根节点，而B的原有的左子树作为A的右子树。
LR平衡旋转（先左后右双旋转）
原因：在结点A的左孩子的右子树上插入新的结点
调整方法：先左旋后右旋操作：（1）将A的左孩子B的右孩子结点C代替B，将B作为C的左子树的根节点，而C的原有的左子树变为B的右子树；（2）然后再将C结点向上代替A的位置，将A作为C的右子树的根节点，而C的原有的右子树变为A的左子树。
RL平衡旋转（先右后左左双旋转）
原因：再结点A的右孩子的左子树上插入新的结点
调整方法：先右旋后左旋操作：（1）将A的右孩子B的左孩子结点C代替B，将B作为C的右子树的根节点，而C的原有的右子树变为B的左子树；（2）然后再将C结点向上代替A的位置，将A作为C的左子树的根节点，而C原有的左子树变为A的右子树。
