CLASSES D'ARBRES (BINAIRE , BINAIRE DE RECHERCHE, AVL , BICOLORE ...) + INTERFAC
cs_FireDraGon
Messages postés
21
Date d'inscription
mardi 23 avril 2002
Statut
Membre
Dernière intervention
12 juillet 2004
-
18 juin 2004 à 15:46
psycared Messages postés 4 Date d'inscription lundi 22 novembre 2010 Statut Membre Dernière intervention 2 décembre 2011 - 2 déc. 2011 à 18:20
psycared Messages postés 4 Date d'inscription lundi 22 novembre 2010 Statut Membre Dernière intervention 2 décembre 2011 - 2 déc. 2011 à 18:20
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/23649-classes-d-arbres-binaire-binaire-de-recherche-avl-bicolore-interface-graphique
https://codes-sources.commentcamarche.net/source/23649-classes-d-arbres-binaire-binaire-de-recherche-avl-bicolore-interface-graphique
2 déc. 2011 à 18:20
26 mars 2008 à 13:43
D'autre part, Arbre.java contient des champs inutiles pour certains types d'arbres. Comme les arbres sépcialisés définissent des méthodes, ne pourraient-ils pas directement définir les champs supplémentaires qu'ils requièrent? par exemple le champ "frere" est inutile si on n'a pas d'arbe bicolore, et ce source ne permet pas de transformer un type d'arbre dans un autre car il n'y a pas de fonction de rééquilibrage adaptée à chaque type d'arbre.
A la base, tous ces arbres sont binaires, seul le critère d'équilibrage change. On pourrait s'attendre à pouvoir gérer des arbes quelconques de degré supérieur à 2.
De façon générale, ce type de classe est surtout ditactique, mais dans ce cas autant faire simple, car la hoérarchie de classes Java n'est pas utilisée de façon optimale. Autant utiliser les collections standards de Java où on a un conteneur "SortedTree" pour faire la même chose de façon plus générale avec des valeurs stockées pouvant aussi être des objets quelconques et un sous-classement possible pour le le critère d'ordonnancement des valeurs dans l'arbre (en implémentant un Comparator dans la sous-classe conteneur): par exemple un HashedTree n'est rien d'autre qu'un arbre trié dans lequel les valeurs stockées sont triées par leur valeur (int) de hachage, et maintenu équilibré en hauteur (avec une tolérance heuristique locale ou globale).
Note: les opérations d'équilibrage sont couteuses car cela consiste à caluler ou maintenir en cache la hauteur de l'arbre. Généralement on stocke dans chaque noeud la hauteur maximale de l'arbre porté par ce noeud, et l'équilibrage tente de maintenir égales les hauteurs des sous-abres gacuhe et droite quand ils existent, et s'assurer qu'un noeud parent porte au moins 3 descendants; cela suffit pour un équilibrage partiel mais efficace et suffisant la plupart du temps dans le cas d'arbres binaires au contenu très souvent modifié; il suffit de maintenir aussi le nombre total de noeud dans l'arbre au sein de chaque feuille pour ne pas avoir à parcourir chaque fois tout l'arbre pour les compter. Mais on peut aussi ne maintenir dans chaque noeud que la différence entre le nomnbre de noeuds descendants à droite et le nombre de nouds descendants à gauche, cette différence devant rester dans un petit intervalle de +/-N; dès que cette différence dépasse, on applique un rééquilibrage global de ce sous-arbre, ou partiel (par exemple réduire cette différence de moitié, plus rapide à réaliser si l'arbre subit de fréquentes mises à jour). Le critère à utiliser peut même être dynamique en comptant le nombre de recherches dans l'arbre depuis la dernière mise à jour: si ce nombre de recherche dépasse un seuil de réorganisation, on réduit ce seuil; on compte aussi le nombre d'ajouts ou suppressions depuis un la dernière recherche, et si ce nombre dépasse un seuil on augmente ce seuil de réorganisation.
Pour les réorganisations d'équilibrage, on utilise les primitives de rotation de valeurs.
18 juin 2004 à 15:46
Correction de 2 bugs