Tri de list en utilisant les abr

Soyez le premier à donner votre avis sur cette source.

Vue 11 140 fois - Téléchargée 794 fois

Description

Bonne classe BinaryTree pour la manip des arbres binaires de recherches(fonctionnalités de base).
cette classe nous permettera après de trier une liste d'objets.la liste étant une autre classe SorList écrite à la base de la classe Stack de Java.
l'idée étant de construire un ABR à partir de la liste concernée et après parcourir l'arbre dans l'ordre Left->Root->Right ou l'inverse selon l'ordre de tri soihaité, au fur et à mesure du parcours on construit une nouvelle liste qui elle contiendera automatiquement les éléments triés.
+quelques exceptions traitées (NullPointerException,...).
le code est assez simple pour le comprendre. les classes ne sont pas bien commentées mais je rectifierai après.
Vos suggestions sont les bienvenus pour améliorer les classe implémentées.

Conclusion :


bonne compréhension

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
203
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019

pas de copier-coller. Mais n'importe qui comprend ou sait ce qu'est un arbre binaire, c'est une structure de base.
En revanche, les notions d'équilibrage sont nettement plus intéressantes, la question étant de savoir *quand* on doit rééquilibrer un arbre ou un sous-arbre.
Il faut être concient qu'un ajout simple et sans précaution de pleins de noeuds dans un arbre binaire conduit à un arbre totalement dégénéré (réduit à une liste chainée à droite ou un liste chainée à gauche) dans un cas finalement assez fréquent: quand les éléments ajoutés sont ordonnés, et dans ce cas l'arbre binaire est encore plus couteux que la liste simple car plus compliqué à parcourir et plus volumineux en mémoire.
Messages postés
17
Date d'inscription
lundi 6 décembre 2004
Statut
Membre
Dernière intervention
26 avril 2008

Bonjour tout le monde
verdy_p, merci pour le cours :d cé du copier/coller ??
Bon l'admin a fait son travail, les membres n'ont pas à refaire les mêmes remarques
plus que çà, lisez-bien la description de ma source, c'est bien noté (fonctionnalités de base)

à bientôt
Messages postés
203
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019

Effectivement, ce code n'a rien d'exceptionnel. Il aurait été plus utile de fournir un AVL équilibré (c'est à dire inclure une fonction d'équilibrage réduisant la hauteur moyenne des noeuds dans l'arbre en augmentant la densité des noeuds pleins; idéalement un abre binaire équilibré ne contient des noeuds avec un seul fils (droite ou gauche) que si ces neids sont porteurs de feuilles (sans aucun descendant), et il y a à peu près autant de noeuds pleins (à deux fils) que de noeuds feuilles (sans fils), un critère statistique heuristique cherchant à maintenir ce rapport dans l'arbre entier en l'appliquant récursivement à chacune de ses branches, avec une tolérance.
On n'est pas formécement obligé de maintenir un compteur d'équilibrage (par exemple la différence ente le nombre de noeuds descendants à droite et de noeuds descendants à gauche) dans chaque noeud, si on utilise l fonction de rééquilibrage tous les N ajouts ou suppresion dans l'arbre (par exemple toutes les 256 opérations: si l'insertion dans l'arbre se fait de façon aléatoire, l'arbre est à peu près équilibré, mais si l'insertion est ordonnée, l'arbre obtenu est totalement déséquilibré et devient une simple liste).

Rappelons que le but d'utiliser un arbre plutôt qu'une lsite est de réduire la distance de parcours des noeuds pour trouver un noeud donné par test successif; l'équilibrage au moins partiel est donc une condition pour qu'un arbre soit intéressant à utiliser: l'insertion dans l'arbre aura un coût qui doit être balancé par un accès plus rapide en lecture seulement, ce qui signifie qu'il y aura beaucoup moins d'insertions/suppression dans l'arbre que de parcours ultérieur à la recherche d'un noeud. On peut donc passer un peu plus de temps lors des insertions/suppressions pour maintenir l'équilibre, ce temps étant ensuite récupéré pour les parcours ultérieurs en lecture seule.

Bref un arbre binaire sans équilibrage ne sert à rien du tout, autant utiliser une liste, ce sera plus rapide et prendra moins de mémoire!

La base permetttant de rééquilibrer une branche est de trouver rapidement les feuilles extrèmes à droite une branche gauche à rééquilibrer, et remonter cette feuille à la racine par rotation successive pour ensuite insérer le noeud porteur des branches en tant que feuille extrème à à guche dans l'autre branche, là aussi par rotation successive en descendant. Il y a des librairies qui font ça très bien.

Il existe aussi un algorithme optimal en temp pour rééquilibrer un arbre binaire (dont l'équilibrage est dans un état quelconque): un tel also transforme d'abord l'arbre en liste dégénénérée (tous les noeuds liés à droite uniquement, aucun fils à gauche), puis connaissant la longueur totale de la liste, la coupe en deux au milieu et fait de ce noeud la nouvelle racine portant chaque demi-liste, puis il subdivise récursivement chacune des deux sous-listes à droite et à gauche.

La généralisation de ces algorithmes d'équilibrage est le B-Arbre (B-Tree) pour des noeuds de degré supérieur à 2: le critère d'équilibrage est de maintenir un niveau minimum de remplissage de chaque noeud non terminal (pour l'arbre binaire ce niveau ne peut valoir que 50% ou 100%, à 50% le B-Arbre c'est un arbre binaire simple sans équilibrage, à 100% c'est un équilibrage total, coûteux; de fait les B-Arbres sont normalement de degré 3 au minimum avec un taux de 67%, plus souvent de degré 4 minimum avec un taux de 75% des branches, mais généralement de degré 6 minimum avec 85% des branches occupées, ou degré 9 avec 85% des 8 "slots" remplis à chaque noeud racine).

Dans les bases de données, les noeuds sont souvent de degré variable, car les "slots" sont de longueur variable (pour contenir les valeurs de clés), dans des noeuds de taille fixe (le noeud est d'une taille pouvant être lue en un seul accès disque ou dans une seule page mémoire, entre 512 octets et 4Ko par noeud, pointeurs de branches compris, le nombre de branches stockable par noeud dépendant des longueurs de clés stockées.) Cette disposition maixmise la densité d'information stockée sur disque ou la localité en mémoire, et réduit la fragmentation en facilitant l'utilisant des espaces laissés libres.

Toute bonne librairie oulibre traitant des B-arbes et autres AVL traite du cas plus simple de l'arbre binaire et de l'importance de son équilibrage et la façon de le faire.
Messages postés
5350
Date d'inscription
dimanche 4 mai 2003
Statut
Modérateur
Dernière intervention
29 juin 2020
96
Salut,

apres avoir regardé le code dsl mais il n'a rien d'initié je le repasse en débutant.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.