目錄
一、什麼是平衡二叉樹
二、平衡二叉樹的高度能達到$log_2n$嗎？
三、平衡二叉樹的調整
3.1 右單旋
3.2 左單旋
3.3 左-右雙旋
3.4 右-左雙旋
3.5 完善平衡二叉樹
例：搜尋樹結點不同插入次序，将導緻不同的深度和平均查找長度ASL
上圖為按照自然月份序列建構的搜尋樹，它的ASL為\((1+2*2+3*3+4*3+5*2+6*1)/12=3.5\)
上圖為按照平衡二叉樹建構的搜尋樹，它的ASL為\(3.0\)
上圖為按照月份字元串大小順序建構的搜尋樹，他的ASL為\(6.5\)
“平衡因子”（Balance Factor，簡稱BF）： \(BF(T) = h_L - h_R\)，其中\(h_L\)和\(h_R\)分别為T的左、右子樹的高度。
平衡二叉樹（Balanced Binary Tree）（AVL樹）：空樹，或者任一結點左、右子樹高度差的絕對值不超過1，即\(BF(T)|\leq{1}\)
二、平衡二叉樹的高度能達到\(log_2n\)嗎？
如下圖所示為完全二叉樹的高度計算：
設\(n_h\)為高度為h的平衡二叉樹的最少結點數。結點數最少時，我們可以得知左（右）子樹最多比右（左）子樹多一個結點：
上述公式類似于斐波那契序列： \(F_0=1，F_1=1，F_i=F_{i-1}+F_{i-2}\quad{f}or\quad{i}>1\)，即我們可以通過斐波那契的規律，來探讨平衡二叉樹的高度計算。
設\(n_h\)是高度為h的平衡二叉樹的最小結點數，有如下推導：
按照上圖的推導，我們可以得出：給定結點數為n的AVL樹的最大高度為\(O(log_2n)\)
不平衡的“發現者”是Mar，“麻煩結點”Nov在發現者右子樹的右邊，因而叫做RR插入，需要RR旋轉（右單旋）
“發現者”是Mar，“麻煩結點”Apr在發現者左子樹的左邊，因而叫LL插入，需要LL旋轉（左單旋）
“發現者”是May，“麻煩結點”Jan在左子樹的右邊，因而叫LR插入，需要LR旋轉
“發現者”是Aug，“麻煩結點”是Feb在右子樹的左邊，因而叫RL插入，需要LR旋轉
接下來我們使用上述所說的四種方法，完善我們的平衡二叉樹。
調整後的結果為：