TRI DE LIST EN UTILISANT LES ABR

Commentaire de verdy_p le 26/03/2008 13:01:02

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.