Cách tìm chỉ mục của phần tử trong TreeSet?

Question

Tôi đang sử dụng TreeSet<Integer> và tôi khá đơn giản muốn tìm chỉ mục của một số trong tập hợp. Có cách nào tốt đẹp để làm điều này mà thực sự làm cho việc sử dụng O (log (n)) phức tạp của cây nhị phân?

(Nếu không, tôi nên làm gì, và không ai biết tại sao không? Tôi rất tò mò tại sao một lớp học như vậy sẽ được bao gồm trong Java mà không cần một cái gì đó giống như một chức năng tìm kiếm.)

Answer 1

Như @Yrlec chỉ ra set.headSet(element).size sẽ trả về 0 mặc dù không có yếu tố này trong các thiết lập.Vì vậy, chúng tôi phải kiểm tra:

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

Đây là một trường hợp thử nghiệm để hiển thị các vấn đề:

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

Tôi chọc xung quanh TreeSet và giao diện của nó trong một thời gian, và cách tốt nhất tôi tìm thấy để có được những chỉ số của một nguyên tố là:

set.headSet(element).size() 

headSet(element) trả về phụ TreeSet của các yếu tố ít hơn đối số của nó, vì vậy kích thước của bộ này sẽ là chỉ mục của phần tử được đề cập. Một giải pháp kỳ lạ thực sự.

Answer 3

Lớp TreeSet trong Java không có khả năng tìm chỉ mục của một số trong tập hợp. Để làm được điều đó, bạn phải cung cấp việc triển khai của riêng mình - đó là một cây Đỏ-Đen bên dưới mui xe, và nó có thể được tăng cường để hỗ trợ hoạt động chỉ mục. Hãy xem thủ tục OS-RANK trong chương "Tăng cường cấu trúc dữ liệu" của "Giới thiệu về thuật toán", đó chính xác là những gì bạn đang yêu cầu.

Answer 4

Tôi gặp vấn đề tương tự. Vì vậy, tôi lấy mã nguồn của java.util.TreeMap và viết IndexedTreeMap. Nó thực hiện của riêng tôi IndexedNavigableMap:

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

Việc thực hiện dựa trên việc cập nhật trọng lượng nút trong cây đỏ-đen khi nó được thay đổi. Trọng lượng là số lượng các nút con bên dưới một nút nhất định, cộng với một - tự. Ví dụ khi một cây có thể xoay sang trái:

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 chỉ đơn giản là cập nhật trọng lượng lên vào thư mục gốc:

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

Và khi chúng ta cần phải tìm ra nguyên tố theo chỉ số ở đây là việc thực hiện rằng sử dụng trọng lượng:

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

Cũng có rất tiện dụng tìm kiếm các chỉ số của một phím:

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

Tôi sẽ sớm triển khai IndexedTreeSet, trong khi đó bạn có thể sử dụng bộ khóa từ IndexedTreeMap.

Cập nhật: Chỉ mụcTreeSet được triển khai ngay bây giờ.

Bạn có thể tìm thấy những kết quả của công tác này tại http://code.google.com/p/indexed-tree-map/

Answer 5

đây cho thấy chức năng của tôi:

// CHỨC NĂNG CHO CHO MỘT VỊ TRÍ STRING VÀO 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++; 
     } 
    } 
}