自平衡樹 (Self-Balancing Trees)

概述

二元搜尋樹（Binary Search Tree, BST）是一種常見的資料結構，能夠支援高效的搜尋、插入與刪除。然而，如果沒有額外機制保持「平衡」，一般 BST 可能會退化，導致效能大幅下降。
因此，出現了 自平衡樹 (Self-Balancing Trees)，透過插入與刪除時的自動調整，確保樹的高度維持在合理範圍，使操作時間複雜度穩定在 O(log n)。

---

一般二元搜尋樹的問題

一般二元搜尋樹可能退化成鏈表
├─ 插入順序：1, 2, 3, 4, 5
├─ 結果：形成一條直線
├─ 搜尋時間複雜度：O(n)
└─ 失去樹結構的優勢

在這種情況下，BST 的效率會接近於線性搜尋，失去使用樹結構的意義。

---

自平衡樹的優勢

自平衡樹保持平衡
├─ 樹高維持在 O(log n)
├─ 搜尋/插入/刪除：O(log n)
├─ 自動調整結構
└─ 適合頻繁增刪的場景

---

AVL 樹

AVL 樹是第一種提出的自平衡二元搜尋樹，由 Adelson-Velsky 和 Landis 在 1962 年提出。它的特點是「嚴格平衡」。

平衡條件

• 每個節點的左右子樹高度差不能超過 1
• 平衡因子 = 左子樹高度 - 右子樹高度
• 平衡因子範圍：[-1, 0, 1]

旋轉操作

左旋 (Left Rotation)

     y                    x
    / \                  / \
   x   C     →         A   y
  / \                      / \
 A   B                    B   C

右旋 (Right Rotation)

   y                      x
  / \                    / \
 x   C       →         A   y
/ \                        / \
A   B                      B   C

插入後的平衡調整

情況	平衡因子	調整方式
LL	+2, +1	右旋
RR	-2, -1	左旋
LR	+2, -1	左旋後右旋
RL	-2, +1	右旋後左旋

AVL 樹能保證搜尋速度快，但因為調整嚴格，插入和刪除的旋轉次數可能較多。

---

紅黑樹 (Red-Black Tree)

紅黑樹則是一種「相對平衡」的二元搜尋樹，雖然不像 AVL 樹那麼嚴格，但能在插入與刪除時維持近似平衡。由於調整較少，它在 增刪操作頻繁的場合 更適合。

性質

1. 每個節點是紅色或黑色
2. 根節點是黑色
3. 紅色節點的子節點都是黑色
4. 從根到葉子的每條路徑包含相同數量的黑色節點
5. 葉子節點（NIL）都是黑色

插入操作

插入新節點（紅色）
├─ 如果父節點是黑色：直接插入
├─ 如果父節點是紅色：
│  ├─ 叔節點是紅色：重新著色
│  └─ 叔節點是黑色：旋轉 + 重新著色
└─ 確保根節點是黑色

刪除操作

刪除節點
├─ 找到替代節點
├─ 刪除目標節點
├─ 如果替代節點是紅色：直接刪除
├─ 如果替代節點是黑色：
│  ├─ 兄弟節點是紅色：旋轉
│  ├─ 兄弟節點是黑色：
│  │  ├─ 兄弟的子節點都是黑色：重新著色
│  │  └─ 兄弟的子節點有紅色：旋轉 + 重新著色
└─ 確保根節點是黑色

常見應用

• Java：TreeMap、TreeSet
• C++ STL：map、set
• Linux 核心：排程器使用紅黑樹管理計時器與資源

---

時間複雜度比較

操作	一般 BST	AVL 樹	紅黑樹
搜尋	O(n)	O(log n)	O(log n)
插入	O(n)	O(log n)	O(log n)
刪除	O(n)	O(log n)	O(log n)

---

總結

• 一般 BST：若資料分布不均，可能退化為鏈表，效能差。
• AVL 樹：嚴格平衡，搜尋速度快，適合查詢頻繁的場景。
• 紅黑樹：相對平衡，調整成本低，適合增刪頻繁的應用。

掌握這些自平衡樹的特性，有助於理解許多底層資料結構的實作，例如程式語言標準庫、核心系統等。