Bツリーデータ構造
1. 概要
このチュートリアルでは、自己平衡型ツリーデータ構造であるBツリーについて説明します。 Bツリーのプロパティとさまざまな操作を紹介します。
2. 序章
Bツリーはツリーデータ構造です。 このツリー構造では、データはノードとリーフの形式で格納されます。 Bツリーは自己平衡型ソート検索ツリーとして知られています。 これは、バイナリ検索ツリー（BST）のより複雑で更新されたバージョンであり、追加のツリープロパティがあります。
バイナリ検索ツリーとBツリーの主な違いは、Bツリーが親ノードに対して複数の子ノードを持つことができることです。ただし、バイナリ検索ツリーには、親に対して2つの子ノードしか含めることができません。ノード。
二分探索木とは異なり、 Bツリーはノード内に複数のキーを持つことができます。任意のノードのキーの数と子の数は、B-の順序によって異なります。木。 キーは、任意のノードに格納される値です。 Bツリーの例を見てみましょう。
3. プロパティ
BツリーのいくつかのプロパティはBSTに似ています。 親ノードのキーは、常に左側のサブツリーノードのキー値よりも大きくなります。 同様に、親ノードのキーは常に右側のサブツリーノードのキー値よりも小さくなります。
単一ノードに対して複数のキーを持つことができます。単一ノードは3つ以上の子を持つことができます。
すべてのリーフノードは同じレベルである必要があります。リーフノードとは、子ノードがないノードを意味します。
Bツリーの順序が。であるとします。 これは、すべてのノードが最大の子を持つことができることを意味します。 したがって、すべてのノードは、ルートノードを除く最大キーと最小キーを持つことができます。
順序のBツリーを取りましょう。 Bツリーのプロパティによると、どのノードでも最大数のキーを持つことができます。 したがって、この場合のキー。 さらに、どのノードも最小限のキーを持つことができます。 したがって、キー。
4. Bツリー操作
他のツリーデータ構造と同様に、 Bツリーでは、検索、挿入、削除の3つの主要な操作を実行できます。各操作について1つずつ説明します。
4.1. 検索
Bツリーの構造は、いくつかのプロパティが追加されたバイナリ検索ツリーに似ています。 したがって、Bツリーでの検索操作はBSTと同じように機能します。 最初に、ルートノードから検索を開始します。
検索するノードのキー値に応じて、ルートノードから左または右のサブツリーに移動します。 これに加えて、Bツリーでは、ノードに3つ以上のブランチが存在する可能性があるため、いくつかの決定があります。
最良の場合と最悪の場合のBツリーの検索時間計算量はです。ここで、はBツリーの要素の総数を示します。
4.2. 挿入
挿入は、Bツリーに要素を挿入または追加する操作です。 このプロセスでは、いくつかの点に留意する必要があります。 Bツリーのルートノードに要素を挿入できません。リーフノードから要素の挿入を開始する必要があります。
さらに、Bツリーにノードを挿入する際に、任意のノードでキーの最大数を確認し、昇順で要素を追加する必要があります。
空のBツリーにいくつかのノードを挿入する例を見てみましょう。 ここでは、空のBツリーにノードを挿入します。 Bツリーの順序がであると仮定しましょう。 したがって、ノードに含めることができる子の最大数はです。 さらに、この場合、ノードのキーの最大数と最小数はと（四捨五入）になります。
要素を挿入するときは、値を昇順でしか挿入できないことを覚えておく必要があります。 さらに、Bツリーが常に上方向に成長するように、常にリーフノードに要素を挿入します。
ノードと：で挿入プロセスを開始しましょう
次に、ノードを挿入します。 ただし、ノードに含めることができる最大のキーはここにあるため、そのリーフノードに新しい要素を挿入するスペースはありません。 したがって、ノードを分割する必要があります。 ノードを分割するには、中央値キーを取得し、そのキーを上に移動します。
次に、次の要素であるを挿入します。 より大きいので、最初に右側のサブツリーに移動します。 右側のサブツリーには、キーを持つノードがあります。 着信ノードのキーが。より大きい。 したがって、このノードを次の右側に追加します。
キーで次のノードを挿入しましょう。 最初にルートをチェックし、より大きいので、正しいサブツリーに移動します。 右側のサブツリーでは、より大きいとが表示されます。 したがって、の右側に挿入します。 しかし、やはり十分なスペースがありません。 したがって、それを分割し、その中央値を上位ノードに移動します。
同様に、次のノードをkeyで挿入します。
最後に、Bツリーのプロパティに従って残りのすべてのノードを1つずつ追加しましょう。
Bツリーの挿入プロセスの時間計算量はです。
4.3. 消す
削除は、Bツリーからキーを削除するプロセスです。 このプロセスの間、Bツリーのプロパティを維持する必要があります。 キーを削除した後、Bツリーのプロパティに従うようにツリーを再度配置する必要があります。さらに、削除する前にBツリーでそのキーを検索する必要があります。
Bツリーからキーを削除する場合、2つの状況が考えられます。
Bツリーからの削除の例を見てみましょう。ここでは、順序のBツリーを取り上げています。 ノードに含めることができる子の最大数はです。 さらに、この場合、ノードのキーの最大数と最小数は次のようになります。
ターゲットキーのリーフノードに最低限必要なキーよりも多く含まれている場合は、何も心配する必要はありません。 ターゲットキーを削除する必要があります。 削除後も、完全なBツリーになります。
ターゲットキーのリーフノードに含まれるキーの数が最小の場合、キーを単純に削除することはできません。削除すると、Bツリーの条件に違反するためです。 このような場合、そのノードに最低限必要なキーよりも多くのキーがある場合は、すぐ左のノードからキーを借用します。
左側のノードの最大値をその親ノードに転送します。 その後、値の大きいキーが借り手ノードに転送されます。 さらに、ノードからターゲットキーを削除できます。 キーを持つノードを削除したいとしましょう：
もう1つの可能な方法は、ノードに必要な最小キーを超える場合、すぐ右のノードからキーを借用することです。右ノードの最小値をその親ノードに転送します。 小さい方のキー値が借り手ノードに転送されます。 その後、ノードからターゲットキーを削除できます。 キーを持つノードを削除したいとしましょう：
次に、ターゲットキーのノードの左の兄弟も右の兄弟も必要最小限のキーを超えていない場合のシナリオについて説明します。このような場合、2つのノードをマージする必要があります。 2つのノードのうち、1つのノードにターゲットノードのキーが含まれている必要があります。 マージする際には、親ノードも考慮する必要があります。
キーがのノードを削除するとします。 その兄弟ノードには、最小数を超えるキーが含まれていません。 ここでの最初のステップは、ノードをマージすることです。 この例では、ターゲットキーのノードの左側のノードをマージしました。 ノードをマージした後、ターゲットノードを削除します。
次に、ターゲットキーが内部ノードにある場合について説明します。
このような場合、最初に考えられるオプションは、ターゲットキーをその順序の前のキーに置き換えることです。ここでは、ターゲットキーの左側のノードを取得し、最も高い値のキーを選択して、それをターゲットキーに置き換えます。 。 ここでノードを削除します：
左側に必要な最小キーを超えていない場合は、ターゲットキーをその順序の後続キーに置き換えます。ここでは、ターゲットキーの右側のノードを取得し、最小値のキーを選択して、これをターゲットキーに置き換えます。
ターゲットキーの順序の後続ノードと順序の先行ノードに必要なキーの最小数を超えていない場合、2つの隣接するノードをマージする必要があります。たとえば、次の削除：
77の削除後：
Bツリーの削除プロセスの時間計算量はです。
6. 結論
Bツリーは、大量のデータを格納するために最もよく使用されるデータ構造の1つです。 このチュートリアルでは、Bツリーについて詳しく説明しました。 プロパティと操作を例とともに示しました。
