Discussion :

[Ekinoks]

Salut !

Je cherche à ranger des objets (Boite) dans une structure de donnée qui me permette de récupérer le plus rapidement possible :
- Soit la boite qui a exactement le volume que je demande
- Soit, si cette boite n'existe pas, les deux boites qui borne le volume demandé.

J'ai donc pensé au arbre, avec des temps d'insertion et de recherche en O(ln(n)).
J'ai cherché dans les bibliothèques java, et je suis tombé sur le "TreeSet" qui avait l'air de correspondre exactement à ce que je voulais =)

J'ai donc commencer a implémenter la chose, jusqu'au moment de faire la fameuse recherche. Là, impossible de trouver un moyen d'effectuer une recherche dans l'arbre mais seulement un parcourt séquentielle avec un Itérator

J'ai cherché sur mon moteur de recherche favori comment effectuer une recherche dans un arbre "TreeSet" mais je n'ai rien trouvé :^/


Je trouve bizarre que l'on ne puissent pas faire de recherche dans un "TreeSet" alors que le principale but d'un Arbre est justement de faire cela...

C'est pour quoi je pose a question ici, est t'il possible d'effectuer une recherche dans un arbre "TreeSet" ?

Merci pour vos réponses =)

[Cobalt59]

Salut !

J'espère avoir bien compris ta question.

Pourquoi pas utiliser java.DOM (qui est utilisé pour le parcours de xml) afin de créer ton arbre.
TreeSet est bien mais pour ton genre de recherche ce ne doit pas être le top.

[Ekinoks]

Salut Cobalt59, et merci pour ta réponse =)

En fait, le problème n'est pas de créer l'arbre, mais plutôt d'effectuer une recherche dedans en temps logarithmique.

Je me retrouve actuellement un "TreeSet" remplie et je cherche comment effectuer un recherche dedans.

[Cobalt59]

Désole mais je ne penses pas que TreeSet soit la meilleure solution à ton problème.
Comme tu le sais un fichier xml est un arbre n-aires. Et tu peux le modéliser avec dom puis faire des recherches avec sax.
Donc je penses qu'il est possibles de faire ce que tu as besoins avec dom et sax.
Désolé mais je n'ai pas de solution toute faites.

Si vraiment tu veux rester sur un TreeSet tu peux optimiser tes recherches ( avec un iterator je ne vois pas comment faire autrement sur un Set ) avec un Comparator juste avant ta recherche, afin d'arriver plus vite à ton résultat.
Les méthodes add et contains étends faites en un temps log(n), on reste ( àpeu près ) dans ce que tu recherches.

Sinon il va falloir faire appel aux matheux

[Ekinoks]

ok, dans ce cas je pense que le plus simple serais que je créer moi même une classe d'arbre binaire de recherche (il sera pas équilibré mais tampi ^^)

Merci pour ton aide Cobalt59