Comment trouver le rang d'un élément dans un TreeSet

Question

Je sais que vous pouvez trouver le premier et le dernier élément d'un jeu d'arbres. Et si je voulais savoir ce que le deuxième ou le troisième élément était sans itération? Ou, plus préférable, compte tenu d'un élément, comprendre son rang dans l'arborescence.

Merci

EDIT: Je pense que vous pouvez le faire en utilisant tailset, par exemple. comparez la taille de l'ensemble original avec la taille de la queue. Quelle est l'efficacité du jeu de queues?

Answer 1

Selon la source de l'implémentation Sun JDK6, tailSet(E).size() effectue une itération sur l'ensemble queue et compte les éléments, donc cet appel est O (tail set tail).

Answer 2

Il n'y a pas d'autre moyen que Iterator.

Modifié:

Essayez ceci:

treeSet.higher(treeSet.first()); 

Cela devrait donner deuxième élément sur TreeSet. Je ne suis pas sûr si cela est plus optimisé alors juste en utilisant Iterator.

Answer 3

TreeSet ne fournit pas une méthode de classement efficace. Je suspecte (vous pouvez confirmer en regardant sa source) que TreeSet ne garde même pas de bits d'information supplémentaires (c.-à-d. Nombre d'éléments sur les sous-arbres gauche et droit de chaque nœud) que l'on aurait besoin d'effectuer de telles requêtes dans O (n)) heure. Il ne semble donc pas y avoir de méthode rapide pour trouver le rang d'un élément de TreeSet.

Si vous avez vraiment vraiment besoin, vous pouvez mettre en œuvre votre propre SortedSet avec un arbre binaire équilibré qui permet de telles requêtes ou modifier la mise en œuvre TreeSet pour créer une nouvelle implémentation qui est augmentée pour permettre de telles requêtes. Reportez-vous au chapitre sur l'augmentation des structures de données dans CLRS pour plus de détails sur la façon dont cela peut réellement être fait.