跳轉到

6.1 AVL樹與旋轉#

概念說明#

AVL 樹 是第一種自平衡二元搜尋樹，不變式為：每個節點的左右子樹高度差（平衡因子）為 −1、0 或 +1。可證明滿足此條件的樹高 ≤ 1.44·log₂(n+2)，因此所有操作穩定 O(log n)。

插入或刪除後，若某節點的平衡因子變成 ±2，就用旋轉修復。依「破壞路徑的方向」分四種情況，但實質只有兩種手術：

  • LL 型（左邊太高，破壞節點在左小孩的左子樹）→ 右旋轉
  • RR 型 → 左旋轉
  • LR 型（左小孩的右子樹）→ 先對左小孩左旋，再對自己右旋
  • RL 型 → 先對右小孩右旋，再對自己左旋

旋轉步驟#

右旋轉（對 z，其左小孩為 y）：

  1. y 接替 z 的位置（由 z 的父節點指向 y）。
  2. z 變成 y 的右小孩。
  3. y 原本的右小孩轉給 z 當左小孩。

左旋轉完全對稱。旋轉不改變中序順序，故 BST 性質完好。實作上常用「遞迴插入 + 回傳新子樹根」的寫法，讓父節點的指標自動接好。

Python 實作#

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1              # 葉高 1

def h(n):        return n.height if n else 0
def update(n):   n.height = 1 + max(h(n.left), h(n.right))
def balance(n):  return h(n.left) - h(n.right)

def rotate_right(z):
    y = z.left
    t3 = y.right
    y.right = z
    z.left = t3
    update(z); update(y)             # 先更新低的 z
    return y                          # 新子樹根

def rotate_left(z):
    y = z.right
    t3 = y.left
    y.left = z
    z.right = t3
    update(z); update(y)
    return y

def rebalance(n):
    update(n)
    b = balance(n)
    if b > 1:                         # 左太高
        if balance(n.left) < 0:       # LR 型
            n.left = rotate_left(n.left)
        return rotate_right(n)        # LL 型
    if b < -1:                        # 右太高
        if balance(n.right) > 0:      # RL 型
            n.right = rotate_right(n.right)
        return rotate_left(n)         # RR 型
    return n

def insert(n, val):
    if n is None:
        return AVLNode(val)
    if val < n.val:   n.left  = insert(n.left, val)
    elif val > n.val: n.right = insert(n.right, val)
    else:             return n
    return rebalance(n)

class AVLTree:
    def __init__(self):
        self.root = None
    def insert(self, val):
        self.root = insert(self.root, val)
    def height(self):
        return h(self.root)

    def in_order(self):
        out = []
        def walk(n):
            if n:
                walk(n.left); out.append(n.val); walk(n.right)
        walk(self.root)
        return out

# 致命測試：有序插入（會讓普通 BST 退化成鏈）
t = AVLTree()
for x in range(1, 16):
    t.insert(x)
print(t.height())          # 4（純 BST 此時高 15）
print(t.in_order())        # 仍是有序的 [1..15]

def check_avl(n):          # 驗證平衡性質
    if n is None:
        return 0
    lh, rh = check_avl(n.left), check_avl(n.right)
    assert abs(lh - rh) <= 1, f"節點 {n.val} 失衡"
    return 1 + max(lh, rh)
check_avl(t.root)
print("AVL 平衡檢查通過")

複雜度分析#

搜尋、插入、刪除皆 O(log n)：路徑長度 O(log n)，沿途各節點的旋轉與高度更新 O(1)。刪除最壞可能觸發 O(log n) 次旋轉（一路修上去），插入至多 2 次；空間 O(n)。實務上 AVL 適合「查多改少」的場景，因為它樹最矮、搜尋路徑最短。

練習#

  1. 手工追蹤：依序插入 10, 20, 30, 40, 50, 25，寫出每次觸發的旋轉類型與最終樹形。
  2. 實作 AVL 的 delete：刪除後沿回溯路徑對每個節點呼叫 rebalance，並用 1000 筆隨機資料驗證刪除後仍平衡。
  3. 統計實驗：分別用「BST 亂序插入」與「AVL 插入」處理 10 萬筆隨機數，比較兩者的樹高與 10 萬次搜尋的總耗時。