在Java中，即時通訊創建SortedSet從一個總是要排序（但只是ArrayList類型）的列表。我認爲一個接一個地添加它們會有很差的性能（例如在AVL樹的情況下），因爲它將不得不對樹進行重新排序。從有序列表樹構造
我的問題是，如何應該我要創建這個集？以一種儘可能快的方式建立一棵平衡的樹？
具體實施我打算用要麼IntRBTreeSet或IntAVLTreeSet從http://fastutil.dsi.unimi.it/docs/it/unimi/dsi/fastutil/ints/IntSortedSet.html
寫作這件事之後，我認爲表現不佳不會影響我太多反正（太小的數據量），但我還在對如何在一般情況下完成這項工作感興趣。
具有樹實現的集合將從頂部的列表中獲取中間元素。因此，算法將是如下：
紅黑樹對於一般情況來說是個不錯的選擇，它們插入速度非常快。請參閱Chris Okasaki's paper以獲得優雅而快速的實施。 Functional Java庫有一個通用的Set類，它由根據本文實現的紅黑樹支持。
您是否因簡單的插入元素而出現性能問題？
如果沒有，請不要優化。
有效點。但爲了討論的緣故，我們假設他確實有性能問題。 – 2009-02-24 02:01:45
在TreeSet（http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html）類中構建的類使用紅黑樹作爲其支持樹（並且，已經注意到，紅黑樹對於插入來說相當快）。這裏是紅黑樹上的good info（當插入大部分已經訂購的數據時，它們沒有典型二叉樹實現的問題）。
如果您正在處理大量數據集（足夠大以便需要基於磁盤的備份或重要的分頁文件交換），那麼B +樹就是一個非常好的選擇（請參閱JDBM以瞭解基於Java的自平衡版本B +樹 - 它沒有實現Set，但如果需要可以這樣使用）。
根據您的應用程序實際使用此數據的方式，您可能需要考慮GlazedLists庫，並使您的列表「生效」。如果你所做的只是靜態分析，那麼這可能是矯枉過正的，但它是處理基於列表的數據的絕佳方式。絕對值得一讀。
隨着關於使用Set的所有討論，在我看來，問題可能會被重新闡述。爲什麼要使用Set？如果您只想檢查成員資格，並且對源列表進行排序，那麼對該對象執行二進制搜索 - 與您可以設想的任何n-tree相比，該搜索速度會更快（也可能更快），並且這並不難碼。
所以，設想一個OrderedListSet接口，它只是包裝下屬的List對象。只要用於排列列表的比較器也用於二分搜索，這應該是非常直接的。
所有Set操作將以getIndex（Object ob）調用開始，然後在列表上執行相應的操作。
問題是列表被排序，但它不在保證順序的數據結構中。所以我可以假設它的順序，但不能絕對確保我的代碼將工作 – gcrain 2009-02-26 22:32:17
我認爲這是一個不錯的選擇。仍然可以快速訪問（數組）列表來插入它們，列表元素將以何種方式排序（不是很高）。 – gcrain 2009-02-26 04:30:14