Nous avons vu que la recherche d'un élément dans un arbre binaire de recherche implique de partir de la racine et de descendre dans l'arbre, potentiellement jusqu'à une feuille. Le coût d'une telle opération est donc limité par la hauteur de l'arbre.

En conséquence, il est souhaitable de privilégier parmi les formes possibles d'un tel arbre celles qui ont la plus petite hauteur. Le minimum théorique est facile à calculer : un arbre de hauteur h peut accueillir au plus 2^h éléments.

Malheureusement, exiger qu'un arbre binaire de recherche ait toujours la plus petite hauteur possible est très coûteux : chaque insertion ou suppression peux nécessiter de vastes restructurations. Il a donc fallu inventer des compromis qui permettent de préserver de bonnes performances en recherche sans trop dégrader les autres opérations.

Une des clés pour minimiser la hauteur d'un arbre est l'équilibre : pour un nœud donné, si un sous-arbre est plus haut que l'autre, c'est que l'on pourrait probablement faire mieux en répartissant différemment les nœuds.

On nomme équilibre d'un nœud la différence entre la hauteur de son sous-arbre droit et de son sous-arbre gauche. Dans un arbre AVL (nommé d'après ses inventeurs Georgii Adelson-Velsky et Evguenii Landis), tous les nœuds doivent avoir un équilibre compris entre -1 et 1.

Pour faciliter le maintien de cette propriété, dans chaque nœud on va stocker la hauteur de son sous-arbre. Il est possible de ne stocker que l'équilibre (qui prend moins de place), mais c'est plus difficile à gérer donc nous ne le ferons pas.

Pour insérer un nouvel élément, on procède comme avec un arbre binaire de recherche quelconque, en descendant l'arbre jusqu'à trouver la position idéale d'insertion. Une fois le nouveau nœud ajouté, on suit le chemin inverse jusqu'à la racine en mettant à jour les hauteurs des ancêtres du nouveau nœud.

Il arrivera parfois que la nouvelle hauteur ainsi obtenue déséquilibre l'arbre. Pour rétablir l'équilibre, il faut procéder à une ou deux rotations. Partons du principe qu'un ancêtre est déséquilibré, et que le nouveau nœud est dans son sous-arbre gauche (s'il est dans le sous-arbre droit, on appliquera la même technique en miroir).

Le fils gauche de cet ancêtre est important également. Examinons en premier quoi faire si le nouveau nœud est dans le sous-arbre gauche du fils gauche :

Une simple rotation droite appliquée directement à l'ancêtre rétablit son équilibre. Si au contraire le nouveau nœud est dans le sous-arbre droit du fils gauche, il faut faire deux rotations pour revenir à une situation correcte :

Remarque Le résultat d'un tel rééquilibrage est dans tous les cas un sous-arbre de la même hauteur qu'avant l'insertion, donc tous les nœuds au dessus de ce sous-arbre n'auront pas besoin d'être rééquilibrés.

Là aussi, on part de la technique employée normalement pour les arbres binaires de recherche. La suppression peut causer une diminution de la hauteur de certains sous-arbres, et donc parfois un déséquilibre. Comme précédemment, on va remonter du point de suppression jusqu'à la racine en mettant à jour les hauteurs, et en cas de déséquilibre, une modification locale viendra rétablir la situation.

La différence est que si un ancêtre est déséquilibré, nous n'allons pas modifier le sous-arbre où a eu lieu la suppression car elle est déjà plus courte. Nous regarderons plutôt le sous-arbre le plus haut, et exactement comme dans l'insertion nous changerons de méthode suivant comment ce sous-arbre est lui-même équilibré.

Vous pouvez utiliser les mêmes diagrammes que pour l'insertion afin de décider quelles modifications apporter. Néanmoins la hauteur du sous-arbre rééquilibré ne sera pas nécessairement identique à la hauteur du sous-arbre avant suppression, donc nous devrons potentiellement répéter cette opération plusieurs fois.