IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Interfaces Graphiques en Java Discussion :

tri d'arbre


Sujet :

Interfaces Graphiques en Java

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    151
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 151
    Par défaut tri d'arbre
    bonjour tout le monde,

    voilà mon pb, j'ai un JXTreeTable que j'aimerai trier. Vu que le modèle de donnée est un arbre, mon but est de trier cet arbre.

    Première question : existe-t-il une méthode déjà faites pour trier un arbre selon un critère ?? en tout cas j'ai pas trouvé.

    Pour résumer mon arbre de donnée :
    J'ai un arbre de profondeur max 2. Certains noeuds n'ont pas de fils. Au max, ma treetable a 500 éléments.

    -- côté perf --
    Plutôt que de trier à chacune des mises à jour de mon arbre, je pensais trier une bonne fois pour toute quand l'utilisateur choisit l'action de trier et ensuite insérer les éléments qui arrivent "à la bonne place" (du coup perdre un peu plus de temps à chaque l'insertion/suppression mais gagner en tri)
    Déjà est-ce déconnant d'agir comme ça ?

    -- côté implémentation pour le tri d'arbre --
    idée d'implementation 1
    1 - je mets tous les fils de la racine dans une liste temporaire
    2 - je trie la liste avec les tri "standard" des collections (Java.util.Collection et ses algos de sort)
    3 - je détruis mes noeuds et je les re-crée en se basant sur ma liste triée
    4 - je répète l'opération pour chacun des noeuds qui a des fils (sachant que tous les noeuds intermédiaire n'auront pas forcément de fils)

    + : rapide/facile à coder, sur, l'algo de tri est forcément performant
    - : en terme de gestion de donnée ça me semble un peu lourd, si le tri est rapide qu'en est-il de la reconstruction de tout mon arbre ? par contre je ne manipule des noeuds qu'une fois pour toute (à la recréation de mon arbre).


    idée d'implementation 2
    1 - Je trie directement les noeuds de mon arbre avec un algo "fait maison"
    2 - je répète l'opération pour chacun des noeuds qui a des fils

    + : ça me semble beaucoup plus léger et "naturel" comme manière de faire
    - : je suppose que les algos de tri du package collections seront meilleurs que les miens. Autre chose, Je manipule beaucoup les noeuds (suppression/insertion à la bonne place) ... est-ce plus couteux que de tout détruire et de tout reconstruire ?


    Je ne demande pas une implémentation, c'est juste pour discuter sur des méthodes de tris d'arbre (maintenant si quelqu'un me le fait, moi ça me va aussi ). Je reste ouvert à toutes autres possibilités

  2. #2
    Membre très actif
    Inscrit en
    Mars 2008
    Messages
    283
    Détails du profil
    Informations forums :
    Inscription : Mars 2008
    Messages : 283
    Par défaut
    coté perf :

    Si j'ai bien compris ton idée : Tu veux ajouter un bouton pour que l'utilisateur trie lui même les données après ses ajouts/suppression.

    1) Tout dépends de ce que tu souhaite faire, une application totalement dynamique ou non
    2) Ne t'en fait pas pour les 500 éléments, c'est dans les 10000 éléments qu'il faut t'inquiéter
    3) Ton idée consiste simplement à séparer le listener de ton bouton d'ajout en deux (je pense que tu sera d'accord avec moi si je dis qu'avec une suppression, le tri est inutile), il n'y a rien de critiquable dedans. Même le bloc-note le fait (quand tu tape ton texte et que tu ne fait pas enregistrer, rien ne se passe sur ton disque dur )

    coté tri :

    Tes deux implantations se rejoignent :

    Si tu peux toi même créer ton arbre, fait un arbre n-aire (pour 500 éléments, mieux vaux faire comme ça) sous forme de liste de liste de liste de ..... (en gros un arbre = une liste d'arbres). Implémente ensuite l'interface Comparable, tu peux ensuite utiliser Collection.sort();

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    151
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 151
    Par défaut
    quand je parlais ajout/supression c'est que si je travaille directement sur l'arbre pour trier ne serait-ce que pour permuter 2 noeuds je suis obligé de les "supprimer" et de les "ajouter" chacun à leur place.
    Donc travailler directement sur l'arbre me fera donc multiplier les ajouts/suppresion dans l'arbre (sinon oui bien évidement je suis d'accord, supprimer un noeud ne me fait pas refaire mon tri )

    pour l'idée du bouton, oui c'est bien ça je veux rajouter un bouton sachant que le bouton peut être la collone sur laquelle on veut trier mais également un choix plus complexe pour permettre le tri sur plusieurs critères. Par contre, une fois le tableau trié, ma table "mémorise" la méthode de tri choisi (sur quelle(s) colonne(s) et ensuite quel ordre (desc/asc) pour chacune des colonnes) et place le nouvel élément à la bonne place. celà permet d'éviter d'avoir à retrier tout le tableau et de reconstruire mon arbre juste pour un élément. Le modèle est donc dynamique (pour répondre à ton 1) )

    oki merci pour tes remarques.

    2) Ne t'en fait pas pour les 500 éléments, c'est dans les 10000 éléments qu'il faut t'inquiéter
    oki, de toute façon, je pense que le mieux reste d'implémenter les deux méthodes de bourrer ma table avec vraiment beaucoup d'éléments et de comparer.

  4. #4
    Expert confirmé
    Avatar de sinok
    Profil pro
    Inscrit en
    Août 2004
    Messages
    8 765
    Détails du profil
    Informations personnelles :
    Âge : 45
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Août 2004
    Messages : 8 765

  5. #5
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    151
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 151
    Par défaut
    Merci.

    pour le lien je vais voir ce que ça donne pour intégrer la sortabletreetable à mon projet ...

Discussions similaires

  1. Gestion d'arbres par représentation intervallaire - Déplacements et tris
    Par samche dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 18/06/2013, 15h58
  2. Tri d'un arbre par représentation intervallaire
    Par Seb33300 dans le forum Langage SQL
    Réponses: 6
    Dernier message: 09/10/2012, 19h50
  3. [Méthode de tri][Arbre binaire] Problème dans l'ordre total
    Par jgavard dans le forum Collection et Stream
    Réponses: 1
    Dernier message: 24/04/2007, 16h55
  4. tri arbre binaire
    Par catilina dans le forum C
    Réponses: 2
    Dernier message: 20/10/2005, 09h48

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo