113 年 國立中央大學工業管理研究所碩士班大數據組《資料結構》

核心觀念

本題考查線性資料結構（Linear Data Structures）中最基本的兩大實作方式：陣列（Array） 與 鏈結串列（Linked List） 在底層記憶體配置與演算法複雜度上的對比。核心觀念涵蓋：

1. 記憶體配置（Memory Allocation）：連續記憶體空間（Contiguous Allocation）與非連續記憶體空間（Non-contiguous Allocation）之特性。
2. 時間複雜度（Time Complexity）：隨機存取（Random Access, $O(1)$）與循序存取（Sequential Access, $O(N)$）、以及元素插入與刪除（Insertion / Deletion）之代價。
3. 空間與硬體效能開銷（Space & Hardware Performance Trade-off）：指標額外空間開銷（Pointer Overhead）與 CPU 快取局部性（Cache Locality）。

---

解題方法

分析鏈結串列相較於陣列的優缺點時，必須從四大軸線系統化切入：

1. 空間彈性與記憶體配置：動態擴展能力 vs 預先宣告空間。
2. 資料存取效能：索引位址計算（Indexing） vs 指標走訪（Traversal）。
3. 異動操作代價：元素搬移（Shifting） vs 指標重導向（Re-linking）。
4. 硬體親和性：快取記憶體命中率（Cache Miss Rate）與指標額外佔用空間。

---

選項分析

本題為觀念問答題，將比較項目拆解為具體維度，逐項分析鏈結串列相較於陣列的優勢與劣勢：

一、 鏈結串列相較於陣列的「優點」（Advantages）

1. 動態記憶體配置（Dynamic Memory Allocation）：

   • 分析：鏈結串列不需在編譯期或宣告時預先指定固定的大小，能在執行期（Runtime）隨資料增加或減少動態申請與釋放節點空間。
   • 對比：傳統陣列在宣告時即固定容量。若預留過大會造成記憶體浪費；若預留過小，當空間不足時需進行重新配置（Reallocation）並搬移整體資料，時間代價為 $O(N)$。

2. 高效的插入與刪除操作（Efficient Insertion & Deletion）：

   • 分析：在已知目標位置指標的前提下，鏈結串列進行節點插入或刪除只需修改指標指向（Pointer Adjustment），時間複雜度為 $O(1)$。
   • 對比：陣列若在中間或頭部進行插入／刪除，為了維持記憶體的連續性，必須將目標位置後方的所有元素向前或向後移動（Shifting），最壞與平均時間複雜度皆為 $O(N)$。

3. 無記憶體空間預留浪費：

   • 分析：鏈結串列按需分配（Allocate on Demand），不需像陣列一樣預留未使用的連續空間。

---

二、 鏈結串列相較於陣列的「缺點」（Disadvantages）

1. 不支援隨機存取（No Random Access）：
   • 分析：鏈結串列的節點分散於記憶體中，無法透過索引（Index）直接計算出目標位址。欲存取第 $k$ 個元素，必須從頭指標（Head Pointer）開始順序走訪（Sequential Access），時間複雜度為 $O(N)$。
   • 對比：陣列佔用連續記憶體空間，存取第 $i$ 個元素可直接透過位址偏移公式求解：$\text{Address}(A[i]) = \text{Base Address} + i \times \text{Element Size}$，時間複雜度為 $O(1)$。

核心觀念

廣義串列可用巢狀子串列表示多變數多項式。每一層對應一個變數，節點記錄該變數的指數，並以子串列表示後續變數的項；最後一層記錄係數。

以下採用 $x \to y \to z \to \text{係數}$ 的表示順序。每個節點寫成「指數：子串列」；係數以葉節點表示。題目未附結構圖，因此以這種常見的廣義串列表示法作答。

解題方法

先依 $x$ 的指數分組，再在各組內依 $y$ 的指數分組，最後記錄 $z$ 的指數與係數。將多項式按變數整理為：

$$P(x,y,z) = x^5(5y^2z) + x^3(2yz^2 + 7y^4z^6) + x^2(y^3z)$$

以方括號表示串列、以「指數：子串列」表示節點，並讓各層指數由大到小排列，得到：

$$\begin{aligned} P = [&5:[2:[1:5]],\\ &3:[4:[6:7],\ 1:[2:2]],\\ &2:[3:[1:1]]] \end{aligned}$$

讀取方式如下：

核心觀念

本題考查資料結構中的**最大堆積（Max-Heap）**構建。

1. 最大堆積（Max-Heap）定義：
   最大堆積為一種滿足以下兩項性質的樹狀資料結構：

   • 結構性質（Structural Property）：必須為一棵完全二元樹（Complete Binary Tree）。除了最底層外，其餘各層均須填滿節點；最底層之節點必須由左至右依序連續填入，不可留有空位。
   • 堆積性質（Heap Order Property）：對於樹中任意節點 $i$（根節點除外），其父節點（Parent）之鍵值必大於或等於該節點之鍵值，即：
     $\text{Key}(\text{Parent}(i)) \ge \text{Key}(i)$
     因此，整棵樹的根節點（Root）永遠維持全樹的最大值。

2. 堆積建置演算法（Heap Construction）：
   在研究所入學考試中，給定一組數列建立堆積時，常見兩種標準演算法：

   • 逐一插入法（Successive Insertion / Swim Up）：從空堆積開始，將數列元素依序加入樹尾（維護完全二元樹結構），並執行向上調整（Percolate Up / Swim），時間複雜度為 $O(n \log n)$。此為未特別指定演算法時的最標準預設解法。
   • 由下而上建堆法（Bottom-Up Heapify / Floyd's Algorithm）：將原始數列直接對應為完全二元樹，再從最後一個非葉節點（索引 $\lfloor n/2 \rfloor$）開始往根節點方向逐一執行向下調整（Percolate Down / Sink），時間複雜度為 $O(n)$。

---

解題方法

方法一：逐一插入法（Successive Insertion，標準解答推導）

輸入數列：4, 12, 1, 24, 6, 18, 21, 9, 5

• Step 1: 插入 4

  • 樹狀結構：
    $4$

• Step 2: 插入 12

  • 放入 4 之左子節點。因 $12 > 4$，執行向上調整（Swim Up），12 與 4 交換。
  • 樹狀結構：

        12
       /
      4
    

• Step 3: 插入 1

  • 放入 12 之右子節點。因 $1 \le 12$，滿足堆積性質，無須調整。
  • 樹狀結構：

        12
       /  \
      4    1
    

• Step 4: 插入 24

  • 放入 4 之左子節點。
  • 比較：$24 > 4$，交換；再與父節點 12 比較：$24 > 12$，交換至根節點。
  • 樹狀結構：

        24
       /  \
      12   1
     /
    4
    

• Step 5: 插入 6

  • 放入 12 之右子節點。比較：$6 \le 12$，無須調整。
  • 樹狀結構：

        24
       /  \
      12   1
     /  \
    4    6
    

• Step 6: 插入 18

  • 放入 1 之左子節點。
  • 比較：$18 > 1$，交換；再與父節點 24 比較：$18 \le 24$，停止調整。
  • 樹狀結構：

        24
       /  \
      12   18
     /  \ /
    4   6 1
    

• Step 7: 插入 21

  • 放入 18 之右子節點。
  • 比較：$21 > 18$，交換；再與父節點 24 比較：$21 \le 24$，停止調整。
  • 樹狀結構：

        24
       /  \
      12   21
     /  \ /  \
    4   6 1  18
    

• Step 8: 插入 9

  • 放入 4 之左子節點。
  • 比較：$9 > 4$，交換；再與父節點 12 比較：$9 \le 12$，停止調整。
  • 樹狀結構：

        24
       /  \
      12   21
     /  \ /  \
    9   6 1  18
    

  /
  4

核心觀念

2-3-4 樹的每個節點最多可含 3 個鍵，鍵值依序遞增；含有 $k$ 個鍵的內部節點有 $k+1$ 個子節點。插入時，遇到滿節點（含 3 個鍵）就將中間鍵提升至父節點，並把其餘兩鍵分成左右子節點，維持樹的平衡。

解題方法

採用由根往下的插入方式。原根節點 $[8,22,35]$ 已滿，先將中間鍵 $22$ 提升為新根：

• 新根為 $[22]$。
• 左子樹根為 $[8]$，子節點為 $[2]$、$[11]$。
• 右子樹根為 $[35]$，子節點為 $[23,25,27]$、$[40]$。

因為 $29>22$，往右子樹插入。節點 $[35]$ 的左子節點 $[23,25,27]$ 已滿，將其中間鍵 $25$ 提升至父節點，得到：

• 父節點 $[25,35]$。
• 三個子節點依序為 $[23]$、$[27]$、$[40]$。

核心觀念

本題考查無向加權圖的最小生成樹（MST）。生成樹必須連接所有頂點且不含環；若圖有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊。本圖有 $8$ 個頂點，因此最小生成樹要選 $7$ 條邊，並使總權重最小。

Kruskal 演算法依邊權重由小到大選邊，遇到會形成環的邊就跳過；Prim 演算法從指定頂點出發，每次選擇連接已納入頂點與未納入頂點的最小權重邊。

解題方法

(a) 最小生成樹

將各邊依權重由小到大排列：

$$(a,f):3,\ (b,h):5,\ (b,c):7,\ (d,h):9,\ (e,f):11,\ (c,d):13,\ (b,g):16,\ (d,g):17,\ (a,b):20,\ (d,e):22,\ (a,e):28,\ (a,g):35,\ (e,g):38$$

依序選取不會形成環的邊：

1. 選 $(a,f)$，權重 $3$。
2. 選 $(b,h)$，權重 $5$。
3. 選 $(b,c)$，權重 $7$。
4. 選 $(d,h)$，權重 $9$。
5. 選 $(e,f)$，權重 $11$。
6. 略過 $(c,d)$，因為 $c$ 和 $d$ 已經經由 $c-b-h-d$ 相連，加入會形成環。
7. 選 $(b,g)$，權重 $16$。
8. 略過 $(d,g)$，因為 $d$ 和 $g$ 已經相連，加入會形成環。
9. 選 $(a,b)$，權重 $20$。此時已選滿 $7$ 條邊，所有頂點連通。

因此最小生成樹的邊為：

$$\{(a,f),(b,h),(b,c),(d,h),(e,f),(b,g),(a,b)\}$$

總權重為：

$$3+5+7+9+11+16+20=71$$

(b) Kruskal 演算法步驟

從最小權重邊開始檢查，加入不會形成環的邊：

核心觀念

算術運算式（Arithmetic Expression）依據運算子（Operator）與運算元（Operand）的相對位置，分為三種表示法：

1. 中序表示法（Infix Notation）：運算子位於兩運算元之間，如 $(A + B)$。人類慣用，但需依賴括號與運算子優先順序。
2. 前序表示法（Prefix / Polish Notation）：運算子位於兩運算元之前，如 $+ A B$。
3. 後序表示法（Postfix / Reverse Polish Notation, RPN）：運算子位於兩運算元之後，如 $A B +$。

電腦在處理運算式轉換時，核心依賴堆疊（Stack）或運算式樹（Expression Tree）：

• 後序轉前序（Postfix $\to$ Prefix）：由左至右掃描後序運算式。遇到運算元則推入堆疊；遇到運算子時，從堆疊彈出兩個運算元 $op_2$（先彈出者為右運算元）與 $op_1$（後彈出者為左運算元），組合成新的前序子式 $\text{operator} + op_1 + op_2$，再推回堆疊。
• 前序轉後序（Prefix $\to$ Postfix）：由右至左掃描前序運算式。遇到運算元則推入堆疊；遇到運算子時，從堆疊彈出兩個運算元 $op_1$（先彈出者為左運算元）與 $op_2$（後彈出者為右運算元），組合成新的後序子式 $op_1 + op_2 + \text{operator}$，再推回堆疊。

---

解題方法

(a) Postfix $\to$ Prefix：$ab+c/d*e+5-$

採用由左至右掃描堆疊法推導：

步驟	讀取 Token	動作說明	堆疊內容（由底至頂）
1	$a$	運算元，推入堆疊	["a"]
2	$b$	運算元，推入堆疊	["a", "b"]
3	$+$	彈出 $op_2=b$, $op_1=a$，組合成 +ab 推回	["+ab"]
4	$c$	運算元，推入堆疊	["+ab", "c"]
5	$/$	彈出 $op_2=c$, $op_1=\text{+ab}$，組合成 /+abc 推回	["/+abc"]
6	$d$	運算元，推入堆疊	["/+abc", "d"]
7	$*$	彈出 $op_2=d$, $op_1=\text{/+abc}$，組合成 */+abcd 推回	["*/+abcd"]
8	$e$	運算元，推入堆疊	["*/+abcd", "e"]
9	$+$	彈出 $op_2=e$, $op_1=\text{*/+abcd}$，組合成 +*/+abcde 推回	["+*/+abcde"]
10	$5$	運算元，推入堆疊	["+*/+abcde", "5"]
11	$-$	彈出 $op_2=5$, $op_1=\text{+*/+abcde}$，組合成 -+*/+abcde5 推回	["-+*/+abcde5"]

核心觀念

本題考查遞迴函式（recursive function）的定義，以及遞迴相較於迭代的優缺點。

遞迴函式必須包含兩個核心部分：

1. 基底條件（base case）：直接給出答案，使函式停止繼續呼叫自己。
2. 遞迴條件（recursive case）：將原問題轉換成規模較小的同類型問題，並呼叫函式本身求解。

若缺少基底條件，函式會不斷呼叫自己，最終造成 stack overflow（堆疊溢位）。

---

解題方法

判斷一個函式是否為遞迴函式，可依序檢查：

1. 函式的定義或執行過程中，是否直接或間接呼叫自己。
2. 是否有明確的終止條件。
3. 每次遞迴是否使問題規模變小，逐步接近終止條件。

例如階乘函式：

$$n! = \begin{cases} 1, & n=0\\ n(n-1)!, & n>0 \end{cases}$$

其中：

• $n=0$ 是基底條件。
• $n(n-1)!$ 是遞迴條件。
• 每次呼叫都將問題由 $n$ 縮小為 $n-1$，因此最後會到達 $n=0$。

---

(a) 遞迴函式的定義

遞迴函式是指：函式在執行過程中直接或間接呼叫自身，以解決原問題的一種函式設計方式。

完整的遞迴函式通常由以下兩部分組成：

• 基底條件：處理最簡單的情況，並停止遞迴。
• 遞迴呼叫：將原問題分解為規模較小的相同問題。

以階乘為例：

factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

factorial(n) 在函式內再次呼叫 factorial(n - 1)，因此是遞迴函式。

---

(b) 遞迴函式的優點

1. 程式碼較簡潔、易於表達

對於可分解成相同子問題的問題，遞迴寫法通常比迴圈更接近數學定義，程式碼較簡短，也較容易表達問題結構。

例如樹的走訪、二元搜尋、合併排序與快速排序，都能自然地使用遞迴描述。

2. 適合處理階層式或分割式資料

核心觀念

本題旨在考驗雜湊表（Hash Table）的基本操作、雜湊函數計算以及開放定址法（Open Addressing）中的線性探測（Linear Probing）碰撞處置策略。

1. 雜湊函數（Hash Function）：
   本題採用除法雜湊法（Division Method），公式為：
   $h(k) = k \bmod 10$
   其中 $k$ 為鍵值（Key），雜湊表大小 $m = 10$（有效索引位址為 $0, 1, 2, \dots, 9$）。

2. 開放定址法與線性探測（Linear Probing）：
   當兩個以上的鍵值映射到同一個雜湊位址時發生「碰撞（Collision）」。線性探測會在發生碰撞時，順序檢查下一個連續的槽位（Slot）。其探測序列公式為：
   $h(k, i) = (h(k) + i) \bmod 10 \quad (i = 0, 1, 2, \dots)$

   • $i = 0$：初次嘗試原本的雜湊位址 $h(k)$。
   • $i > 0$：發生碰撞時，向後尋找第 $i$ 個槽位。若到達陣列末端（索引 9），則透過取餘數運算迴繞（Wrap-around）回到索引 0。

3. 主要群聚現象（Primary Clustering）：
   線性探測會在雜湊表中形成連續被佔用的區塊。隨著連續區塊變大，後續發生碰撞時需要探測的次數也會顯著增加。

---

解題方法

依序將鍵值 $25, 35, 14, 5, 16, 26, 19$ 插入大小為 10 的雜湊表中。初始狀態下，槽位 $0 \sim 9$ 皆為空（Empty）。

步驟 1：插入 25

• 計算雜湊值：$h(25) = 25 \bmod 10 = 5$。
• 檢查槽位 5：目前為空位，無碰撞。
• 結果：將 25 放入槽位 5。

步驟 2：插入 35

• 計算雜湊值：$h(35) = 35 \bmod 10 = 5$。
• 檢查槽位 5：已有 25，發生碰撞！
• 線性探測：
  • $i=1 \implies h(35, 1) = (5 + 1) \bmod 10 = 6$。
• 檢查槽位 6：目前為空位。
• 結果：將 35 放入槽位 6。

步驟 3：插入 14

• 計算雜湊值：$h(14) = 14 \bmod 10 = 4$。
• 檢查槽位 4：目前為空位，無碰撞。
• 結果：將 14 放入槽位 4。

步驟 4：插入 5

• 計算雜湊值：$h(5) = 5 \bmod 10 = 5$。
• 檢查槽位 5：已有 25，發生碰撞！
• 線性探測：
  • $i=1 \implies h(5, 1) = (5 + 1) \bmod 10 = 6$（已有 35，發生碰撞！）。
  • $i=2 \implies h(5, 2) = (5 + 2) \bmod 10 = 7$。
• 檢查槽位 7：目前為空位。
• 結果：將 5 放入槽位 7。

步驟 5：插入 16

• 計算雜湊值：$h(16) = 16 \bmod 10 = 6$。
• 檢查槽位 6：已有 35，發生碰撞！
• 線性探測：
  • $i=1 \implies h(16, 1) = (6 + 1) \bmod 10 = 7$（已有 5，發生碰撞！）。
  • $i=2 \implies h(16, 2) = (6 + 2) \bmod 10 = 8$。
• 檢查槽位 8：目前為空位。
• 結果：將 16 放入槽位 8。

步驟 6：插入 26

• 計算雜湊值：$h(26) = 26 \bmod 10 = 6$。
• 檢查槽位 6：已有 35，發生碰撞！
• 線性探測：
  • $i=1 \implies h(26, 1) = (6 + 1) \bmod 10 = 7$（已有 5，發生碰撞！）。
  • $i=2 \implies h(26, 2) = (6 + 2) \bmod 10 = 8$（已有 16，發生碰撞！）。
  • $i=3 \implies h(26, 3) = (6 + 3) \bmod 10 = 9$。
• 檢查槽位 9：目前為空位。
• 結果：將 26 放入槽位 9。

核心觀念

本題旨在考驗**雜湊表（Hash Table）中碰撞處理（Collision Handling）**的完整理論體系與實務應用。

1. 雜湊與碰撞的定義：

   • 雜湊函數（Hash Function）：將 key 值的集合 $K$ 對應至雜湊表長度為 $m$ 的位址空間 $\{0, 1, \dots, m-1\}$，記為 $h(k)$。
   • 碰撞（Collision）：當兩個不同的 key 值 $k_1 \neq k_2$，經雜湊函數計算後得到相同的儲存位址，即 $h(k_1) = h(k_2)$。
   • 鴿籠原理（Pigeonhole Principle）：由於可能的 key 值數量（$|K|$）通常遠大於雜湊表的大小（$m$），因此碰撞在數學上是無法完全避免的，必須設計有效的機制來處理。

2. 載入因子（Load Factor, $\alpha$）：

   • 定義為 $\alpha = \frac{n}{m}$，其中 $n$ 為目前已插入的資料總筆數，$m$ 為雜湊表的大小。
   • $\alpha$ 是評估雜湊表效能與碰撞機率的核心指標。

---

解題方法

處理碰撞的方法主要分為兩大類：分離鏈結法（Separate Chaining）與開放定址法（Open Addressing）。以下詳述其運作原理、數學公式、詳細範例與優缺點分析。

---

一、分離鏈結法（Separate Chaining）

1. 運作原理

雜湊表的每個 Slot（槽位）不直接儲存資料本身，而是維護一個指標（Pointer），指向一個動態資料結構（通常為單向鏈結串列 Single Linked List）。當發生碰撞時，新資料直接掛接在該 Slot 所對應的鏈結串列尾端或前端。

2. 詳細範例

• 設定：雜湊表大小 $m = 5$，位址為 $\{0, 1, 2, 3, 4\}$。雜湊函數 $h(k) = k \bmod 5$。
• 依次插入 Key：$12, 22, 7, 15, 27$。

推導步驟：

1. 插入 $12$：$h(12) = 12 \bmod 5 = 2 \implies \text{Slot } 2: [12]$
2. 插入 $22$：$h(22) = 22 \bmod 5 = 2$（發生碰撞，掛至 Slot 2 串列尾端）$\implies \text{Slot } 2: [12] \to [22]$
3. 插入 $7$：$h(7) = 7 \bmod 5 = 2$（發生碰撞，掛至 Slot 2 串列尾端）$\implies \text{Slot } 2: [12] \to [22] \to [7]$
4. 插入 $15$：$h(15) = 15 \bmod 5 = 0 \implies \text{Slot } 0: [15]$
5. 插入 $27$：$h(27) = 27 \bmod 5 = 2$（發生碰撞，掛至 Slot 2 串列尾端）$\implies \text{Slot } 2: [12] \to [22] \to [7] \to [27]$

最終雜湊表狀態：

• Slot 0: $[15]$
• Slot 1: $\text{null}$
• Slot 2: $[12] \to [22] \to [7] \to [27]$
• Slot 3: $\text{null}$
• Slot 4: $\text{null}$

3. 時間複雜度與優缺點

• 時間複雜度：
  • 平均（Average Case）：尋找成功或失敗的時間為 $O(1 + \alpha)$。
  • 最壞（Worst Case）：若所有 key 皆雜湊至同一 Slot，退化為鏈結串列搜尋，$O(n)$。
• 優點：
  1. 實作簡單，刪除節點非常方便，只需調整鏈結串列指標。
  2. 不受表大小限制：載入因子 $\alpha$ 可以大於 1，雜湊表永遠不會填滿。
  3. 對於不良雜湊函數造成的聚集問題容忍度較高。
• 缺點：
  1. 需要額外空間儲存指標（Pointer Overhead），降低記憶體利用率。
  2. 鏈結串列節點在記憶體中非連續分布，快取快取命中率（Cache Locality）較差。

---

二、開放定址法（Open Addressing）

1. 運作原理

所有元素皆直接存放在雜湊表的 Slot 中（不使用外部鏈結串列）。當欲插入位址發生碰撞時，透過**探測序列（Probe Sequence）**依序尋找下一個未被佔用的空 Slot。

一般探測公式為：
$h(k, i) = (h'(k) + f(i)) \bmod m, \quad i = 0, 1, 2, \dots, m-1$
其中 $i$ 表示第 $i$ 次探測，$h'(k)$ 為輔助雜湊函數，$f(i)$ 為探測偏移量函數。

常用的三種探測技術如下：

---

(A) 線性探測法（Linear Probing）

• 公式：$f(i) = i \implies h(k, i) = (h'(k) + i) \bmod m$

• 詳細範例：

  • 設定：$m = 7$，位址 $\{0, \dots, 6\}$，$h'(k) = k \bmod 7$。
  • 依次插入 Key：$10, 17, 24$。

推導步驟：

1. 插入 $10$：$h'(10) = 10 \bmod 7 = 3$ $\implies$ Slot 3 為空，放入。
2. 插入 $17$：$h'(17) = 17 \bmod 7 = 3$（碰撞于 Slot 3）。
   • $i=1 \implies h(17, 1) = (3 + 1) \bmod 7 = 4$ $\implies$ Slot 4 為空，放入。
3. 插入 $24$：$h'(24) = 24 \bmod 7 = 3$（碰撞于 Slot 3）。
   • $i=1 \implies h(24, 1) = 4$（碰撞于 Slot 4）。
   • $i=2 \implies h(24, 2) = (3 + 2) \bmod 7 = 5$ $\implies$ Slot 5 為空，放入。

最終雜湊表狀態：
Slot 3: $10$ | Slot 4: $17$ | Slot 5: $24$（其餘 Slot 為空）

---

(B) 二次探測法（Quadratic Probing）

• 公式：$f(i) = c_1 i + c_2 i^2$（常見簡化型為 $f(i) = i^2$）$\implies h(k, i) = (h'(k) + i^2) \bmod m$

• 詳細範例：

  • 設定：$m = 7$，位址 $\{0, \dots, 6\}$，$h'(k) = k \bmod 7$。
  • 依次插入 Key：$10, 17, 24$。

推導步驟：

1. 插入 $10$：$h'(10) = 3 \implies$ 放入 Slot 3。

核心觀念

本題考查**AVL 樹（AVL Tree）作為資料庫主鍵索引（Primary Index）**的設計與實作機制。核心知識點涵蓋：

1. 資料庫記錄與索引架構（Database Record & Indexing Structure）：

   • 資料記錄包含 patient_id（整數，作為搜尋鍵 Key）、name（字串）與 weight（浮點數）。
   • AVL 樹節點儲存鍵值、資料指標（或完整記錄）以及維護樹平衡所需的「高度（Height）」資訊。

2. AVL 樹的平衡定義（Balance Property）：

   • 對於樹中任意節點 $v$，其**平衡因子（Balance Factor, $BF$）**定義為：
     $BF(v) = \text{height}(\text{left\_child}) - \text{height}(\text{right\_child})$
   • 嚴格維持 $BF(v) \in \{-1, 0, 1\}$。若某次操作破壞平衡（$|BF| > 1$），必須透過**單旋轉（Single Rotation）或雙旋轉（Double Rotation）**恢復平衡。

3. 四種旋轉型態（Rebalancing Rotations）：

   • LL 型：在左子樹的左子樹插入/刪除導致不平衡，對失衡點進行右旋轉（Right Rotation）。
   • RR 型：在右子樹的右子樹插入/刪除導致不平衡，對失衡點進行左旋轉（Left Rotation）。
   • LR 型：在左子樹的右子樹插入/刪除導致不平衡，先對左子節點左旋，再對失衡點右旋。
   • RL 型：在右子樹的左子樹插入/刪除導致不平衡，先對右子節點右旋，再對失衡點左旋。

---

解題方法

本題要求設計一個以 Patient ID 為索引鍵的 AVL 樹系統，並說明插入（Insertion）與刪除（Deletion）操作與具體實例。

1. 資料結構設計（Data Structure Design）

#include <iostream>
#include <string>
#include <algorithm>

// 病患資料記錄 (Patient Record)
struct PatientRecord {
    int patient_id;     // 索引鍵 (Key)
    std::string name;   // 病患姓名
    float weight;       // 病患體重
};

// AVL 樹節點 (AVL Tree Node)
struct AVLNode {
    PatientRecord data;   // 病患資料
    int height;           // 節點高度
    AVLNode* left;        // 左子樹指標
    AVLNode* right;       // 右子樹指標

    AVLNode(int id, std::string n, float w)
        : data{id, n, w}, height(1), left(nullptr), right(nullptr) {}
};

2. 核心輔助函式（Helper Functions）

• 取得高度與平衡因子：
  $\text{height}(p) = \begin{cases} 0 & \text{if } p = \text{nullptr} \\ p\to\text{height} & \text{otherwise} \end{cases}$
  $BF(p) = \text{height}(p\to\text{left}) - \text{height}(p\to\text{right})$

• 旋轉操作實作：

// 取得高度
int getHeight(AVLNode* n) {
    return n ? n->height : 0;
}

// 取得平衡因子
int getBalanceFactor(AVLNode* n) {
    return n ? getHeight(n->left) - getHeight(n->right) : 0;
}

// 更新節點高度
void updateHeight(AVLNode* n) {
    if (n) {
        n->height = 1 + std::max(getHeight(n->left), getHeight(n->right));
    }
}

// 右旋轉 (Right Rotate) - 處理 LL 型
AVLNode* rotateRight(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    x->right = y;
    y->left = T2;

    updateHeight(y);
    updateHeight(x);

    return x; // 新的根節點
}

// 左旋轉 (Left Rotate) - 處理 RR 型
AVLNode* rotateLeft(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    y->left = x;
    x->right = T2;

    updateHeight(x);
    updateHeight(y);

    return y; // 新的根節點
}

---

3. 插入操作（Insertion）與範例說明

插入步驟：

1. 依照二元搜尋樹（BST）規則將新記錄插入適當位置。
2. 沿著遞迴路徑由下往上更新每個節點的高度。
3. 計算平衡因子 $BF$。若 $BF > 1$ 或 $BF < -1$，依據插入位置執行相應旋轉修正：
   • $BF > 1$ 且 $\text{key} < \text{node}\to\text{left}\to\text{key} \implies$ LL 型（右旋轉）
   • $BF > 1$ 且 $\text{key} > \text{node}\to\text{left}\to\text{key} \implies$ LR 型（左旋再右旋）
   • $BF < -1$ 且 $\text{key} > \text{node}\to\text{right}\to\text{key} \implies$ RR 型（左旋轉）
   • $BF < -1$ 且 $\text{key} < \text{node}\to\text{right}\to\text{key} \implies$ RL 型（右旋再左旋）

實例演練（Insertion Example）：

依次插入 Patient ID 序列：30, 20, 10（假設姓名為 A, B, C）。

1. 插入 ID 30：建立根節點 (30)，高度為 $1$。
2. 插入 ID 20：20 < 30，掛於 30 的左子節點。