TreeSetの要素のインデックスを見つけるには？

Question

私はTreeSet<Integer>を使用しています。私はかなり単純にセット内の数字のインデックスを探したいと思います。バイナリツリーの複雑さ（O（log（n））の複雑さを実際に利用する良い方法がありますか？

（ない場合は、私が何をすべき、と誰もがそのようなクラスは、検索機能のようなものなしでJavaで含まれることになる理由はなぜでしょうか？私は興味が知っているん。）

Answer 1

でこの作業の結果を見つけることができます。だから我々は、より良いチェックをしたい：ここ

return set.contains(element)? set.headSet(element).size(): -1; 

は、問題を示すために、テスト・ケースである：ここ

public static void main(String args[]){ 
    TreeSet<Integer> set = new TreeSet<>(); 
    set.add(4); 
    set.add(2); 
    set.add(3); 
    set.add(1); 

    System.out.println(set.headSet(1).size());//0 
    System.out.println(set.headSet(2).size());//1 
    System.out.println(set.headSet(3).size());//2 
    System.out.println(set.headSet(4).size());//3 
    System.out.println(set.headSet(-1).size());//0!!Caution!,retusn 0 though it does not exits 

} 

Answer 2

私はTreeSetの周りつついとそのしばらくの間のインタフェース、およびIは要素のインデックスを取得することが分かっ最良の方法は次のとおりです。

set.headSet(element).size() 

headSet(element)その引数より小さい要素のサブTreeSetを返すので、このセットのサイズはなります問題の要素のインデックス。確かに奇妙な解決策。

Answer 3

JavaのTreeSetクラスには、セット内の数値のインデックスを見つける機能がありません。そのためには、独自の実装を提供する必要があります。これは、Red-Blackツリーであり、索引操作をサポートするために拡張することができます。 「アルゴリズムの紹介」の「データ構造の拡張」の章のOS-RANKの手順を見てください。それはあなたが求めているものです。

Answer 4

私は同じ問題を抱えていました。そこで、私はjava.util.TreeMapのソースコードをとり、IndexedTreeMapと書きました。

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> { 
    K exactKey(int index); 
    Entry<K, V> exactEntry(int index); 
    int keyIndex(K k); 
} 

実装は、それが変更された場合赤黒ツリーのノードの重みを更新するに基づいています：それは私自身のIndexedNavigableMapを実装しています。重みは、与えられたノードの下にある子ノードの数に1を加えたものです。たとえば、ツリーは左に回転させたときに：私たちはここに、インデックスによって要素が使用する実装で見つける必要があるとき

void updateWeight(int delta) { 
     weight += delta; 
     Entry<K, V> p = parent; 
     while (p != null) { 
      p.weight += delta; 
      p = p.parent; 
     } 
    } 

をそして：

private void rotateLeft(Entry<K, V> p) { 
    if (p != null) { 
     Entry<K, V> r = p.right; 

     int delta = getWeight(r.left) - getWeight(p.right); 
     p.right = r.left; 
     p.updateWeight(delta); 

     if (r.left != null) { 
      r.left.parent = p; 
     } 

     r.parent = p.parent; 


     if (p.parent == null) { 
      root = r; 
     } else if (p.parent.left == p) { 
      delta = getWeight(r) - getWeight(p.parent.left); 
      p.parent.left = r; 
      p.parent.updateWeight(delta); 
     } else { 
      delta = getWeight(r) - getWeight(p.parent.right); 
      p.parent.right = r; 
      p.parent.updateWeight(delta); 
     } 

     delta = getWeight(p) - getWeight(r.left); 
     r.left = p; 
     r.updateWeight(delta); 

     p.parent = r; 
    } 
    } 

updateWeightは、単にルートまでの重みを更新重み：

public K exactKey(int index) { 
    if (index < 0 || index > size() - 1) { 
     throw new ArrayIndexOutOfBoundsException(); 
    } 
    return getExactKey(root, index); 
} 

private K getExactKey(Entry<K, V> e, int index) { 
    if (e.left == null && index == 0) { 
     return e.key; 
    } 
    if (e.left == null && e.right == null) { 
     return e.key; 
    } 
    if (e.left != null && e.left.weight > index) { 
     return getExactKey(e.left, index); 
    } 
    if (e.left != null && e.left.weight == index) { 
     return e.key; 
    } 
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1); 
} 

はまた、キーのインデックスを見つけることは非常に便利になる：

public int keyIndex(K key) { 
    if (key == null) { 
     throw new NullPointerException(); 
    } 
    Entry<K, V> e = getEntry(key); 
    if (e == null) { 
     throw new NullPointerException(); 
    } 
    if (e == root) { 
     return getWeight(e) - getWeight(e.right) - 1;//index to return 
    } 
    int index = 0; 
    int cmp; 
    if (e.left != null) { 
     index += getWeight(e.left); 
    } 
    Entry<K, V> p = e.parent; 
    // split comparator and comparable paths 
    Comparator<? super K> cpr = comparator; 
    if (cpr != null) { 
     while (p != null) { 
      cmp = cpr.compare(key, p.key); 
      if (cmp > 0) { 
       index += getWeight(p.left) + 1; 
      } 
      p = p.parent; 
     } 
    } else { 
     Comparable<? super K> k = (Comparable<? super K>) key; 
     while (p != null) { 
      if (k.compareTo(p.key) > 0) { 
       index += getWeight(p.left) + 1; 
      } 
      p = p.parent; 
     } 
    } 
    return index; 
} 

私はすぐにIndexedTreeSetを実装します。その間、IndexedTreeMapのキーセットを使用できます。

更新： IndexedTreeSetが実装されました。セットには、この要素が存在しないにもかかわらず@Yrlecは0をset.headSet(element).size意志リターンを指摘するように

あなたがhttp://code.google.com/p/indexed-tree-map/

Answer 5

は私の機能を示しています。

// TreeSetのに文字列位置をGIVEする機能グアバで代替または番目の1があった場合、それは反復して `O（N）`で見つけることができる非常に少なくとも

private static void get_posistion(TreeSet abre, String codig) { 
    Iterator iterator; 
    iterator = abre.iterator(); 
    int cont = 0; 
    String prova = ""; 

    while (iterator.hasNext()) {      
     prova = iterator.next().toString(); 
     if (codig.equals(prova)) { 
      System.out.println(cont); 
     } else { 
      cont++; 
     } 
    } 
}