如何查找TreeSet中元素的排名

Question

我知道您可以在樹中找到第一個和最後一個元素。如果我想知道第二個或第三個元素沒有迭代是什麼？或者，更可取的是，給定一個元素，找出它在樹中的排名。

感謝

編輯：我認爲你可以使用tailset，即做到這一點。比較原始集合的大小和尾部集合的大小。尾部效率如何？

Answer 1

根據Sun JDK6實現的源代碼，tailSet(E).size()遍歷尾集並對元素進行計數，因此該調用爲O（尾集大小）。

Answer 2

除了迭代器以外沒有別的辦法。

編輯：

試試這個：

treeSet.higher(treeSet.first()); 

這應該在TreeSet中給予第二個元素。我不確定這是否更優化，然後使用Iterator。

Answer 3

TreeSet沒有提供有效的排名方法。我懷疑（你可以通過查看它的來源來確認）TreeSet甚至不需要在O（日誌）中執行任何額外的信息位（即每個節點的左右子樹上的元素的計數） （n））時間。因此，似乎沒有任何快速找到TreeSet元素排名的方法。

如果你真的需要它，你可以實現你自己的SortedSet一個平衡二叉搜索樹，它允許這樣的查詢或修改TreeSet實現創建它擴充到允許此類查詢一個新的實現。有關如何實際完成此操作的更多詳細信息，請參閱CLRS中增強數據結構一章。