java - TreeSet 内の要素のランクを見つける方法

Question

ツリーセットの最初と最後の要素を見つけることができることは知っています。反復せずに 2 番目または 3 番目の要素が何であるかを知りたい場合はどうすればよいでしょうか? または、より望ましいのは、要素を指定して、ツリーセット内のランクを把握することです。

ありがとう

編集：テールセットを使用してそれを行うことができると思います。元のセットのサイズとテールセットのサイズを比較します。テールセットはどれくらい効率的ですか？

Answer 1

TreeSetは、効率的なランク メソッドを提供しません。TreeSetO(log ( n)) 時間。したがって、 の要素のランクを見つける高速な方法はないようですTreeSet。

本当に必要な場合は、SortedSetそのようなクエリを許可するバランスの取れた二分探索木を使用して独自に実装するか、実装を変更して、そのTreeSetようなクエリを許可するように拡張された新しい実装を作成できます。これを実際に行う方法の詳細については、CLRS でのデータ構造の拡張に関する章を参照してください。

Answer 2

Iterator 以外に方法はありません。

編集:

これを試して：

treeSet.higher(treeSet.first());

これにより、TreeSet に 2 番目の要素が与えられます。これが Iterator を使用するよりも最適化されているかどうかはわかりません。

Answer 3

Sun JDK6 実装のソースによるとtailSet(E).size()、末尾セットを反復処理して要素をカウントするため、この呼び出しは O(末尾セット サイズ) です。