如何查找TreeSet中元素的索引？

Question

我使用的是一個TreeSet<Integer>，我很想找到一組數字的索引。有沒有一種很好的方式來實現這一點，它實際上是利用二叉樹的O（log（n））複雜度？

（如果沒有，我應該做的，沒有人知道爲什麼不呢？我很好奇，爲什麼這樣一類將包括在Java中沒有類似的搜索功能。）

Answer 1

發現這項工作的結果作爲@Yrlec指出set.headSet(element).size將返回0，雖然有在集中沒有這個元素。所以我們最好檢查：

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中和它一會兒，我發現得到一個元素的索引的最好辦法就是接口：

set.headSet(element).size() 

headSet(element)返回小於它的參數元素的子TreeSet，所以這集的大小將是有問題的元素的索引。確實是一個奇怪的解

Answer 3

Java中的TreeSet類無法找到集合中某個數字的索引。爲此，你必須提供你自己的實現 - 它是一個紅黑樹，它可以被擴充來支持索引操作。看看「算法簡介」的「擴展數據結構」一章中的OS-RANK過程，這正是您要求的。

Answer 4

我有同樣的問題。於是我拿了java.util.TreeMap的源代碼並寫了IndexedTreeMap。它實現了我自己的IndexedNavigableMap：

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

的實現是基於當它改變了紅黑樹更新節點的權重。重量是給定節點下的子節點數量，加上一個自我。例如，當一棵樹被旋轉到左邊：

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只需更新重量達根：

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

而當我們需要找到通過索引此處的元素是實現使用權重：

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現已實施。

您可以在http://code.google.com/p/indexed-tree-map/

Answer 5

在這裏展示我的功能：

//函數給出一個字符串的位置INTO TreeSet中

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++; 
     } 
    } 
}