平衡二叉樹(AVL樹)
平衡二叉樹的由來：前面我們提過使用樹的結(jié)構(gòu)來進行查找操作會很方便川梅，但是當樹只有左子樹or只有右子樹時，其查找效率為O(n),離O(log n) 差的太多掏导。所以我們要盡量避免這種情況。而采取的措施就是使二叉樹的左子樹和右子樹盡量相等(平衡)藕甩，這就是所謂的平衡二叉樹土匀。
搜索樹結(jié)點的不同插入次序，將導(dǎo)致不同的深度和平均查找長度ASL
平衡二叉樹(AVL樹)的定義
"平衡因子(Balance Factor,簡稱BF)"：BF(T) = H(L) - H(R),其中H(L) 和H(R)分別為T的左舱殿、右子樹的高度奥裸。
平衡二叉樹：又稱為AVL樹：原因是發(fā)明該樹的科學(xué)家名字的首字母
平衡二叉樹(Balanced Binary Tree)(AVL樹)：空樹 or 任一結(jié)點左、右子樹高度差的絕對值不超過1沪袭，即|BF(T)| <= 1
問題：平衡二叉樹的高度能達到log n嗎湾宙？
設(shè)N(h)高度為h的平衡二叉樹的最少結(jié)點數(shù)。結(jié)點數(shù)最少時：
平衡二叉樹
AVL樹的高度可以為O(log n)
平衡二叉樹的調(diào)整
平衡二叉樹是搜索樹冈绊，所以無論怎么調(diào)整侠鳄，最后都要保證是搜索樹。
發(fā)現(xiàn)者and破壞者的解釋
平衡樹調(diào)整的幾種模式：
- RR插入(RR旋轉(zhuǎn))(右單旋)：不平衡的"發(fā)現(xiàn)者"死宣，"破壞結(jié)點"在發(fā)現(xiàn)者右子樹的右邊
- LL插入(LL旋轉(zhuǎn))(左單旋)："破壞結(jié)點"在發(fā)現(xiàn)者左子樹的左邊
- LR插入(LR旋轉(zhuǎn))："破壞結(jié)點"在左子樹的右邊
- RL插入(RL旋轉(zhuǎn))："破壞結(jié)點"在右子樹的左邊
注意：有時候插入元素即便不需要調(diào)整結(jié)構(gòu)伟恶，也可能需要重新計算一些平衡因子
