109 年 國立臺灣大學電機工程研究所丙組《資料結構（B）》

核心觀念

本題考查雜湊表的「線性探測法（linear probing）」。

雜湊表共有 $13$ 個槽位，索引為 $0$ 至 $12$。對鍵值 $k$，第 $i$ 次探測的位置為：

$$h(k,i)=(k+i)\bmod 13$$

其中：

• 第 $0$ 次探測：先檢查 $k\bmod 13$
• 若該位置已被占用，則依序檢查下一格
• 探測到索引 $12$ 後，會循環回索引 $0$

插入鍵值時，必須按照題目指定的順序進行，因為先前插入的資料會影響後續碰撞結果。

解題方法

依序計算每個鍵值的初始位置，遇到碰撞時採用線性探測。

插入順序	鍵值	初始位置 $k\bmod 13$	探測結果	最終位置
1	$66$	$66\bmod 13=1$	槽位 $1$ 空	$1$
2	$4$	$4\bmod 13=4$	槽位 $4$ 空	$4$
3	$84$	$84\bmod 13=6$	槽位 $6$ 空	$6$
4	$91$	$91\bmod 13=0$	槽位 $0$ 空	$0$
5	$100$	$100\bmod 13=9$	槽位 $9$ 空	$9$
6	$72$	$72\bmod 13=7$	槽位 $7$ 空	$7$
7	$70$	$70\bmod 13=5$	槽位 $5$ 空	$5$
8	$37$	$37\bmod 13=11$	槽位 $11$ 空	$11$

此時已占用的槽位為：

核心觀念

本題考查「由未排序陣列建立 Binary Heap」的時間複雜度。常見建堆方法有兩種：

1. 逐一插入元素：每次插入最多需上浮 $O(\log n)$，總複雜度為 $O(n\log n)$。
2. Floyd bottom-up 建堆法：從最後一個非葉節點開始，依序向前執行下沉（heapify），總複雜度可達 $O(n)$。

題目問的是最佳的標準建堆方法之最壞情況複雜度，因此應採用 Floyd bottom-up 建堆法。

---

解題方法：Floyd bottom-up 建堆法

將陣列視為一棵近似完全二元樹。葉節點本身已符合 Heap 性質，因此只需從最後一個非葉節點開始，對每個節點執行下沉操作。

對高度為 $h$ 的節點，下沉最多需移動 $h$ 層，因此所需時間為 $O(h)$。

在完全二元樹中，高度為 $h$ 的節點數量至多約為：

$$\frac{n}{2^{h+1}}$$

因此，所有節點進行 heapify 的總成本為：

$$T(n) \leq \sum_{h=0}^{\log n} \frac{n}{2^{h+1}}O(h)$$

整理得：

$$T(n) = O\left( n\sum_{h=0}^{\log n}\frac{h}{2^h} \right)$$

而級數

$$\sum_{h=0}^{\infty}\frac{h}{2^h}$$

收斂為常數，因此：

$$T(n)=O(n)$$

此外，建立 Heap 至少必須讀取並處理所有 $n$ 個元素，因此下界為 $\Omega(n)$。綜合上下界：

$$T(n)=\Theta(n)$$

所以其最壞情況時間複雜度為 $O(n)$。

---

選項分析

• (A) $O(n)$：正確

核心觀念

Binary heap 是一棵完全二元樹，並滿足 min-heap 性質：每個父節點的鍵值都小於或等於子節點。因此，最小值必定位於根節點。

Binary heap 的高度為

$$h=\lfloor \log_2 n \rfloor=O(\log n)$$

delete-min 必須移除根節點，並維持 heap 性質。

解題方法

執行一次 delete-min 的步驟如下：

1. 移除根節點，也就是最小值。
2. 將最後一個節點移到根的位置。
3. 由根向下進行 sift-down，每次與較小的子節點交換，直到恢復 min-heap 性質。

每一層只需進行固定次數的比較與交換，因此每層耗時為 $O(1)$。最壞情況下，新根元素一路下沉至葉節點，最多經過 heap 高度 $h$ 層：

$$T(n)=O(h)=O(\log n)$$

若輸入排列使得替代根元素必須一路下沉，確實會經過 $\Theta(\log n)$ 層，因此最壞情況為

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

選項分析

• (A) $O(1)$：錯誤。
  移除根節點本身是常數時間，但將最後一個節點移至根後，可能需要一路向下調整，最多經過 $\Theta(\log n)$ 層。

核心觀念

本題考查二元堆積（binary heap）的合併（union）效率，以及「自底向上建堆」的時間複雜度。

二元堆積具有：

• 完全二元樹結構；
• 最大堆中每個父節點皆不小於子節點，最小堆則相反；
• 若共有 $n$ 個元素，自底向上建堆的時間複雜度為 $O(n)$。

兩個二元堆積合併後，只需將兩者的元素放在同一個陣列中，再重新調整成一個合法的二元堆積。

---

解題方法

設兩個 binary heaps 的大小分別為 $n_1$ 與 $n_2$，且

$$n_1+n_2=n$$

合併步驟如下：

1. 將兩個 heap 的陣列直接串接，花費

$$O(n_1+n_2)=O(n)$$

2. 對合併後陣列執行自底向上的 Build-Heap。

雖然單一節點的 heapify 最壞可能花費 $O(\log n)$，但所有節點的總成本不是 $n\log n$。靠近樹葉的節點高度很低，只有少數節點具有較高高度，因此總和為

$$\sum_{h\ge 0}\frac{n}{2^{h+1}}O(h) = O\left( n\sum_{h\ge 0}\frac{h}{2^h} \right) = O(n)$$

所以整個 union 操作的時間複雜度為

$$O(n)+O(n)=O(n)$$

因此正確選項為 (D)。

---

選項分析

• (A) $O(1)$：錯誤。
  兩個 heap 的所有元素必須被納入合併後的 heap。輸入規模為 $n$，至少需要處理這些元素，時間不可能固定為常數。

核心觀念

二項堆（Binomial Heap）由數棵不同階數的二項樹組成，且每個階數至多一棵。對含有 $m$ 個元素的二項堆而言，最多有

$$\lfloor \log_2 m \rfloor+1=O(\log m)$$

棵根節點。

插入一個元素時，會先建立一棵 $B_0$ 二項樹，再與原有二項堆合併。若發生相同階數的二項樹，便需反覆合併並進位，因此單次插入的最壞時間複雜度為

$$O(\log m).$$

解題方法

題目詢問的是 $n$ 次連續插入操作的最壞情況。每次插入最多處理 $O(\log n)$ 個階數，因此逐次累加：

$$\underbrace{O(\log n)+O(\log n)+\cdots+O(\log n)}_{n\text{ 次}} =O(n\log n).$$

因此選擇

$$\boxed{O(n\log n)}.$$

選項分析

• (A) $O(n)$：錯誤。
  $O(n)$ 是在採用攤銷分析時，連續 $n$ 次插入可得到的典型總成本；但題目問的是最壞情況時間複雜度，不能直接使用攤銷成本取代單次操作的最壞成本。

核心觀念

二項堆（binomial heap）由不同階數的二項樹組成，且每個階數至多一棵。大小為 $2^k$ 的二項樹稱為 $B_k$，其根節點度數為 $k$。

二項堆的根串列至多包含

$$\lfloor \log_2 n \rfloor+1$$

個根節點，因此根串列長度為 $O(\log n)$。

插入一個元素時，先建立一棵單節點二項樹 $B_0$，再將它與原二項堆合併。若原堆中已存在 $B_0$，兩棵 $B_0$ 會合併成一棵 $B_1$；若又存在 $B_1$，則繼續合併成 $B_2$，形成類似二進位加法的進位鏈。

解題方法

將插入視為對二項堆進行一次「二進位進位」：

• 沒有 $B_0$ 時，插入只需加入根串列，時間為 $O(1)$。
• 若已有 $B_0$，就合併成 $B_1$。
• 若已有 $B_0,B_1,\ldots,B_{k-1}$，插入後可能連續合併 $k$ 次，直到形成 $B_k$。

由於二項堆最多只有 $O(\log n)$ 種不同階數，因此最壞情況下最多進行 $O(\log n)$ 次二項樹合併。每次合併只需比較兩個根節點並調整指標，成本為 $O(1)$。

因此，一次插入的最壞時間複雜度為

$$O(\log n).$$

例如，若目前根串列對應的階數狀態類似二進位數

$$111\ldots111,$$

插入新的 $B_0$ 後，會產生連續進位：

$$B_0\rightarrow B_1\rightarrow B_2\rightarrow \cdots,$$

最長進位鏈的長度與 $\log n$ 同階。

選項分析

核心觀念

Binomial heap 由多棵 binomial tree 組成，且每種階數的 binomial tree 至多一棵。若 heap 大小為 $n$，其根串列中的樹數量最多為：

$$\lfloor \log_2 n \rfloor + 1 = O(\log n)$$

Binomial heap 的最小元素必定位於某棵 binomial tree 的根節點，因為每棵樹皆符合 min-heap 性質。因此，find-min 只需掃描所有根節點，找出鍵值最小者。

解題方法

逐一檢查根串列中的根節點：

1. 取得根串列中所有 binomial tree 的根。
2. 維護目前最小鍵值。
3. 掃描最多 $O(\log n)$ 個根節點。
4. 回傳其中鍵值最小的根。

因此：

$$T(n)=O(\text{根節點數量})=O(\log n)$$

故標準 binomial heap 未額外維護最小值指標時，find-min 的最壞時間複雜度為：

$$\boxed{O(\log n)}$$

選項分析

• (A) $O(1)$：錯誤。
  若實作額外維護指向最小根節點的指標，find-min 才能達到 $O(1)$。

核心觀念

Fibonacci heap 的 insert 操作會：

1. 建立一個新的樹節點。
2. 將該節點直接加入根串列。
3. 若新節點的鍵值小於目前最小值，更新最小值指標。
4. 增加堆積中的節點數量。

插入時不需要進行合併（consolidation），也不需要調整樹高。因此，這些步驟都只需固定次數的指標操作。

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

需注意：Fibonacci heap 的 insert 不僅是攤銷時間 $O(1)$，其單次操作的最壞情況時間也為 $O(1)$。真正需要攤銷分析的是 extract-min、decrease-key 等可能引發大量級聯操作的程序。

解題方法

判斷 Fibonacci heap 插入的實際操作：

• 新節點加入根串列：$O(1)$。
• 比較新節點與最小節點：$O(1)$。
• 必要時更新最小值指標：$O(1)$。
• 更新節點數量：$O(1)$。

總時間為固定數量的常數操作，因此：

$$O(1)+O(1)+O(1)+O(1)=O(1)$$

所以正確選項為 (A)。

選項分析

• (A) $O(1)$：正確。
  插入只需將新節點放入根串列，並可能更新最小值指標，不需依照 $n$ 進行搜尋或重組。

在 Fibonacci 堆中，decrease‑key 會把目標節點的鍵值減小，若此鍵值小於其父節點的鍵值，必須切割該節點並將其加入根列表。若被切割的節點之前已經是「標記」的子節點，則會遞迴向上切割其父節點，這個過程稱為級聯切割（cascading cut）。

每次切割會把一個節點從其原本的樹中抽出，使根列表的樹數增加。根列表中樹的最大度（degree）受到如下性質限制：

核心觀念

本題考查 Fibonacci heap 中 delete-min 的攤銷時間複雜度。

Fibonacci heap 的重要複雜度如下：

• insert：攤銷 $O(1)$
• find-min：$O(1)$
• decrease-key：攤銷 $O(1)$
• delete-min：攤銷 $O(\log n)$

delete-min 會刪除最小根節點，將其子節點移至根串列，再進行 consolidation，合併相同 degree 的樹。雖然單次合併可能需要處理許多根節點，但透過勢能法分析，其攤銷成本為 $O(\log n)$。

---

解題方法

設目前 Fibonacci heap 中的節點數不超過原始大小 $n$。

單次 delete-min 的攤銷時間為：

$$\widehat{T}_{\text{delete-min}}=O(\log n)$$

連續執行 $n$ 次時，總時間上界為：

$$n\cdot O(\log n)=O(n\log n)$$

也可以從勢能函數理解。Fibonacci heap 常用的勢能函數為：

$$\Phi(H)=t(H)+2m(H)$$

其中：

• $t(H)$：根串列中的樹數量
• $m(H)$：被標記的節點數量

delete-min 可能暫時增加實際操作量，但 consolidation 會大量合併根樹，使根串列最後只剩下 $O(\log n)$ 棵樹。由於勢能的下降可抵銷部分實際成本，單次攤銷成本仍為 $O(\log n)$。

因此：

$$\boxed{n\text{ 次 delete-min 的總時間為 }O(n\log n)}$$

---

選項分析

核心觀念

Fibonacci heap 的 decrease-key 主要成本來自 cascading cut（級聯切割）：

1. 將節點鍵值降低。
2. 若違反父子關係，將該節點從父節點切下，移至 root list。
3. 若父節點已經被標記，則繼續向上級聯切割。

一次 decrease-key 最壞可能沿著樹的路徑切割大量節點。對大小為 $n$ 的 Fibonacci heap 而言，最壞可達 $O(n)$。

---

解題方法

單次操作的最壞時間為：

$$T_{\text{decrease-key}}(n)=O(n)$$

因此，連續執行 $n$ 次 decrease-key，其最壞總時間為：

$$n\cdot O(n)=O(n^2)$$

Fibonacci heap 常見的 $O(1)$ 是 decrease-key 的攤銷時間，不是單次操作的最壞時間。題目明確問的是 worst case，因此要使用最壞時間分析。

---

選項分析

• (A) $O(n)$：錯誤。
  這是將 decrease-key 的攤銷時間 $O(1)$ 乘上 $n$ 次所得的結果，屬於攤銷分析，不是本題要求的最壞情況分析。

核心觀念

Leftist heap（左偏樹）同時具備：

1. Heap-order property：父節點的鍵值不大於子節點，因此最小值必定位於根節點。
2. Leftist property：每個節點的右子樹空路徑長度較短，用來保證合併操作的效率。

find-min 只需回傳根節點的鍵值，不需要走訪其他節點。若以指標直接維護根節點，取出根節點即完成操作。

解題方法

設左偏樹的根節點指標為 root，則：

$$\text{find-min()} = \text{return } root.key$$

此操作只包含一次根節點存取，執行時間與節點總數 $n$ 無關，因此：

$$T(n)=\Theta(1)$$

最壞情況也同樣只需存取根節點，所以時間複雜度為：

$$O(1)$$

因此正確選項為 (A)。

選項分析

• (A) $O(1)$：正確。
  左偏樹符合 heap-order property，最小元素位於根節點；find-min 直接讀取根節點即可完成。

• (B) $O(\log^* n)$：錯誤。
  此複雜度不是左偏樹 find-min 的標準複雜度。find-min 不需要依照樹高或特殊函數進行搜尋。

核心觀念

Leftist heap（左偏樹）同時具備：

1. Heap-order property：父節點的鍵值不大於子節點，因此最小值必定位於根節點。
2. Leftist property：每個節點的右子樹空路徑長度較短，用來保證合併操作的效率。

find-min 只需回傳根節點的鍵值，不需要走訪其他節點。若以指標直接維護根節點，取出根節點即完成操作。

解題方法

設左偏樹的根節點指標為 root，則：

$$\text{find-min()} = \text{return } root.key$$

此操作只包含一次根節點存取，執行時間與節點總數 $n$ 無關，因此：

$$T(n)=\Theta(1)$$

最壞情況也同樣只需存取根節點，所以時間複雜度為：

$$O(1)$$

因此正確選項為 (A)。

選項分析

• (A) $O(1)$：正確。
  左偏樹符合 heap-order property，最小元素位於根節點；find-min 直接讀取根節點即可完成。

• (B) $O(\log^* n)$：錯誤。
  此複雜度不是左偏樹 find-min 的標準複雜度。find-min 不需要依照樹高或特殊函數進行搜尋。

核心觀念

AVL tree 是一種高度平衡的二元搜尋樹，對每個節點都必須滿足：

$$|\text{左子樹高度}-\text{右子樹高度}|\le 1$$

要找「100 個節點的 AVL tree 高度上限」，必須思考：

在固定高度下，符合 AVL 平衡條件所需的最少節點數是多少？

高度越高，所需的最少節點數越多。因此，只要找出「最少節點數不超過 100 的最大高度」即可。

以下採用資料結構常用定義：葉節點高度為 $0$，高度以最長邊數計算。

---

解題方法

令 $N(h)$ 表示高度為 $h$ 的 AVL tree 所需的最少節點數。

為了讓高度為 $h$ 且節點數最少，左右子樹的高度必須盡量小，同時仍維持 AVL 平衡，因此兩棵子樹的高度為：

$$h-1 \quad\text{與}\quad h-2$$

所以有遞迴式：

$$N(h)=N(h-1)+N(h-2)+1$$

其中：

• 高度 $0$：只有一個根節點，因此 $N(0)=1$
• 高度 $1$：根節點加上兩個葉節點，因此 $N(1)=2$

逐步計算：

$$\begin{aligned} N(0)&=1\\ N(1)&=2\\ N(2)&=2+1+1=4\\ N(3)&=4+2+1=7\\ N(4)&=7+4+1=12\\ N(5)&=12+7+1=20\\ N(6)&=20+12+1=33\\ N(7)&=33+20+1=54\\ N(8)&=54+33+1=88\\ N(9)&=88+54+1=143 \end{aligned}$$

因此：

核心觀念

2-3-4 tree 是一種平衡搜尋樹，具有以下性質：

• 每個內部節點至少有 $2$ 個子節點，最多有 $4$ 個子節點。
• 所有葉節點位於相同深度。
• 樹高通常定義為「根節點到最深葉節點的邊數」，根節點高度為 $0$。

要讓節點數固定時樹高最大，必須使每一層的分支數最少，也就是每個內部節點都只有 $2$ 個子節點。

解題方法

設樹高為 $h$。當每個內部節點都只有 $2$ 個子節點時，各層的最少節點數為：

$$1,2,2^2,\ldots,2^h$$

因此，高度為 $h$ 的 2-3-4 tree 至少包含：

$$1+2+2^2+\cdots+2^h =2^{h+1}-1$$

題目給定節點總數為 $255$，因此必須滿足：

$$2^{h+1}-1\leq 255$$ $$2^{h+1}\leq 256=2^8$$ $$h+1\leq 8$$ $$h\leq 7$$

而且高度 $7$ 確實可以達成，因為：

$$1+2+4+\cdots+128=255$$

也就是一棵每個內部節點都恰有 $2$ 個子節點的完全平衡樹。

選項分析

核心觀念

Binomial heap 是由多棵 binomial tree 組成，且每種階數至多一棵。

階數為 $k$ 的 binomial tree 記為 $B_k$，具有：

• 節點數：$2^k$
• 根節點的 degree：$k$

因此，若 heap 中存在階數為 $k$ 的 binomial tree，至少需要有 $2^k$ 個 items。含有 $n$ 個 items 的 binomial heap，其最大階數為：

$$\left\lfloor \log_2 n \right\rfloor$$

解題方法

本題有 $2020$ 個 items，計算：

$$2^{10}=1024,\qquad 2^{11}=2048$$

因為：

$$1024 \le 2020 < 2048$$

所以：

$$\left\lfloor \log_2 2020 \right\rfloor=10$$

也可由二進位分解理解：

$$2020=1024+512+256+128+64+32+16+8+4$$

其中最大的 $2^k$ 為 $2^{10}=1024$，因此 heap 中可能包含一棵 $B_{10}$，但不可能包含 $B_{11}$，因為 $B_{11}$ 單獨就需要 $2048$ 個節點。

選項分析

核心觀念

Fibonacci heap 中，若某個樹根的階（order）為 $k$，即其 degree 為 $k$，則該樹所能包含的最少節點數為：

$$S(k)=F_{k+2}$$

其中 Fibonacci 數列定義為：

$$F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}$$

因此，題目詢問「order 6 的最小 Fibonacci heap」，就是求 degree 為 $6$ 的 Fibonacci 樹，其最少節點數。

解題方法

逐步計算 Fibonacci 數列：

$$F_0=0$$ $$F_1=1$$ $$F_2=1,\quad F_3=2,\quad F_4=3,\quad F_5=5$$ $$F_6=8,\quad F_7=13,\quad F_8=21$$

由最小節點數公式：

$$S(6)=F_{6+2}=F_8=21$$

所以最小 Fibonacci heap 的節點數為 $21$。

選項分析

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）與 AVL 樹的高度及基本操作複雜度。

對含有 $n$ 個節點的二元樹：

• 若樹高為 $h$，搜尋、插入、刪除等沿樹根至葉節點進行的操作，時間複雜度通常為 $O(h)$。
• 一般 BST 不保證平衡，最壞情況可能退化成鏈結串列，此時 $h=\Theta(n)$。
• AVL 樹是高度平衡的 BST，保證 $h=\Theta(\log n)$。

AVL 樹的平衡條件為每個節點的左右子樹高度差至多為 $1$：

$$\left|h_{\text{left}}-h_{\text{right}}\right|\leq 1$$

因此 AVL 樹高度為 $O(\log n)$。

---

解題方法

逐一判斷各敘述是否對所有大小為 $n$ 的樹都成立。關鍵在於：

$$\text{操作時間} = O(\text{樹高})$$

再分辨該資料結構是否保證高度為 $O(\log n)$。

---

選項分析

(A) The search operation in a binary search tree of size n is $O(\log n)$.

錯誤。

一般 BST 不保證平衡。若插入資料已經按照遞增順序排列，BST 可能退化如下：

$$1\rightarrow 2\rightarrow 3\rightarrow \cdots \rightarrow n$$

此時樹高為：

$$h=\Theta(n)$$

搜尋最深層節點需走訪 $\Theta(n)$ 個節點，因此最壞時間複雜度為：

$$\Theta(n)$$

只有在 BST 額外保證平衡時，搜尋才是 $O(\log n)$。

---

(B) The height of a binary search tree of size n is $\Theta(\log n)$.

錯誤。

一般 BST 的高度取決於節點排列方式：

• 完全平衡時：

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

• 退化成鏈結串列時：

$$h=\Theta(n)$$

因此一般 BST 的高度只能表示為：

$$\Omega(\log n)\leq h\leq O(n)$$

不能保證為 $\Theta(\log n)$。

---

核心觀念

AVL 樹要求每個節點左右子樹高度差至多為 $1$。插入或刪除後，若節點失衡，就依失衡方向旋轉：

• LL、RR 型：單旋轉。
• LR、RL 型：雙旋轉。

判斷選項時，沿二元搜尋樹的路徑找到插入或刪除位置，再由下往上檢查是否失衡及所需旋轉。

解題方法與選項分析

原樹中與本題相關的結構如下：

• 根節點 $50$ 的右子樹為 $67$；$67$ 的左子為 $61$（左子為 $55$），右子為 $80$（左子為 $75$，右子為 $87$，而 $87$ 的右子為 $95$）。
• $50$ 的左子樹根為 $13$；$13$ 的左子為 $4$（左子為 $1$），右子為 $35$。$35$ 的左子為 $23$（左右子分別為 $18、27$），右子為 $41$。

(A) 正確。
插入 $66$ 的搜尋路徑為 $50 \to 67 \to 61$，接著 $66$ 成為 $61$ 的右子。此時 $61$ 的左右子樹高度相同，$67$ 仍符合 AVL 平衡條件，不需旋轉。因此 $66$ 的父節點是 $61$。

(B) 正確。
插入 $99$ 後，它成為 $95$ 的右子。節點 $87$ 因右側過高而呈 RR 型失衡，對 $87$ 做左旋，局部結構變成：

$$\begin{array}{c} 95\\ /\quad\backslash\\ 87\quad99 \end{array}$$

因此 $95$ 有兩個子節點。

核心觀念

紅黑樹（Red-Black Tree）是一種具有平衡性質的二元搜尋樹。每個節點具有紅色或黑色，並遵守以下條件：

1. 根節點為黑色。
2. 每個節點為紅色或黑色。
3. 紅色節點的子節點必須為黑色，因此不會出現連續兩個紅色節點。
4. 從任一節點到其所有外部節點（通常以黑色的 NIL 節點表示）的路徑，黑色節點數量相同。
5. 紅黑樹的高度為 $O(\log n)$)。

其中，從某節點到外部節點路徑上的黑色節點數量稱為 black-height，記為 $bh$。

---

解題方法

本題逐一對照紅黑樹的定義與高度性質判斷。選項中的「root-to-external-node path」指的是從根節點走到外部 NIL 節點的路徑。

紅黑樹的高度為 $h$ 時，由於紅色節點不能連續出現，因此任一路徑上紅色節點數量至多為黑色節點數量。故有：

$$h \leq 2bh$$

另一方面，具有 black-height $bh$ 的紅黑樹至少包含：

$$2^{bh}-1$$

個內部節點，因此：

$$n \geq 2^{bh}-1$$

得到：

$$bh \leq \log_2(n+1)$$

所以：

$$h \leq 2\log_2(n+1)=O(\log n)$$

---

選項分析

(A) The root is always black.

正確。

紅黑樹的標準定義規定根節點必須為黑色。此條件有助於統一路徑上的黑色節點數量定義，也屬於紅黑樹的基本性質。

---

(B) Each node is colored red or black.

正確。

紅黑樹中的每個節點都必須被標記為紅色或黑色，不能出現第三種顏色。

---

(C) No root-to-external-node path has two consecutive red nodes.

核心觀念

紅黑樹操作會依序調整節點顏色與子樹結構，使每條根至外部節點的路徑維持相同黑節點數，且不出現連續紅節點。插入時，新節點先視為紅色，再用旋轉與重新著色修正；刪除黑節點時，若其子節點為紅色，替補後須調整顏色。

將紅節點與其黑色父節點合併，可得到對應的 2-3-4 樹。以下高度以根到最深葉節點的邊數計算。

解題方法

依 Fig.2 的實際結構與顏色判斷各操作：

• 插入 86 的搜尋路徑是 $82\to90\to88\to87\to85$，新節點 86 接在 85 下方。
• 插入 9 的搜尋路徑是 $82\to13\to10$，新節點接在 10 下方。
• 刪除 87 時，紅色節點 85 是黑色節點 87 的子節點。
• 刪除 10 時，沿路向下需處理 13 右側的紅色子樹 51；其後透過旋轉與重新著色，會讓 15 成為 13 的父節點。
• 將圖中紅黑節點合併為 2-3-4 樹後，根到最深一層的路徑有 2 條邊。

選項分析

核心觀念

AA 樹的「層級（level）」與節點在圖上的深度不同，其規則為：

• 空節點的層級為 $0$，新插入的節點層級為 $1$。
• 左子節點的層級必須比父節點低 $1$。
• 右子節點可以與父節點同層級，形成「右水平連結」，但不能連續出現兩條右水平連結。

插入時，先依二元搜尋樹規則找到位置，再由下往上依序執行：

1. skew：若左子節點與父節點同層級，做右旋；節點層級不變。
2. split：若節點、右子節點、右孫節點皆同層級，做左旋，並將旋轉後的新子樹根層級加 $1$。

解題方法

依原圖的水平連結及 AA 樹規則，可得：

層級	節點
$3$	$77$
$2$	$42、63、90$
$1$	$4、15、62、69、79、86、93$

其中 $42\to63$、$4\to15$、$79\to86$ 是右水平連結。各選項的插入操作皆分別從原圖開始，並非連續插入。

選項分析

(A) 錯誤。

節點 $4$ 的層級為 $1$，節點 $63$ 的層級為 $2$，兩者不同層級。$42$ 與 $63$ 才是同層級。

(B) 正確。

$62$ 與 $69$ 都是葉節點，層級皆為 $1$。

(C) 錯誤。

插入 $1$ 時，先將它放在 $4$ 的左側，層級為 $1$，接著向上調整：

1. 在 $4$ 執行 skew，形成同層級的右鏈 $1\to4\to15$。
2. 執行 split，使 $4$ 成為這棵子樹的根，層級升為 $2$；左右子節點分別是 $1$、$15$。
3. 此時 $42$ 與其左子節點 $4$ 同為層級 $2$，在 $42$ 執行 skew，形成同層級的右鏈 $4\to42\to63$。
4. 再執行 split，使 $42$ 成為子樹根，層級升為 $3$；$4$ 與 $63$ 都維持層級 $2$。

核心觀念

雜湊表（Hash Table）利用雜湊函數將 key 映射至表格中的位置：

$$h(\text{key}) \rightarrow \text{index}$$

因此，雜湊表擅長處理「指定 key 是否存在」以及「指定 key 的資料」等操作。設雜湊表中有 $n$ 筆資料，在雜湊函數分布良好且碰撞處理適當時：

• 搜尋指定 key：平均 $O(1)$
• 插入指定 key：平均 $O(1)$
• 刪除指定 key：平均 $O(1)$

雜湊表的索引依據是 key 經過雜湊函數後的結果，並未維持所有 key 的大小順序。因此，找最小 key 或刪除最小 key 並不是標準雜湊表擅長的操作。

---

解題方法

判斷每個選項是否能由雜湊表直接有效支援：

1. 若操作指定一個明確的 key，能直接利用雜湊函數定位，屬於雜湊表的基本操作。
2. 若操作要求找出「全體 key 中最小者」，必須比較許多 key 的大小；雜湊表本身沒有排序資訊，無法保證常數時間完成。

---

選項分析

(A) Find key

正確。

給定一個 key，可計算其雜湊值：

$$i=h(\text{key})$$

再至位置 $i$ 檢查資料。若發生碰撞，依照 chaining 或 open addressing 的規則繼續尋找。

平均時間複雜度為：

$$O(1)$$

最差情況可能退化為：

$$O(n)$$

---

(B) Insert key

正確。

插入新 key 時，先計算：

$$i=h(\text{key})$$

再將 key 放入對應位置。若該位置已有其他 key，使用碰撞處理機制放置資料。

平均時間複雜度為：

核心觀念

本題考查二項堆（binomial heap）的結構性質，以及 Stack、Queue 的進出順序。

二項堆由若干棵二項樹組成，且滿足：

• 每棵二項樹的階數皆不重複，因此至多有一棵 $B_k$。
• 階數為 $k$ 的二項樹 $B_k$ 含有 $2^k$ 個節點。
• $B_k$ 的高度為 $k$。
• 一個含有 $n$ 個元素的二項堆，其二項樹數量不超過 $O(\log n)$。
• Stack 遵循後進先出（LIFO）。
• Queue 遵循先進先出（FIFO）。

解題方法

逐一套用二項樹與線性資料結構的定義，判斷各敘述是否符合標準性質。

選項分析

(A) In a binomial heap, there is at most one binomial tree of order 3.

正確。

二項堆中至多存在一棵相同階數的二項樹。若有兩棵相同階數的二項樹，合併操作會將它們連結成一棵階數加一的二項樹。

因此，對於階數 $3$ 的二項樹 $B_3$，二項堆中至多有一棵，故此敘述正確。

(B) In a binomial heap of n items, the height among all binomial trees is $O(\log n)$.

正確。

階數為 $k$ 的二項樹 $B_k$ 有

$$2^k$$

個節點，且高度為 $k$。

在含有 $n$ 個元素的二項堆中，任何一棵二項樹的節點數不能超過 $n$，所以有

$$2^k \leq n.$$

兩邊取對數可得

$$k \leq \log_2 n.$$

因此所有二項樹中的最大高度為

$$O(\log n),$$

故此敘述正確。

(C) In a binomial heap of n items, there is $O(\log n)$ binomial trees.

正確。

$\displaystyle [\log_2 n]!$ 的 Stirling 近似為

$$[\log_2 n]! =\Theta\!\big((\log n)^{\log n}\big) =\Theta\!\big(e^{\,n\ln\!\ln n}\big),$$

遠大於 $n\log n$，故 (A) 錯。

$n!$ 與 $(\log n)^n$ 的比率

$$\frac{n!}{(\log n)^n} \asymp\frac{(n/e)^n}{(\log n)^n} =\bigg(\frac{n}{e\log n}\bigg)^{\!n}\!\to\infty ,$$

故 $n! \not\sim (\log n)^n$，(B) 錯。

$n! > (\log n)^n$ 明顯成立。

$\log (n!) = \Theta(n\log n) \quad\text{(Stirling)}$