多数のノードを迅速に挿入するための最適なセルフバランシング BST

Question

いくつかの自己バランス調整に関する詳細を見つけることができました BSTいくつかの情報源を調べましたが、さまざまな状況でどれを使用するのが最適であるか (または本当に問題ないかどうか) について詳しく説明した適切な説明は見つかりませんでした。

が欲しい BST これは、1,000 万を超えるノードを格納するのに最適です。ノードの挿入順序は基本的にランダムであり、ノードを削除する必要はないため、最適化する必要があるのは挿入時間だけです。

これを使用して、パズル ゲームで以前に訪れたゲームの状態を保存し、以前の構成がすでに存在しているかどうかをすぐに確認できるようにするつもりです。

Answer 1

赤、黒 挿入が多いアプリケーションには AVL よりも優れています。比較的均一なルックアップが予想される場合は、レッドブラックが最適です。最近表示された要素が再び表示される可能性が高くなる、比較的不均衡な検索が予想される場合は、次のように使用します。 スプレーツリー.

Answer 2

なぜ使用するのか BST まったく？あなたの説明からすると、辞書はそれ以上ではないにしても、同様に機能します。

を使用する唯一の理由は、 BST コンテナの内容をキー順にリストしたい場合です。確かに、そんなことをしたいとは思えませんが、その場合はハッシュ テーブルを使用してください。 O(1) 挿入と検索だけでなく、削除の心配もありません。これ以上に優れたものはありませんか?

Answer 3

2つの自己バランス BST私が最もよく知っているのは赤と黒です。 AVL, したがって、他のソリューションが優れているかどうかは明確には言えませんが、私の記憶では、赤黒は、赤黒と比較して挿入が速く、取得が遅くなります。 AVL.

したがって、挿入が検索よりも優先される場合は、赤黒の方が良い解決策になる可能性があります。

Answer 4

[ハッシュ テーブルには] O(1) の挿入と検索があります

これは間違っていると思います。

まず、キースペースを有限に制限すると、要素を配列に格納して O(1) リニア スキャンを実行できます。または、配列をシャッフルソートし、O(1) の予想時間でリニア スキャンを実行することもできます。物が有限であれば、物は簡単に O(1) になります。

したがって、ハッシュ テーブルに任意のビット文字列が格納されるとします。キーのセットが無限にあり、それぞれが有限である限り、それはあまり問題ではありません。次に、クエリと挿入入力のすべてのビットを読み取る必要があります。そうでない場合は、空のハッシュに y0 を挿入し、y1 に対してクエリを実行します。ここで、y0 と y1 は、見ていない単一のビット位置で異なります。

ただし、キーの長さがパラメータではないとしましょう。挿入と検索に O(1) かかる場合、特にハッシュには O(1) 時間がかかります。これは、ハッシュ関数からの有限量の出力のみを確認することを意味します (そこから、 なれ 有限の出力のみです、当然です）。

これは、バケットの数が有限である場合、すべて同じハッシュ値を持つ文字列のセットが無限に存在する必要があることを意味します。たくさん挿入したとします。そのうち ω(1) を選択し、クエリを開始します。これは、私のクエリに答えるために、ハッシュ テーブルが他の O(1) 挿入/検索メカニズムにフォールバックする必要があることを意味します。どちらを使用すればよいでしょうか。なぜそれを直接使用しないのでしょうか?