詳解什麼是平衡二叉樹（AVL）（修訂補充版）
詳解什麼是平衡二叉樹（AVL）（修訂補充版）
前言
Wiki:在 電腦科學 中， AVL樹 是最早被髮明的 自平衡二叉查詢樹 。在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，因此它也被稱為 高度平衡樹 。查詢、插入和刪除在平均和最壞情況下的 時間複雜度 都是 O(logn）。增加和刪除元素的操作則可能需要藉由一次或多次 樹旋轉 ，以實現樹的重新平衡。AVL 樹得名於它的發明者 G. M. Adelson-Velsky 和 Evgenii Landis ，他們在1962年的論文《An algorithm for the organization of information》中公開了這一資料結構。
1 為什麼要有平衡二叉樹
二叉搜尋樹一定程度上可以提高搜尋效率，但是當原序列有序時，例如序列 A = {1，2，3，4，5，6}，構造二叉搜尋樹如圖 1.1。依據此序列構造的二叉搜尋樹為右斜樹，同時二叉樹退化成單鏈表，搜尋效率降低為 O(n)。
圖 1.1
在此二叉搜尋樹中查詢元素 6 需要查詢 6 次。
二叉搜尋樹的查詢效率取決於樹的高度，因此保持樹的高度最小，即可保證樹的查詢效率。同樣的序列 A，將其改為圖 1.2 的方式儲存，查詢元素 6 時只需比較 3 次，查詢效率提升一倍。
圖 1.2
可以看出當節點數目一定，保持樹的左右兩端保持平衡，樹的查詢效率最高。
這種左右子樹的高度相差不超過 1 的樹為平衡二叉樹。
2. 定義
平衡二叉查詢樹：簡稱平衡二叉樹。由前蘇聯的數學家 A delse- V elskil 和 L andis 在 1962 年提出的高度平衡的二叉樹，根據科學家的英文名也稱為 AVL 樹。它具有如下幾個性質：
- 可以是空樹。
- 假如不是空樹，任何一個節點的左子樹與右子樹都是平衡二叉樹，並且高度之差的絕對值不超過 1。
平衡之意，如天平，即兩邊的分量大約相同。
例如圖 2.1 不是平衡二叉樹，因為節點 60 的左子樹不是平衡二叉樹。
圖 2.1
圖 2.2 也不是平衡二叉樹，因為雖然任何一個節點的左子樹與右子樹都是平衡二叉樹，但高度之差已經超過 1 。
圖 2.2
圖 2.3 是平衡二叉樹。
圖 2.3
3. 平衡因子
定義：某節點的左子樹與右子樹的高度(深度)差即為該節點的平衡因子（BF,Balance Factor），平衡二叉樹中不存在平衡因子大於 1 的節點。在一棵平衡二叉樹中，節點的平衡因子只能取 0 、1 或者 -1 ，分別對應著左右子樹等高，左子樹比較高，右子樹比較高。
圖 3.1 
圖 3.2 
圖 3.3
4. 節點結構
定義平衡二叉樹的節點結構：
typedef struct AVLNode *Tree;
typedef int ElementType;
struct AVLNode{
int depth; //深度，這裡計算每個節點的深度，通過深度的比較可得出是否平衡
Tree parent; //該節點的父節點
ElementType val; //節點值
Tree lchild;
Tree rchild;
AVLNode(int val=0) {
parent = NULL;
depth = 0;
lchild = rchild = NULL;
this->val=val;
}
};
5. AVL樹插入時的失衡與調整
圖 5.1 是一顆平衡二叉樹
圖 5.1
在此平衡二叉樹插入節點 99 ，樹結構變為：
動圖 5.2
在動圖 5.2 中，節點 66 的左子樹高度為 1，右子樹高度為 3，此時平衡因子為 -2，樹失去平衡。
在動圖 5.2 中，以節點 66 為父節點的那顆樹就稱為 最小失衡子樹 。
最小失衡子樹：在新插入的節點向上查詢，以第一個平衡因子的 絕對值 超過 1 的節點為根的子樹稱為最小不平衡子樹。也就是說，一棵失衡的樹，是有可能有多棵子樹同時失衡的。而這個時候，我們只要調整最小的不平衡子樹，就能夠將不平衡的樹調整為平衡的樹。
平衡二叉樹的失衡調整主要是通過旋轉最小失衡子樹來實現的。根據旋轉的方向有兩種處理方式， 左旋 與 右旋 。
旋轉的目的就是減少高度，通過降低整棵樹的高度來平衡。哪邊的樹高，就把那邊的樹向上旋轉。
5.1 左旋
圖 5.1.1
以圖 5.1.1 為例，加入新節點 99 後， 節點 66 的左子樹高度為 1，右子樹高度為 3，此時平衡因子為 -2。為保證樹的平衡，此時需要對節點 66 做出旋轉，因為右子樹高度高於左子樹，對節點進行左旋操作，流程如下：
（1）節點的右孩子替代此節點位置
（2）右孩子的左子樹變為該節點的右子樹
（3）節點本身變為右孩子的左子樹
整個操作流程如動圖 5.1.2 所示。
動圖 5.1.2
- 節點的右孩子替代此節點位置 —— 節點 66 的右孩子是節點 77 ，將節點 77 代替節點 66 的位置
- 右孩子的左子樹變為該節點的右子樹 —— 節點 77 的左子樹為節點 75，將節點 75 挪到節點 66 的右子樹位置
- 節點本身變為右孩子的左子樹 —— 節點 66 變為了節點 77 的左子樹
5.2 右旋
右旋操作與左旋類似，操作流程為：
（1）節點的左孩子代表此節點
（2）節點的左孩子的右子樹變為節點的左子樹
（3）將此節點作為左孩子節點的右子樹。
動圖 5.2.1
6. AVL樹的四種插入節點方式
假設一顆 AVL 樹的某個節點為 A，有四種操作會使 A 的左右子樹高度差大於 1，從而破壞了原有 AVL 樹的平衡性。平衡二叉樹插入節點的情況分為以下四種：
圖 6.0
具體分析如下：
6.1 A的左孩子的左子樹插入節點(LL)
只需要執行一次右旋即可。
動圖 6.1
實現程式碼如下：
//LL型調整函式
//返回:新父節點
Tree LL_rotate(Tree node){
//node為離操作節點最近的失衡的節點
Tree parent=NULL,son;
//獲取失衡節點的父節點
parent=node->parent;
//獲取失衡節點的左孩子
son=node->lchild;
//設定son節點右孩子的父指標
if (son->rchild!=NULL)son->rchild->parent=node;
//失衡節點的左孩子變更為son的右孩子
node->lchild=son->rchild;
//更新失衡節點的高度資訊
update_depth(node);
//失衡節點變成son的右孩子
son->rchild=node;
//設定son的父節點為原失衡節點的父節點
son->parent=parent;
//如果失衡節點不是根節點，則開始更新父節點
if (parent!=NULL){
//如果父節點的左孩子是失衡節點，指向現在更新後的新孩子son
if (parent->lchild==node){
parent->lchild=son;
}else{
//父節點的右孩子是失衡節點
parent->rchild=son;
}
}
//設定失衡節點的父親
node->parent=son;
//更新son節點的高度資訊
update_depth(son);
return son;
}
6.2 A的右孩子的右子樹插入節點(RR)
只需要執行一次左旋即可。
動圖 6.2
實現程式碼如下：
//RR型調整函式
//返回新父節點
Tree RR_rotate(Tree node){
//node為離操作節點最近的失衡的節點
Tree parent=NULL,son;
//獲取失衡節點的父節點
parent=node->parent;
//獲取失衡節點的右孩子
son=node->rchild;
//設定son節點左孩子的父指標
if (son->lchild!=NULL){
son->lchild->parent=node;
}
//失衡節點的右孩子變更為son的左孩子
node->rchild=son->lchild;
//更新失衡節點的高度資訊
update_depth(node);
//失衡節點變成son的左孩子
son->lchild=node;
//設定son的父節點為原失衡節點的父節點
son->parent=parent;
//如果失衡節點不是根節點，則開始更新父節點
if (parent!=NULL){
//如果父節點的左孩子是失衡節點，指向現在更新後的新孩子son
if (parent->lchild==node){
parent->lchild=son;
}else{
//父節點的右孩子是失衡節點
parent->rchild=son;
}
}
//設定失衡節點的父親
node->parent=son;
//更新son節點的高度資訊
update_depth(son);
return son;
}
6.3 A的左孩子的右子樹插入節點(LR)
若 A 的左孩子節點 B 的右子樹 E 插入節點 F ，導致節點 A 失衡，如圖：
圖 6.3
A 的平衡因子為 2 ，若仍按照右旋調整，則變化後的圖形為這樣：
圖 6.3.1
經過右旋調整發現，調整後樹仍然失衡，說明這種情況單純的進行右旋操作不能使樹重新平衡。那麼這種插入方式需要執行兩步操作，使得旋轉之後為 原來根節點的左孩子的右孩子作為新的根節點 。
（1）對失衡節點 A 的左孩子 B 進行左旋操作，即上述 RR 情形操作。
（2）對失衡節點 A 做右旋操作，即上述 LL 情形操作。
調整過程如下：
圖 6.3.2 
圖 6.3.3
也就是說，經過這兩步操作，使得 原來根節點的左孩子的右孩子 E 節點成為了新的根節點 。
程式碼實現：
//LR型，先左旋轉，再右旋轉
//返回：新父節點
Tree LR_rotate(Tree node){
RR_rotate(node->lchild);
return LL_rotate(node);
}
6.4 A的右孩子的左子樹插入節點(RL)
右孩子插入左節點的過程與左孩子插入右節點過程類似，也是需要執行兩步操作，使得旋轉之後為 原來根節點的右孩子的左孩子作為新的根節點 。
（1）對失衡節點 A 的右孩子 C 進行右旋操作，即上述 LL 情形操作。
（2）對失衡節點 A 做左旋操作，即上述 RR 情形操作。
圖 6.4 
圖 6.4.1 
圖 6.4.2
也就是說，經過這兩步操作，使得 原來根節點的右孩子的左孩子 D 節點成為了新的根節點 。
程式碼實現：
//RL型，先右旋轉，再左旋轉
//返回:新父節點
Tree RL_rotate(Tree node){
LL_rotate(node->rchild);
return RR_rotate(node);
}
補充：
上述四種插入方式的程式碼實現的輔助程式碼如下：
//更新當前深度
void update_depth(Tree node){
if (node==NULL){
return;
}else{
int depth_Lchild=get_balance(node->lchild); //左孩子深度
int depth_Rchild=get_balance(node->rchild); //右孩子深度
node->depth=max(depth_Lchild,depth_Rchild)+1;
}
}
//獲取當前節點的深度
int get_balance(Tree node){
if (node==NULL){
return 0;
}
return node->depth;
}
//返回當前平衡因子
int is_balance(Tree node){
if (node==NULL){
return 0;
}else{
return get_balance(node->lchild)-get_balance(node->rchild);
}
}
6.5 小總結
- 在所有的不平衡情況中，都是按照先 尋找最小不平衡樹 ，然後 尋找所屬的不平衡類別 ，再 根據 4 種類別進行固定化程式的操作 。
- LL , LR ，RR ，RL其實已經為我們提供了最後哪個節點作為新的根指明瞭方向。如 LR 型最後的根節點為原來的根的左孩子的右孩子，RL 型最後的根節點為原來的根的右孩子的左孩子。只要記住這四種情況，可以很快地推匯出所有的情況。
- 維護平衡二叉樹，最麻煩的地方在於平衡因子的維護。建議讀者們根據小吳提供的圖片和動圖，自己動手畫一遍，這樣可以更加感性的理解操作。
7. AVL樹的四種刪除節點方式
AVL 樹和二叉查詢樹的刪除操作情況一致，都分為四種情況：
（1）刪除葉子節點
（2）刪除的節點只有左子樹
（3）刪除的節點只有右子樹
（4）刪除的節點既有左子樹又有右子樹
只不過 AVL 樹在刪除節點後需要重新 檢查平衡性並修正 ，同時，刪除操作與插入操作後的平衡修正區別在於，插入操作後只需要對插入棧中的彈出的第一個非平衡節點進行修正，而刪除操作需要修正棧中的所有非平衡節點。
刪除操作的大致步驟如下：
- 以前三種情況為基礎嘗試刪除節點，並將訪問節點入棧。
- 如果嘗試刪除成功，則依次檢查棧頂節點的平衡狀態，遇到非平衡節點，即進行旋轉平衡，直到棧空。
- 如果嘗試刪除失敗，證明是第四種情況。這時先找到被刪除節點的右子樹最小節點並刪除它，將訪問節點繼續入棧。
- 再依次檢查棧頂節點的平衡狀態和修正直到棧空。
對於刪除操作造成的非平衡狀態的修正，可以這樣理解：對左或者右子樹的刪除操作相當於對右或者左子樹的插入操作，然後再對應上插入的四種情況選擇相應的旋轉就好了。
7.1 刪除葉子節點
處理步驟：
①、將該節點直接從樹中刪除；
②、其父節點的子樹高度的變化將導致父節點平衡因子的變化，通過向上檢索並推算其父節點是否失衡；
③、如果其父節點未失衡，則繼續向上檢索推算其父節點的父節點是否失衡…如此反覆②的判斷，直到根節點 ；如果向上推算過程中發現了失衡的現象，則進行 ④ 的處理；
④、如果其父節點失衡，則判斷是哪種失衡型別 [LL、LR、RR、RL] ，並對其進行相應的平衡化處理。如果平衡化處理結束後，發現與原來以父節點為根節點的樹的高度發生變化，則繼續進行 ② 的檢索推算；如果與原來以父節點為根節點的高度一致時，則可說明父節點的父節點及祖先節點的平衡因子將不會有變化，因此可以退出處理；
動圖 7.1.1
具體數字演示：
動圖 7.1
7.2 & 7.3 刪除的節點只有左子樹或右子樹
處理步驟：
①、將左子樹（右子樹）替代原有節點 C 的位置；
②、節點 C 被刪除後，則以 C 的父節點 B 為起始推算點，依此向上檢索推算各節點（父、祖先）是否失衡；
③、如果其父節點未失衡，則繼續向上檢索推算其父節點 的父節點 是否失衡…如此反覆 ② 的判斷，直到根節點 ；如果向上推算過程中發現了失衡的現象，則進行 ④ 的處理；
④、如果其父節點失衡，則判斷是哪種失衡型別 [LL、LR、RR、RL] ，並對其進行相應的平衡化處理。如果平衡化處理結束後，發現與原來以父節點為根節點的樹的高度發生變化，則繼續進行 ② 的檢索推算；如果與原來以父節點為根節點的高度一致時，則可說明父節點的父節點及祖先節點的平衡因子將不會有變化，因此可以退出處理；
動圖 7.2
7.4 刪除的節點既有左子樹又有右子樹
處理步驟：
①、找到被刪節點 B 和替代節點 BLR (節點 B 的前繼節點或後繼節點 —— 在此選擇 前繼 )；
②、將替代節點 BLR 的值賦給節點 B ，再把替代節點 BLR 的左孩子 BLRL 替換替代節點 BLR 的位置；
③、以 BLR 的父節點 BL 為起始推算點，依此向上檢索推算父節點或祖先節點是否失衡；
④、如果其父節點未失衡，則繼續向上檢索推算其父節點的父節點是否失衡…如此反覆③的判斷，直到根節點；如果向上推算過程中發現了失衡的現象，則進行⑤的處理；
⑤、如果其父節點失衡，則判斷是哪種失衡型別 [LL、LR、RR、RL] ，並對其進行相應的平衡化處理。如果平衡化處理結束後，發現與原來以父節點為根節點的樹的高度發生變化，則繼續進行 ② 的檢索推算；如果與原來以父節點為根節點的高度一致時，則可說明父節點的父節點及祖先節點的平衡因子將不會有變化，因此可以退出處理；
動圖 7.4
注：在這裡，小吳並沒有給出 AVL 的刪除操作的程式碼，也沒有給出平衡性修復的動畫，因為我並不打算過多去討論它，更復雜的刪除操作過程將放在後續的 紅黑樹 中進行討論。
總結
通過對 AVL 的插入操作和刪除操作可以看出，平衡二叉樹的優勢在於不會出現普通二叉查詢樹的最差情況，即退化成連結串列結構，但為了保證高度平衡（對稱），動態插入和刪除的代價也隨之增加。
AVL 的旋轉問題看似複雜，但實際上如果你親自用筆紙操作一下還是很好理解的。