AVL樹初識

一、AVL樹簡介

AVL樹是一種自平衡二叉搜索樹（Binary Search Tree, BST），于1962年由Georgy Adelson-Velsky和Evgenii Landis提出，名字也來自他們兩位的姓氏首字母組合。它通過在插入、刪除節點后維持平衡性，確保在查找、插入、刪除操作上保持 $O(\log n)$ 的平均和最壞時間復雜度。

---

二、AVL樹的平衡條件

在普通的二叉搜索樹中，樹的高度可能因為插入或刪除導致嚴重失衡，從而退化成鏈表。而AVL樹通過維護**平衡因子（Balance Factor）**來保持平衡。

平衡因子的定義：

$$\text{平衡因子}=\text{左子樹的高度}?\text{右子樹的高度}$$

• 平衡因子的絕對值不超過1（即 $?1$、0、1），則該節點視為平衡。
• AVL樹要求所有節點的平衡因子絕對值 $\le 1$。

通過對節點的平衡因子進行檢查和旋轉操作，AVL樹能始終維持其平衡性。

---

三、AVL樹的基本操作

1. 查找（Search）

AVL樹本質上是二叉搜索樹，查找過程與普通二叉搜索樹相同，時間復雜度為 $O(\log n)$。

2. 插入（Insert）

插入新節點的過程包括以下步驟：

1. 常規插入： 按照二叉搜索樹的規則插入新節點。
2. 更新平衡因子： 從插入位置向上回溯，更新祖先節點的高度或平衡因子。
3. 檢測并恢復平衡： 如果某節點的平衡因子絕對值超過1，根據具體情況執行旋轉操作。

插入導致的失衡類型

類型	條件	解決方法
LL失衡	節點的平衡因子為 +2，且左子節點的平衡因子 $\ge 0$	單右旋
LR失衡	節點的平衡因子為 +2，且左子節點的平衡因子 $<0$	先左旋后右旋
RR失衡	節點的平衡因子為 -2，且右子節點的平衡因子 $\le 0$	單左旋
RL失衡	節點的平衡因子為 -2，且右子節點的平衡因子 $>0$	先右旋后左旋

3. 刪除（Delete）

刪除操作分以下幾種情況：

1. 刪除葉子節點或單子節點：

   • 直接刪除節點或用子節點替換。

2. 刪除有兩個子節點的節點：

   • 找出該節點的前驅或后繼節點，用其值覆蓋當前節點，并遞歸刪除前驅/后繼節點。

3. 更新并恢復平衡：

   • 從被刪除節點的位置向上回溯，更新祖先節點的平衡因子，若失衡則執行旋轉操作。

---

四、旋轉操作

AVL樹通過旋轉操作調整樹的結構，從而恢復平衡。旋轉分為以下四種：

1. 單右旋（LL失衡）

• 觸發條件：節點的平衡因子為 +2，且左子節點的平衡因子 $\ge 0$。
• 示例：

        A                          B/ \                        / \B   α     => 右旋         C   A/ \                        /   / \C   β                      γ   β   α

2. 先左旋后右旋（LR失衡）

• 觸發條件：節點的平衡因子為 +2，且左子節點的平衡因子 $<0$。
• 示例：

        A                          A                          C/ \        => 左旋         / \        => 右旋         / \B   α       B   α          C   A\          / \               / \C        B   γ             β   α/ \       / \  β   γ     β   γ  

3. 單左旋（RR失衡）

• 觸發條件：節點的平衡因子為 -2，且右子節點的平衡因子 $\le 0$。
• 示例：

        A                          B/ \                        / \α   B     => 左旋         A   C/ \                    / \β   C                  α   β

4. 先右旋后左旋（RL失衡）

• 觸發條件：節點的平衡因子為 -2，且右子節點的平衡因子 $>0$。
• 示例：

        A                          A                          C/ \        => 右旋         / \        => 左旋         / \α   B       α   C          A   B/ \         \            / \C   γ         B          α   β/ \          / \β   γ        β   γ

---

五、時間復雜度與特性

• 高度： AVL樹的高度保持在 $O(\log n)$ 量級，最壞情況下的高度為 ${\log }_{?}(n)$（$?$ 為黃金比例，約為1.618）。
• 查找： 時間復雜度為 $O(\log n)$。
• 插入/刪除： 時間復雜度為 $O(\log n)$。
• 額外空間： 需要維護每個節點的高度或平衡因子信息。

---

六、AVL樹優缺點

優點：

1. 查找性能優秀，適用于查找頻繁的場景。
2. 平衡性好，樹的高度始終接近最優。

缺點：

1. 插入和刪除操作需要額外的旋轉和更新，性能開銷相對紅黑樹更高。
2. 實現復雜，邏輯較為繁瑣。

---

七、示例

以下為插入數據的過程示例：

插入數據：10, 20, 5, 15, 25, 30

1. 插入10：

   10

2. 插入20：

   10\20

3. 插入5：

     10/  \5    20

4. 插入15：

     10/  \5    20/15

5. 插入25：

     10/  \5    20/  \15   25

6. 插入30，觸發RR失衡，左旋后結果：

        20/  \10    25/  \      \5   15      30

---

八、總結

AVL樹是一種高效的自平衡二叉搜索樹，適用于對查找效率要求較高的場景，但在插入刪除頻繁的情況下，其復雜度和性能可能略遜于紅黑樹。