[algorithms] AVL Tree 自平衡二元搜尋樹

cover

BST 退化成鏈表的問題，AVL Tree 用旋轉解決了——代價是每次插入刪除都要多做一點事。

為什麼需要自平衡

AVL Tree = BST + 自動平衡。嚴格保證左右子樹高度差不超過 1，所以搜尋、插入、刪除都是穩定的 O(log n)，不會退化。讀多寫少的場景選 AVL，讀寫均衡選 Red-Black Tree。

為什麼 BST 需要平衡？

依序插入 1, 2, 3, 4, 5 到普通 BST：

1                    插到 AVL 裡：
 \
  2                      2
   \                    / \
    3       vs         1   4
     \                    / \
      4                  3   5
       \
        5
 
高度 5（鏈表）         高度 3（平衡）

左邊搜尋是 O(n)，右邊是 O(log n)。差距在資料量大時非常可怕。

平衡因子

BF(節點) = 左子樹高度 - 右子樹高度

AVL 的鐵律：每個節點的 |BF| ⇐ 1。一旦違反，就觸發旋轉修復。

四種旋轉

不平衡只有四種型態，每種有對應的修復方式：

LL（左左）→ 右旋

      z                 y
     /                 / \
    y       →         x   z
   /
  x

RR（右右）→ 左旋

  z                     y
   \                   / \
    y       →         z   x
     \
      x

LR（左右）→ 先左旋再右旋

    z            z            x
   /            /            / \
  y    →       x    →       y   z
   \          /
    x        y

RL（右左）→ 先右旋再左旋

  z          z              x
   \          \            / \
    y  →       x   →      z   y
   /            \
  x              y

看起來複雜，但規律很明確：單邊偏就單旋，折彎就雙旋。寫 code 時其實就是判斷 BF 和子節點的 BF，然後 call 對應的旋轉函式。

旋轉本身沒什麼玄機——就是把幾個指標接來接去，順手把被拉下來的那棵子樹掛回正確的位置：

// 右旋：把左小孩 x 提上來當老大，原本的 y 降去右邊
Node rightRotate(Node y) {
    Node x = y.left;
    Node B = x.right;   // x 的右子樹要改嫁給 y 的左邊
    x.right = y;
    y.left = B;
    updateHeight(y);    // 順序很重要：先更新降下去的 y
    updateHeight(x);
    return x;           // 新的子樹根
}
 
// 左旋：右旋的鏡像
Node leftRotate(Node x) {
    Node y = x.right;
    Node B = y.left;
    y.left = x;
    x.right = B;
    updateHeight(x);
    updateHeight(y);
    return y;
}

updateHeight 一定要「先更新降下去的節點、再更新升上來的節點」——順序反了高度會算錯，這是旋轉最容易踩的隱形坑。

插入流程

照正常 BST 規則插入
沿插入路徑往回更新每個節點的高度
檢查 BF，不平衡就旋轉

漂亮的地方在於：這三步全塞進同一個遞迴函式，回溯時自然由下往上修復，你不用另外寫一個「找不平衡點」的迴圈：

Node insert(Node node, int value) {
    if (node == null) return new Node(value);   // 1. BST 插入
 
    if (value < node.value) node.left = insert(node.left, value);
    else                    node.right = insert(node.right, value);
 
    updateHeight(node);                          // 2. 回溯更新高度
    int balance = getBalance(node);              // 3. 檢查 BF 決定旋轉
 
    if (balance > 1 && value < node.left.value)          // LL
        return rightRotate(node);
    if (balance < -1 && value > node.right.value)        // RR
        return leftRotate(node);
    if (balance > 1 && value > node.left.value) {        // LR
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    if (balance < -1 && value < node.right.value) {      // RL
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

四個 if 就是前面那四種旋轉型態的直譯——balance 判左右偏、子節點的 value 判有沒有折彎。刪除是同一套邏輯的鏡像，只是回溯時可能連續觸發多次旋轉（插入最多轉一次就穩，刪除不保證）。

插入順序 10, 20, 30：
 
Step 1: 10       Step 2: 10        Step 3: RR 不平衡 → 左旋
                           \             10              20
                            20             \            /  \
                                            20   →    10   30
                                             \
                                              30

旋轉本身是 O(1)（只改幾個指標），整個插入過程是 O(log n)。攤開來看四個操作：

操作	時間複雜度
搜尋	O(log n)
插入	O(log n)
刪除	O(log n)
單次旋轉	O(1)

重點不是「都很快」，而是這些 O(log n) 有嚴格保證、不會退化——普通 BST 的搜尋最壞是 O(n)，AVL 靠 BF ≤ 1 的鐵律把最壞情況也釘死在 O(log n)。

🎬 互動視覺化：BST 退化 vs AVL 自平衡對照 — 依序插入 1,2,3,4,5，親眼看普通 BST 歪成一條鏈、AVL 每次插入後怎麼旋轉把自己拉回平衡。

AVL vs Red-Black Tree

	AVL	Red-Black
平衡嚴格度	嚴格（BF ⇐ 1）	寬鬆
搜尋	略快（更平衡）	略慢
插入/刪除	旋轉次數較多	旋轉次數較少
適用場景	讀多寫少	讀寫均衡
實際使用	資料庫索引	Java TreeMap/TreeSet、Linux kernel

面試問到「為什麼 Java TreeMap 用 Red-Black Tree 不用 AVL Tree？」——因為 Map 通常插入刪除頻繁，Red-Black Tree 的旋轉開銷比較小。

但如果你的場景是「建好之後主要拿來查」（像資料庫索引），AVL Tree 更平衡所以搜尋更快。

AVL Tree 是完美主義者——每次操作都要確保自己完美平衡。Red-Black Tree 則是務實派，差不多就好。兩種都對，看你能接受多少不完美。

接下來往哪走

Segment Tree 線段樹 — 下一篇：樹狀結構從「搜尋」轉向「區間查詢」
Red-Black Tree 紅黑樹 — 表格裡那個「務實派」對照組的完整拆解
Skip List 跳躍表 — 不靠旋轉、靠隨機化達成平衡的第三條路

Terry Yao's Blog

目錄

AVL Tree 自平衡二元搜尋樹