C++でFusionTree（フュージョンツリー）を実装する方法

FusionTree（フュージョンツリー）は、wビット整数をキーとして連想配列（辞書）操作を高速に実現するための木構造データ構造です。各ノードが複数のキーを持つ多分木構造を採用しており、B木に似た性質を持ちながら、ビット演算を活用することで従来の平衡木より高速な検索が可能になります。

本記事では、6ビット整数を格納するFusionTreeをC++で実装するサンプルプログラムを、アルゴリズムの手順・コード・実行結果とともにわかりやすく解説します。

FusionTreeの主な特徴

• 1つのノードが最大6個のキーと7個の子ポインタを持つ多分木構造
• ノード内のキーは常にソートされた状態で管理される
• ノードが満杯になった時点で分割（スプリット）を行うことで木のバランスを維持
• 挿入・検索・走査などの基本操作を効率的に実行できる

アルゴリズムの手順

プログラムで使用する主な関数と処理の流れは以下の通りです。

Begin
    木に挿入する要素の個数と、各要素の値を入力として受け取る。
    構造体FusionTreeを定義し、必要な変数を宣言する。
    新しいノードを生成する関数 init() を作成する。
    木を走査して内容を表示する関数 traverse() を作成する。
    ノード内のキーをソートする関数 sort() を作成する。
    満杯になったノードを分割する関数 split_child() を作成する。
    キーを木に挿入する関数 insert() を作成する。
    main() 内で insert() を呼び出してFusionTreeを構築し、
    traverse() を呼び出して結果を表示する。
End

各関数の役割

• init()：新しいノードを確保し、キー配列（int[6]）、子ポインタ配列（7個）、葉フラグ、キー数を初期化します。
• traverse()：再帰的に木を巡回し、すべてのキーを順番に出力します。
• sort()：単純な交換ソートにより、ノード内のキーを昇順に並べ替えます。
• split_child()：キーが6個に達したノードを中央値（3番目のキー）を基準に左右に分割し、親へ中央値を引き上げます。
• insert()：適切な挿入位置を探索しながら降りていき、途中で満杯ノードを見つけたら分割してから挿入します。

サンプルコード

以下がC++による実装例です。

#include<iostream>
using namespace std;

// ノードの宣言
struct FusionTree {
    int *d;                    // キーの配列
    FusionTree **child_ptr;    // 子ポインタの配列
    bool l;                    // 葉ノードかどうかのフラグ
    int n;                     // 現在保持しているキーの数
}*r = NULL, *np = NULL, *x = NULL;

// 新しいノードを作成する
FusionTree* init() {
    int i;
    np = new FusionTree;
    np->d = new int[6];
    np->child_ptr = new FusionTree *[7];
    np->l = true;
    np->n = 0;
    for (i = 0; i < 7; i++) {
        np->child_ptr[i] = NULL;
    }
    return np;
}

// 木を再帰的に走査して表示する
void traverse(FusionTree *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(FusionTree *x, int i) {
    int j, mid;
    FusionTree *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 fusion tree\n";
    traverse(r);
}

実行結果

10〜70の7つの要素を順に挿入した場合の出力例です。

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 fusion tree
10 20
30
40 50 60 70

まとめ

このプログラムでは、B木と同様の考え方を応用し、ノードの満杯時に中央値を親へ引き上げて木を分割することで、バランスの取れたFusionTreeを構築しています。挿入のたびに適切な子ノードを選んで降りていくことで、常に整序された状態を保ちながらデータを管理できます。FusionTreeは理論的にはワード並列性を利用した高速な検索が魅力のデータ構造であり、本実装はその基本的な枠組みを理解するのに最適な入門例といえます。