Javaでは、常に順序付けられるリストからSortedSetを作成しています（ただし、ArrayListタイプのみです）。それらを1つずつ追加すると、ツリーを何度も並べ替える必要があるため、パフォーマンスがかなり低下すると思います（AVLツリーの場合など）。
私の質問は、このセットをどのように作成すればよいですか? バランスの取れたツリーをできるだけ早く構築する方法は?
私が使用することを計画していた特定の実装は、 http: //fastutil.dsi.unimi.it/docs/it/unimi/dsi/fastutil/ints/IntSortedSet.html の IntRBTreeSet または IntAVLTreeSet でした。
これを書いた後、とにかくパフォーマンスの悪さはあまり影響しないと思いますが（データ量が少なすぎます）、一般的なケースでそれがどのように行われるかについてはまだ興味があります.
ツリー実装を持つセットには、リストの中間要素が一番上にあります。したがって、アルゴリズムは次のようになります。
赤黒木は一般的なケースに適した選択であり、挿入が非常に高速です。エレガントで高速な実装については、Chris Okasaki の論文を参照してください。Functional Javaライブラリには、このホワイト ペーパーに従って実装された赤黒ツリーによってサポートされる汎用Setクラスがあります。
Set の使用についてのすべての議論で、おそらく問題が再記述される可能性があることが私には思い浮かびます。なぜセットを使用するのですか? メンバーシップを確認したいだけで、ソース リストがソートされている場合は、オブジェクトのバイナリ検索を実行します。これは、想像できるどの n-tree よりも高速 (そしておそらく高速) であり、それほど難しくはありません。コード。
したがって、下層の List オブジェクトをラップするだけの OrderedListSet インターフェイスを想像してください。リストの順序付けに使用されるコンパレーターが二分探索にも使用される限り、これは非常に簡単です。
すべての Set 操作は getIndex(Object ob) 呼び出しで開始され、適切なアクションが List に対して実行されます。
組み込みの TreeSet ( http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html ) クラスは、バッキング ツリーとして赤黒ツリーを使用します (そして、 、赤黒木は挿入に対して非常に高速です）。ここに赤黒木に関する良い情報があります (ほとんどが既に順序付けられているデータを挿入する場合、典型的な二分木実装の問題はありません)。
巨大なデータ セット (ディスク ベースのバッキングや重要なページング ファイル スワップが必要なほど大きい) を扱っている場合、B+Tree は非常に優れたオプションです (セルフバランシング B+Tree の Java ベース バージョンについては、JDBMを参照してください - Set を実装していませんが、必要に応じてそのように使用できます)。
アプリケーションがこのデータを実際にどのように使用しているかによっては、GlazedListsライブラリを検討して、リストを「ライブ」にすることをお勧めします。静的分析だけを行っている場合、これはやり過ぎかもしれませんが、リスト ベースのデータを操作するための非常に優れた方法です。間違いなく読む価値があります。
要素を挿入するだけの単純なアプローチでパフォーマンスの問題がありますか?
そうでない場合は、最適化しないでください。