前言
Wiki:在計算機科學中，
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. 定義
平衡二叉查找樹：簡稱平衡二叉樹。由前蘇聯的數學家 Adelse-Velskil 和 Landis 在 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 為父節點的那顆樹就稱為 最小失衡子樹。
最小失衡子樹：在新插入的節點向上查找，以第一個平衡因子的
平衡二叉樹的失衡調整主要是通過旋轉最小失衡子樹來實現的。根據旋轉的方向有兩種處理方式，左旋 與 右旋 。
旋轉的目的就是減少高度，通過降低整棵樹的高度來平衡。哪邊的樹高，就把那邊的樹向上旋轉。
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 的旋轉問題看似複雜，但實際上如果你親自用筆紙操作一下還是很好理解的。
/ 今日問題 /
已知我有 132 個好友，其中有 5 人關注了咪蒙。你可以通過 (批量）刪除/添加好友並觀察咪蒙好友關注數來推測誰關注了咪蒙。假設反覆刪除添加好友不會被揍，找到這 5 個好友需要進行多少次操作？