🌳 Arbre AVL — Rotations auto-équilibrantes

Pourquoi le facteur d'équilibre doit-il rester dans {−1, 0, 1} ?

Cette plage est le seuil précis qui garantit une hauteur de l'arbre en O(log n) de manière prouvée. Adelson-Velsky et Landis ont démontré qu'un arbre respectant cet invariant a une hauteur d'au plus environ 1,44·log₂(n+2), donc autoriser des facteurs d'équilibre de ±1 offre assez de flexibilité pour une insertion efficace tout en garantissant une hauteur logarithmique.

Quelle est la différence entre une rotation simple et une rotation double ?

Une rotation simple (cas LL ou RR) corrige un déséquilibre causé par un sous-arbre lourd du même côté que son propre enfant lourd — une seule réécriture de pointeur suffit. Une rotation double (cas LR ou RL) traite un déséquilibre « en zigzag » où l'enfant lourd penche du côté opposé, nécessitant deux rotations : d'abord sur l'enfant pour le convertir en cas de rotation simple, puis sur le nœud lui-même.

Comment un arbre AVL se compare-t-il à un arbre rouge-noir ?

Les deux garantissent une hauteur en O(log n), mais les arbres AVL imposent un invariant d'équilibre plus strict, offrant des arbres plus courts et une recherche plus rapide. Les arbres rouge-noir assouplissent la contrainte d'équilibre (autorisant le chemin racine-feuille le plus long à être jusqu'à deux fois le plus court), ce qui signifie moins de rotations lors de l'insertion et de la suppression. Cela rend les arbres AVL avantageux pour les charges de travail à forte lecture et les arbres rouge-noir avantageux pour les charges de travail à forte écriture.

Pourquoi la suppression peut-elle nécessiter des rotations à chaque niveau jusqu'à la racine, contrairement à l'insertion ?

Une insertion n'ajoute de la hauteur qu'à un seul sous-arbre, donc au plus une rotation (simple ou double) est jamais nécessaire pour restaurer l'équilibre, après quoi la hauteur globale du sous-arbre est ramenée à sa valeur d'avant insertion. Une suppression peut réduire la hauteur d'un sous-arbre, et cette réduction peut se propager vers le haut, déclenchant potentiellement une rotation de rééquilibrage à chaque ancêtre sur le chemin vers la racine — jusqu'à O(log n) rotations dans le pire des cas.