3

次数 8 の B ツリーがあるとします。これは、8 つのポインターと 7 つの要素を持つことができることを意味します。A から G までの文字がこの B ツリーに格納されているとします。したがって、この B ツリーは、7 つの要素を含む単一のノードにすぎません。

次に、J をツリーに挿入しようとします。空きがないので、ノードを分割して新しいルート ノードを作成する必要があります。ルート ノードに昇格する要素はどれですか?

4

1 に答える 1

2

2*t - 1フルノード(キー付き)に新しい要素を挿入したい場合

  • ノードの中央値キー (中央のキー) を選択して分割します。
  • それぞれキーを持つ2つの新しい子を生成しt-1ます（前のキーに従って分割します）
  • 中央値は親ノードに残ります
  • 次に、通常の挿入アルゴリズムに従って、新しい要素を配置する場所を探します。
于 2010-04-04T16:55:26.923 に答える