2-3-4 樹筆記

基本定義

• 2-3-4 樹 是一種 自平衡多路搜尋樹（Balanced Multi-Way Search Tree），每個節點最多可以包含 2、3 或 4 個子節點，因此命名為 2-3-4 樹。
• 2-3-4 樹的節點有以下三種類型：
  1. 2-節點：包含 1 個鍵與 2 個子節點。
  2. 3-節點：包含 2 個鍵與 3 個子節點。
  3. 4-節點：包含 3 個鍵與 4 個子節點。
• 鍵值大小順序規則：
  • 所有左子樹的鍵值小於父節點的第一個鍵值。
  • 中間子樹的鍵值介於父節點的兩個鍵值之間。
  • 右子樹的鍵值大於父節點的第二個鍵值。

特點

• 2-3-4 樹是一種 完全平衡樹，所有葉節點在同一層，樹的高度盡量保持最低，以便在最壞情況下仍能保證 O(log n) 的操作效率。
• 與其他平衡樹相比，2-3-4 樹因其節點可以容納多個鍵值，所以在插入與刪除時，調整的次數比 AVL 樹或紅黑樹少。

操作時間複雜度

• 搜尋（Search）：O(log n)
• 插入（Insert）：O(log n)
• 刪除（Delete）：O(log n)

常見操作

插入（Insertion）

1. 從根節點開始：
   • 若根節點是 4-節點，則先分裂根節點，將中間鍵值提升，然後繼續插入。
2. 找到適當的子樹位置：
   • 按照鍵值大小找到合適的子樹進行遞迴搜索。
3. 處理 4-節點：
   • 當遇到 4-節點時，將該節點進行分裂，將中間的鍵值提升到父節點（如果父節點也是 4-節點，則繼續分裂），將 4-節點分解為兩個 2-節點。
4. 插入新鍵值：
   • 將新鍵值插入到合適的 2-節點或 3-節點中，保證節點內的鍵值順序正確。

刪除（Deletion）

1. 找到要刪除的鍵值位置：
   • 若刪除的是葉節點的鍵值，直接刪除即可。
2. 刪除內部節點的鍵值：
   • 用前驅或後繼鍵值替換要刪除的鍵值，然後在葉節點中刪除前驅或後繼鍵值。
3. 處理 2-節點的鍵值不足：
   • 若刪除操作導致節點鍵值不足（2-節點變成 1-節點），則需要進行「鍵值借用」或「合併」操作。
   • 鍵值借用：從相鄰兄弟節點中借取一個鍵值，使當前節點成為 2-節點。
   • 合併節點：若兄弟節點是 2-節點，則將兄弟節點與父節點的鍵值合併，形成新的 3-節點或 4-節點。

節點分裂（Node Split）

• 當 4-節點插入新鍵值後無法容納更多的鍵值時，需要進行節點分裂：
  • 將 4-節點中的中間鍵值提升到父節點。
  • 4-節點分解為兩個 2-節點。
  • 若父節點也是 4-節點，則繼續對父節點進行分裂，直到樹恢復平衡。

優缺點

優點

• 高度平衡：所有葉節點都位於相同的深度，避免了退化成鏈表的情況。
• 操作簡單：每個節點最多只有三個鍵值，可以有效地減少旋轉與調整次數。
• 穩定性高：適合用於資料庫索引等需要大量查詢操作的場景。

缺點

• 節點需要儲存更多鍵值：相較於二元搜尋樹，每個節點需要儲存更多鍵值與子節點指標，因此節點的記憶體消耗較大。
• 插入與刪除較為複雜：當節點鍵值數過多時，可能需要進行多次分裂或合併操作。

使用場景

• 資料庫系統索引結構：如 B 樹、B+ 樹等結構的基礎，用來提升資料庫查詢效能。
• 檔案系統管理：用來建立檔案系統的層次結構，方便快速查找檔案或資料夾。
• 平衡樹管理：適合用於鍵值數量較多且需要平衡操作的應用場景。