Bツリーを使ってソートを実現するC++プログラムの解説

本記事では、Bツリー（B-Tree）を使用してソート済みの数列を取得する方法を解説します。Bツリーはn分木（n-ary tree）の一種です。ソートされた順序を得るには、まずBツリーを構築し、そこへ数値を次々と挿入していきます。ここで扱うBツリーは、1つのノードにつき最大5個の要素を保持できます。要素数が上限を超えた場合は、ノードを分割（スプリット）して新しいレベルを形成します。

各ノードが保持する要素は最大5個と非常に少ないため、ノード内のソートにはバブルソートを採用しています。扱う要素数が少ないため、全体のパフォーマンスに与える影響はほとんどありません。

構築したツリーを走査（トラバース）することで、各ノードが持つすべての値を取得できます。その結果として得られる要素列は、非降順（昇順）にソートされたものになります。

アルゴリズム

traverse(p)

入力：木のノード p
出力：木の走査順序

Begin
    for i in range 0 to n-1, do
        if p is not a leaf node, then
            traverse(child of p at position i)
        end if
        print the data at position i
        done
        if p is not a leaf node, then
            traverse(child of p at position i)
        end if
End

sort(a, n)

入力：ソート対象の配列 a と、その配列に含まれる要素数 n
出力：ソート済みの配列

Begin
    for i in range 0 to n-1, do
        for j in range 0 to n-1, do
            if a[i] > a[j], then
                swap a[i] and a[j]
            end if
        done
    done
End

split_node(x, i)

入力：分割対象のノード x。i は葉ノードの場合は (-1)、それ以外は正の値
出力：分割後のノードの中央要素

Begin
    Create a node np3, and mark it as leaf node
    if i is -1, then
        mid := Data from position 2 of x
        Set the data at position 2 of x to 0
        Reduce the number of data in x by 1
        create a new node called np1, and mark it as non-leaf node
        mark x as leaf node
        Insert all of the nodes of x from position 3 to 5 into np3
        Also insert all of the child reference of x from position 3 to 5 into np3
        Remove the inserted elements from the node x
        insert mid into the first position of np1
        make x as left child and np3 as right child of np1
        increase the element count of np1, and make this as root.
    else
        y := the subtree at location i
        mid := data from position 2 of y
        Set the data at position 2 of y to 0
        Reduce the number of data in y by 1
        Insert all of the nodes of y from position 3 to 5 into np3
        increase the element count of np3, and remove inserted elements from y
        add y child at position i, and add np3 at position i+1
    end if
End

insert(a)

入力：挿入する要素 a
出力：更新後のBツリー

Begin
    x := root
    if x is null, then
        create a root node and take root into x
    else
        if x is leaf node, and has 5 elements, then
            temp_node := split_child(x, -1)
            x := root
            i := find correct position to insert a
            x := child of x at position i
        else
            while x is not a leaf node, do
                i := find correct position to insert a
                if child of x at position i, has 5 elements, then
                    temp_node := split_child(x, i)
                    add temp_node data at position x->n of x
                else
                    x := child of x at position i
                end if
            done
        end if
    end if
    add a into x at position x->n
    sort elements of x
End

C++による実装コード

#include<iostream>
using namespace std;
struct BTreeNode{ //Bツリーのノード構造体を作成
    int *data;
    BTreeNode **child_ptr;
    bool leaf;
    int n;
}*root = NULL, *np = NULL, *x = NULL;
BTreeNode * getNode(){
    int i;
    np = new BTreeNode;
    np->data = new int[5]; //データフィールド5つとリンクフィールド6つを設定
    np->child_ptr = new BTreeNode *[6];
    np->leaf = true; //初期状態ではノードは葉
    np->n = 0;
    for (i = 0; i < 6; i++) {
        np->child_ptr[i] = NULL; //すべてのポインタをNULLで初期化
    }
    return np;
}
void traverse(BTreeNode *p) {
    cout<<endl;
    int i;
    for (i = 0; i < p->n; i++) { //Bツリー全体を再帰的に走査
        if (p->leaf == false){
            traverse(p->child_ptr[i]);
        }
        cout << " " << p->data[i];
    }
    if (p->leaf == false) {
        traverse(p->child_ptr[i]);
    }
    cout<<endl;
}
void sort(int *p, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j <= n; j++) {
            if (p[i] > p[j]){
                swap(p[i], p[j]);
            }
        }
    }
}
int split_child(BTreeNode *x, int i){ //ノードを「1つの親＋2つの子」の3ノードに分割
    int mid;
    BTreeNode *np1, *np3, *y;
    np3 = getNode(); //np3という新しい葉ノードを作成
    np3->leaf = true;
    if (i == -1) {
        mid = x->data[2]; //中央の要素を取得
        x->data[2] = 0;
        x->n--;
        np1 = getNode();
        np1->leaf = false;
        x->leaf = true;
        for (int j = 3; j < 5; j++) {
            np3->data[j - 3] = x->data[j];
            np3->child_ptr[j - 3] = x->child_ptr[j];
            np3->n++;
            x->data[j] = 0;
            x->n--;
        }
        for (int j = 0; j < 6; j++) {
            x->child_ptr[j] = NULL;
        }
        np1->data[0] = mid;
        np1->child_ptr[np1->n] = x;
        np1->child_ptr[np1->n + 1] = np3;
        np1->n++;
        root = np1;
    } else {
        y = x->child_ptr[i];
        mid = y->data[2];
        y->data[2] = 0;
        y->n--;
        for (int j = 3; j < 5; j++) {
            np3->data[j - 3] = y->data[j];
            np3->n++;
            y->data[j] = 0;
            y->n--;
        }
        x->child_ptr[i] = y;
        x->child_ptr[i + 1] = np3;
    }
    return mid;
}
void insert(int a){ //Bツリーへの挿入
    int i, tmp_node;
    x = root;
    if (x == NULL) {
        root = getNode();
        x = root;
    } else {
        if (x->leaf == true && x->n == 5){ //ノードが葉であり、データを5つ持つ場合
            tmp_node = split_child(x, -1); //ノードを分割して新しいレベルを作成
            x = root;
            for (i = 0; i < (x->n); i++) {
                if ((a > x->data[i]) && (a < x->data[i + 1])) {
                    i++;
                    break;
                } else if (a < x->data[0]) {
                    break;
                } else {
                    continue;
                }
            }
            x = x->child_ptr[i];
        } else {
            while (x->leaf == false) {
                for (i = 0; i < (x->n); i++) {
                    if ((a > x->data[i]) && (a < x->data[i + 1])) {
                        i++;
                        break;
                    } else if (a < x->data[0]) {
                        break;
                    } else {
                        continue;
                    }
                }
                if ((x->child_ptr[i])->n == 5) {
                    tmp_node = split_child(x, i);
                    x->data[x->n] = tmp_node;
                    x->n++;
                    continue;
                } else {
                    x = x->child_ptr[i];
                }
            }
        }
    }
    x->data[x->n] = a;
    sort(x->data, 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 tree\n";
    traverse(root);
}

実行結果

enter the no of elements to be inserted
8
enter the element
54
enter the element
23
enter the element
98
enter the element
52
enter the element
10
enter the element
23
enter the element
47
enter the element
84
traversal of constructed tree
10 23 23 47
52
54 84 98

このように、8個の整数をBツリーに挿入した後、ツリーを走査することで 10 23 23 47 52 54 84 98 という昇順にソートされた数列が得られます。重複した値（23）も正しく保持されている点にも注目してください。