0

明日の試験の復習をしているのですが、質問に行き詰まっていました。M = 4、L = 3 で値 1 ~ 25 を含む有効な B ツリーを描画する必要があります。問題は、ツリーを答えのように見せることができないことです。回答ツリーは次のようになります。

             9            14             22
            /       |             |        \
         4 7       12           17 20        24
        / | \     /  \         /  |  \      /  \
       1  4  7   9   12      14  17  20   22   24
       2  5  8   10  13      15  18  21   23   25
       3  6      11          16  19  21  

これが読みにくい場合は申し訳ありません。おそらく私は答えを間違ってコピーしましたが、これが正しい答えかどうかを誰かが確認できますか? もしそうなら、この答えはどのようにして得られたのですか?

4

1 に答える 1

0

BTree ではなく B+ ツリーについて話しているようで、小さなタイプミスがあります。キー 21 がリーフで複製されています [20,21,21]。おっしゃる通り、オーダーは4です。

答えは有効な B+ ツリーですが、1 ~ 25 の値を順番に追加して得られるものではありません。質問は、キーを追加する特定の順序を示していましたか、それとも自分でそれを決定しようとする質問でしたか? 長い試行錯誤のプロセスを除けば、シーケンスをどのように決定するかはわかりませんが、次のデモページを使用して試すことができます。

http://goneill.co.nz/btree-demo.php

挿入のさまざまなシーケンスを試したい場合は、オフライン バージョンをダウンロードして、Hardcoded() 関数を編集することをお勧めします。

http://goneill.co.nz/btree.php

ただし、すべてJavaScriptで作成されているため、役に立たない場合があります。

于 2013-04-24T05:35:55.760 に答える