第二部分：優先處理（續）¶

< 上一題：QoS 優先權管理 | 返回目錄 | 下一題：最短路徑計算 >

場景：查詢過去任意時間範圍的流量¶

監控系統需要回答這類問題：

「10:30 到 11:15 之間，台北到東京的流量總共是多少？」

你有數百萬筆流量紀錄，每筆都有時間戳。需要快速回答**範圍查詢（Range Query）**。

Hash Table？只能查「某個時間點」，不能查範圍
排序陣列？可以二分搜尋範圍邊界，但插入新紀錄要 $O(n)$

你需要一個**既能快速查詢，又能快速插入**的資料結構。

第 4 題：流量紀錄索引 - BST 與平衡樹¶

Binary Search Tree（BST）是支援「有序操作」的經典結構。但普通 BST 可能退化成鏈表，所以我們需要**自平衡**的變種。

(a) BST 基本操作¶

3 分 ・大二

你需要知道：BST 的定義和基本操作

題目：

說明 BST 的**有序性質（BST Property）**
實作 search、insert、find_min、find_max 操作
分析這些操作的時間複雜度（用樹高 $h$ 表示）

提示

BST Property：左子樹所有值 < 根 < 右子樹所有值
操作時間取決於要走幾層

解答

1. BST Property：

對於任意節點 $x$： - 左子樹所有節點的值 < $x$ 的值 - 右子樹所有節點的值 > $x$ 的值

這個性質**遞迴地**對每個子樹成立。

推論：BST 的**中序遍歷（Inorder Traversal）** 產生有序序列。

2. 基本操作：

class TreeNode:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    else:
        return search(root.right, key)

def insert(root, key, value=None):
    if root is None:
        return TreeNode(key, value)
    if key < root.key:
        root.left = insert(root.left, key, value)
    elif key > root.key:
        root.right = insert(root.right, key, value)
    else:
        root.value = value  # 更新
    return root

def find_min(root):
    while root.left:
        root = root.left
    return root

def find_max(root):
    while root.right:
        root = root.right
    return root

3. 時間複雜度：

所有操作都是「從根走到目標」，最多走 $h$ 層（$h$ = 樹高）。

操作	時間複雜度
search	$O(h)$
insert	$O(h)$
find_min	$O(h)$
find_max	$O(h)$

問題：$h$ 是多少？

最好：完全平衡，$h = O(\log n)$
最壞：退化成鏈表，$h = O(n)$

BST 的中序遍歷

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key)
        inorder(root.right)

對於 BST，中序遍歷輸出**有序序列**。

這就是為什麼 BST 適合範圍查詢：找到範圍起點，然後按中序遍歷直到終點。

(b) BST 刪除操作¶

3 分 ・大二

插入容易，刪除複雜。刪除一個節點後，要維持 BST Property。

你需要知道：BST 刪除的三種情況

題目：

說明刪除操作的三種情況及處理方法
實作 delete 操作

手動模擬：從下面的 BST 刪除節點 5

      5
    /   \
   3     7
  / \   / \
 2   4 6   8

解答

1. 三種情況：

Case 1：葉節點 - 直接刪除

Case 2：只有一個子節點 - 用子節點取代自己

Case 3：有兩個子節點 - 找**中序後繼（Inorder Successor）或**中序前驅（Inorder Predecessor） - 用後繼/前驅的值取代自己 - 刪除後繼/前驅（它最多只有一個子節點）

中序後繼：右子樹的最小值 中序前驅：左子樹的最大值

2. 實作：

def delete(root, key):
    if root is None:
        return None

    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        # 找到要刪除的節點
        if root.left is None:
            return root.right  # Case 1 & 2
        elif root.right is None:
            return root.left   # Case 2

        # Case 3: 有兩個子節點
        successor = find_min(root.right)
        root.key = successor.key
        root.value = successor.value
        root.right = delete(root.right, successor.key)

    return root

3. 模擬刪除 5：

原樹：      刪除 5（Case 3）
      5          找右子樹最小 = 6
    /   \        用 6 取代 5
   3     7       刪除原本的 6
  / \   / \
 2   4 6   8

結果：
      6
    /   \
   3     7
  / \     \
 2   4     8

© BST 退化問題與平衡樹的動機¶

4 分 ・大三

如果依序插入 [1, 2, 3, 4, 5]，會發生什麼事？

退化成**鏈表**！每次操作都是 $O(n)$，完全失去 BST 的優勢。

你需要知道：如何避免 BST 退化？

題目：

證明：$n$ 個節點的 BST，高度範圍是 $[\lfloor \log_2 n \rfloor, n-1]$
什麼是**平衡樹（Balanced BST）**？常見的平衡樹有哪些？
說明 AVL Tree 的平衡條件

解答

1. 高度範圍：

最小高度：完全平衡二元樹 - 每層盡量填滿 - 高度 $h$ 的樹最多有 $2^{h+1} - 1$ 個節點 - 反過來，$n$ 個節點至少需要高度 $h = \lfloor \log_2 n \rfloor$

最大高度：退化成鏈表 - 每層只有一個節點 - 高度 = $n - 1$

2. 平衡樹：

定義：保證樹高 $h = O(\log n)$ 的 BST

常見平衡樹：

名稱	平衡條件	特點
AVL Tree	左右子樹高度差 ≤ 1	嚴格平衡，查詢快
Red-Black Tree	黑高相等 + 顏色規則	插入/刪除旋轉次數少
B-Tree	節點可有多個 key	適合磁碟 I/O
Splay Tree	攤銷平衡	適合有 locality 的存取

3. AVL Tree 平衡條件：

對於每個節點，平衡因子（Balance Factor）：

\[BF(x) = \text{height}(\text{left}(x)) - \text{height}(\text{right}(x))\]

AVL 條件：每個節點的 $|BF| \leq 1$

也就是說，左右子樹高度差最多為 1。

AVL Tree 高度上界

設 $N(h)$ = 高度為 $h$ 的 AVL Tree 最少需要多少節點？

$N(0) = 1$（只有根）
$N(1) = 2$（根 + 一個子節點）
$N(h) = N(h-1) + N(h-2) + 1$（左右子樹差 1，加上根）

這類似 Fibonacci 數列！

\[N(h) = F_{h+3} - 1 \approx \frac{\phi^{h+3}}{\sqrt{5}}\]

反過來，$n$ 個節點的 AVL Tree 高度：

\[h \leq 1.44 \log_2(n+2) - 1.33 = O(\log n)\]

結論：AVL Tree 保證 $h = O(\log n)$。

(d) AVL Tree 旋轉操作¶

4 分 ・大三

AVL Tree 如何在插入/刪除後維持平衡？答案是**旋轉（Rotation）**。

你需要知道：四種不平衡情況及對應的旋轉

題目：

說明**單旋轉（LL, RR）和**雙旋轉（LR, RL）
手動模擬：依序插入 [10, 20, 30, 25, 27]，畫出每步的 AVL Tree

提示

LL：左子樹的左子樹太高 → 右旋
RR：右子樹的右子樹太高 → 左旋
LR：左子樹的右子樹太高 → 先左旋再右旋
RL：右子樹的左子樹太高 → 先右旋再左旋

解答

1. 四種旋轉：

LL 不平衡 → 右旋（Right Rotation）：

    z                    y
   /                   /   \
  y       →           x     z
 /
x

def right_rotate(z):
    y = z.left
    T3 = y.right

    y.right = z
    z.left = T3

    update_height(z)
    update_height(y)
    return y

RR 不平衡 → 左旋（Left Rotation）：

z                        y
 \                     /   \
  y       →           z     x
   \
    x

LR 不平衡 → 先左旋再右旋：

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

先對 y 左旋，再對 z 右旋。

RL 不平衡 → 先右旋再左旋：

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

2. 模擬插入：

Insert 10:
    10      (平衡)

Insert 20:
    10
      \
       20   (平衡，BF=1)

Insert 30:
    10
      \
       20   (10 的 BF = -2，RR 不平衡)
        \
         30

→ 左旋：
       20
      /  \
     10  30   (平衡)

Insert 25:
       20
      /  \
     10  30
        /
       25     (平衡)

Insert 27:
       20
      /  \
     10  30
        /
       25     (30 的 BF = 2，RL 不平衡)
        \
         27

→ 先對 25 左旋：
       20
      /  \
     10  30
        /
       27
      /
     25

→ 再對 30 右旋：
       20
      /  \
     10  27
        /  \
       25  30

最終結果：
       20
      /  \
     10  27
        /  \
       25  30

(e) Red-Black Tree 概念¶

3 分 ・碩一

AVL Tree 很嚴格（高度差 ≤ 1），每次操作可能需要多次旋轉。Red-Black Tree 用不同的平衡策略，減少旋轉次數。

你需要知道：Red-Black Tree 的五大性質

題目：

列出 Red-Black Tree 的五個性質
說明 Red-Black Tree 如何保證 $h = O(\log n)$
比較 AVL Tree 和 Red-Black Tree 的優缺點

解答

1. Red-Black Tree 五大性質：

每個節點是**紅色**或**黑色**
根是黑色
葉節點（NIL）是黑色（這裡的葉是指 NULL 節點）
紅色節點的子節點必須是黑色（不能有連續兩個紅）
從任一節點到其所有後代葉節點的路徑，黑色節點數相同（黑高相等）

2. 高度證明：

設「黑高」$bh(x)$ = 從 $x$ 到任意葉的黑色節點數（不含 $x$）。

引理：以 $x$ 為根的子樹至少有 $2^{bh(x)} - 1$ 個內部節點。

由性質 4（沒有連續紅），從根到葉的路徑上，紅色節點最多是黑色的一半。

設樹高 $h$，黑高 $bh \geq h/2$。

\[n \geq 2^{bh} - 1 \geq 2^{h/2} - 1$$ $$h \leq 2 \log_2(n+1) = O(\log n)\]

3. AVL vs Red-Black：

特性	AVL Tree	Red-Black Tree
平衡嚴格度	更嚴格（高度差 ≤ 1）	較寬鬆（高度差可達 2 倍）
樹高	$\leq 1.44 \log n$	$\leq 2 \log n$
查詢速度	更快（樹更矮）	稍慢
插入/刪除旋轉	可能多次	最多 2-3 次
適用場景	查詢多於修改	修改頻繁

實務選擇： - 資料庫索引（查詢多）→ AVL 或 B-Tree - 語言內建 Map（增刪查平衡）→ Red-Black Tree（C++ STL, Java TreeMap）

進階挑戰：Range Query 實作¶

3 分 ・碩一

回到原始問題：「查詢 10:30 到 11:15 之間的所有流量紀錄」

你需要知道：如何在 BST 上實現高效的範圍查詢？

題目：

設計演算法：給定範圍 $[lo, hi]$，找出所有 key 在範圍內的節點
分析時間複雜度（設結果有 $k$ 個節點）

解答

1. Range Query 演算法：

def range_query(root, lo, hi, result):
    if root is None:
        return

    # 如果當前節點可能有左邊的結果
    if root.key > lo:
        range_query(root.left, lo, hi, result)

    # 如果當前節點在範圍內
    if lo <= root.key <= hi:
        result.append(root)

    # 如果當前節點可能有右邊的結果
    if root.key < hi:
        range_query(root.right, lo, hi, result)

原理：利用 BST 性質剪枝。如果當前節點 < lo，左子樹全部 < lo，不用看。

2. 時間複雜度：

遍歷的節點數：$O(h + k)$
$h$ 個節點在「找邊界」的路徑上
$k$ 個節點在結果中
總時間：$O(h + k) = O(\log n + k)$（平衡樹）

比較： - 排序陣列 + 二分搜尋：$O(\log n + k)$，但插入 $O(n)$ - 平衡 BST：查詢 $O(\log n + k)$，插入 $O(\log n)$

BST 在「動態資料 + 範圍查詢」的場景完勝！

第 4 題小結：你的索引工具箱¶

「查詢任意時間範圍的流量」
    │
    ├─► (a) 需要有序結構？→ BST
    │       → 中序遍歷產生有序序列
    │       → 操作時間 O(h)
    │
    ├─► (b) 怎麼刪除？
    │       → 三種情況：葉、單子、雙子
    │       → 雙子：用後繼取代
    │
    ├─► (c) 怕退化成鏈表？→ 平衡樹
    │       → AVL：高度差 ≤ 1
    │       → Red-Black：黑高相等
    │
    ├─► (d) AVL 怎麼維持平衡？→ 旋轉
    │       → LL/RR：單旋轉
    │       → LR/RL：雙旋轉
    │
    └─► 進階：範圍查詢？
            → O(log n + k)
            → 動態資料的最佳選擇

概念	重點
BST Property	左 < 根 < 右，中序有序
操作複雜度	$O(h)$，退化時 $h = n$
AVL Tree	$\\|BF\\| \leq 1$，$h \leq 1.44 \log n$
Red-Black Tree	五性質，$h \leq 2 \log n$，旋轉少
Range Query	$O(\log n + k)$

< 上一題：QoS 優先權管理 | 返回目錄 | 下一題：最短路徑計算 >

操作	時間複雜度
search	\(O(h)\)
insert	\(O(h)\)
find_min	\(O(h)\)
find_max	\(O(h)\)