tri d'arbre

**kisame** · 09/04/2008, 18h42

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

**Grimly_old** · 09/04/2008, 23h22

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

**kisame** · 10/04/2008, 08h33

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.