Comment trouver l'indice d'un élément dans un TreeSet?
j'utilise un TreeSet<Integer> et je voudrais tout simplement à trouver l'indice d'un nombre dans l'ensemble. Y a-t-il une bonne façon de le faire qui utilise réellement la complexité O(log(n)) des arbres binaires?
(Si non, que dois-je faire, et personne ne sait pourquoi pas? Je suis curieux de savoir pourquoi une telle classe serait incluse dans Java sans quelque chose comme une fonction de recherche.)
5 réponses
comme le souligne @Yrlec set.headSet(element).size retourne 0 s'il n'existe pas de cet élément dans l'ensemble. Donc, nous ferions mieux de vérifier:
return set.contains(element)? set.headSet(element).size(): -1;
Voici un test pour montrer le problème:
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
}
J'ai parcouru TreeSet et ses interfaces pendant un certain temps, et la meilleure façon que j'ai trouvée pour obtenir L'index d'un élément est:
set.headSet(element).size()
headSet(element) renvoie le sous -TreeSet des éléments de moins que son argument, de sorte que la taille de cet ensemble sera l'indice de l'élément en question. Une solution étrange en effet.
j'ai eu le même problème. Alors j'ai pris le code source de java.util.TreeMap et écrit IndexedTreeMap. Il implémente mon propre IndexedNavigableMap:
public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
K exactKey(int index);
Entry<K, V> exactEntry(int index);
int keyIndex(K k);
}
l'implémentation est basée sur la mise à jour des poids des noeuds dans l'arbre rouge-noir quand il est modifié. Le poids est le nombre de noeuds enfant sous un noeud donné, plus un-moi. Par exemple, lorsqu'un arbre tourne à gauche:
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;
}
}
updatewweight met tout simplement à jour les poids jusqu'à la racine:
void updateWeight(int delta) {
weight += delta;
Entry<K, V> p = parent;
while (p != null) {
p.weight += delta;
p = p.parent;
}
}
Et quand nous avons besoin de trouver l'élément à l'index ici est la mise en œuvre qui utilise des pondérations:
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);
}
est également très pratique pour trouver l'index d'une clé:
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;
}
J'implémenterai bientôt IndexedTreeSet, en attendant vous pouvez utiliser le jeu de touches de IndexedTreeMap.
mise à Jour: la version indexée de TreeSet est implémentée maintenant.
Vous pouvez découvrir le résultat de ce travail à http://code.google.com/p/indexed-tree-map/
TreeSet classe en Java n'a pas la capacité de trouver l'indice d'un nombre dans l'ensemble. Pour cela, vous devez fournir votre propre implémentation - c'est un arbre rouge-noir sous le capot, et il peut être augmenté pour supporter l'opération d'index. Jetez un oeil à l' OS-RANK procédure dans le chapitre "augmentation des Structures de données" de "Introduction aux algorithmes", c'est précisément ce que vous demandez.
ici montrer ma fonction:
/ / FUNCTION FOR GIVE A STRING POSITION 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++;
}
}
}