AVL Tree est un arbre de recherche binaire équilibré. Le message présentait des arbres de recherche binaires. Les temps de recherche, d'insertion et de suppression d'un arbre binaire dépendent de la hauteur de l'arbre. Dans le pire des cas, la hauteur est O(n). Si un arbre est parfaitement équilibré – c'est-à-dire un arbre binaire complet – sa hauteur est log n. Peut-on maintenir un arbre parfaitement équilibré ? Oui, mais cela coûtera cher. Le compromis consiste à maintenir un arbre bien équilibré, c'est-à-dire que les hauteurs des deux sous-arbres de chaque nœud sont à peu près les mêmes.

Les arbres AVL sont bien équilibrés. Les arbres AVL ont été inventés en 1962 par deux informaticiens russes, G. M. Adelson-Velsky et E. M. Landis (d'où le nom AVL). Dans un arbre AVL, la différence entre les hauteurs des deux sous-arbres de chaque nœud est 0 ou 1. On peut montrer que la hauteur maximale d'un arbre AVL est O(log n).

Le processus d'insertion ou de suppression d'un élément dans une arborescence AVL est le même que dans une arborescence de recherche binaire classique, sauf que vous devrez peut-être rééquilibrer l'arborescence après une opération d'insertion ou de suppression. Le facteur d'équilibre d'un nœud est la hauteur de son sous-arbre droit moins la hauteur de son sous-arbre gauche. Un nœud est dit équilibré si son facteur d'équilibre est -1, 0 ou 1. Un nœud est considéré comme lourd à gauche si son facteur d'équilibre est -1, et lourd à droite si son facteur d'équilibre est 1.