B樹 C++ 完整實作：插入、刪除、分裂、合併與層序列印

B樹 C++ 完整實作：插入、刪除、分裂、合併與層序列印

B樹 是一種自平衡的多路搜尋樹，廣泛應用於資料庫索引與檔案系統。本文提供一個完整、可編譯執行的 C++ B樹實作 (階數 M=2，即 2-3-4 樹)，涵蓋插入、刪除、節點分裂/合併、前驅/後繼查找、鍵值交換等核心操作，並附帶層序遍歷輸出驗證。

資料結構定義

class BTree {
    static const int M = 2; // 階數，每個節點最多 2*M-1=3 個鍵，2*M=4 個孩子

    struct BTNode {
        int keyNum;                 // 當前鍵數量
        int key[2 * M - 1];         // 鍵陣列
        BTNode* child[2 * M];       // 孩子指標陣列
        bool isLeaf;                // 是否葉子節點
    };

    BTNode* root;

    // 私有輔助方法...
public:
    BTree(); ~BTree();
    void insert(int key);
    void remove(int key);
    BTNode* search(int key, int& index);
    void PrintRow(); // 層序列印
};

核心操作邏輯解析

插入流程

1. 若根節點滿 (3 個鍵)，建立新根，分裂舊根，樹高增加 1。
2. 遞迴下降至葉子節點，確保路徑上節點不滿 (透過 SplitChild 預先分裂)。
3. 在葉子節點有序插入鍵值。

節點分裂

當節點擁有 2*M-1 個鍵時分裂：

• 中間鍵 (第 M 個) 上移至父節點。
• 左半部 (前 M-1 個鍵) 留在原節點。
• 右半部 (後 M-1 個鍵) 移至新建立的兄弟節點。
• 若非葉子，對應移動孩子指標。

刪除流程

1. 定位鍵值所在節點。
2. 若為葉子，直接移除鍵值。
3. 若為內部節點，以前驅 (左子樹最大) 或後繼 (右子樹最小) 替換，遞迴刪除該前驅/後繼。
4. 刪除後若節點鍵數 < M-1，嘗試向兄弟借鍵 (ExchangeLeft/RightNode) 或與兄弟合併 (merge)。
5. 根節點特殊處理：若根只剩 1 個鍵且兩孩子皆為 M-1，合併並降低樹高。

關鍵輔助操作

測試主程式與輸出

int main() {
    BTree tree;
    // 插入 20 個字元鍵值
    string keys = "cngah ekqmwflt zydprxys";
    for (char c : keys) if (c != ' ') tree.insert(c);
    
    tree.remove('n');
    tree.remove('b'); // 不存在
    
    tree.PrintRow(); // 層序列印樹結構
    return 0;
}

完整原始碼結構

程式碼包含以下核心部分 (完整可編譯版本請參考原始輸入)：

• 建構子/解構子：初始化空根節點，解構時層序釋放所有節點記憶體。
• Search：標準 B樹搜尋，回傳節點與鍵索引。
• InsertNonFull / SplitChild：插入核心遞迴邏輯。
• RemoveNonLess / merge / ExchangeLeft/RightNode：刪除核心邏輯。
• PrintRow：使用佇列實現層序遍歷，每行輸出一個節點的所有鍵。

學習重點提示

• 理解 M (最小度數) 如何決定節點容量與分裂/合併閾值。
• 掌握「預先分裂」策略：下降過程中確保目標節點不滿，避免回溯。
• 刪除時「借鍵優先、合併次之」的平衡維護邏輯。
• 根節點分裂增加樹高、合併減少樹高的特殊處理。