C++でBツリー（B木）を実装するプログラム｜次数6の実装例

Bツリー（B木）は、1つのノードが2つ以上の子ノードを持つことができる、二分探索木を一般化した木構造です。自己平衡型のデータ構造の一種であり、データを常にソート済みの状態で保持しながら、対数時間 O(log n) での順次アクセス・検索・挿入・削除を実現します。この特性から、データベースやファイルシステムなど、大量のデータを効率的に扱う必要がある分野で広く採用されています。

本記事では、次数6のBツリーをC++で実装するプログラムを、アルゴリズムの流れとともに解説します。

アルゴリズム

ノードを木に挿入する関数 insert() の処理の流れは以下の通りです。

開始
    ノードを木に挿入するための関数 insert()
        変数 x を根（ルート）として初期化する
    x が葉ノードであり、かつもう1つ要素を格納できる余裕がある場合
        値 a を x に挿入する
    x が葉ノードでない場合
        次にたどるべき x の子ノードを探す
        子ノードに空きがあれば、x をその子ノードに移す
        子ノードが満杯の場合はそれを分割し、x を分割後のいずれか一方へ向ける
        （値 a が子の中央のキーより小さければ前半部分、大きければ後半部分を選択）
        分割の際には、子ノードから親 x へキーを1つ引き上げる
終了

サンプルコード

#include<iostream>
using namespace std;
struct BTree//ノードの宣言 {
    int *d;
    BTree **child_ptr;
    bool l;
    int n;
}*r = NULL, *np = NULL, *x = NULL;

BTree* init()//ノードの生成 {
    int i;
    np = new BTree;
    np->d = new int[6];//次数6
    np->child_ptr = new BTree *[7];
    np->l = true;
    np->n = 0;
    for (i = 0; i < 7; i++) {
        np->child_ptr[i] = NULL;
    }
    return np;
}

void traverse(BTree *p)//木の巡回 {
    cout<<endl;
    int i;
    for (i = 0; i < p->n; i++) {
        if (p->l == false) {
            traverse(p->child_ptr[i]);
        }
        cout << " " << p->d[i];
    }
    if (p->l == false) {
        traverse(p->child_ptr[i]);
    }
    cout<<endl;
}

void sort(int *p, int n)//キーの整列 {
    int i, j, t;
    for (i = 0; i < n; i++) {
        for (j = i; j <= n; j++) {
            if (p[i] >p[j]) {
                t = p[i];
                p[i] = p[j];
                p[j] = t;
            }
        }
    }
}

int split_child(BTree *x, int i) {
    int j, mid;
    BTree *np1, *np3, *y;
    np3 = init();//新しいノードの作成
    np3->l = true;
    if (i == -1) {
        mid = x->d[2];//中央のキーを取得
        x->d[2] = 0;
        x->n--;
        np1 = init();
        np1->l= false;
        x->l= true;
        for (j = 3; j < 6; j++) {
            np3->d[j - 3] = x->d[j];
            np3->child_ptr[j - 3] = x->child_ptr[j];
            np3->n++;
            x->d[j] = 0;
            x->n--;
        }
        for (j = 0; j < 6; j++) {
            x->child_ptr[j] = NULL;
        }
        np1->d[0] = mid;
        np1->child_ptr[np1->n] = x;
        np1->child_ptr[np1->n + 1] = np3;
        np1->n++;
        r = np1;
    } else {
        y = x->child_ptr[i];
        mid = y->d[2];
        y->d[2] = 0;
        y->n--;
        for (j = 3; j <6 ; j++) {
            np3->d[j - 3] = y->d[j];
            np3->n++;
            y->d[j] = 0;
            y->n--;
        }
        x->child_ptr[i + 1] = y;
        x->child_ptr[i + 1] = np3;
    }
    return mid;
}

void insert(int a) {
    int i, t;
    x = r;
    if (x == NULL) {
        r = init();
        x = r;
    } else {
        if (x->l== true && x->n == 6) {
            t = split_child(x, -1);
            x = r;
            for (i = 0; i < (x->n); i++) {
                if ((a >x->d[i]) && (a < x->d[i + 1])) {
                    i++;
                    break;
                } else if (a < x->d[0]) {
                    break;
                } else {
                    continue;
                }
            }
            x = x->child_ptr[i];
        } else {
            while (x->l == false) {
                for (i = 0; i < (x->n); i++) {
                    if ((a >x->d[i]) && (a < x->d[i + 1])) {
                        i++;
                        break;
                    } else if (a < x->d[0]) {
                        break;
                    } else {
                        continue;
                    }
                }
                if ((x->child_ptr[i])->n == 6) {
                    t = split_child(x, i);
                    x->d[x->n] = t;
                    x->n++;
                    continue;
                } else {
                    x = x->child_ptr[i];
                }
            }
        }
    }
    x->d[x->n] = a;
    sort(x->d, x->n);
    x->n++;
}

int main() {
    int i, n, t;
    cout<<"enter the no of elements to be inserted\n";
    cin>>n;
    for(i = 0; i < n; i++) {
        cout<<"enter the element\n";
        cin>>t;
        insert(t);
    }
    cout<<"traversal of constructed B tree\n";
    traverse(r);
}

プログラムのポイント

• BTree構造体：各ノードはキー配列 d、子ノードへのポインタ配列 child_ptr、葉かどうかを示すフラグ l、キーの個数 n を持ちます。
• init()：新しいノードを生成して初期化します。
• traverse()：木全体を再帰的に巡回し、すべてのキーを出力します。
• split_child()：満杯になったノードを中央のキーを基準に左右に分割し、中央のキーを親ノードへ引き上げます。
• insert()：挿入位置を探索しながら木を降りていき、途中で満杯のノードに出会ったら先に分割を行ってから挿入します。

実行結果

enter the no of elements to be inserted
7
enter the element
10
enter the element
20
enter the element
30
enter the element
40
enter the element
50
enter the element
60
enter the element
70
traversal of constructed B tree
10 20
30
40 50 60 70

このように、10〜70の7個の要素を挿入すると、巡回結果からキーが正しくソートされた状態でBツリーに格納されていることが確認できます。ノードが満杯になるたびに自動的に分割されるため、木の高さが低く保たれ、高速な検索・挿入が可能になっています。