次のセット操作を時間と空間の両方で効率的にサポートするデータ構造はどれですか？
これらの操作を行うための3つの異なる方法を考えることができます。2つのセットがあり、それらのサイズは両方ともNであると仮定します。
ビット配列：
1. O(N) 2.O(N) 3.O(1) 4.O(1) 5.O(1)
ハッシュ表：
1. O(N) 2.O(N) 3.O(1) 4.O(1) 5.O(1)
注文したツリー：
1. O(NlogN) 2.O(NlogN) 3.O(logN) 4.O(logN) 5.O(logN)
ビット配列とHashTableは高速ですが、メモリの使用量が多すぎます。順序付きツリーは低速ですが、消費するメモリが少なくなります。
注意：セットには、浮動小数点数や文字列など、整数以外の他のタイプが含まれる場合があります
他にどのようなデータ構造が高速で一般的であり、スペース効率が良いですか？
1つのオプションは、注文したツリーをブルームフィルターで補強して、ismemberof型テストを高速化することです。
全体的な動作は次のようになると思います。
1. O(N log(N) ) 2. O( ? ) 3.O(1) 4.O(log(N)) 5.O( log(N) )
ただし、正確な詳細は、フィルターのサイズ、セットのサイズ、およびドメインのサイズによって異なります。
別のオプションは、JudyArraysです。私はこの種の使用のためにそれらについて良いことを聞いたことがありますが、個人的な経験はありません。
さらに別のオプションは、（純粋な二分木ではなく）フォレストアプローチです。
Binary Heap (最も簡単なもの)、Binomial Heap (結合を高速化)、およびFibonacci Heap (実装が最も難しいが、標準操作の償却時間が最もよく知られている)をお勧めします。
操作 バイナリ ヒープ 二項ヒープ フィボナッチ ヒープ (償却)
1. 結合 O(n) O(logn) O(1)
2. 差分 O(nlogn) O(nlogn) O(nlogn)
3. find(ismemberof) O(n) O(n) O(n)
4. O(lgn) O(lgn) O(1) を追加
5. O(lgn) O(lgn) O(lgn) を削除
ただし、これらの構造は、ほとんどの場合、挿入、検索/抽出 min(max)、結合、および削除操作が必要な場合に使用されます。findおよびdiff操作の実行時間は依然として不十分です。
Union-FindDataStructureを調べることもできます