TreeSet에서 요소의 색인을 찾는 방법은 무엇입니까?

Question

저는 TreeSet<Integer>을 사용하고 있습니다. 세트의 숫자 인덱스를 찾고 싶습니다. 실제로 이진 트리의 O (log (n)) 복잡성을 사용하는 좋은 방법이 있습니까? (나는 어떻게해야하지 않을 경우 누군가가 이러한 클래스는 검색 기능과 같은없이 자바에 포함 왜? 내가 궁금해서 이유를 알지 않습니다.)

Answer 1

에서이 작업의 결과를 확인할 수 있습니다.TreeSet의에 캐릭터의 위치를 ​​줘

// 기능 :

여기

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 클래스에는 집합의 숫자 인덱스를 찾는 기능이 없습니다. 이를 위해 자체 구현을 제공해야합니다.이 구현은 Red-Black 트리이며, 인덱스 작업을 지원하기 위해 추가 될 수 있습니다. "Introduction to Algorithms"의 "Augmenting Data Structures"장의 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을 구현합니다. 가중치는 주어진 노드 아래에있는 자식 노드의 수와 하나의 자체입니다.

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

은 또한에 오는 키의 인덱스를 찾는 매우 편리합니다 923,210

나는 그 사이에 당신은 IndexedTreeMap에서 키 설정을 사용할 수 있습니다, 곧 IndexedTreeSet을 구현합니다.

업데이트 : IndexedTreeSet 이제 구현됩니다. 세트에는이 요소가 없지만 @Yrlec 0을 set.headSet(element).size 것이다 수익을 지적 하듯이

당신은 http://code.google.com/p/indexed-tree-map/

Answer 5

내 기능을 보여줍니다 여기에

return set.contains(element)? set.headSet(element).size(): -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++; 
     } 
    } 
}