6

ノードのオーバーフローが発生したときに正確に何が起こるかを理解しようとしています。情報: 私の b+ ツリーには、ブロックごとに 4 つのポインターと 3 つのデータ セクションがあります。問題：オーバーフローが発生すると、私の場合はそれぞれ2つのキーを持つ2つのノードに分割し、息子から消去せずに親ノードに中間値を挿入することを理解しました（bツリーとは異なります）。

しかし、私は状況に陥りました：

                                |21|30|50|

           |10|20|-|      |21|22|25|  |30|40|-| |50|60|80|

最初にキー 23 を挿入したい |21|22|25| を分割します。に: |21|22|-| と |23|25|-| ここで、キー 23 を親 |21|30|50| に挿入する必要があります。魔女は別の分割を引き起こします。|21|23|-| と |30|50|-| しかし、30 の前のポインタはどこを指すのでしょうか? このポインターと 23 の後のポインターの両方が |23|25|-| を指している可能性はありますか? ?

4

5 に答える 5

2

23を挿入する場合：

  • あなたが言ったように、21|22|-| と |23|25|-| 作成されます
  • 2 つのノードには親が必要です
  • 親はルート ノード |21|23|30|50| に作成されます。
  • ルートの要素が多すぎます
  • ルートを 2 つのノード |21|23|- と |30|50|- に分割します。
  • 2 つの新しいノードに新しい親を追加します (ツリーの新しいルートになります)。

基本的に、その挿入はツリーの深さを 1 増やします

于 2011-06-11T07:55:56.410 に答える
-1

何が起こるかを理解しなければならない問題は、使用している表現モデルが悪いためです。ポインターに関連付けられた1つのデータ値と、データ値がポインターによって参照されるサブツリー内の最小値であるという不変条件が必要です。

したがって、これは、挿入前にbツリーノードを表す方法です。

                         10|21|30|50|                       <--- root node

         10|20|    21|22|25|     30|40|       50|60|80|     <--- leaf nodes

この表現では、ルートノードの値10の後のポインターは、最初の値10などのリーフノードを指しています。

23を挿入すると、最初の値が21のリーフノードに挿入されます。これにより、次のツリーが生成され、分割する必要はありません。 

                         10|21|30|50|                       <--- root node

         10|20|    21|22|23|25|     30|40|    50|60|80|     <--- leaf nodes

あなたが説明した効果を生み出す24を挿入すると、次のようになります。

                              10|30|                         <--- new root node

                        10|21|24|   30|50|                   <--- intermediate nodes

         10|20|   21|22|23|   24|25|   30|40|    50|60|80|   <--- leaf nodes

ご覧のとおり、あいまいさはもうありません。リーフノードが分割され、キーポインタペア24 | ルートノードに挿入する必要がありました。いっぱいだったので、分割する必要がありました。5つの値があるので、3つの値を持つ1つのノードと2つの1つのノードを取得します。左側のノードと右側のノードのどちらが3つの値を取得するかを自由に選択できます。重要なのは、基本的な不変条件が保持されることです。ノードの各キー値は、関連するポインターによって参照されるサブツリー内の最小要素です。新しいルートノードを追加する必要があり、そのキー値ポインタセットが明確になっているはずです。あいまいさはありません。

これはまた、多くの最適化戦略が可能であることを明らかにします。ルートノードを分割する代わりに、値21をいっぱいではない左側のリーフノードに移動することもできます。最初の値が10の場合。これにより、ルートノードを分割する必要がなくなり、bツリーの高さを変更せずに維持し、bツリーの塗りつぶしを改善できます。したがって、スペースと検索時間を最小限に抑えることができます。しかし、これは、横方向のバランス調整が実行可能かどうかを効率的に確認できることを意味します。ルートノードのキー値の変更は引き続き必要です。等

ご覧のとおり、bツリーの値10は、リーフノードがない場合は実際には必要ありません。bツリー表現（つまり、ウィキペディア）では省略されることがよくありますが、混乱を招く可能性があり、おそらくここにいる理由です。:)

于 2011-06-11T09:16:13.763 に答える
-1

私が教えられたことから、最後のノードがn/2未満のノードを持つことは問題ありません。したがって、あなたの例では、トップノードは次のようになります。

             |23|
         /        \
    |21|22|-|       |25|-|-|

それは一理あると思います。考えてみれば、リーブノードが5個あるので、上位からのポインタは5個必要です。この配置は、5 つのポインターを持つことができる唯一の方法です。他のすべての組み合わせでは、ノードがオーバーフローするか、余分なポインターが作成されます。

ノードが |21|22|-| の場合 および |23|25|-| の場合、ルート ノードは |23|-|-| になります。次に、右側のノードに 23 があることは意味がありません。右側のノードにあるものは何でも 23 以上でなければならないからです。

于 2013-05-01T12:07:03.587 に答える