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

核心觀念

本題考查單向鏈結串列（Singly Linked List）的環狀結構檢測（Cycle Detection），核心演算法為 Floyd's Cycle-Finding Algorithm（弗洛伊德尋環演算法），又常稱為龜兔賽跑演算法（Tortoise and Hare Algorithm）或快慢指標法（Fast and Slow Pointers）。

1. 環狀鏈結串列定義：
   若單向鏈結串列中存在環（Cycle），則串列中某個節點的 next 指標會指向先前的某個節點，導致串列無法到達 termination node (nullptr)。
2. 相對速度定理：
   • 設定兩個指標同時從串列開頭出發：慢指標（slow）每次向前移動 $1$ 個節點，快指標（fast）每次向前移動 $2$ 個節點。
   • 若串列無環，fast 必先抵達末端 (nullptr)。
   • 若串列存在環，當兩指標皆進入環後，以 slow 為參考座標系，fast 相對於 slow 的相對移動速度為每次向前接近 $1$ 個節點（即 $2 - 1 = 1$）。由於環是封閉結構，fast 必然會在有限步數內追上 slow 並重合（即指向同一記憶體位址）。

---

解題方法

1. 演算法推導與步驟說明

• Step 1 (初始化)：宣告兩指標 slow 與 fast，初值皆指向頭節點 head。
• Step 2 (迴圈條件與邊界檢查)：檢查 fast != nullptr 且 fast->next != nullptr。若不滿足，代表已抵達串列末端，串列無環，傳回 false。
• Step 3 (指標移動)：
  • slow = slow->next（向前走 $1$ 步）
  • fast = fast->next->next（向前走 $2$ 步）
• Step 4 (相遇判定)：若移動後 slow == fast，代表快指標在環內追上慢指標，串列存在環，傳回 true。

2. C++ 風格偽代碼 (C++ Style Pseudocode)

// 單向鏈結串列節點結構
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    /**
     * 檢測單向鏈結串列中是否存在環
     * @param head 鏈結串列頭節點指標
     * @return bool 若存在環傳回 true，否則傳回 false
     */
    bool hasCycle(ListNode* head) {
        // 邊界條件判斷：空串列或僅有一個節點且無環
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        // 當快指標及其下一個節點皆有效時持續推進
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;          // 慢指標走 1 步
            fast = fast->next->next;    // 快指標走 2 步

            // 兩指標指向相同記憶體位址，代表存在環
            if (slow == fast) {
                return true;
            }
        }

        // 快指標抵達末端 nullptr，代表無環
        return false;
    }
};

3. 時間與空間複雜度分析

核心觀念

二元搜尋樹（BST）中，每個節點都符合以下規則：左子樹的鍵值小於該節點，右子樹的鍵值大於該節點。

中序走訪依序採用「左子樹、根節點、右子樹」，因此 BST 的中序結果會由小到大排列。刪除有兩個子節點的節點時，可用其中序後繼取代：中序後繼是該節點右子樹中的最小值。

解題方法

(a) 中序走訪

依「左、根、右」順序走訪：

1. 先走訪根節點 $15$ 的左子樹：依序得到 $8, 10, 12$。
2. 再訪問根節點 $15$。
3. 最後走訪右子樹：依序得到 $17, 20, 25$。

因此，中序序列為：

$$8,\ 10,\ 12,\ 15,\ 17,\ 20,\ 25$$

(b) 刪除值為 $15$ 的節點

節點 $15$ 有左、右兩個子節點，採用中序後繼法重整 BST：

核心觀念

最大堆是完全二元樹，且每個父節點的值都大於或等於其子節點。以陣列從 1 開始編號時，索引為 $i$ 的節點，其父節點索引為 $\lfloor i/2 \rfloor$，左、右子節點索引分別為 $2i$、$2i+1$。

插入時，先放到完全二元樹的下一個空位，再向上調整；刪除最大值時，將最後一個節點移至根節點並刪除原位置，再向下調整。

解題方法

原卷圖中的初始最大堆有 6 個節點：根節點為 50，第二層為 30、20；第三層為 10、15、5，其中 5 是 20 的左子節點。因此，第 7 個位置是 20 的右子節點。

(a) 插入 60

先將 60 放入第 7 個位置，也就是 20 的右子節點：

$$[50,30,20,10,15,5,60]$$

接著向上調整：

1. 60 大於父節點 20，交換兩者：

$$[50,30,60,10,15,5,20]$$

2. 60 大於父節點 50，再交換：

$$[60,30,50,10,15,5,20]$$

60 已到根節點，且所有父節點都大於或等於子節點，調整完成。

核心觀念

本題考查：

• 深度優先搜尋（DFS）與廣度優先搜尋（BFS）的 spanning tree。
• Kruskal’s algorithm：依邊權重由小到大選邊，若形成 cycle 則跳過。
• Prim’s algorithm：從起點開始，每次選擇連接目前樹集合與外部頂點之最小權重邊。
• 最小生成樹（Minimum Spanning Tree, MST）必須連接全部 $7$ 個頂點，且恰有 $7-1=6$ 條邊。

鄰接串列依字母順序排列如下：

• $a：b,d$
• $b：a,c,h$
• $c：b,g,h$
• $d：a,e,h$
• $e：d,h$
• $g：c,h$
• $h：b,c,d,e,g$

---

（a）DFS 與 BFS spanning tree

DFS

從 $b$ 出發，且每次依字母順序拜訪：

$$b\to a\to d\to e\to h\to c\to g$$

因此 DFS spanning tree 的加入邊順序為：

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

樹狀結構可表示為：

b
└─a
   └─d
      └─e
         └─h
            └─c
               └─g

BFS

從 $b$ 開始：

1. 拜訪 $b$，依序發現 $a,c,h$。
2. 拜訪 $a$，發現尚未拜訪的 $d$。
3. 拜訪 $c$，發現尚未拜訪的 $g$。
4. 拜訪 $h$，發現尚未拜訪的 $e$。
5. 其餘頂點皆已發現。

BFS 拜訪順序為：

$$b,\ a,\ c,\ h,\ d,\ g,\ e$$

BFS spanning tree 的加入邊順序為：

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

樹狀結構為：

       b
    /  |  \
   a   c   h
   |   |   |
   d   g   e

---

（b）Kruskal’s algorithm

解題方法

先將所有邊依權重由小到大排列：

邊	權重
$(b,c)$	8
$(c,h)$	10
$(c,g)$	11
$(g,h)$	11
$(a,d)$	13
$(d,h)$	20
$(d,e)$	21
$(b,h)$	26
$(e,h)$	28
$(a,b)$	38

同權重的邊以字母順序處理，因此先處理 $(c,g)$，再處理 $(g,h)$。

逐邊判斷

1. 加入 $(b,c)$，目前沒有 cycle。
2. 加入 $(c,h)$，目前沒有 cycle。
3. 加入 $(c,g)$，目前沒有 cycle。
4. $(g,h)$ 會形成 cycle $g-c-h-g$，跳過。
5. 加入 $(a,d)$，目前沒有 cycle。
6. 加入 $(d,h)$，連接兩個不同的 connected components。
7. 加入 $(d,e)$，納入頂點 $e$。

核心觀念

本題考驗多維陣列在記憶體中的定址計算（Array Address Mapping），包含**以列為主（Row-Major Order）與以行為主（Column-Major Order）**兩種記憶體配置順序。

記憶體本質上是一維連續空間，將多維陣列對映至一維記憶體位址時，核心在於計算目標元素之前累積了多少個元素（即位址偏移量 $\text{Offset}$）。

定義與通用公式如下：
設三維陣列 $C[d_1:u_1, d_2:u_2, d_3:u_3]$，基底位址為 $\text{Base}(C[d_1, d_2, d_3])$，每個元素占用 $S$ 個位元組（Bytes）。
各維度的長度（大小）分別為：
$L_1 = u_1 - d_1 + 1, \quad L_2 = u_2 - d_2 + 1, \quad L_3 = u_3 - d_3 + 1$

對於目標元素 $C[i, j, k]$：

1. 以列為主（Row-Major Order）：最右側維度（高維度）變動最快。前方累積的元素數量為：
   $\text{Offset}_{\text{row}} = (i - d_1) \times (L_2 \times L_3) + (j - d_2) \times L_3 + (k - d_3)$
   記憶體位址公式為：
   $\text{Address}(C[i, j, k]) = \text{Base} + \text{Offset}_{\text{row}} \times S$

2. 以行為主（Column-Major Order）：最左側維度（低維度）變動最快。前方累積的元素數量為：
   $\text{Offset}_{\text{col}} = (k - d_3) \times (L_1 \times L_2) + (j - d_2) \times L_1 + (i - d_1)$
   記憶體位址公式為：
   $\text{Address}(C[i, j, k]) = \text{Base} + \text{Offset}_{\text{col}} \times S$

---

解題方法

1. 整理已知條件

• 陣列維度與範圍：$C[1:4, 1:5, 1:6]$
  • 第一維度長度 $L_1 = 4 - 1 + 1 = 4$
  • 第二維度長度 $L_2 = 5 - 1 + 1 = 5$
  • 第三維度長度 $L_3 = 6 - 1 + 1 = 6$
• 起始元素位址：$\text{Base}(C[1,1,1]) = 1344$
• 單一元素大小：$S = 2 \text{ bytes}$
• 目標元素：$C[i, j, k] = C[3, 4, 5]$
  • 索引偏移：$i - d_1 = 3 - 1 = 2$、$j - d_2 = 4 - 1 = 3$、$k - d_3 = 5 - 1 = 4$

2. 計算步驟

(a) 以列為主（Row-Major Order）位址推導

• 計算目標元素前方累積的元素個數：
  $\text{Offset}_{\text{row}} = 2 \times (5 \times 6) + 3 \times 6 + 4$
  $\text{Offset}_{\text{row}} = 2 \times 30 + 18 + 4 = 60 + 18 + 4 = 82$
• 代入位址計算公式：
  $\text{Address}(C[3,4,5]) = 1344 + 82 \times 2 = 1344 + 164 = 1508$

(b) 以行為主（Column-Major Order）位址推導

• 計算目標元素前方累積的元素個數：

核心觀念

本題旨在考驗考生對 堆疊（Stack）資料結構 在 後序運算式求值（Postfix Expression Evaluation） 中的應用，以及基礎 模數運算（Modulus Operation） 的能力。

1. 後序運算式（Postfix Expression / Reverse Polish Notation）：運算子位於運算元之後，不需要括號即可明確定義運算優先順序。
2. 堆疊（Stack）求值規則：
   • 遇到 運算元（Operand）：將其推入（Push）堆疊。
   • 遇到 二元運算子（Binary Operator）：從堆疊中彈出（Pop）兩個運算元，先彈出者為 右運算元（$op_2$），後彈出者為 左運算元（$op_1$），執行運算 $op_1 \text{ op } op_2$ 後，將計算結果推回（Push）堆疊。
3. 模數運算（Modulus）：$x \bmod m$ 代表 $x$ 除以 $m$ 的餘數，滿足 $x = q \cdot m + r$（其中 $0 \le r < m$）。

---

解題方法

步驟一：已知變數數值對照

根據題目給定：
$A = 3$, $B = 4$, $C = 5$, $D = 7$, $E = 9$, $F = -12$

步驟二：後序運算式堆疊求值

待求值的後序運算式為：A B + D * E F A D * + / + C +

利用堆疊由左至右依序掃描符號並進行計算：

1. A：Push $3$ $\rightarrow$ Stack: [3]
2. B：Push $4$ $\rightarrow$ Stack: [3, 4]
3. +：Pop $4$, Pop $3$ $\rightarrow$ 計算 $3 + 4 = 7$ $\rightarrow$ Push $7$ $\rightarrow$ Stack: [7]
4. D：Push $7$ $\rightarrow$ Stack: [7, 7]
5. *：Pop $7$, Pop $7$ $\rightarrow$ 計算 $7 \times 7 = 49$ $\rightarrow$ Push $49$ $\rightarrow$ Stack: [49]
6. E：Push $9$ $\rightarrow$ Stack: [49, 9]
7. F：Push $-12$ $\rightarrow$ Stack: [49, 9, -12]
8. A：Push $3$ $\rightarrow$ Stack: [49, 9, -12, 3]
9. D：Push $7$ $\rightarrow$ Stack: [49, 9, -12, 3, 7]
10. *：Pop $7$, Pop $3$ $\rightarrow$ 計算 $3 \times 7 = 21$ $\rightarrow$ Push $21$ $\rightarrow$ Stack: [49, 9, -12, 21]
11. +：Pop $21$, Pop $-12$ $\rightarrow$ 計算 $(-12) + 21 = 9$ $\rightarrow$ Push $9$ $\rightarrow$ Stack: [49, 9, 9]

核心觀念

本題旨在考驗檔案系統（File Systems）中兩大核心樹狀索引結構——B-tree（B 樹） 與 B+ tree（B+ 樹） 的結構差異、磁碟 I/O 特性、檢索效能及維護成本。

1. 結構定義與資料儲存位置：

   • B-tree：所有節點（包含內部節點與葉子節點）均同時儲存搜尋鍵（Key）與對應的資料指標（Data Pointer）。
   • B+ tree：僅底層葉子節點（Leaf Nodes）儲存完整的 Key 與 Data Pointer；內部節點（Internal Nodes）僅儲存 Key 與子節點指標（Child Pointer）作為路由導引（Routing Index）。此外，所有葉子節點之間以雙向鏈結串列（Doubly Linked List）相連。

2. 分支度（Branching Factor / Fan-out）與樹高（Tree Height）推導：
   設磁碟區塊（Disk Page）大小固定為 $B$ 位元組，鍵值長度為 $k$，子節點指標長度為 $p$，資料指標長度為 $d$：

   • B-tree 內部節點容量公式：$m_{\text{B}} \cdot p + (m_{\text{B}} - 1) \cdot (k + d) \le B \implies m_{\text{B}} \approx \frac{B - k}{k + p + d} + 1$
   • B+ tree 內部節點容量公式：$m_{\text{B+}} \cdot p + (m_{\text{B+}} - 1) \cdot k \le B \implies m_{\text{B+}} \approx \frac{B - k}{k + p} + 1$

   由於 $d > 0$，故分支度 $m_{\text{B+}} \gg m_{\text{B}}$。給定總筆數 $N$，樹高 $h \approx \lceil \log_{m} N \rceil$，故 B+ tree 的樹高顯著低於 B-tree（$h_{\text{B+}} \le h_{\text{B}}$）。

3. 檢索複雜度與磁碟 I/O：

   • 點查詢（Point Lookup）：B-tree 最佳為 $O(1)$、最壞為 $O(h_{\text{B}})$；B+ tree 恆為 $O(h_{\text{B+}})$（延遲極度穩定）。
   • 範圍查詢（Range Query）：B-tree 需執行中序走訪（In-order Traversal），產生 $O(K \log N)$ 的隨機磁碟 I/O（Random I/O）；B+ tree 僅需 $O(\log N)$ 找到起始頁面，後續 $K$ 筆資料以 $O(K)$ 執行順序磁碟 I/O（Sequential I/O）。

---

解題方法

本題分為兩子題，解題切入點如下：

• (a) 偏好 B-tree 的情境切入點：
  立足於 B-tree 「非葉節點即可直接命中資料」與「無重複鍵值儲存」的物理特性，尋找不需範圍查詢且強調特定熱點存取或無鍵值冗餘負擔的檔案系統情境。
• (b) 混合查詢情境之推薦與權衡分析切入點：
  明確推薦 B+ tree，並分別從 空間效率（分支度與樹高推導）、讀寫效能（點查詢安定性與順序 vs. 隨機 I/O）、維護複雜度（內部節點與葉子節點更新機制）三個面向進行數學與邏輯嚴謹的對比。

---

選項與子題深度剖析

(a) 偏好 B-tree 優於 B+ tree 的兩大檔案系統應用情境

1. 情境一：高存取局部性（Locality of Reference）且需「早期終止查詢（Early Search Termination）」的熱點資料檔案系統

   • 原理與分析：B-tree 的內部節點（含根節點與第一層節點）直接存放資料指標。若檔案系統具備強烈的存取局部性（例如系統組態檔、根目錄索引檔等高頻存取的熱點檔案），可經由調整置於較淺的內部節點中。
   • 效能優勢：點查詢在第 $1 \sim 2$ 次磁碟 Page 讀取時即可命中並傳回資料，搜尋時間複雜度最佳可達 $O(1)$。相對地，B+ tree 無論目標資料頻次高低，均被強制要求走訪至樹底葉子節點（固定需要 $h$ 次磁碟 I/O）。因此在熱點資料點查詢佔絕大多數的情境下，B-tree 具備更高的平均檢索速度。

2. 情境二：完全無範圍查詢需求、且鍵值（Key）極大之記憶體受限檔案系統

   • 原理與分析：B+ tree 的內部節點僅儲存 Key 作為分流導引，底層葉子節點仍需重複儲存一份相同的 Key，存在「鍵值冗餘（Key Duplication）」。
   • 效能優勢：當檔案系統僅執行精確點查詢（如 Hash-like 檔案檢索系統），且 Key（如長字串檔名或 UUID）佔用大量位元組時，B-tree 能完全消除鍵值重複儲存的開銷。在記憶體或快取空間極度受限的嵌入式檔案系統中，B-tree 能提供更精簡的整體索引空間佔用。

---

(b) 兼具點查詢與範圍查詢之結構推薦與權衡評估

【系統推薦】：強烈推薦選用 B+ tree。

i. 空間效率（Space Efficiency）

• B-tree：內部節點需同時容納 Key、Child Pointer 與 Data Pointer，導致節點分支度 $m_{\text{B}}$ 較小、樹高 $h_{\text{B}}$ 較高。

核心觀念：
本題考查檔案系統（File Systems）中外存儲存結構 B-tree 與 B+ tree 的效能關鍵要素，即 區塊大小（Block Size / Node Size） 與 磁碟 I/O 次數（Disk I/O Count） 之間的權衡關係（Trade-off）。

1. 磁碟 I/O 瓶頸：外存系統的效能瓶頸在於磁碟存取（Disk I/O），而非 CPU 計算時間。B-tree／B+ tree 的節點大小通常直接映射至作業系統的磁碟區塊大小（Block Size 或 Page Size，常見為 $4\text{ KB}$、$8\text{ KB}$ 或 $16\text{ KB}$），使一次節點讀寫正好對應一次物理磁碟 I/O。
2. 階數（Order / Degree $m$）與樹高（Tree Height $h$）：
   若區塊大小為 $B$，鍵值（Key）與指標（Pointer）大小分別為 $K$ 與 $P$，則內部節點可容納的最大分支數（即階數 $m$）滿足：
   • B+ tree 內部節點：$m \approx \frac{B + K}{K + P}$
   • B-tree 內部節點（含資料欄位或資料指標 $D$）：$m \approx \frac{B + P}{K + P + D}$
3. 搜尋複雜度：儲存 $N$ 筆資料時，檢索所需的最大磁碟 I/O 次數等於樹高 $h$：
   $h \approx O(\log_m N) = O\left(\frac{\log N}{\log m}\right)$
   分歧度（Branching Factor） $m$ 越大，樹高 $h$ 越矮，磁碟 I/O 次數越少。

---

解題方法：
分析 Block Size 對 B-tree 與 B+ tree 效能的影響時，應從「Block Size 過大 vs. 過小的權衡（Trade-off）」以及「B-tree 與 B+ tree 結構特性的差異」兩個維度切入推導：

1. 推導 Block Size 對樹高與磁碟 I/O 的直接控制：區塊越大 $\implies$ 單一節點可存放更多 Key 與指標 $\implies$ 階數 $m$ 增加 $\implies$ 樹高 $h$ 降低 $\implies$ 隨機搜尋磁碟 I/O 減少。
2. 比較 B-tree 與 B+ tree 的區塊空間利用率：
   • B+ tree 內部節點僅儲存路由 Key 與指標，不儲存實際資料（Data Record），因此在相同的 Block Size 下，B+ tree 能提供遠高於 B-tree 的階數 $m$，大幅降低樹高。
   • B+ tree 的葉節點（Leaf Nodes）包含全部資料並以串列（Linked List）相連，對範圍查詢（Range Query）可達成順序 I/O（Sequential I/O），極大化 Block Size 的預讀效能。
3. 歸納最佳區塊大小（Optimal Block Size）的選擇原則：區塊大小過大會帶來內部碎塊與記憶體快取負擔，過小則會引發樹高暴增；實務上必須與作業系統 Page Size 及磁碟扇區大小（Sector Size）保持對齊。

---

選項分析：
本題為問答題（非選擇題），以下針對「Block Size 過大」、「Block Size 過小」及「B-tree vs. B+ tree 結構差異」對效能的影響逐一進行深入剖析：

1. 選擇較大的區塊大小（Larger Block Size）之影響：
   • 正向影響（降低 Disk I/O）：
     節點容量大，使階數 $m$ 顯著提升。搜尋資料時樹高 $h \approx O(\log_m N)$ 變矮，存取資料所需的隨機磁碟 I/O 次數顯著減少，大幅提升檔案系統檢索速度。
   • 負向影響（空間與快取開銷）：
     • 內部碎塊（Internal Fragmentation）：B-tree/B+ tree 節點的填滿率下限通常為 $\lceil m/2 \rceil$，當 Block Size 過大時，未使用的空間增多，造成記憶體與磁碟空間浪費。

本題考查 B-tree 的插入操作，特別是當節點需要分裂（split）時的處理。

核心觀念：

• B-tree 性質：

  • 每個節點（除了根節點）至少有 $t-1$ 個鍵值，最多有 $2t-1$ 個鍵值，其中 $t$ 是 B-tree 的最小度數（minimum degree）。
  • 根節點至少有 1 個鍵值（除非是空樹）。
  • 每個節點的鍵值是排序的。
  • 每個內部節點的鍵值用於分隔其子節點的鍵值範圍。
  • 所有葉節點都在同一層。

• 最小度數 $t$：在本題中，$t=3$。

  • 每個節點（非根）至少有 $t-1 = 3-1 = 2$ 個鍵值。
  • 每個節點最多有 $2t-1 = 2 \times 3 - 1 = 5$ 個鍵值。
  • 每個內部節點（非根）最多有 $t = 3$ 個子節點。
  • 根節點最多有 $2t = 6$ 個子節點。

• 插入操作：

  1. 找到包含該鍵值的葉節點。
  2. 將鍵值插入到葉節點中（保持排序）。
  3. 如果節點中的鍵值數量超過 $2t-1$，則節點需要分裂：
     a. 找到中間鍵值。
     b. 將中間鍵值向上（父節點）移動。
     c. 將中間鍵值左側的鍵值組成一個新的左子節點。
     d. 將中間鍵值右側的鍵值組成一個新的右子節點。
     e. 如果父節點也滿了，則繼續分裂。如果分裂到根節點，則根節點分裂，樹的高度增加一層。

初始 B-tree 結構：
最小度數 $t=3$。節點最多 5 個鍵值，最多 6 個子節點。
根節點：[5, 13, 22, 35] (4 個鍵值，5 個子節點，這是合法的)
葉節點：
[1, 4]
[6, 7, 8, 11]
[14, 18]
[25, 27, 30, 31]
[50, 60]

注意：題目給出的初始結構中，根節點有 4 個鍵值，意味著它有 5 個子節點。這些子節點應該是包含上述葉節點的內部節點。
根節點：[5, 13, 22, 35]
子節點 1 (鍵值 < 5)：[1, 4]
子節點 2 (5 < 鍵值 < 13)：[6, 7, 8, 11]
子節點 3 (13 < 鍵值 < 22)：[14, 18]
子節點 4 (22 < 鍵值 < 35)：[25, 27, 30, 31]
子節點 5 (鍵值 > 35)：[50, 60]

這是一個合法的 B-tree 結構，因為每個節點的鍵值數量在 $t-1=2$ 到 $2t-1=5$ 之間（根節點至少 1 個）。

插入鍵值序列：26, 29, 2, 10, 9。

Operation 1: insert 26

1. 尋找插入位置：
   • 26 > 35 嗎？否。
   • 26 > 22 嗎？是。26 在 22 和 35 之間。
   • 轉到根節點的第 4 個子節點（索引 3，鍵值 22 < 鍵值 < 35）。
   • 該節點是 [25, 27, 30, 31]。
2. 插入到葉節點：
   • 將 26 插入到 [25, 27, 30, 31] 中，保持排序。
   • 節點變為：[25, 26, 27, 30, 31]。
3. 檢查分裂：
   • 節點 [25, 26, 27, 30, 31] 有 5 個鍵值，已達到最大容量 ($2t-1=5$)。
   • 需要分裂。中間鍵值是 27。
   • 將 27 向上移動到父節點。
   • 左子節點：[25, 26]。
   • 右子節點：[30, 31]。
4. 更新父節點：
   • 父節點是根節點 [5, 13, 22, 35]。
   • 插入 27。節點變為：[5, 13, 22, 27, 35]。
5. 檢查分裂（父節點）：
   • 根節點 [5, 13, 22, 27, 35] 有 5 個鍵值，已達到最大容量 ($2t-1=5$)。
   • 需要分裂。中間鍵值是 22。
   • 將 22 向上移動，成為新的根節點。
   • 左子樹的新根節點：[5, 13]。其子節點是原來的 [1, 4] 和 [6, 7, 8, 11]。
   • 右子樹的新根節點：[27, 35]。其子節點是新的 [25, 26]、[30, 31] 和原來的 [50, 60]。

Operation 1 結果：
根節點：[22]
子節點 1 (鍵值 < 22)：[5, 13]
子節點 2 (鍵值 > 22)：[27, 35]

內部節點結構：
[5, 13] 的子節點：[1, 4], [6, 7, 8, 11]
[27, 35] 的子節點：[25, 26], [30, 31], [50, 60]

Operation 2: insert 29

1. 尋找插入位置：
   • 29 > 22 嗎？是。
   • 29 > 27 嗎？是。29 在 27 和 35 之間。
   • 轉到根節點 [22] 的右子節點 [27, 35]。
   • 該節點是 [27, 35]。
2. 插入到葉節點：
   • 將 29 插入到 [27, 35] 中，保持排序。
   • 節點變為：[27, 29, 35]。
3. 檢查分裂：
   • 節點 [27, 29, 35] 有 3 個鍵值，小於最大容量 5。不需要分裂。

Operation 2 結果：
根節點：[22]
子節點 1 (鍵值 < 22)：[5, 13]
子節點 2 (鍵值 > 22)：[27, 29, 35]

內部節點結構：
[5, 13] 的子節點：[1, 4], [6, 7, 8, 11]
[27, 29, 35] 的子節點：[25, 26], [30, 31], [50, 60] (注意：29 插入後，[27, 29, 35] 成為內部節點，其子節點被調整)
* 27 < 鍵值 < 29：[25, 26]
* 29 < 鍵值 < 35：[30, 31]
* 鍵值 > 35：[50, 60]

Operation 3: insert 2

1. 尋找插入位置：
   • 2 < 22 嗎？是。
   • 2 < 5 嗎？是。2 在 5 的左邊。
   • 轉到根節點 [22] 的左子節點 [5, 13]。
   • 該節點是 [5, 13]。
2. 插入到葉節點：
   • 將 2 插入到 [5, 13] 中，保持排序。
   • 節點變為：[2, 5, 13]。
3. 檢查分裂：
   • 節點 [2, 5, 13] 有 3 個鍵值，小於最大容量 5。不需要分裂。

Operation 3 結果：
根節點：[22]
子節點 1 (鍵值 < 22)：[2, 5, 13]
子節點 2 (鍵值 > 22)：[27, 29, 35]

內部節點結構：
[2, 5, 13] 的子節點：[1, 4], [6, 7, 8, 11]
[27, 29, 35] 的子節點：[25, 26], [30, 31], [50, 60]

Operation 4: insert 10

1. 尋找插入位置：
   • 10 < 22 嗎？是。
   • 10 > 5 嗎？是。10 在 5 和 13 之間。
   • 轉到根節點 [22] 的左子節點 [2, 5, 13]。
   • 該節點是 [2, 5, 13]。
2. 插入到葉節點：
   • 將 10 插入到 [2, 5, 13] 中，保持排序。
   • 節點變為：[2, 5, 10, 13]。
3. 檢查分裂：
   • 節點 [2, 5, 10, 13] 有 4 個鍵值，小於最大容量 5。不需要分裂。