java - resueltos - ¿Cómo encontrar el índice de un elemento en un TreeSet?

tipos de colecciones en java

Question

Estoy usando un TreeSet<Integer> y simplemente me gustaría encontrar el índice de un número en el conjunto. ¿Existe una buena manera de hacer esto que realmente haga uso de la complejidad O (log (n)) de los árboles binarios?

(De lo contrario, ¿qué debo hacer? ¿Alguien sabe por qué?) Tengo curiosidad por saber por qué dicha clase se incluiría en Java sin algo así como una función de búsqueda.

Answer 1

Busqué TreeSet y sus interfaces por un tiempo, y la mejor manera que encontré para obtener el índice de un elemento es:

set.headSet(element).size()

headSet(element) devuelve el subconjunto TreeSet de elementos menos que su argumento, por lo que el tamaño de este conjunto será el índice del elemento en cuestión. Una solución extraña de hecho.

Answer 2

Como @Yrlec señala set.headSet(element).size devolverá 0 aunque no hay este elemento en el conjunto. Así que será mejor que verifiquemos:

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

Aquí hay un caso de prueba para mostrar el problema:

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 3

La clase TreeSet en Java no tiene la capacidad de encontrar el índice de un número en el conjunto. Para eso, tendrías que proporcionar tu propia implementación: es un árbol Rojo-Negro bajo el capó, y se puede aumentar para admitir la operación de índice. Eche un vistazo al procedimiento OS-RANK en el capítulo "Aumento de las estructuras de datos" de "Introducción a los algoritmos", es precisamente lo que está solicitando.

Answer 4

Yo tuve el mismo problema. Así que tomé el código fuente de java.util.TreeMap y escribí IndexedTreeMap . Implementa mi propio IndexedNavigableMap :

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

La implementación se basa en actualizar los pesos de los nodos en el árbol rojo-negro cuando se cambia. El peso es la cantidad de nodos secundarios debajo de un nodo dado, más uno mismo. Por ejemplo, cuando un árbol se gira hacia la izquierda:

 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 simplemente actualiza los pesos hasta la raíz:

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

Y cuando necesitamos encontrar el elemento por índice, aquí está la implementación que usa ponderaciones:

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

También resulta muy útil encontrar el índice de una clave:

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

Implementaré IndexedTreeSet pronto, mientras tanto, puedes usar el conjunto de claves de IndexedTreeMap.

Actualización: IndexedTreeSet se implementa ahora.

Puede encontrar el resultado de este trabajo en http://code.google.com/p/indexed-tree-map/

Answer 5

aquí muestro mi función:

// FUNCIÓN PARA DAR UNA POSICIÓN DE CADENA EN 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++;
}
}
}