AVL樹筆記

學習影片
https://www.youtube.com/watch?v=2j8VlJFkLFg

基本定義

• AVL 樹 是一種自平衡的二元搜尋樹（Binary Search Tree, BST）。
• 每個節點的左右子樹高度差（平衡因子）不超過 1，保證搜尋、插入、刪除操作的時間複雜度為 O(log n)。
• 平衡因子（Balance Factor, BF）：
  • 用來衡量每個節點的平衡狀態。
  • 計算公式：BF = Height(Left Subtree) - Height(Right Subtree)
  • 範圍：-1 ≤ BF ≤ 1，當 |BF| > 1 時，表示該節點失衡，需要進行旋轉操作來調整。

特點

• 保持自平衡：在每次插入或刪除節點後，透過旋轉操作（左旋、右旋、左右旋、右左旋）來恢復平衡。
• 時間複雜度：
  • 插入、刪除、搜尋：O(log n)。
• 適用場景：
  • 適合用於頻繁查詢且插入、刪除不太頻繁的應用場景，如：資料庫索引、符號表、操作系統中的管理結構。

常見操作

插入（Insertion）

1. 將新節點放置在二元搜尋樹適當的位置（依據值的大小來決定）。
2. 插入後檢查節點的平衡因子，確認是否需要進行旋轉。
3. 若某節點失衡，則透過以下四種旋轉操作之一來恢復平衡。

刪除（Deletion）

1. 找到並刪除節點（刪除過程與普通二元搜尋樹相同）。
2. 更新平衡因子並檢查是否失衡。
3. 根據平衡因子執行相應的旋轉操作。

旋轉（Rotation）

• 單左旋轉（LL）：

  • 適用於某節點的右子樹過高（右子樹的高度比左子樹高 2 或更多）。
  • 範例：

         10
           \
            20
              \
               30
    → 單左旋轉 →
         20
        /  \
       10   30
    

• 單右旋轉（RR）：

  • 適用於某節點的左子樹過高（左子樹的高度比右子樹高 2 或更多）。
  • 範例：

         30
        /
       20
      /
     10
    → 單右旋轉 →
         20
        /  \
       10   30
    

• 左右旋轉（LR）：

  • 適用於左子樹的右子樹較重的情況。
  • 先對左子樹執行一次左旋轉，再對祖父節點執行右旋轉。
  • 範例：

       30
      /
    10
      \
      20
    → 左右旋轉 →
         20
        /  \
       10   30
    

• 右左旋轉（RL）：

  • 適用於右子樹的左子樹較重的情況。
  • 先對右子樹執行一次右旋轉，再對祖父節點執行左旋轉。
  • 範例：

      10
        \
         30
        /
      20
    → 右左旋轉 →
         20
        /  \
       10   30
    

優缺點

• 優點：

• 保持高度平衡，保證所有操作的時間複雜度為 O(log n)。

• 相較於普通二元搜尋樹，可以避免最壞情況退化為鏈表結構。

• 缺點：

• 插入與刪除後可能需要多次旋轉，維護代價較高。

• 當資料量大且操作頻繁時，旋轉操作可能增加不必要的額外計算成本。

使用場景

• 資料庫索引：適合用於儲存需要快速查找的資料，如關鍵字索引、資料庫查詢。
• 符號表：在編譯器中，用來快速查詢變數與函數名稱。
• 多重集合（Multiset）管理：適用於插入與刪除不頻繁但查詢操作多的情況。