Qu'est-ce qu'un arbre AVL ?

Chaque nœud d'un arbre AVL suit sa propre hauteur : le nombre d'arêtes sur le chemin le plus long vers une feuille. Une feuille a une hauteur de 1, et un sous-arbre vide compte comme une hauteur de 0. À partir de la hauteur des deux enfants d'un nœud, vous pouvez calculer son facteur d'équilibre : height(left) - height(right).

Un nœud est équilibré lorsque son facteur d'équilibre est -1, 0 ou 1. La règle de l'arbre AVL est simple : chaque nœud doit rester équilibré, tout le temps. Chaque fois qu'une insertion ou une suppression pousse le facteur d'équilibre d'un nœud à 2 ou -2, l'arbre effectue une rotation : un réarrangement local de quelques pointeurs qui rétablit l'équilibre en temps constant sans rompre l'ordre de l'arbre de recherche.

Il existe quatre cas de rotation (gauche-gauche, droite-droite, gauche-droite, droite-gauche), mais ils se résument tous à deux blocs de construction : une rotation simple à gauche et une rotation simple à droite. Vous construirez les deux à partir de zéro dans les prochaines leçons.