問題タブ [2-3-4-tree]

次の 2-3-4 ツリーから 15 を削除します。単純に 17 を上に移動することを考えましたが、それが正しいかどうかはわかりません。

次のツリーから 15 を削除します。

削除後の 2-3-4 ツリーはどのようになりますか? この場合、単純に 17 上げるのは正しくないと思います。しかし、よくわかりません。

番号 50、40、60、30、70 のリストがあります。これらを空の 2-3-4 ツリーに挿入するとします。これらの数字のどれがツリーの親ルートで、その理由は? 広告掲載順ですか、数字の大きさですか。数字のリストを与えるときに 234Tree を描画できるようにしたいと考えています。最初に親ルートとして使用するものがわからないため、それができないようです。簡単に言えば、このツリーの親ルートを指定する要因は何ですか。

Java で 2-3-4 ツリーを赤黒ツリーに変換しようとしていますが、それを理解するのに苦労しています。

問題を簡単にするために、これらの 2 つの基本的なクラスを次のように記述しましたが、ここからどこへ行くべきかわかりません。

私は 2-3-4 ツリーが有効であると仮定しており、メソッドが呼び出されたときに赤黒のツリーを返したいと考えています。

次のコードも試してみましたが、うまくいきませんでした。

keys.size() == 2, 1....の場合など

理論的には再帰的でなければならないことは知っていますが、それを理解するのに苦労しています。何かご意見は？

1. トップダウンの 2,3,4 ツリーに 3 つの要素を入力するとします。3 つの要素すべてがルートに入るでしょうか。
2. 後続の挿入では、3 番目の要素は、リーフ ノードの場合にのみノードに挿入されます (または、3 つのキー ノードに遭遇したときにキーがキックされた場合はノードに挿入されます)。

私が使用しているデータ構造の教科書でこの質問が尋ねられるのを見たところ、質問は続きます

次の主張が間違っていることを示す例を挙げてください。

最良のケースは O(log n) であり、BST を使用するよりも優れていることはわかっていますが、それだけであり、もっともらしい説明が見つからないようです。このステートメントが間違っていることをどのように証明できますか?

2-3-4 ツリーの 1 つのノードは、8 つのポインターで構築できます。最大 4 つの子ノードへのポインター、検索キーに一致するキー、または 4 つの子ノードのどれを決定するかを決定するキーを含む最大 3 つの実際のレコードへのポインター再帰先、および親ノード ポインター。

今日の一般的なハードウェアには 8 バイトのポインターがあり、64 バイトのノードを提供します。さらに、最新の CPU には 64 バイトのキャッシュ ラインがあります。ノードがキャッシュ ラインと整列している場合、各ノードは 1 つのキャッシュ ライン ヒットのみを必要とします。7 つのポインターのうち最初のポインターを参照した後、残りはすべて L1 キャッシュに格納されます。

赤黒ツリーは実装がはるかに簡単で、小さなコードは高速なコードである必要がありますが、ツリーの降下の各レベルでは L1 キャッシュ ミスのリスクがあります。1023 個のオブジェクトの場合、2-3-4 ツリーでは、キャッシュにロードする最悪のケースで 5 つのノードが必要です。完全にバランスの取れたバイナリ ツリーには 10 が必要ですが、バランスが崩れているため、赤黒ではさらに必要になる場合があります (最悪の場合: 20?)

1 つのデータ構造を単純に叩く小さなテスト ハーネスは、おそらくすべてをキャッシュに保持するため、赤黒ツリーが 2-3-4 と同様のパフォーマンスであると報告される可能性があります。しかし、複雑な実世界のアプリケーションでは、2-3-4 ツリーを使用すると実時間と待ち時間が大幅に短縮される可能性があると感じています。

これに関するコンセンサスや研究はありますか？