【考試向】資料結構筆記（2-3 Tree 跟 2-3-4 Tree）
【考試向】資料結構筆記（2-3 Tree 跟 2-3-4 Tree）
歡迎你點入本篇文章！我是 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 必須滿足以下三個嚴格的條件：
- 節點種類限制：樹上的每一個內部節點，只能是 2-Node（2-節點）或3-Node（3-節點）。
- 搜尋樹性質（排序規則）：左子樹的值永遠小於父節點的值，右子樹的值永遠大於父節點的值。
- 絕對平衡（Perfectly Balanced）：這棵樹的所有葉節點（Leaf nodes，也就是最底層沒有子節點的節點）都必須在同一個階層（Level）。
2-Node 與 3-Node
什麼是 2-Node（2-節點）？
「2-Node」代表這個節點有 2 個子節點分支（左子樹與右子樹），也就是一般二元樹儲存資料的形式。
為了區分這 2 個分支，這個節點內部只會存放 1 筆資料。
假設這唯一的一筆資料叫做 Ldata。
分支規則：
- 左子樹（Left Child）：裡面所有的資料值，都必須小於（<）Ldata。
- 右子樹（Right Child）：裡面所有的資料值，都必須大於（>）Ldata。
架構示意圖：
左子節點存放的資料必須小於 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。
架構示意圖：
- Ldata < Rdata
- 左子節點存放的資料必須小於 Ldata
- 中子節點存放的資料必須大於 Ldata，小於 Rdata
- 右子節點存放的資料必須大於 Rdata
2-3 Tree 的加入操作
在 2-3 Tree 中加入新資料，則有兩條規則：
- 永遠從葉節點（Leaf Node）加入：不會一開始就把新資料插在樹的中間層，總會先往下搜尋，找到最底層合適的葉節點，然後把資料塞進去。
- 樹是往上生長的：當葉節點空間不夠時，資料會往上推升（Promote），甚至產生新的根節點（Root），讓整棵樹長高一層。
情況一：葉節點是 2-Node
當找到應該插入新資料的葉節點時，發現它只是一個 2-Node（裡面只有一筆資料 Ldata），還有一個空位。
直接把新資料放進這個節點中，並依照大小排序，這個節點就變成了一個 3-Node（包含 Ldata 與 Rdata）。
如：2-node 變化 3-node 的過程（左是加入前，右是加入後）。
情況二：葉節點是 3-Node
當找到的葉節點是 3-Node（裡面已有 Ldata 和 Rdata），沒有空位可以放新資料了，這時就會觸發 2-3 Tree 的機制：分裂（Split）與推升（Promote）。
操作流程：
- 暫時塞入：先把新資料硬塞進去，變成一個暫時且不合法的 4-Node（裡面有 3 筆資料）。
- 排序：將這 3 筆資料由小到大排序（小、中、大）。
- 分裂拆解：
- 最小的資料留在原地，變成左邊新的 2-Node。
- 最大的資料獨立出來，變成右邊新的 2-Node。
- 向上推升：中間的那筆資料會往上，加入到它們的父節點（Parent）中。
如：
情況三：父節點也是 3-Node
情況二發生時的延伸狀況，當中間的資料被推升到父節點時，如果父節點原本也已經是一個客滿的 3-Node 怎麼辦？
父節點接收了被推升上來的資料後，也會變成一個暫時的 4-Node，於是父節點也必須再次分裂，並將它自己的中間值繼續往上推升給祖父節點。
這個過程會產生連鎖反應，一路往上推，直到遇到一個有空位（2-Node）的長輩節點可以將它收容為止。
如現在有一棵樹：
然後現在要加入 25 進去：
- 從根節點開始比對：25 小於 30，所以往左子樹走。
- 找到左邊的葉節點
(10, 20)，把 25 塞進去。 - 此時葉節點變成暫時的 4-Node：
(10, 20, 25)。 - 分裂與推升：
- 10 留在原地（成為新的左邊 2-Node）。
- 25 獨立出來（成為新的右邊 2-Node）。
- 中間值 20 往上給父節點。
可以發現根節點也成為 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）
從零建立一棵 2-3 Tree
依序插入 10, 20, 30, 40, 50：
2-3 Tree 的刪除操作
1. 找刪除目標是否為葉節點
如果要刪除的資料剛好在最底層的葉節點就直接進入第二步。
但如果要刪除的資料在內部節點（樹的中間或根節點），不能直接把它挖掉，因為這樣底下的子樹會斷掉。
解法：找節點做替換。
尋找這筆資料的中序後繼者（In-order Successor），即右子樹中最小的值（或者左子樹中最大的值也可以）。
把這個後繼者的值複製上來覆蓋掉要刪除的資料，然後任務就變成了去葉節點刪除那個後繼者。
因為後繼者一定在葉節點上，所以所有刪除動作，最終都會變成刪除葉節點資料的問題。
2. 刪除葉節點上的資料（兩種情況）
情況一：目標在 3-Node 中
如果包含目標資料的葉節點是一個 3-Node（裡面有兩筆資料），直接把目標資料刪掉，該節點會剩下 1 筆資料，合法退化成一個 2-Node，樹的結構不需要任何改變。
圖例：刪除 30。上為刪除前，下為刪除後。
情況二：目標在 2-Node 中
如果葉節點是一個 2-Node（裡面只有一筆資料），你把它刪掉後，這個節點就空了（變成 0-Node），違反了 2-3 Tree 的規則，稱之為下溢（Underflow）。
為了解決這個空節點，有兩個解決方案，優先嘗試借，借不到再合併。
3. 空節點情形（借用與合併）
當遇到空節點時，只能向直接相鄰的親兄弟（左兄弟或右兄弟）求救。
方案 A：向富有的兄弟借（Rotation / 旋轉）
如果旁邊的親兄弟是一個 3-Node（也就是它很富有，有兩筆資料），那就可以跟它借。
注意：不能直接把兄弟的資料拿過來，會破壞大小順序，須透過父節點來做轉換。
操作流程（以向右兄弟借為例）：
- 把父節點的資料拉下來，填補空節點。
- 把右兄弟裡面最小的資料推上去，填補父節點的空缺。
圖例：刪除 10（向右兄弟借）。
- 父節點 20 下來填補空節點。
- 接著把右兄弟最小節點 30 往上提，結束。
方案 B：與貧窮的兄弟合併（Merge）
如果旁邊的兄弟也是一個 2-Node（大家都很窮，只有一筆資料，沒得借），那只能選擇合併。
操作流程：
- 把父節點中夾在空節點和兄弟之間的那筆資料拉下來。
- 將空節點、拉下來的父節點資料、以及兄弟節點，三者合併成一個新的 3-Node。
圖例：刪除 10（兄弟只有 30，沒得借）。
4. 連鎖反應與樹變矮（合併的後遺症）
在方案 B 當中，把父節點的資料拉下來會導致兩種後果：
- 父節點原本是 3-Node：父節點被拉走一筆資料後，還剩一筆，變成合法的 2-Node。
- 父節點原本是 2-Node：父節點唯一的資料被拉走，父節點自己變成了空節點。
遇到後果 2 時怎麼辦？把父節點當作剛才的葉節點，重新執行第三步（向它的兄弟借，或者合併）。
最終情況：根節點變空（樹變矮）
如果連鎖反應一路傳遞到最頂端的根節點（Root），導致根節點的資料被拉下來合併，根節點變成了空節點。
結論：直接把這個空的根節點刪除，原本合併出來的那個節點，就會自動成為整棵樹「新的根節點」。
回到前面方案 B 的例子，由於現在 (20, 30) 變成葉節點，而父節點是空的，所以 (20, 30) 就變成新的根節點。
父節點原本是 3-Node 的情形
情況一：左邊的子節點空了（與中間兄弟合併）
空節點在最左邊，兄弟在中間，它們之間夾著的是父節點左邊的資料（30）。
操作：把父節點左邊的 30 拉下來，跟中間的兄弟合併。
結果：父節點剩下 50 變成合法的 2-Node。
圖解：（上為合併前，下為合併後）
情況二：右邊的子節點空了（與中間兄弟合併）
空節點在最右邊，兄弟在中間，它們之間夾著的是父節點右邊的資料（50）。
操作：把父節點右邊的 50 拉下來，跟中間的兄弟合併。
結果：父節點剩下 30 變成合法的 2-Node。
圖解：（上為合併前，下為合併後）
情況三：中間的子節點空了（可以選左邊或右邊合併）
如果破洞剛好在中間，這時有兩個選擇（兩種做法都是合法的，只要程式邏輯一致即可）：
選擇 A：與「左兄弟」合併
空節點與左兄弟之間夾著的是 30。
操作：拉下 30，與左兄弟合併，父節點剩下 50。
選擇 B：與「右兄弟」合併
空節點與右兄弟之間夾著的是 50。
操作：拉下 50，與右兄弟合併，父節點剩下 30。
2-3 Tree 刪除操作範例
假設現在有一棵 2-3 Tree 長這樣：
現在要刪除 10，由於他是 2-Node，因此刪除後要跟兄弟借資料，但他的兄弟也是 2-Node，所以借不了，所以把 20 拉下來合併變成：
但原本的父節點成為空節點，因此再跟兄弟 (40, 60) 借，由於他是 3-Node，所以直接借：
- 把根節點
30拉下來，填補左邊的空缺。 - 把右兄弟裡面最小的
40推上去，成為新的根節點。 - 右兄弟剩下
60，退化成 2-Node。
處理完後，接下來要做的是怎麼處理 60 底下的子節點。
這邊就直接根據 BST 的規則分配即可，由於 35 比 60 小、也比 40 小，但比 30 大，所以分配給 30 當作右子節點，剩餘的兩個 50、70 根據規則就直接留下來即可。（50 當左子節點，70 當右子節點）
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 必須滿足以下三個條件：
- 節點種類限制：樹上的每一個內部節點，只能是 2-Node、3-Node 或 4-Node。
- 搜尋樹性質（排序規則）：由左至右，子樹的值必須嚴格遵照父節點資料的大小區間進行劃分。
- 絕對平衡：這棵樹的所有葉節點（Leaf nodes）都必須在同一個階層（Level）。
2-Node
「2-Node」代表這個節點有 2 個子節點分支。
為了區分這 2 個分支，這個節點內部只存放 1 筆資料。
假設這筆資料為 Ldata。
分支規則：
- 左子樹：所有資料皆 < Ldata。
- 右子樹：所有資料皆 > Ldata。
示意圖：
3-Node
「3-Node」代表這個節點有 3 個子節點分支。
為了劃分出 3 個區塊，節點內部必須存放 2 筆資料。
假設這兩筆資料為 Ldata 和 Mdata，在節點內部必須滿足 Ldata < Mdata。
分支規則：
- 左子樹：所有資料皆 < Ldata。
- 中間子樹：所有資料皆介於兩者之間，即 > Ldata 且 < Mdata。
- 右子樹：所有資料皆 > Mdata。
示意圖：
4-Node
「4-Node」代表這個節點有 4 個子節點分支。
為了能劃分出 4 個區間，節點內部必須存放 3 筆資料。
假設這三筆資料分別為 Ldata、Mdata 和 Rdata，在節點內部必須滿足 Ldata < Mdata < Rdata。
分支規則：
- 最左子樹：所有資料皆 < Ldata。
- 中左子樹：所有資料皆介於 > Ldata 且 < Mdata。
- 中右子樹：所有資料皆介於 > Mdata 且 < Rdata。
- 最右子樹：所有資料皆 > Rdata。
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）開始一路往下尋找目標葉節點。
- 遇到 2-Node 或 3-Node：順著大小規則繼續往下走。
- 遇到 4-Node
(L, M, R)：直接分裂。- 把中間的 M 往上推給父節點。
- 左邊的 L 和右邊的 R 分裂成兩個獨立的 2-Node。
- 分裂完之後，再繼續往下尋找。
- 到達葉節點：把新資料按照大小順序塞進去。
這保證了每次往上推升資料時，父節點永遠都有空位可以收容它，永遠不需要再回頭往上處理連鎖反應。
加入操作範例：從零開始加入 2-3-4 Tree
依序插入 10, 20, 30, 40, 50, 60。
- 插入
10, 20, 30- 一開始樹是空的，依序把這三個數字塞進根節點，空間足夠，根節點變成了一個極限狀態的 4-Node。
- 插入
40（觸發根節點分裂）- 插入
40時從根節點出發，由於根節點是 4-Nodes 因此直接分裂。 - 中間值
20往上推（因為它是 Root，所以直接變成新的 Root），10和30變成子節點。 - 分裂完後，繼續尋找
40該放哪，由於40 > 20，往右邊找，放在葉節點30中，變成 3-Node。 
- 插入
- 插入
50- 從根節點
20（2-Node，不用分裂）出發，往右走到葉節點(30, 40)（3-Node，不用分裂）。 - 把
50塞進去，右邊的葉節點變成了 4-Node。 
- 從根節點
- 插入
60- 從根節點
20出發，往右走。 - 來到右子節點
(30, 40, 50)，發現是 4-Node，則分裂。 - 中間值
40往上推升給父節點。 - 父節點
20收取40變成(20, 40)。 - 原本的節點分裂成
30和50。 - 分裂完成後，繼續尋找 60 的位置，由於
60 > 40，往最右邊走，來到葉節點50。 
- 從根節點
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，向富有的右兄弟借。
情況 B：兄弟 S 也是窮鬼（它是 2-Node）
兄弟也只有一筆資料，沒辦法借，這時只能選擇合併。
- 操作：把父節點
P夾在中間的那筆資料直接拉下來，和C以及S，三者大團圓，合併成一個 4-Node。
父節點 P 被拉走一筆資料，父節點會不會變成空節點？不會。因為我們是沿路養胖下來的，除了根節點之外，保證走到 P 的時候，P 絕對已經被養胖成至少是 3-Node 了，所以 P 被抽走一筆資料，頂多退化回 2-Node。
圖解：目標在左子節點 C，與窮兄弟合併。
特殊情況：如果連根節點都是 2-Node 怎麼辦？
一開始出發時，如果 Root 是 2-Node，且它的兩個子節點也都是 2-Node。
- 操作：直接把 Root 和兩個子節點，三者合併成一個全新的 4-Node Root。
- 結果：整棵樹就變矮了一層，然後繼續往下走。
2-3-4 Tree 的刪除操作範例
假設有棵 2-3-4 Tree 長這樣：
然後我們要刪除 10 這個節點。
- 先從根節點出發，由於 10 < 40，往 20 前進，在此發現 20 是 2-Node，因此要先養胖他。
- 20 節點的兄弟是 3-Node，因此可以借節點過來：
- 把父節點的 40 拉下來，60 補過去。
- 那原本的左子節點 50 則要順應 BST 規則給 20, 40 當作右子節點。
- 繼續往下，找到葉節點 10，但他是 2-Node，也要先把他養胖。
- 找兄弟 30 節點做合併（兩個都是 2-Node）
- 將父節點的 20 拉下來（10 < 20 < 30）
- 三者做合併。
- 移除節點 10：
總整理
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，整棵樹提早變矮一層。
