平衡二叉树(AVL树)

平衡二叉树(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破坏者的解释

平衡树调整的几种模式：

1. RR插入(RR旋转)(右单旋)：不平衡的"发现者"，"破坏结点"在发现者右子树的右边
2. LL插入(LL旋转)(左单旋)："破坏结点"在发现者左子树的左边
3. LR插入(LR旋转)："破坏结点"在左子树的右边
4. RL插入(RL旋转)："破坏结点"在右子树的左边

注意：有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子