---
# System prepended metadata

title: 【考試向】資料結構筆記（2-3 Tree 跟 2-3-4 Tree）
tags: [資料結構, 程式設計, 電腦]

---

# 【考試向】資料結構筆記（2-3 Tree 跟 2-3-4 Tree）

[TOC]

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

## 2-3 Tree

2-3 Tree 是一種非常經典的自我平衡搜尋樹（Self-balancing search tree）。

它的發明是為了改善一般二元搜尋樹（Binary Search Tree, BST）在最糟情況下（資料依序輸入）會退化成一條直線，導致搜尋效率大幅降低的問題。

2-3 Tree 的核心在於它允許一個節點裡面存放超過一筆資料，並且透過「向上分裂」的機制，來保證整棵樹永遠是絕對平衡的。

### 2-3 Tree 的基礎定義與特性

在 2-3 Tree 中，「2」和「3」代表的是一個節點可以擁有的子節點數量（Children）。

一棵標準的 2-3 Tree 必須滿足以下三個嚴格的條件：

1. 節點種類限制：樹上的每一個內部節點，只能是 2-Node（2-節點）或3-Node（3-節點）。
2. 搜尋樹性質（排序規則）：左子樹的值永遠小於父節點的值，右子樹的值永遠大於父節點的值。
3. 絕對平衡（Perfectly Balanced）：這棵樹的所有葉節點（Leaf nodes，也就是最底層沒有子節點的節點）都必須在同一個階層（Level）。

### 2-3 Tree 最多 / 最少能存放的鍵值（資料）

- 2-3 Tree **最少**能存放 $(2^0 + 2^1 + \cdots + 2^{h - 1}) = 2^h - 1$ 筆資料
- 2-3 Tree **最多**能存放 $(3^0 + 3^1 + \cdots + 3^{h - 1}) = 3^h - 1$ 筆資料。

例如求高度 $h = 6$ 的 2-3 Tree 最多能放多少筆資料，則 $3^6 - 1 = 729 - 1 = 728$ 。（level 從 0 開始算）

### 2-Node 與 3-Node

#### 什麼是 2-Node（2-節點）？

「2-Node」代表這個節點有 2 個子節點分支（左子樹與右子樹），也就是一般二元樹儲存資料的形式。

為了區分這 2 個分支，這個節點內部只會存放 1 筆資料。

假設這唯一的一筆資料叫做 `Ldata`。

分支規則：

- 左子樹（Left Child）：裡面所有的資料值，都必須小於（<）Ldata。
- 右子樹（Right Child）：裡面所有的資料值，都必須大於（>）Ldata。

架構示意圖：

![image](https://hackmd.io/_uploads/SJAyqV1C-x.png)

左子節點存放的資料必須小於 Ldata；中子節點存放的資料必須大於 Ldata。

#### 什麼是 3-Node（3-節點）？

「3-Node」代表這個節點有 3 個子節點分支（左、中、右子樹）。

為了能夠劃分出 3 個區塊，這個節點內部必須存放 2 筆資料。

假設這兩筆資料分別是 `Ldata`（左邊的資料）與 `Rdata`（右邊的資料）。在節點內部，必須滿足 `Ldata < Rdata`。

分支規則：

- 左子樹（Left Child）：裡面所有的資料值，都必須小於（<）Ldata。
- 中子樹（Middle Child）：裡面所有的資料值，必須介於 Ldata 和 Rdata 之間（即 Ldata < x < Rdata）。
- 右子樹（Right Child）：裡面所有的資料值，都必須大於（>）Rdata。

架構示意圖：

![image](https://hackmd.io/_uploads/HJLCcNkAWg.png)

- Ldata < Rdata
- 左子節點存放的資料必須小於 Ldata
- 中子節點存放的資料必須大於 Ldata，小於 Rdata
- 右子節點存放的資料必須大於 Rdata

### 2-3 Tree 的加入操作

在 2-3 Tree 中加入新資料，則有兩條規則：

1. 永遠從葉節點（Leaf Node）加入：不會一開始就把新資料插在樹的中間層，總會先往下搜尋，找到最底層合適的葉節點，然後把資料塞進去。
2. 樹是往上生長的：當葉節點空間不夠時，資料會往上推升（Promote），甚至產生新的根節點（Root），讓整棵樹長高一層。

#### 情況一：葉節點是 2-Node

當找到應該插入新資料的葉節點時，發現它只是一個 2-Node（裡面只有一筆資料 Ldata），還有一個空位。

直接把新資料放進這個節點中，並依照大小排序，這個節點就變成了一個 3-Node（包含 Ldata 與 Rdata）。

如：2-node 變化 3-node 的過程（左是加入前，右是加入後）。

![image](https://hackmd.io/_uploads/SytxeS10-x.png)

#### 情況二：葉節點是 3-Node

當找到的葉節點是 3-Node（裡面已有 Ldata 和 Rdata），沒有空位可以放新資料了，這時就會觸發 2-3 Tree 的機制：分裂（Split）與推升（Promote）。

操作流程：

1. 暫時塞入：先把新資料硬塞進去，變成一個暫時且不合法的 4-Node（裡面有 3 筆資料）。
2. 排序：將這 3 筆資料由小到大排序（小、中、大）。
3. 分裂拆解：
    - 最小的資料留在原地，變成左邊新的 2-Node。
    - 最大的資料獨立出來，變成右邊新的 2-Node。
4. 向上推升：中間的那筆資料會往上，加入到它們的父節點（Parent）中。

如：

![image](https://hackmd.io/_uploads/ByAogrJAWe.png)

#### 情況三：父節點也是 3-Node

情況二發生時的延伸狀況，當中間的資料被推升到父節點時，如果父節點原本也已經是一個客滿的 3-Node 怎麼辦？

父節點接收了被推升上來的資料後，也會變成一個暫時的 4-Node，於是父節點也必須再次分裂，並將它自己的中間值繼續往上推升給祖父節點。

這個過程會產生連鎖反應，一路往上推，直到遇到一個有空位（2-Node）的長輩節點可以將它收容為止。

如現在有一棵樹：

![image](https://hackmd.io/_uploads/H1ALbryRbl.png)

然後現在要加入 25 進去：

1. 從根節點開始比對：25 小於 30，所以往左子樹走。
2. 找到左邊的葉節點 `(10, 20)`，把 25 塞進去。
3. 此時葉節點變成暫時的 4-Node：`(10, 20, 25)`。
4. 分裂與推升：
    - 10 留在原地（成為新的左邊 2-Node）。
    - 25 獨立出來（成為新的右邊 2-Node）。
    - 中間值 20 往上給父節點。

![image](https://hackmd.io/_uploads/BJd-XrJCZx.png)

可以發現根節點也成為 4-nodes，因此在這邊也做一次分裂：

- `20` 留在原地（成為新的左邊 2-Node）。
- `50` 獨立出來（成為新的右邊 2-Node）。
- 中間值 `30` 繼續往上。
- 注意：因為原本的 `(30, 50)` 就是根節點，上面已經沒有長輩了，所以上去的 `30` 會直接成為這棵樹全新的根節點。

當父節點分裂成 20 和 50 時，原本掛在它底下的那些子樹該何去何從？

根據二元搜尋樹的大小規則重新分配：

- 新節點 20 的子樹：
    - 左子樹：接上剛剛第一層分裂出來的 10（因為 10 < 20）
    - 右子樹：接上剛剛第一層分裂出來的 25（因為 25 > 20）
- 新節點 50 的子樹：
    - 左子樹：接上原本的中間子樹 40（因為 40 < 50）
    - 右子樹：接上原本的右邊子樹 `(60, 70)`（因為 > 50）

![image](https://hackmd.io/_uploads/SJ0HNBk0Ze.png)

### 從零建立一棵 2-3 Tree

依序插入 `10, 20, 30, 40, 50`：

1. ![image](https://hackmd.io/_uploads/S1DeBrkAbg.png)
2. ![image](https://hackmd.io/_uploads/SkkWHSy0Zl.png)
3. ![image](https://hackmd.io/_uploads/BywmSB1AZx.png)
4. ![image](https://hackmd.io/_uploads/rkDESSJ0-e.png)
5. ![image](https://hackmd.io/_uploads/SJYIrSJCWx.png)

### 2-3 Tree 的刪除操作

#### 1. 找刪除目標是否為葉節點

如果要刪除的資料剛好在最底層的葉節點就直接進入第二步。

但如果要刪除的資料在內部節點（樹的中間或根節點），不能直接把它挖掉，因為這樣底下的子樹會斷掉。

解法：找節點做替換。

尋找這筆資料的中序後繼者（In-order Successor），即右子樹中最小的值（或者左子樹中最大的值也可以）。

把這個後繼者的值複製上來覆蓋掉要刪除的資料，然後任務就變成了去葉節點刪除那個後繼者。

因為後繼者一定在葉節點上，所以所有刪除動作，最終都會變成刪除葉節點資料的問題。

#### 2. 刪除葉節點上的資料（兩種情況）

**情況一：目標在 3-Node 中**

如果包含目標資料的葉節點是一個 3-Node（裡面有兩筆資料），直接把目標資料刪掉，該節點會剩下 1 筆資料，合法退化成一個 2-Node，樹的結構不需要任何改變。

圖例：刪除 30。上為刪除前，下為刪除後。

![image](https://hackmd.io/_uploads/SyPaKS1Cbg.png)

**情況二：目標在 2-Node 中**

如果葉節點是一個 2-Node（裡面只有一筆資料），你把它刪掉後，這個節點就空了（變成 0-Node），違反了 2-3 Tree 的規則，稱之為下溢（Underflow）。

為了解決這個空節點，有兩個解決方案，優先嘗試借，借不到再合併。

#### 3. 空節點情形（借用與合併）

當遇到空節點時，只能向直接相鄰的親兄弟（左兄弟或右兄弟）求救。

**方案 A：向富有的兄弟借（Rotation / 旋轉）**

如果旁邊的親兄弟是一個 3-Node（也就是它很富有，有兩筆資料），那就可以跟它借。

注意：不能直接把兄弟的資料拿過來，會破壞大小順序，須透過父節點來做轉換。

操作流程（以向右兄弟借為例）：

1. 把父節點的資料拉下來，填補空節點。
2. 把右兄弟裡面最小的資料推上去，填補父節點的空缺。

圖例：刪除 10（向右兄弟借）。

![image](https://hackmd.io/_uploads/B1q59SkCZx.png)

- 父節點 20 下來填補空節點。
- 接著把右兄弟最小節點 30 往上提，結束。

**方案 B：與貧窮的兄弟合併（Merge）**

如果旁邊的兄弟也是一個 2-Node（大家都很窮，只有一筆資料，沒得借），那只能選擇合併。

操作流程：

1. 把父節點中夾在空節點和兄弟之間的那筆資料拉下來。
2. 將空節點、拉下來的父節點資料、以及兄弟節點，三者合併成一個新的 3-Node。

圖例：刪除 10（兄弟只有 30，沒得借）。

![image](https://hackmd.io/_uploads/BkAmiByAbx.png)

#### 4. 連鎖反應與樹變矮（合併的後遺症）

在方案 B 當中，把父節點的資料拉下來會導致兩種後果：

1. 父節點原本是 3-Node：父節點被拉走一筆資料後，還剩一筆，變成合法的 2-Node。
2. 父節點原本是 2-Node：父節點唯一的資料被拉走，父節點自己變成了空節點。

遇到後果 2 時怎麼辦？把父節點當作剛才的葉節點，重新執行第三步（向它的兄弟借，或者合併）。

#### 最終情況：根節點變空（樹變矮）

如果連鎖反應一路傳遞到最頂端的根節點（Root），導致根節點的資料被拉下來合併，根節點變成了空節點。

結論：直接把這個空的根節點刪除，原本合併出來的那個節點，就會自動成為整棵樹「新的根節點」。

回到前面方案 B 的例子，由於現在 `(20, 30)` 變成葉節點，而父節點是空的，所以 `(20, 30)` 就變成新的根節點。

#### 父節點原本是 3-Node 的情形

**情況一：左邊的子節點空了（與中間兄弟合併）**

空節點在最左邊，兄弟在中間，它們之間夾著的是父節點左邊的資料（30）。

操作：把父節點左邊的 30 拉下來，跟中間的兄弟合併。

結果：父節點剩下 50 變成合法的 2-Node。

圖解：（上為合併前，下為合併後）

![image](https://hackmd.io/_uploads/SJUiML1Cbl.png)

**情況二：右邊的子節點空了（與中間兄弟合併）**

空節點在最右邊，兄弟在中間，它們之間夾著的是父節點右邊的資料（50）。

操作：把父節點右邊的 50 拉下來，跟中間的兄弟合併。

結果：父節點剩下 30 變成合法的 2-Node。

圖解：（上為合併前，下為合併後）

![image](https://hackmd.io/_uploads/HklJ7Iy0Wx.png)

**情況三：中間的子節點空了（可以選左邊或右邊合併）**

如果破洞剛好在中間，這時有兩個選擇（兩種做法都是合法的，只要程式邏輯一致即可）：

**選擇 A：與「左兄弟」合併**

空節點與左兄弟之間夾著的是 30。

操作：拉下 30，與左兄弟合併，父節點剩下 50。

![image](https://hackmd.io/_uploads/H1YM78kC-x.png)

**選擇 B：與「右兄弟」合併**

空節點與右兄弟之間夾著的是 50。

操作：拉下 50，與右兄弟合併，父節點剩下 30。

![image](https://hackmd.io/_uploads/r1grmLJ0Zx.png)

### 2-3 Tree 刪除操作範例

假設現在有一棵 2-3 Tree 長這樣：

![image](https://hackmd.io/_uploads/SyLWpr1CZx.png)

現在要刪除 10，由於他是 2-Node，因此刪除後要跟兄弟借資料，但他的兄弟也是 2-Node，所以借不了，所以把 20 拉下來合併變成：

![image](https://hackmd.io/_uploads/SJNtTSk0Zx.png)

但原本的父節點成為空節點，因此再跟兄弟 `(40, 60)` 借，由於他是 3-Node，所以直接借：

1. 把根節點 `30` 拉下來，填補左邊的空缺。
2. 把右兄弟裡面最小的 `40` 推上去，成為新的根節點。
3. 右兄弟剩下 `60`，退化成 2-Node。

處理完後，接下來要做的是怎麼處理 60 底下的子節點。

![image](https://hackmd.io/_uploads/HkPby8yCWx.png)

這邊就直接根據 BST 的規則分配即可，由於 35 比 60 小、也比 40 小，但比 30 大，所以分配給 30 當作右子節點，剩餘的兩個 50、70 根據規則就直接留下來即可。（50 當左子節點，70 當右子節點）

![image](https://hackmd.io/_uploads/SycKkUkAZl.png)

## 2-3-4 Tree

2-3-4 Tree 是 2-3 Tree 的擴充版，它不僅保留了絕對平衡的特性，也是後來知名的紅黑樹（Red-Black Tree）的底層邏輯基礎。

### 2-3-4 Tree 的基礎定義與特性

在 2-3-4 Tree 中，「2」、「3」、「4」同樣代表一個節點可以擁有的子節點分支數量（Children）。

一棵標準的 2-3-4 Tree 必須滿足以下三個條件：

1. 節點種類限制：樹上的每一個內部節點，只能是 2-Node、3-Node 或 4-Node。
2. 搜尋樹性質（排序規則）：由左至右，子樹的值必須嚴格遵照父節點資料的大小區間進行劃分。
3. 絕對平衡：這棵樹的所有葉節點（Leaf nodes）都必須在同一個階層（Level）。

### 2-Node

「2-Node」代表這個節點有 2 個子節點分支。

為了區分這 2 個分支，這個節點內部只存放 1 筆資料。

假設這筆資料為 Ldata。

分支規則：

- 左子樹：所有資料皆 < Ldata。
- 右子樹：所有資料皆 > Ldata。

示意圖：

![image](https://hackmd.io/_uploads/SkXUldeCWx.png)

### 3-Node

「3-Node」代表這個節點有 3 個子節點分支。

為了劃分出 3 個區塊，節點內部必須存放 2 筆資料。

假設這兩筆資料為 Ldata 和 Mdata，在節點內部必須滿足 Ldata < Mdata。

分支規則：

- 左子樹：所有資料皆 < Ldata。
- 中間子樹：所有資料皆介於兩者之間，即 > Ldata 且 < Mdata。
- 右子樹：所有資料皆 > Mdata。

示意圖：

![image](https://hackmd.io/_uploads/S1Qsg_eCWl.png)

### 4-Node

「4-Node」代表這個節點有 4 個子節點分支。

為了能劃分出 4 個區間，節點內部必須存放 3 筆資料。

假設這三筆資料分別為 Ldata、Mdata 和 Rdata，在節點內部必須滿足 Ldata < Mdata < Rdata。

分支規則：

- 最左子樹：所有資料皆 < Ldata。
- 中左子樹：所有資料皆介於 > Ldata 且 < Mdata。
- 中右子樹：所有資料皆介於 > Mdata 且 < Rdata。
- 最右子樹：所有資料皆 > Rdata。

![image](https://hackmd.io/_uploads/SJgDZdeA-l.png)

### 2-3-4 Tree 加入操作

2-3-4 Tree 因為節點的容量變大了，所以 2-3-4 Tree 可徹底消除連鎖反應。

在 2-3 Tree 中採的是由下而上（Bottom-Up）的策略：先塞進葉節點，滿了了才往上推，如果父節點也滿了就繼續往上推。

但在實務上，2-3-4 Tree 最經典且最常被使用的策略是由上而下（Top-Down）。

#### 由上而下預先分裂（Top-Down）

在往下尋找葉節點的路上，只要看到 4-Node 就將其分裂。

操作流程：準備插入一筆新資料，從根節點（Root）開始一路往下尋找目標葉節點。

1. 遇到 2-Node 或 3-Node：順著大小規則繼續往下走。
2. 遇到 4-Node `(L, M, R)`：直接分裂。
    - 把中間的 M 往上推給父節點。
    - 左邊的 L 和右邊的 R 分裂成兩個獨立的 2-Node。
    - 分裂完之後，再繼續往下尋找。
3. 到達葉節點：把新資料按照大小順序塞進去。

這保證了每次往上推升資料時，父節點永遠都有空位可以收容它，永遠不需要再回頭往上處理連鎖反應。

### 加入操作範例：從零開始加入 2-3-4 Tree

依序插入 `10, 20, 30, 40, 50, 60`。

1. 插入 `10, 20, 30`
    - 一開始樹是空的，依序把這三個數字塞進根節點，空間足夠，根節點變成了一個極限狀態的 4-Node。
    - ![image](https://hackmd.io/_uploads/rkb97dx0Wx.png)
2. 插入 `40`（觸發根節點分裂）
    - 插入 `40` 時從根節點出發，由於根節點是 4-Nodes 因此直接分裂。
    - 中間值 `20` 往上推（因為它是 Root，所以直接變成新的 Root），`10` 和 `30` 變成子節點。
    - 分裂完後，繼續尋找 `40` 該放哪，由於 `40 > 20`，往右邊找，放在葉節點 `30` 中，變成 3-Node。
    - ![image](https://hackmd.io/_uploads/Hy_mNOe0Wl.png)
3. 插入 `50`
    - 從根節點 `20`（2-Node，不用分裂）出發，往右走到葉節點 `(30, 40)`（3-Node，不用分裂）。
    - 把 `50` 塞進去，右邊的葉節點變成了 4-Node。
    - ![image](https://hackmd.io/_uploads/ryH_4ulRWe.png)
4. 插入 `60`
    - 從根節點 `20` 出發，往右走。
    - 來到右子節點 `(30, 40, 50)`，發現是 4-Node，則分裂。
    - 中間值 `40` 往上推升給父節點。
    - 父節點 `20` 收取 `40` 變成 `(20, 40)`。
    - 原本的節點分裂成 `30` 和 `50`。
    - 分裂完成後，繼續尋找 60 的位置，由於 `60 > 40`，往最右邊走，來到葉節點 `50`。
    - ![image](https://hackmd.io/_uploads/BJKWBdxRWl.png)

### 2-3-4 Tree 刪除操作

#### 只能刪除葉節點

這點和 2-3 Tree 一模一樣：

如果要刪除的資料在內部節點，找它的中序後繼者（In-order Successor，右子樹中最小的值），把後繼者的值複製上來覆蓋，然後把目標改成去葉節點刪除那個後繼者。

所以，所有的刪除操作，最終都會變成走到葉節點刪除資料。

#### 由上而下，沿路養胖 2-Node

從根節點（Root）出發，準備一路往下走，假設現在站在父節點 `P`，下一步準備要走到子節點 `C`。

- 如果 `C` 是 3-Node 或 4-Node：直接進入該節點。
- 如果 `C` 是 2-Node：不能走進該節點，須想辦法養胖他。

怎麼養胖？看向 `C` 的兄弟節點 `S`：

**情況 A：兄弟 S 很富有（它是 3-Node 或 4-Node）**

既然兄弟有錢，就透過父節點來借。

- 操作：把父節點 `P` 夾在中間的那筆資料拉下來給 `C`，然後把兄弟 `S` 靠近我們這邊的資料推上去還給父節點 `P`。
- 結果：`C` 得到了一筆新資料，成功長胖變成 3-Node，父節點 `P` 資料數不變，兄弟 `S` 瘦了一點但依然合法。

圖解：目標在左子節點 `C`，向富有的右兄弟借。

![image](https://hackmd.io/_uploads/r1fbhdl0Zg.png)

![image](https://hackmd.io/_uploads/SkWt6dg0be.png)

**情況 B：兄弟 S 也是窮鬼（它是 2-Node）**

兄弟也只有一筆資料，沒辦法借，這時只能選擇合併。

- 操作：把父節點 `P` 夾在中間的那筆資料直接拉下來，和 `C` 以及 `S`，三者大團圓，合併成一個 4-Node。

父節點 `P` 被拉走一筆資料，父節點會不會變成空節點？不會。因為我們是沿路養胖下來的，除了根節點之外，保證走到 `P` 的時候，`P` 絕對已經被養胖成至少是 3-Node 了，所以 `P` 被抽走一筆資料，頂多退化回 2-Node。

圖解：目標在左子節點 `C`，與窮兄弟合併。

![image](https://hackmd.io/_uploads/HkEsTde0-g.png)

![image](https://hackmd.io/_uploads/Hy6haueCWx.png)

#### 特殊情況：如果連根節點都是 2-Node 怎麼辦？

一開始出發時，如果 Root 是 2-Node，且它的兩個子節點也都是 2-Node。

- 操作：直接把 Root 和兩個子節點，三者合併成一個全新的 4-Node Root。
- 結果：整棵樹就變矮了一層，然後繼續往下走。

### 2-3-4 Tree 的刪除操作範例

假設有棵 2-3-4 Tree 長這樣：

![image](https://hackmd.io/_uploads/S1f31Fl0Zl.png)

然後我們要刪除 10 這個節點。

1. 先從根節點出發，由於 10 < 40，往 20 前進，在此發現 20 是 2-Node，因此要先養胖他。
2. 20 節點的兄弟是 3-Node，因此可以借節點過來：
    - 把父節點的 40 拉下來，60 補過去。
    - 那原本的左子節點 50 則要順應 BST 規則給 20, 40 當作右子節點。
    - ![image](https://hackmd.io/_uploads/HkwPbFlCZe.png)
3. 繼續往下，找到葉節點 10，但他是 2-Node，也要先把他養胖。
    - 找兄弟 30 節點做合併（兩個都是 2-Node）
    - 將父節點的 20 拉下來（10 < 20 < 30）
    - 三者做合併。
    - ![image](https://hackmd.io/_uploads/HJG5bKgR-l.png)
4. 移除節點 10：
    - ![image](https://hackmd.io/_uploads/B1ciZYxAbl.png)

## 總整理

### 2-3 Tree

2-3 Tree 是一種自我平衡搜尋樹，為了解決一般二元搜尋樹（BST）在最糟情況下退化成直線的問題，透過允許節點存放多筆資料與向上分裂機制，確保樹始終保持絕對平衡。

### 特性與規則

- 節點種類：內部節點只能是 2-Node 或 3-Node。
- 排序規則：嚴格遵守左小、右大的搜尋樹性質。
- 絕對平衡：所有的葉節點（Leaf nodes）永遠在同一階層。

### 節點結構定義

- 2-Node：含 1 筆資料（Ldata），具 2 個子分支。左子樹恆小於 Ldata，右子樹恆大於 Ldata。
- 3-Node：含 2 筆資料（Ldata、Rdata，且 Ldata < Rdata），具 3 個子分支。左子樹恆小於 Ldata，中子樹介於兩者之間，右子樹恆大於 Rdata。

### 加入操作（Bottom-Up 策略）

- 基本原則：永遠從葉節點加入新資料，空間不足時樹會往上生長。
- 葉節點為 2-Node：直接放入資料，升級為 3-Node。
- 葉節點為 3-Node（分裂與推升）：暫時形成不合法的 4-Node。將 3 筆資料排序後，最小與最大值各自獨立為新的 2-Node，中間值「向上推升」至父節點。
- 連鎖反應：若推升後導致父節點也爆滿，則父節點繼續分裂推升，一路往上直到遇見有空位的長輩節點，或產生全新的根節點（整棵樹長高一層）。

### 刪除操作（Bottom-Up 策略）

- 內部節點刪除：不能直接挖除。須尋找中序後繼者（右子樹最小值）來覆蓋目標值，將問題轉化為「刪除葉節點」。
- 刪除 3-Node 葉節點：直接刪除目標，合法退化成 2-Node。
- 刪除 2-Node 葉節點（下溢 Underflow）：節點變空，必須向外求援。
- 向兄弟借（Rotation）：若親兄弟是 3-Node，將父節點資料拉下填補空位，並將兄弟中最靠近的一筆資料推上父節點。
- 與兄弟合併（Merge）：若親兄弟也是 2-Node（沒得借），則將父節點中夾在兩者間的資料拉下，與空節點、兄弟節點三者合併為一個新的 3-Node。
- 合併後遺症：拉下父節點可能導致父節點變空，此時需視父節點為新的空節點，繼續向上借用或合併。若根節點變空，則直接刪除，由合併出的節點成為新根節點（整棵樹變矮一層）。

### 2-3-4 Tree

2-3-4 Tree 是 2-3 Tree 的擴充版（紅黑樹的底層邏輯），透過增加節點容量並改用由上而下（Top-Down）策略，徹底解決了操作時繁瑣的連鎖反應。

### 特性與結構

- 節點種類：內部節點只能是 2-Node、3-Node 或 4-Node。
- 排序規則與絕對平衡：同 2-3 Tree，嚴格遵守區間大小劃分，且所有葉節點必在同一層。
- 4-Node 定義：含 3 筆資料（由小到大排序），具 4 個子分支，依據 3 筆資料切分出 4 個大小區間。

### 加入操作（Top-Down 預先分裂策略）

- 基本原則：由上往下尋找葉節點的過程中，只要遇到 4-Node 就強制預先分裂。
- 分裂機制：遇到 4-Node 時，將中間值往上推給父節點，左右兩值分裂為兩個獨立的 2-Node。
- 優勢：因為沿路已經將 4-Node 拆解，保證每次資料往上推升時，父節點絕對有空位收容，永遠不需要回頭處理連鎖反應。

### 刪除操作（Top-Down 沿路養胖策略）

- 基本原則：同樣將刪除目標轉化至葉節點進行。在由上往下尋找目標的過程中，只要遇到將要走入的子節點為 2-Node，就必須沿路養胖它，避免最終刪除時發生下溢。
- 向富有兄弟借：若該 2-Node 子節點的兄弟是 3-Node 或 4-Node，透過父節點周轉，將父節點資料拉下給子節點，兄弟的資料推上給父節點，成功將子節點養胖為 3-Node。
- 與貧窮兄弟合併：若兄弟也是 2-Node，則將父節點夾在中間的資料直接拉下，與子節點、兄弟節點大團圓合併成一個 4-Node。
- 特殊根節點情況：若出發時 Root 及其兩個子節點皆為 2-Node，則直接將三者合併為一個全新的 4-Node Root，整棵樹提早變矮一層。