O（log2n）に挿入され、まだO（1）を検索するデータ構造

Question

現在、O（log2n）に挿入するデータ構造を要求する代入に取り組んでいますが、O ）。私はlog2n挿入のためにBSTを考えていましたが、O（1）で検索することはできません。ハッシュテーブルはO（1）の検索で最悪のO（n）に挿入できますが、残念ながらこれはO（log2n）の挿入要件に適合しません。

誰もが何か提案がありますか？ありがとう！

Answer 1

バイナリツリーに要素を挿入し、その要素へのポインタをハッシュテーブルに挿入できます。

または、O（1）でハッシュテーブルに要素を挿入し、O（1）で検索し、「O（lb N）を挿入する」という条件で、LogBin（N）の空のループを実行するだけです。

「最悪の場合/平均の場合」：ハッシュテーブルとバイナリツリー（rbのようにバランスがとれていない、プリミティブのみ）は、最悪の場合O（N）を持ちます。私はあなたの割り当ては「平均的なケース」についてのものだと思いますが、これはいつものことです。ハッシュテーブルはO（1）を提供できます。選択したデータセットで攻撃を維持するには、 "universal hashing"を使用します。