查找算法（二）平衡二叉树AVL
查找算法（二）
对于二叉查找树BST可能出现的完全偏斜的情况，平衡二叉树解决了这个问题，不仅保持了BST的中序遍历有序的特性，同时因为左右子树的高度差不大于1，这样它的深度就是和是同数量级的（n是结点的数量），从而平均查找长度也就是数量级的了
平衡二叉树AVL
满足下面条件的就是平衡二叉树：
- 首先是一棵二叉查找树，可以是空树
- 左子树和右子树的高度之差的绝对值不超过1
- 左子树和右子树递归满足上述条件
失去平衡调整的四种情况
这里定平衡因子为：左子树深度 - 右子树深度——所以当平衡因子不为 1 0 -1这三个值的时候就需要调整了
这里的四种调整并不是旋转树的方向，指的时插入到什么位置导致树不平衡，这要注意
-
LL调整
某个结点在其左子树的左子树添加时不平衡
-
LR调整
某个结点在其左子树的右子树添加时不平衡
-
RR调整
某个结点在其右子树的右子树添加时不平衡
-
RL调整
某个结点在其右子树的左子树添加时不平衡
时间复杂度的分析
平衡二叉树的高度决定了插入、查找、删除的事件复杂度，与是同一数量级的。