arbre AVL
En d'autres termes
arbre d'Adelson-Velskii et Landis
Définition
Structure de données en arborescence équilibrée dans laquelle tous les noeuds ont au maximum un niveau d'écart en profondeur dans l'arborescence. Pour maintenir cette propriété, l'arbre est rééquilibré par rotation lors de chaque modification pouvant introduire un écart de profondeur supérieur. La complexité des algorithmes qui en résulte est compensée lors des consultations de l'arbre, puisque l'équilibre permet un accès à chaque noeud en un temps statistiquement minimal.
