3

私はデータ構造の本を 2 冊持っています。2 冊の本には、B ツリー挿入の 2 つの異なるアプローチがあります。

値 k を B ツリーに挿入するとします。適切なリーフ ノードを検索して値 k を挿入した後、特定のリーフ ノードに存在する値がカウントされます。リーフ ノードがいっぱいの場合:

1.葉の要素と新しい要素の中から単一の中央値が選択されます。その後、ノードを2つのノードに分割します。中央値は親ノードにシフトされます。

2.ノードをm/2-1(mは木の順番)の位置で2つに分割します。中央値を親ノードにずらします。その後、適切な位置に値を挿入します。

次の方法のうち、正しいのはどれか。

別の質問:

次数 n の B ツリーに対してノードに含める必要があるキーの最小数は? order=5 の場合、任意のノード (ルートを除く) のキーの最小数は 2 です。

どんな答えでも大歓迎です！

4

1 に答える 1

7

Knuth の定義によると、次数 m の B ツリーは、次のプロパティを満たすツリーです。

  • すべてのノードには最大で m 個の子があります。
  • すべての非リーフ ノード (ルートを除く) には、少なくとも ceil(m⁄2) 個の子があります。
  • ルートがリーフ ノードでない場合、ルートには少なくとも 2 つの子があります。
  • k 個の子を持つ非リーフ ノードには、k-1 個のキーが含まれます。
  • すべての葉は同じレベルに表示され、情報を伝えます。

各内部ノードのキーは、サブツリーを分割する分離値として機能します。たとえば、内部ノードに 3 つの子ノード (またはサブツリー) がある場合、a1 と a2 の 2 つのキーが必要です。左端のサブツリーのすべての値は a1 未満になり、中央のサブツリーのすべての値は a1 と a2 の間にあり、右端のサブツリーのすべての値は a2 より大きくなります。

内部ノード

内部ノードは、リーフ ノードとルート ノードを除くすべてのノードです。それらは通常、要素と子ポインターの順序付けられたセットとして表されます。すべての内部ノードには、最大 U 個の子と最小 L 個の子が含まれます。したがって、要素の数は常に子ポインターの数よりも 1 少なくなります (要素の数は L-1 と U-1 の間です)。U は 2L または 2L−1 でなければなりません。したがって、各内部ノードは少なくとも半分埋まっています。U と L の関係は、2 つのハーフフル ノードを結合して有効なノードを作成し、1 つのフル ノードを 2 つの有効なノードに分割できることを意味します (1 つの要素を親にプッシュする余地がある場合)。これらのプロパティを使用すると、B ツリーから新しい値を削除および挿入したり、ツリーを調整して B ツリーのプロパティを保持したりできます。

ルートノード

ルート ノードの子の数には、内部ノードと同じ上限がありますが、下限はありません。たとえば、ツリー全体の要素が L-1 未満の場合、ルートはツリー内の唯一のノードであり、子はまったくありません。

葉ノード

リーフ ノードの要素数には同じ制限がありますが、子ノードも子ポインターもありません。

http://en.wikipedia.org/wiki/B-Tree

追加:

Knuths 定義を使用した順序 5 (子の最大数) [4 がキーの最大数] の B ツリー。

分割後の内部ノードの子の最小数は 3 [2 キー] です。Bツリーの順序をオーバーフローするとノードが分割されるため。

リスト 11108、3267、11357、12080、6092 の B ツリー

3267、11108、11357、12080 を追加した後。これは子ではなくキーを表示しています。

└── 3267, 11108, 11357, 12080

次に 6092 を追加します。これは子ではなくキーを表示しています。

分割前 (キーの数 > order-1) [5 > 5-1=4]:

└── 3267, 6092, 11108, 11357, 12080

分割後:

└── 11108
    ├── 3267, 6092
    └── 11357, 12080

注: ルート ノードには、他のノードのようにキー/子の最小数がありません。

削除:

削除後のリバランス

リーフ ノードから要素を削除したために最小サイズを下回った場合は、すべてのノードを最小サイズにするために一部の要素を再配分する必要があります。場合によっては、再配置によって欠陥が親に移動し、再分配をツリーの上方、おそらくルートにまで繰り返し適用する必要があります。ルートには最小要素数が適用されないため、ルートが唯一の欠陥ノードになっても問題ありません。ツリーのバランスを再調整するアルゴリズムは次のとおりです。[要出典]

  1. 右の兄弟が最小数を超える要素を持っている場合

    • 不足しているノードの末尾にセパレーターを追加します
    • 親のセパレーターを右の兄弟の最初の要素に置き換えます
    • 右の兄弟の最初の子を欠陥のあるノードの最後の子として追加します

  2. それ以外の場合、左の兄弟に最小数よりも多くの要素がある場合

    • 欠陥のあるノードの先頭にセパレーターを追加します
    • 親のセパレーターを左側の兄弟の最後の要素に置き換えます
    • 左の兄弟の最後の子を欠損ノードの最初の子として挿入します

  3. 両方の直接の兄弟が最小数の要素しか持っていない場合

    • 欠陥のあるノードのすべての要素、その兄弟の 1 つからのすべての要素、および結合された 2 つの兄弟ノード間の親のセパレーターを使用して、新しいノードを作成します。
    • 親からセパレーターを削除し、分離された 2 つの子を結合ノードに置き換えます
    • それによって親の要素数が最小値を下回った場合は、ルートが不足していることが許可されているため、ルートでない限り、その不足しているノードでこれらの手順を繰り返します。

他に考慮すべき唯一のケースは、ルートに要素がなく、子が 1 つある場合です。この場合、それをその唯一の子に置き換えるだけで十分です。

ノード 9062 の事前削除。

└── 6169, 12789
    ├── 1009, 4238, 5139
    ├── 6625, 9062
    └── 12909, 14508, 14703, 14985

バランス調整前

└── 6169, 12789
    ├── 1009, 4238, 5139
    ├── 6625 
    └── 12909, 14508, 14703, 14985

バランス調整後

└── 6169, 12909
    ├── 1009, 4238, 5139
    ├── 6625, 12789
    └── 14508, 14703, 14985

ご覧のとおり、中間ノードの子は最小要件を満たすために親から 12789 を借用し、親は最小要件を満たすために右端の子から 12909 を借用しました。

于 2013-02-23T13:32:16.093 に答える