自平衡 BST：歪了會自己轉正

BST 的老問題

第 16 章結尾提過：BST 按已排序順序插入 → 退化成鏈 → O(n)。

解法：每次插入後檢查樹有沒有歪，歪了就「轉一下」拉回來。

兩種主流自平衡 BST：

AVL 樹：嚴格平衡（左右高度差 ≤ 1），查詢快但旋轉多
紅黑樹：寬鬆平衡（黑高度相同），旋轉少但查詢略慢

旋轉：把歪掉的樹拉正

最重要的基本動作。左旋（LL → balanced）和右旋（RR → balanced）：

右旋：把左子節點提上來當新根，原根降為右子。左旋就是反過來。

AVL 樹：四種不平衡情況

每個節點存 balance factor = 左子樹高 - 右子樹高。合法範圍 [-1, 0, 1]。超出就要旋轉。

四種典型不平衡：

形狀	旋轉
LL（左子樹太重，新節點在左子的左）	右旋
RR（右子樹太重，新節點在右子的右）	左旋
LR（左子樹太重，新節點在左子的右）	先左旋左子 → 再右旋自己
RL（右子樹太重，新節點在右子的左）	先右旋右子 → 再左旋自己

💡LR 和 RL 為什麼要轉兩次？

單純一次旋轉解決不了「Z 字形」的歪斜。要先把 Z 拗成同一邊（變成 LL 或 RR），再做標準旋轉。

跑一遍：依序插入 10, 20, 30

插 10：     10
插 20：     10
              \
               20    （balance=-1，OK）
插 30：     10
              \
               20
                 \
                  30  （balance=-2，RR 不平衡！）

→ 對 10 左旋：

            20
           /  \
          10   30   ✓ balance=0

AVL 複雜度

操作	時間
查詢 / 插入 / 刪除	O(log n) 保證
額外資訊	每節點存 balance factor 或高度

紅黑樹：寬鬆但夠用

每個節點有顏色（紅或黑）。五條規則：

每個節點是紅或黑
根節點是黑
每個葉節點（NIL）是黑
紅節點的兩個子節點都是黑（不能連兩紅）
從任一節點到其後代的任何葉節點，黑節點數量相同

這些規則保證最長路徑 ≤ 最短路徑的 2 倍 → 樹高 O(log n)。

	AVL	紅黑樹
平衡嚴格度	嚴格 (差 ≤ 1)	寬鬆 (最長 ≤ 2 倍最短)
查詢速度	更快（樹更矮）	略慢
插入/刪除	慢（常旋轉）	更快（旋轉少）
用途	查詢密集	插入/刪除密集
實務	DB 索引	C++ map、Java TreeMap、Linux kernel

📝考試會這樣考

題型一：給插入序列，畫出 AVL 樹每步狀態。 標出每個節點的 balance factor，遇到 ±2 就旋轉。訣竅：判斷四種情況（LL/RR/LR/RL）再選旋轉方式。

題型二：判斷四種旋轉。 給樹結構，要你說這是 LL/RR/LR/RL，該怎麼轉。口訣：第一個字母看「不平衡發生在哪一邊」，第二個字母看「新節點在那邊的哪一側」。

題型三：AVL vs 紅黑樹什麼時候用哪個？ 答：

查詢多、插入少 → AVL（樹更矮）
插入/刪除多、查詢少 → 紅黑樹（旋轉成本低）

題型四：紅黑樹的五條規則。 死背，常考填空題。

題型五：為什麼自平衡 BST 樹高 O(log n)？ AVL：高度差 ≤ 1 限制了樹形。h ≤ 1.44 log(n+2)。紅黑：黑高 = h_b，總高 ≤ 2 × h_b，h_b ≤ log(n+1)。

這章記住

BST 會歪掉 → 自平衡 BST 每次插入後旋轉拉正。
AVL：嚴格平衡（差 ≤ 1），查詢快、旋轉多。
紅黑樹：寬鬆（最長 ≤ 2 倍），插入/刪除快、查詢略慢。
四種旋轉：LL / RR / LR / RL——判斷情況、套對應旋轉。
兩者都保證 O(log n)，是現代資料庫和 STL map 的核心。