Arbre AVL
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de  |
Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant. |
En informatique, les arbres AVL sont les premiers arbres binaires de recherche équilibrés inventés. Dans un arbre AVL, les hauteurs des deux sous-arbres d'un même nœud diffèrent au plus de un. La recherche, l'insertion et la suppression 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 nœud est la différence entre la hauteur de son sous-arbre droit et celle de son sous-arbre gauche. Un nœud dont le facteur d'équilibrage est 1, 0, ou -1 est considéré comme équilibré. Un nœud 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 nœud 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).
Sommaire |
[modifier] Opérations
Les opérations de base d'un arbre AVL mettent en œuvre 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".
[modifier] Insertion
L'insertion dans un arbre AVL se déroule en deux étapes : Tout d'abord, on insère le nœud exactement de la même manière que dans un arbre binaire de recherche ; puis on remonte depuis le nœud inséré vers la racine en effectuant une rotation sur chaque sous-arbre déséquilibré. La hauteur de l'arbre étant en O(ln(n)), et les rotations étant à temps constant, l'insertion se fait finalement en O(ln(n)).
[modifier] Suppression
La suppression dans un arbre AVL peut se faire par rotations successives du nœud à 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 O(ln(n)).
[modifier] Recherche
La 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 O(ln(n)), elle se fait donc en O(ln(n)). Contrairement aux arbres splay, la recherche ne modifie pas la structure de l'arbre.
[modifier] Voir aussi
[modifier] Références
- G. Adelson-Velskii et E.M. Landis, "An algorithm for the organization of information." Doklady Akademii Nauk SSSR, 146:263–266, 1962.
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Troisième Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 458–475 de la section 6.2.3: Balanced Trees. NB: Knuth appelle les arbres AVL "balanced trees".
