Voir la source de Arbre AVL

{{voir homonymes|AVL}}

{{Infobox Algorithme}}

[[Image:Unbalanced binary tree.svg|vignette|Un exemple d'arbre binaire de recherche '''non-AVL'''.]]
En [[informatique théorique]], les '''arbres AVL''' ont été historiquement les premiers [[arbre binaire de recherche|arbres binaires de recherche]] [[arbre balancé|automatiquement équilibré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 <math>O(\log(n))</math> dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des [[Rotation d'un arbre binaire de recherche|rotations]].

La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement {{Lien|langue=en|fr=Georgii Adelson-Velsky}} et {{Lien|langue=en|trad=Evgenii Landis|fr=Evgueni Landis}}, qui l'ont publié en [[1962]] sous le titre ''{{Lang|en|An Algorithm for the Organization of Information}}''<ref>{{en}} G. Adelson-Velskii et E. M. Landis, ''{{Lang|en|An Algorithm for the Organization of Information}}''. ''Soviet Mathematics Doklady'', 3:1259–1263, 1962.</ref>.

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 calculé à partir des hauteurs respectives 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).

[[Image:AVLtreef.svg|vignette|Le même [[arbre de recherche]] après un rééquilibrage, maintenant AVL.]]

== Opérations ==

Les opérations de base d'un arbre AVL mettent en œuvre généralement les mêmes algorithmes que pour un [[arbre binaire de recherche]], à ceci près qu'il faut ajouter des rotations de rééquilibrage nommées « rotations AVL ».

=== Insertion ===

L'insertion d'un nœud 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 vers la racine depuis le nœud inséré en corrigeant les facteurs d'équilibrage, si la différence de hauteur est ≤ 1 (en [[valeur absolue]]), ou en effectuant une rotation simple ou double (= 2 rotations simples connexes), si la différence de hauteur est plus élevée que 1. La hauteur ''h'' de l'arbre étant en <math>O(\log(n))</math>, et les rotations ayant un coût constant, l'insertion se fait finalement en <math>O(\log(n))</math>.

Pour chaque insertion, il sera nécessaire de procéder à 0 ou 1 rotation simple ou double.

=== Suppression ===

La suppression dans un arbre AVL peut se faire par rotations successives du nœud à supprimer jusqu'à une feuille (en adaptant les facteurs d'équilibrage ou, si ce n'est pas possible, 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(\log(n))</math>.

Pour chaque suppression, il sera nécessaire de procéder de 0 à ''h'' rotations, où ''h'' est la hauteur de l'arbre.

=== 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 <math>O(\log(n))</math>, elle se fait donc en <math>O(\log(n))</math>. Contrairement à ce qui se passe pour les [[arbre splay|arbres splay]], la recherche ne modifie pas la structure de l'arbre.

== Hauteur ==

Dans un arbre AVL de hauteur ''h'', dans le pire des cas, en supposant que l'arbre est déséquilibré vers la gauche,
le sous-arbre de gauche aura une hauteur de ''h''&nbsp;-&nbsp;1, tandis que le sous-arbre de droite aura une hauteur de ''h''&nbsp;-&nbsp;2. Ceci donne une formule par récurrence pour connaître la taille minimale <math>S_{\text{min}}(h)</math> d'un arbre AVL de hauteur ''h''. Cette formule de récurrence est proche de la [[définition par récurrence]] des [[Suite de Fibonacci|nombres de Fibonacci]] : <math>S_{\text{min}}(h)=S_{\text{min}}(h-1)+S_{\text{min}}(h-2)+1</math>. D'où une estimation asymptotique pour <math>S_{\text{min}}(h)</math> de <math>\frac{1}{\sqrt{5}}\varphi^{h-2}-1,</math> où <math>\varphi</math> est le [[nombre d'or]].

À cause de la propriété d'équilibre des sous-arbres des AVL, la hauteur maximale <math>H_{max}</math> d'un AVL avec <math>n</math> nœuds internes est liée à la taille minimale d'un AVL de hauteur <math>h</math>. La hauteur maximale est inférieure à<ref name="cl-intro-algo">{{Cormen2fr}}, annexe B.</ref>{{,}}<ref>{{en}} Theodore Norvell, {{pdf}} [http://www.engr.mun.ca/~theo/Courses/dm/pub/2004/dm-application5.pdf « {{Langue|en|Application: AVL trees and the golden ratio}} »], {{Langue|en|Discrete Math. for Engineering}}, {{Langue|en|Memorial University}}, 2004.</ref>
<math>
\log_\varphi(\sqrt 5 (n+2)) - 2 = \log_\varphi(2) \cdot \log_2(\sqrt 5 (n+2)) - 2 \approx 1{{,}}44\log_2(n+2) - 0{{,}}328
</math>.

Cela donne une formule pour calculer la hauteur, dans le pire des cas, pour un arbre AVL contenant ''n'' nœuds internes.

Cette grandeur est meilleure que pour les [[arbre bicolore|arbres rouges et noirs]], où on a<ref name="cl-intro-algo" />{{,}}<ref>Pour des informations sur la taille, on pourra aussi consulter la page web {{en}} http://www.dyalog.dk/dfnsdws/n_avl.htm.</ref> <math>2 \times \log_{2}{n}</math>.

== Notes et références ==

<references />

=== Sources ===

* Danièle Beauquier, Jean Berstel, Philippe Chrétienne : ''Éléments d’algorithmique''. Masson, 1992. {{ISBN|2-225-82704-4}} Voir en particulier le chapitre 6 sur les « arbres et ensembles ordonnés ».
* {{en}} [[Donald Knuth]] : ''{{Lang|en|The Art of Computer Programming}}'', volume 3 : « ''{{Lang|en|Sorting and Searching}}'' », {{3e|édition}}. [[Addison-Wesley]], 1997. {{ISBN|0-201-89685-0}} Voir en particulier les pages 458 à 475 de la section 6.2.3 : « ''{{Lang|en|Balanced Trees}}'' », expression qui désigne les arbres AVL chez Knuth.

== Voir aussi ==
=== Articles connexes ===

* [[Rotation d'un arbre binaire de recherche]]
* [[Arbre splay]]
* [[Arbre bicolore]]
* [[Arbre B]]

{{Palette|Arbres informatiques|Structure de données}}

{{portail|informatique théorique}}

[[Catégorie:Arbre (structure de données)|AVL]]