前言
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.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 樹在刪除節點後需要重新檢查平衡性並修正，同時，刪除操作與插入操作後的平衡修正區別在於，插入操作後只需要對插入棧中的彈出的第一個非平衡節點進行修正，而刪除操作需要修正棧中的所有非平衡節點。
刪除操作的大致步驟如下：
以前三種情況為基礎嘗試刪除節點，並將訪問節點入棧。如果嘗試刪除成功，則依次檢查棧頂節點的平衡狀態，遇到非平衡節點，即進行旋轉平衡，直到棧空。如果嘗試刪除失敗，證明是第四種情況。這時先找到被刪除節點的右子樹最小節點並刪除它，將訪問節點繼續入棧。再依次檢查棧頂節點的平衡狀態和修正直到棧空。對於刪除操作造成的非平衡狀態的修正，可以這樣理解：對左或者右子樹的刪除操作相當於對右或者左子樹的插入操作，然後再對應上插入的四種情況選擇相應的旋轉就好了。
總結
AVL 的旋轉問題看似複雜，但實際上如果你親自用筆紙操作一下還是很好理解的。