データ構造におけるBツリーの削除操作とアルゴリズムを解説

Bツリー(B-Tree)は、データベースやファイルシステムなどで広く活用されている平衡木データ構造です。ここでは、Bツリーからノード(キー)を削除する手順について詳しく解説します。

Bツリーの例

まず、以下のようなBツリーを想定してみましょう。

削除操作の基本ルール

Bツリーからの削除処理は、大きく分けて2つの段階があります。まず最初に、削除対象の要素を検索と同じ要領で見つけます。次に、実際の削除を行う際には、Bツリー特有のルールを守る必要があります。

Bツリーでは、各ノードは最低でもm/2個の要素を持たなければなりません。そのため、要素を削除した結果、あるノードの残り要素数がm/2未満になった場合には、そのノードは自動的に調整されます。また、ノード全体が削除された場合には、その子ノード同士がマージ(統合)されます。マージ後のサイズがmと同じになった場合には、さらに2つの部分に分割され、中央値が再び親ノードへと繰り上げられます。

具体例：キー46を削除する場合

例として、キー「46」を削除するケースを考えてみましょう。削除後、2つの子ノード[45]と[47, 49]がマージされ、[45, 47, 49]という1つのノードになります。そして、中央値にあたる47が親ノードへと繰り上げられます。

削除アルゴリズム

以下に、Bツリーからキーを削除するアルゴリズム BTreeDelete(x, key) を示します。

入力: ツリーの根(root)と、削除対象のキー

なお、ここでは削除対象のキーがツリー内に存在することを前提とします。

xが葉(leaf)の場合
    xからキー「key」を持つオブジェクトを削除する
else if xにキー「key」を持つオブジェクトが含まれない場合
    キー範囲が「key」を保持している子 x->child[i] を特定する
    y := x->child[i]
    if yがm/2個の要素を持っている場合
        yの直左または直右の兄弟ノードzがm/2より1つ以上多いオブジェクトを
        持っているならば、x->key[i]をxからyへ移動させてオブジェクトを1つ追加し、
        zの最後または最初のオブジェクトをxへ移動する。
        yが非葉ノードの場合は、zの最後または最初の子ポインタもyへ移動する
    else
        yの隣接する兄弟がm/2個の要素しか持たない場合は、
        yを隣接する兄弟ノードとマージする
    end if
    BTreeDelete(y, key)
else
    if x内で「key」に先行するyがm/2 + 1個以上のオブジェクトを持っている場合
        yを根とする部分木において「key」の先行要素(predecessor)kを見つけ、
        その部分木からkを再帰的に削除し、x内のkeyをkで置き換える
    else if yがm/2個の要素しか持たない場合
        x内で「key」の直後に続く子zを確認する
        if zがm/2+1個以上の要素を持っている場合
            zを根とする部分木において「key」の後続要素(successor)kを見つけ、
            部分木からkを再帰的に削除し、x内のkeyをkで置き換える
    else
        yとzの両方がm/2個の要素しか持たない場合は、両者を1つのノードに
        マージし、「key」も新しいノードへ押し下げる。
        その後、この新しいノードから「key」を再帰的に削除する
    end if
end if