5

私はslady.netの非常にクールな btree アプレットで遊んでいます。特定の動作を理解するのに苦労しています。この開始状態を見てください。

代替テキスト http://www.freeimagehosting.net/uploads/db2931c7da.jpg

この特定の状態は、10、15、30、16、70、1、9、27、45、50、55 のシーケンスを挿入することによって達成されました。

私の質問は、シーケンスに次の値 65 を挿入すると [45, ] ノードに何が起こるかに関するものです。

代替テキスト http://www.freeimagehosting.net/uploads/3b70c1d302.jpg

[55,70] ノードは 65 で分割され、中間値である 65 は上に移動し、[30,50] ノードも分割します。私の質問は: [45, ] ノードが [30, ] ノードの子になるのはなぜですか? その親にはもともと 3 つの子があり、一番左と一番右が新しい別のノードになりました。45 はこれらの値の間にあり、[65, ] ノードの下にも同様に配置された可能性があるようです...なぜですか?

4

3 に答える 3

4

百聞は一見に如かず。アニメーションは 100 万の価値があります。

http://constellationmedia.com/~funsite/static/btree-insert-animation.gif

ここで注目すべき重要なことは、中心ノード 50 がプルアップされると、右の子ノードがあまりにも下にあるために破棄されなければならないということです。ただし、65 には新しい左の子が必要なため、50 は 45 を 65 に渡します。50 には新しい右の子が必要になり、65 を含むノードを子にする必要があるため、新しく形成された 65 を代わりに使用します。

以下に、B ツリーの挿入規則を示します (最大ノード サイズは 4 項目、5 子ノード)。

http://constellationmedia.com/~funsite/static/btree-insertion-rules.png

はxr存在せず、葉に挿入する場合は問題になりません (最初に行います)。ただし、ノードを半分に分割する必要がある場合、新しいxは引き出した中心のアイテムであり、新しいxrは の右の子ですx。

于 2010-07-18T01:56:48.470 に答える
1

45 ノードが 2 番目のダイアグラムの 65 ノードの子であることは意味がありません。右端の分岐は値 > 50 (ルート ノードの右端の値に基づく) のためであり、したがって 45 は中央の分岐に入る必要があります。どこか。

于 2010-07-18T00:26:05.433 に答える
1

各ノードには常に n+1 個の子があり、n はそのノード内のキーの数です。

分割前の [30, 50] ノードには、予想どおり 2 つのキーと 3 つの子があります。それを分割すると、[30, -] ノードと [65, -] ノードになります (そして、50 を 1 レベル上げます)。

次の下位レベルには、(以前に存在していた) [16, 27] および [45, -] ノードと、新しく分割された [55, -] および [70, -] ノードがあります。

2 つの親ノードと 4 つの子ノードがあります。1 つのキーを持つため、各親には 2 つの子が必要です。したがって、順序付け規則を考えると、[45, -]は [30, -] の子でなければなりません。そうしないと、(1) [30, -] には十分な数の子がなく、(2) [65, -] には十分な数の子がないためです。子供が多すぎる。[編集- ノードに対して違法に多すぎるわけではありませんが、分割はバランスが取れているはずです]。

ウィルAも正解です。これは、中間層ノードを分割するときに 50 キーを押し上げることを選択した結果ですが、これは実際には選択できませんでした。[-, -] と [50, 65] で 30 を押し上げるか、[30, 50] と [-, -] で 65 を押し上げるように分割すると、すべてのノードが少なくとも半分満たされている必要があるというルールに違反します。

于 2010-07-18T00:40:30.837 に答える