ランダム要素を選択するためのデータ構造ですか？

Question

2つの操作を効率的にサポートするデータ構造を知っている人はいますか？

1. データ構造体に値を挿入します。
2. 一様にランダムな確率でデータ構造体からエントリをデキューして返します。

これは、入門確率クラスに常に現れる標準的な「大理石の袋」のようなものです。あなたはバッグに任意の大理石を入れることができ、大理石を効率的に無作為に取り除くことができます。

私が持っている最良の解決策は次のとおりです。要素を格納するために自己平衡二分探索木（AVL、AA、赤/黒など）を使用します。これはO（lg n）の挿入時間を与える。ランダムな要素を削除するには、ランダムなインデックスiを選択し、ツリーからi番目の要素を見つけて削除します。構造を適切に拡張した場合、これはO（lg n）時間で実行することもできます。

このランタイムは間違いありませんが、挿入するにはO（1）、デキュー用にO（lg n）を使用するといいでしょうか？あるいは、で動作するものがありますか？ O（1）ハッシュ関数を使って挿入して削除しますか？あるいは、より強い償却された縛り？

誰もがこれを漸近的に速くする方法に関するアイデアはありますか？

Answer 1

はい。ベクトルを使用します。

挿入するには、単に末尾に置き、サイズを増やします。削除するには、要素をランダムに選択し、その内容を終了値と入れ替えてから、終了値をポップアウトします（つまり、終了値を返し、ベクトルのサイズを減らします）。

両方の操作は、O（1）で償却されます。