112 年 國立臺灣大學生物機電系碩士班丁組《資料結構（A）》

核心觀念

本題考查兩個重點：

1. 2-3 樹的結構與平衡性質
2. 以紅黑樹模擬 2-3 樹的方式與優點

2-3 樹是一種高度平衡的多路搜尋樹。每個內部節點只能是：

• 2-node：包含 1 個鍵值、2 個子樹
• 3-node：包含 2 個鍵值、3 個子樹

所有葉節點都位於相同深度，因此搜尋、插入與刪除的時間複雜度皆為 $O(\log n)$。

---

解題方法

判斷 2-3 樹時，應從「節點可容納的鍵值數量」與「所有葉節點深度是否相同」切入；說明紅黑樹的優勢時，則觀察它如何將多路節點轉換成一般二元搜尋樹節點。

（a）2-3 樹的定義與結構

2-3 樹是一種階數為 3 的平衡搜尋樹，具有以下性質。

1. 節點類型

2-node

2-node 含有一個排序鍵值 $K$，以及兩個子樹：

$$T_0 \quad K \quad T_1$$

其中：

• $T_0$ 中所有鍵值小於 $K$
• $T_1$ 中所有鍵值大於 $K$

3-node

3-node 含有兩個排序鍵值 $K_1,K_2$，以及三個子樹：

$$T_0 \quad K_1 \quad T_1 \quad K_2 \quad T_2$$

且必須滿足：

$$\text{keys}(T_0)<K_1<\text{keys}(T_1)<K_2<\text{keys}(T_2)$$

因此，2-3 樹同時具備搜尋樹的排序性與多路分支能力。

2. 所有葉節點等深

2-3 樹最重要的平衡條件是：

所有葉節點必須位於相同層級。

這使樹高不會因資料插入順序而嚴重偏斜。

若樹高為 $h$，則每個內部節點至少有 2 個子樹、最多有 3 個子樹，因此節點數量介於：

$$2^h \leq n+1 \leq 3^h$$

所以：

$$\log_3(n+1)\leq h\leq \log_2(n+1)$$

可知：

$$h=\Theta(\log n)$$

3. 搜尋、插入與刪除

搜尋

在目前節點中比較搜尋鍵值：

• 若節點為 2-node，依大小選擇左子樹或右子樹。
• 若節點為 3-node，依大小選擇三個子樹之一。

由於樹高為 $O(\log n)$，搜尋時間為：

$$O(\log n)$$

插入

插入通常先從根節點向下搜尋，將新鍵值放入適當的葉節點。

若節點由 2-node 插入一個鍵值，可直接成為 3-node：

$$[K]\longrightarrow [K,X]$$

若 3-node 再插入鍵值，會暫時產生三個鍵值，此時必須：

1. 將三個鍵值排序。
2. 將中間鍵值向上提升父節點。
3. 左右兩個鍵值分裂成兩個 2-node。
4. 若父節點也滿了，持續向上分裂。

若根節點分裂，樹高增加 1，但仍維持所有葉節點等深。

刪除

刪除時若造成節點鍵值不足，需透過：

• 向兄弟節點借鍵值
• 與兄弟節點合併
• 配合父節點鍵值下移

來恢復 2-3 樹的節點規則與平衡性。

---

（b）使用紅黑樹實作 2-3 樹概念的優點

紅黑樹是一種加入顏色資訊的二元搜尋樹。它利用「紅色連結」表示同一個 3-node 中的兩個鍵值。

1. 2-node 與 3-node 的對應

一個 2-node 可直接對應一個黑色節點：

   [K]                 K(black)

一個 3-node：

$$[K_1,K_2]$$

可用一個黑色節點與一個紅色子節點表示：

      K2(black)
      /
 K1(red)

或採用相反方向：

 K1(black)
       \
       K2(red)

紅色節點代表與其黑色父節點屬於同一個 2-3 樹節點；黑色節點之間的連結則代表 2-3 樹中不同層級的連結。

2. 維持近似平衡

紅黑樹的主要性質包括：

1. 每個節點非紅即黑。
2. 根節點為黑色。
3. 空葉節點視為黑色。
4. 紅色節點的子節點必須為黑色，不能出現連續紅色。
5. 從任一節點到其所有後代空葉節點的黑色節點數量相同，稱為 black-height。

核心觀念

最小堆積（min-heap）必須同時符合：

1. 完全二元樹：題目已說明輸入以 heap 陣列儲存，因此其樹形結構視為完全二元樹。
2. 最小堆積性質：每個父節點值不得大於其子節點：

$$A[\text{parent}] \leq A[\text{child}]$$

因此，只要存在任一父節點大於子節點，即可判定輸入不是 min-heap。

採用 0-based 陣列索引時，索引為 $i$ 的節點：

$$\text{left}(i)=2i+1$$ $$\text{right}(i)=2i+2$$

解題方法

逐一檢查每個節點的左右子節點：

• 若左子節點存在，檢查 $A[i]\leq A[2i+1]$。
• 若右子節點存在，檢查 $A[i]\leq A[2i+2]$。
• 任一條件不成立，立即回傳 false。
• 全部檢查通過，回傳 true。

只需檢查前 $\lfloor (n-2)/2 \rfloor+1$ 個節點，因為後半段節點都是葉節點，沒有子節點可供比較。

Pseudocode

function isMinHeap(A, n):
    for i ← 0 to floor((n - 2) / 2):
        left ← 2 * i + 1
        right ← 2 * i + 2

        if A[i] > A[left]:
            return false

        if right < n and A[i] > A[right]:
            return false

    return true

其中左子節點對於所有迴圈中的 $i$ 都存在；右子節點則必須先確認 right < n。

更通用、同時檢查左右子節點存在性的寫法如下：

核心觀念

題目要求找出所有「有直接邊指向指定頂點 $v$」的頂點，也就是尋找 $v$ 的所有入鄰點（in-neighbors）。

在標準的 adjacency-list representation 中，每個頂點的串列通常記錄「從該頂點出發」的 outgoing edges。因此，若要判斷哪些頂點有邊指向 $v$，必須檢查所有頂點的 adjacency list。

解題方法

逐一掃描所有 $V$ 個頂點的 adjacency list：

1. 掃描每個頂點本身，需要花費 $\Theta(V)$。
2. 每條有向邊只需被檢查一次，所有 adjacency list 中共有 $E$ 條邊，因此花費 $\Theta(E)$。
3. 找到邊 $(u,v)$ 時，即可判定 $u$ 是所求的入鄰點。

總執行時間為

$$\Theta(V)+\Theta(E)=\Theta(V+E)$$

因此，其 order of growth 為

$$O(V+E)$$

更精確地說是 $\Theta(V+E)$。

選項分析

本題未提供選項，因此無需逐項判斷。若選項中出現：

核心觀念

強連通分量（Strongly Connected Component, SCC）是指有向圖中的極大頂點集合，使集合內任意兩個頂點 $u,v$ 都滿足：

$$u \leadsto v \quad\text{且}\quad v \leadsto u$$

其中 $\leadsto$ 表示存在有向路徑。

有向無環圖（DAG, Directed Acyclic Graph）不含任何有向環。若一個 SCC 包含兩個以上不同頂點，則其中必定存在兩頂點可相互抵達，沿著相互抵達的路徑即可形成有向環，這與 DAG 的定義矛盾。

因此，DAG 中每個 SCC 只能包含單一頂點。

解題方法

對 DAG 的每一個頂點 $v$ 而言，單獨的集合 $\{v\}$ 一定構成 SCC，因為頂點可透過長度為 $0$ 的路徑抵達自身。

核心觀念

Queue（佇列）遵守先進先出（FIFO, First-In First-Out）：

• 新元素由隊尾（rear）加入，稱為 enqueue。
• 元素由隊首（front）移除，稱為 dequeue。

使用單向鏈結串列實作時，若同時維護 front 與 rear 指標：

• 從串列前端插入：$O(1)$
• 從串列前端刪除：$O(1)$
• 從串列尾端插入：有 rear 指標時為 $O(1)$
• 從串列尾端刪除：單向鏈結串列通常為 $O(n)$，因為必須找到尾端節點的前一個節點。

解題方法

判斷兩種設計的效率，重點在於檢查 enqueue 與 dequeue 是否都能在 $O(1)$ 時間內完成。

標準做法是：

• front 指向隊首，負責 dequeue。
• rear 指向隊尾，負責 enqueue。

因此，加入新節點時，直接接在 rear 後方即可；移除節點時，直接刪除 front 所指的節點即可。兩項操作都不需要走訪整條鏈結串列。

選項分析

(a) insert at the front and remove from the end

核心觀念

本題比較四種優先佇列（priority queue）的實作方式，要求分析兩項操作的最壞時間複雜度：

1. insert：插入一個新元素。
2. delete-max：刪除並回傳目前最大元素。

分析時須觀察：

• 最大元素是否能直接定位。
• 插入時是否需要移動或調整其他元素。
• 樹的高度是否有上限。
• 最壞情況下，結構是否可能退化。

以下以 $N$ 表示優先佇列目前的元素數量。

---

解題方法

逐一檢查每種資料結構執行兩項操作所需的步驟數：

• 若只需固定次數的指標或索引操作，為 $O(1)$。
• 若最多需要走訪或搬移 $N$ 個元素，為 $O(N)$。
• 若需沿著樹高進行調整，複雜度為 $O(h)$；二元堆的高度為 $O(\log N)$，一般二元搜尋樹的最壞高度則可能達到 $O(N)$。

---

各實作分析

（a）Unordered linked list

未排序鏈結串列中的元素沒有依照大小排列。

insert

新元素可直接插入串列頭端，只需建立節點並調整少數指標：

$$T_{\text{insert}}(N)=O(1)$$

delete-max

由於串列未排序，必須從頭到尾走訪所有節點，才能找出最大元素。找到最大值後，還需調整其前後節點的連結：

$$T_{\text{delete-max}}(N)=O(N)$$

因此：

$$\boxed{O(1),\ O(N)}$$

---

（b）Ordered array

有序陣列通常依遞增順序排列，因此最大元素位於陣列最後端。

insert

插入新元素時，必須找到正確位置，並將其後方的元素向右搬移，以保持陣列有序。

最壞情況是新元素必須插入陣列最前端，此時最多需要搬移 $N$ 個元素：

$$T_{\text{insert}}(N)=O(N)$$

delete-max

最大元素位於陣列最後端，直接刪除最後一個元素即可，不需搬移其他元素：

$$T_{\text{delete-max}}(N)=O(1)$$

因此：

$$\boxed{O(N),\ O(1)}$$

---

（c）Binary heap

以最大堆（max-heap）實作優先佇列時，根節點永遠是最大元素。

二元堆是一棵近似完全二元樹，其高度為：

$$h=\Theta(\log N)$$

insert

插入時，先將新元素放在堆的下一個可用位置，再依序與父節點比較並向上調整，此程序稱為上浮（swim 或 bubble-up）。

最壞情況下，新元素會一路上浮至根節點，最多經過樹高 $O(\log N)$ 層：

$$T_{\text{insert}}(N)=O(\log N)$$

delete-max

最大元素位於根節點。刪除根節點後，將最後一個元素移至根部，再依序與較大的子節點交換並向下調整，此程序稱為下沉（sink 或 bubble-down）。

最壞情況下，元素會一路下沉至葉節點，最多經過 $O(\log N)$ 層：

$$T_{\text{delete-max}}(N)=O(\log N)$$

因此：

核心觀念

本題考查「以 bottom-up heap construction 建立 heap」以及其線性時間證明。

以最大堆（max-heap）為例，heap 必須同時滿足：

1. 完全二元樹：除了最後一層外，其餘各層皆填滿，最後一層由左至右排列。
2. 堆積性質：每個父節點的鍵值不小於其子節點，即
   $A[\operatorname{parent}(i)] \geq A[i]$

若使用逐一插入的方式建立 heap，每次插入可能需向上調整 $O(\log n)$，總時間為 $O(n\log n)$。本題要求線性時間，應採用 Floyd 提出的 bottom-up heapify。

---

解題方法：由下而上調整

將所有元素先依序放入陣列，形成一棵完全二元樹，但此時尚未必符合堆積性質。

對於以 1 為起始索引的陣列：

• 節點 $i$ 的左子節點為 $2i$
• 節點 $i$ 的右子節點為 $2i+1$
• 葉節點的索引範圍為
  $\left\lfloor \frac{n}{2}\right\rfloor+1,\ldots,n$
• 非葉節點的索引範圍為
  $\left\lfloor \frac{n}{2}\right\rfloor,\ldots,1$

因此，從最後一個非葉節點開始，依序向前對每個節點執行 sift-down：

for i = floor(n/2) downto 1
    sift-down(A, i)

s i f t - d o w n 的作用是：假設節點 $i$ 的左右子樹已經是 heap，將 $A[i]$ 向下交換至適當位置，使以 $i$ 為根的整棵子樹成為 heap。

以最大堆為例，調整步驟如下：

1. 比較目前節點與其左右子節點。
2. 找出鍵值較大的子節點。
3. 若父節點小於該子節點，便交換。
4. 繼續向下調整，直到滿足堆積性質或抵達葉節點。

---

為何必須由下而上？

當處理節點 $i$ 時，它的左右子樹已經先被處理完成，因此皆已是合法的 heap。此時只需將根節點 $A[i]$ 向下移動，即可修正以 $i$ 為根的子樹。

若由上而下處理，子樹尚未完成，無法直接利用已建立的 heap 結構，也無法得到線性時間的保證。

---

線性時間證明

表面上看來，每個節點執行 sift-down 最壞需要 $O(\log n)$，但並非所有節點都位於樹的高處：

• 葉節點數量約為 $n/2$，不需調整。
• 高度為 $1$ 的節點約為 $n/4$。
• 高度為 $2$ 的節點約為 $n/8$。
• 高度為 $h$ 的節點數量至多約為
  $\frac{n}{2^{h+1}}$

高度為 $h$ 的節點最多向下移動 $h$ 層，因此總成本為