【考試向】資料結構筆記（AVL Tree）

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

高度平衡二元搜尋樹（Height Balanced BST）

學習資料結構時，從基礎的二元搜尋樹（BST）跨越到平衡樹是一個非常關鍵的里程碑，在撰寫演算法或面對高壓的程式解題環境時，維持資料結構的高效能，往往是避免 Time Limit Exceeded（TLE）的核心。

要理解「高度平衡」，得要先知道原本的二元搜尋樹（Binary Search Tree, BST）有什麼致命缺點。

在理想狀態下，BST 的查詢、新增和刪除時間複雜度都是 $O(\log N)$。

但如果我們依序插入一組已經排序好的資料（例如：1, 2, 3, 4, 5），這棵樹的節點就會全部往右邊長，退化成一條類似鏈結串列（Linked List）的結構（左或右斜樹 Skewed Tree），此時它的時間複雜度就會跌至 $O(N)$，是我們不樂見的。

高度平衡二元搜尋樹（Height Balanced BST）就是為了解決這個問題而誕生的概念：強迫樹的左右兩側盡量均勻生長，透過在插入或刪除節點時進行動態調整，確保整棵樹的高度始終維持在 $O(\log N)$，從而保證所有基本操作的高效性。

AVL Tree

高度平衡二元搜尋樹是一個概念，而 AVL Tree 是這個概念在歷史上的第一種具體實作方法。

它是由兩位蘇聯計算機科學家 Georgy Adelson-Velsky 和 Evgenii Landis 於 1962 年共同發表的，為了紀念這兩位發明者，這棵樹便以他們名字的首字母縮寫 AVL 來命名。

AVL Tree 的定義

一棵樹要能被稱為 AVL Tree，必須同時滿足以下兩個條件：

必為一棵二元搜尋樹：滿足左子節點 < 父節點 < 右子節點的基本大小關係。
嚴格的高度平衡：樹中任意一個節點的「左子樹高度 $h_L$」與「右子樹高度 $h_r$」相差的絕對值 $|h_L - h_R|$，最大只能是 1。（即 $|h_L - h_R| \le 1$）

只要有任何一個節點的左右子樹高度差超過 1，這棵樹就違反了 AVL Tree 的定義，必須立即修正。

平衡因子（Balance Factor, BF）

為了判斷 AVL Tree 是否滿足定義，需要一個可以量化的指標，即平衡因子（Balance Factor, BF）。

計算公式：$$BF = h_L - h_R$$

$h_L$ 就是左子樹高度，$h_R$ 為右子樹高度。

在 AVL Tree 中，每一個節點的 BF 值只能是以下三種數字：

1（左邊比右邊高一層）
0（左右一樣高）
-1（右邊比左邊高一層）

失衡狀態：當新增或刪除節點後，如果某個節點的 BF 值變成了 2 或 -2，這就失衡了，代表這棵樹某邊長得太重了，必須透過特定的旋轉（Rotation）操作來讓它恢復平衡。

AVL Tree 加入操作

AVL Tree 的加入操作實際上跟二元搜尋樹是一模一樣的，但這個動作會改變這條路徑上所有祖先節點的子樹高度，進而可能改變它們的平衡因子（BF）。

如果沿著新加入的節點一路往上檢查，發現了第一個 BF 變成 2 或 -2 的節點（稱為失衡節點），這時就必須啟動旋轉機制。

判斷要用哪一種旋轉，關鍵在於：新節點是加在失衡節點的哪一側？可歸納成四種路徑，也就是著名的 LL、RR、LR、RL 型態。

LL 型態（Left-Left）與單右旋

發生條件：新節點被插入在失衡節點的左子節點的左子樹上。
狀態特徵：失衡節點的 BF = 2（左邊太重），且它的左子節點 BF = 1。
解決動作：單右旋（Single Right Rotation）
- 概念：因為整棵樹像左邊傾倒，要把失衡節點的左子節點往上提升成新的根節點，原本的失衡節點則順勢往右下沉，變成新根節點的右子節點。
- 實作：如果原本左子節點有自己的右子樹，因為它要被提升了，這個右子樹必須繼承給下沉的失衡節點當作左子樹（這樣才符合 BST 大小規則）。

例：

加入新節點 30：

50 節點的 BF 值為 2（2 - 0 = 2），因此失衡，且插入節點 30 位在 50 的左子節點之左子樹，因此為 LL 型。

調整作法是將 50 的左子節點 40 往上提升變成根節點，而自己去到右邊，成為 40 的右子節點：

RR 型態（Right-Right）與單左旋

發生條件：新節點被插入在失衡節點的右子節點的右子樹上。
狀態特徵：失衡節點的 BF = -2（右邊太重），且它的右子節點 BF = -1。
解決動作：單左旋（Single Left Rotation）
- 概念：LL 的鏡像情況，樹向右邊傾倒，所以我們把失衡節點的右子節點往上提，原本的失衡節點往左下沉，變成新根節點的左子節點。
- 實作：同理，原本右子節點若有左子樹，必須繼承給下沉的失衡節點當作右子樹。

例：（已加入了 50 進去）

根節點 30 的 BF 是 -2（0-2 = -2），因此失衡，且插入節點 50 位在 40 的右子節點之右子樹，因此為 RR 型。

調整作法是將 40 的右子節點 50 往上提升變成根節點，而自己去到左邊，成為 50 的左子節點：

LR 型態（Left-Right）與先左旋再右旋

發生條件：新節點被插入在失衡節點的左子節點的右子樹上。
狀態特徵：失衡節點的 BF = 2，但它的左子節點 BF = -1（呈現一個 < 字型的折線）。
解決動作：雙旋轉（Left-Right Double Rotation）
- 概念：因為這是一個折線，直接對失衡節點旋轉無法解決問題，須分兩步走，先把折線拉直，再進行處理。
- Step 1（局部左旋）：先對失衡節點的左子節點做一次單左旋，這會把原本 < 字型的結構拉直成 / 字型，也就是成功將狀態轉換成 LL 型態。
- Step 2（整體右旋）：既然變成了 LL 型態，就比照 LL 的做法，對失衡節點做一次單右旋即可恢復平衡。

例：

加入節點 45：

可發現根節點的 BF 為 2，其左子節點為 -1，因此為 LR 型，首先把 < 形狀改成直線，把 45 給往上提：

接著再做 LL 型的旋轉：

RL 型態（Right-Left）與先右旋再左旋

發生條件：新節點被插入在失衡節點的右子節點的左子樹上。
狀態特徵：失衡節點的 BF = -2，但它的右子節點 BF = 1（呈現一個 > 字型的折線）。
解決動作：雙旋轉（Right-Left Double Rotation）
- 概念：LR 的鏡像情況，一樣分兩步將折線拉直。
  - Step 1（局部右旋）：先對失衡節點的右子節點做一次單右旋，把 > 字型結構拉直成 \ 字型，轉換成 RR 型態。
  - Step 2（整體左旋）：對失衡節點做一次單左旋，完成平衡。

例：

加入節點 55：

發現根節點 50 的 BF 值為 -2，其右子節點 60 的 BF 值為 1，因此是一個 RL 型，先把 > 字形轉為 \，將 55 往上提：

變成 RR 型後，直接把 55 提升為根節點：

LL、RR、LR、RL 的進階範例

LL

現在有一棵二元搜尋樹：

加入 20 後就打破 AVL Tree 的定義：

以下是每個節點的 BF 值：

由於失衡節點 BF = 2，且其左子節點與左子節點的左子節點 BF 皆為 1，因此為 LL 型，只需考慮調整 50、40、30。

對於有右子節點的 40 來說，到時候只要給 50 當作左子節點即可（因為 45 < 50）。

調整完後就會是：

RR

現在有一棵二元搜尋樹：

加入 80 後就打破了 AVL Tree 的平衡：

由於失衡節點 50 BF = -2，且其右子節點 60 BF = -1，而右子節點的右子樹 70 也是 BF = -1。

對於有左子節點的 60，只要給 50 當右子節點即可（因為 60 > 50）。

調整完後變這樣：

LR

現在有一棵二元搜尋樹：

加入 43 後就打破了 AVL Tree 的平衡：

失衡節點 50 BF = 2，左子節點 40 BF = -1，而其左子節點的右子樹 45 BF = -1，形成一個 < 字形，因此為 LR 型。

首先將 45 往上提，形成 / 形，至於左子節點就給 40 當作右子節點，如下：

轉成 LL 型後就依照其方式做旋轉：

RL

現在有一棵二元搜尋樹：

加入 52 後就打破了 AVL Tree 的平衡：

失衡節點 50 BF = -2，右子節點 60 BF = 1，而其右子節點的左子樹 55 BF = 1，形成一個 > 字形，因此為 RL 型。

首先將 55 往上提，形成 \ 形，至於左子節點先留下，如下：

然後根據 RR 做旋轉：

AVL Tree 的刪除

首先暫時忘記平衡這件事，把 AVL Tree 當作普通的二元搜尋樹（BST）來執行刪除，根據被刪除節點的子節點數量，會有三種情況：

情境 A：刪除葉節點（Leaf Node，無子節點）
- 直接將該節點移除，並將其父節點指向它的指標設為 nullptr（或 NULL）。
情境 B：刪除只有一個子節點的節點
- 直接將該節點移除，並讓它唯一的子節點接替它的位置，與被刪除節點的父節點連接。
情境 C：刪除有兩個子節點的節點
- 不能直接刪除，否則其兩個子樹會斷線。
- 解法：去它的左子樹找最大值，或去右子樹找最小值（通常稱為中序前驅或中序後繼），將那個替換節點的值複製到要刪除的節點上。
- 接著，轉而去刪除那個替換節點，因為替換節點必定最多只有一個子節點，所以問題就成功降級為情境 A 或情境 B。

接著會回溯更新高度與平衡因子（BF），不過這在 C 程式裡面就會幫我們做了，對於手寫實作來說就步就會跳過，實際要做的是判斷失衡與旋轉修復。

在回溯的過程中，一旦發現某個祖先節點的 $|BF| \geq 2$，就代表刪除動作導致了失衡，必須立刻旋轉修復。

判斷旋轉型態的方式與插入時略有不同，插入時看的是新節點加在哪裡，刪除時看的是失衡節點哪邊比較重（高）。

假設失衡的節點為 X，它較高的一側子節點為 Y：

LL 型態（左邊太重）：
- 條件：X 的 BF = 2，且 Y 的 BF = 1 或 0。
- 解決：對 X 執行單右旋。
- 註：Y 的 BF = 0 是刪除操作特有的情況，插入時不會發生，代表 Y 的左右子樹一樣高，旋轉後樹的整體高度不會改變。
RR 型態（右邊太重）：
- 條件：X 的 BF = -2，且 Y 的 BF = -1 或 0。
- 解決：對 X 執行單左旋。
LR 型態（左子樹的右邊較重）：
- 條件：X 的 BF = 2，且 Y 的 BF = -1。
- 解決：先對 Y 執行單左旋，再對 X 執行單右旋。
RL 型態（右子樹的左邊較重）：
- 條件：X 的 BF = -2，且 Y 的 BF = 1。
- 解決：先對 Y 執行單右旋，再對 X 執行單左旋。

舉例：