平衡二叉树(AVL树)
平衡二叉树的由来：前面我们提过使用树的结构来进行查找操作会很方便，但是当树只有左子树or只有右子树时，其查找效率为O(n),离O(log n) 差的太多。所以我们要尽量避免这种情况。而采取的措施就是使二叉树的左子树和右子树尽量相等(平衡)，这就是所谓的平衡二叉树。
搜索树结点的不同插入次序，将导致不同的深度和平均查找长度ASL
平衡二叉树(AVL树)的定义
"平衡因子(Balance Factor,简称BF)"：BF(T) = H(L) - H(R),其中H(L) 和H(R)分别为T的左、右子树的高度。
平衡二叉树：又称为AVL树：原因是发明该树的科学家名字的首字母
平衡二叉树(Balanced Binary Tree)(AVL树)：空树 or 任一结点左、右子树高度差的绝对值不超过1，即|BF(T)| <= 1
问题：平衡二叉树的高度能达到log n吗？
设N(h)高度为h的平衡二叉树的最少结点数。结点数最少时：
平衡二叉树
AVL树的高度可以为O(log n)
平衡二叉树的调整
平衡二叉树是搜索树，所以无论怎么调整，最后都要保证是搜索树。
发现者and破坏者的解释
平衡树调整的几种模式：
- RR插入(RR旋转)(右单旋)：不平衡的"发现者"，"破坏结点"在发现者右子树的右边
- LL插入(LL旋转)(左单旋)："破坏结点"在发现者左子树的左边
- LR插入(LR旋转)："破坏结点"在左子树的右边
- RL插入(RL旋转)："破坏结点"在右子树的左边
注意：有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子
