Arbres binaires de recherche équilibrés AVL

Les arbres AVL, nommés ainsi d'après leurs auteurs : Adelson-Velskii et Landis, sont des arbres binaires équilibrés, c'est à dire qu'en tout noeud, les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1. Pour cela, il est nécessaire d'opérer des ré-équilibrages à l'aide d'opérations de rotation, gauche ou droite, représentées par les schémas ci-dessous :
Rotation droite
Rotation gauche