eBabylone
.com
Desole pas de resultatFlickr Badge ArbreUn article de Wikipedia.y-project.com.
Image:Arbre-non-avl.png Un exemple d'arbre non-AVL En informatique, les arbres AVL sont les premiers arbres binaires de recherche balancés inventés. Dans un arbre AVL, les hauteurs des deux sous-arbres d'un même noeud diffèrent au plus de un. La recherche, l'insertion et la supression sont toutes en O(ln n) dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations. La dénomination "arbre AVL" provient des noms de ses deux inventeurs, respectivement G.M. Adelson-Velsky et E.M. Landis, qui l'ont publié en 1962 sous le titre "An algorithm for the organization of information". Le facteur d'équilibrage d'un noeud est la différence entre lahauteur de son sous-arbre droit et celle de son sous-arbre gauche. Un noeud dont le facteur d'équilibrage est 1, 0, ou -1 est considéré comme équilibré ou balancé. Un noeud avec tout autre facteur est considéré comme déséquilibré et requiert un rééquilibrage. Le facteur d'équilibrage est soit déduit des hauteurs des sous arbres, soit stocké dans chaque noeud de l'arbre (ce qui permet un gain de place, ce facteur pouvant être stocké sur deux bits, mais complexifie les opérations d'insertion et de suppression). Image:Arbre AVL.png Le même arbre après un rééquilibrage
[] OpérationsLes opérations de base d'un arbre AVL mettent en oeuvre généralement les mêmes algorithmes que pour une arbre binaire de recherche, à ceci près qu'il faut ajouter des rotations de rééquilibrage nommées "rotations AVL". [] InsertionL'insertion dans un arbre AVL se déroule en deux étapes: tout d'abord, on insère le noeud exactement de la même manière que dans un arbre binaire de recherche, puis on remonte depuis le noeud inséré vers la racine en effectuant une rotation sur chaque sous-arbre déséquilibré. La hauteur de l'arbre étant en <math>O(ln(n))</math>, et les rotations étant à temps constant, l'insertion se fait finalement en <math>O(ln(n))</math>. [] SuppressionLa suppression dans un arbre AVL peut se faire par rotations successives du noeud à supprimer jusqu'à une feuille (en choisissant ces rotations de sorte que l'arbre reste équilibré), et ensuite en supprimant cette feuille directement. La suppression se fait aussi en <math>O(ln(n))</math>. [] RechercheLa recherche dans un arbre AVL se déroule exactement de la même manière que pour un arbre binaire de recherche, et comme la hauteur d'un arbre AVL est en <math>O(ln(n))</math>, elle se fait donc en <math>O(ln(n))</math>. Contrairement aux arbres splay, la recherche ne modifie pas la structure de l'arbre. [] Voir aussi[] Références
[] Liens externes
La source est wikipedia http://fr.wikipedia.org/wiki/Arbre AVL |
Revue de presse Arbre_AVL
Server 2.0