いくつかの情報源からいくつかのセルフバランスBSTの詳細を見つけることができましたが、さまざまな状況で (またはそれが本当に問題ではない場合) にどれを使用するのが最適かを詳述した適切な説明は見つかりませんでした。
BST1,000 万ノードを超える格納に最適な が欲しい。ノードの挿入順序は基本的にランダムであり、ノードを削除する必要はないため、最適化する必要があるのは挿入時間のみです。
これを使用して、以前にアクセスしたゲームの状態をパズル ゲームに保存し、以前の構成が既に発生しているかどうかをすばやく確認できるようにします。
なぜ aBSTをまったく使用しないのですか? あなたの説明から、辞書は、より良くはないにしても、同様に機能します。
a を使用する唯一の理由BSTは、コンテナの内容をキー順に並べたい場合です。あなたがそれをしたいようには思えません。その場合は、ハッシュテーブルを使用してください。O(1)挿入と検索、削除の心配なし、何が良いでしょうか?
私が最もよく知っている2 つのセルフバランシングは、BST赤黒とAVLです。そのため、他の解決策が優れているかどうかははっきりとは言えませんが、思い出したように、赤黒は に比べて挿入が速く、検索が遅くなりますAVL。
そのため、検索よりも挿入の優先度が高い場合は、赤黒の方が適している可能性があります。
[ハッシュテーブルは] O(1) 挿入と検索
これは間違っていると思います。
まず、キースペースを有限に制限すると、要素を配列に格納して O(1) 線形スキャンを実行できます。または、配列をシャッフルソートしてから、O(1) の予想時間で線形スキャンを実行できます。スタッフが有限の場合、スタッフは簡単に O(1) になります。
したがって、ハッシュ テーブルに任意のビット文字列が格納されるとします。それぞれが有限である無限のキーのセットがある限り、それは大した問題ではありません。次に、クエリと挿入入力のすべてのビットを読み取る必要があります。それ以外の場合は、空のハッシュに y0 を挿入し、y1 でクエリを実行します。ここで、y0 と y1 は、見ていない単一のビット位置で異なります。
しかし、キーの長さはパラメーターではないとしましょう。挿入と検索に O(1) かかる場合、特にハッシュには O(1) の時間がかかります。つまり、ハッシュ関数からの有限量の出力のみを確認することになります (そこから有限の出力しか得られない可能性が高く、許可されています)。 ）。
これは、バケットの数が有限であるため、すべて同じハッシュ値を持つ文字列のセットが無限に存在する必要があることを意味します。それらのうち、大量、つまり ω(1) を挿入し、クエリを開始するとします。これは、クエリに答えるために、ハッシュ テーブルが他の O(1) 挿入/検索メカニズムにフォールバックする必要があることを意味します。それを直接使用しないのはなぜですか?