Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 44

Arbres AVL : Principe, équilibre et rotations

Recommended resources

Bonjour,

Dans notre leçon précédente, nous avons identifié la faiblesse principale des arbres binaires de recherche (ABR) : leur performance, en , n'est pas garantie et peut se dégrader en dans les pires cas. Nous avons introduit le principe des arbres auto-équilibrants comme solution et présenté l'arbre AVL, qui garantit une hauteur logarithmique en maintenant une condition d'équilibre stricte : le facteur d'équilibre de chaque nœud doit rester dans .

Aujourd'hui, nous passons du "pourquoi" au "comment". L'objectif est de maîtriser le mécanisme au cœur des arbres AVL : les rotations. Nous allons analyser les quatre types de déséquilibre qui peuvent survenir après une insertion et apprendre à effectuer les rotations simples et doubles nécessaires pour restaurer l'équilibre de l'arbre. La maîtrise de ces transformations est une compétence fondamentale, souvent évaluée pour sa rigueur algorithmique.

1. Les Quatre Cas de Déséquilibre

Une insertion dans un arbre AVL peut provoquer un déséquilibre. Cela se produit lorsqu'un nœud, sur le chemin de l'insertion, voit son facteur d'équilibre passer à +2 ou -2. Le type de rotation nécessaire dépend de la "forme" du chemin qui a conduit au déséquilibre. En partant du premier nœud déséquilibré (en remontant depuis la feuille insérée), on identifie quatre cas :

  1. Gauche-Gauche (GG ou LL en anglais) : Un déséquilibre de +2 est causé par une insertion dans le sous-arbre gauche du fils gauche.
  2. Droite-Droite (DD ou RR en anglais) : Un déséquilibre de -2 est causé par une insertion dans le sous-arbre droit du fils droit.
  3. Gauche-Droite (GD ou LR en anglais) : Un déséquilibre de +2 est causé par une insertion dans le sous-arbre droit du fils gauche.
  4. Droite-Gauche (DG ou RL en anglais) : Un déséquilibre de -2 est causé par une insertion dans le sous-arbre gauche du fils droit.

Les deux premiers cas (GG, DD) sont dits "externes" et se corrigent par une rotation simple. Les deux derniers (GD, DG) sont "internes" et nécessitent une double rotation.

2. Les Rotations Simples

Une rotation simple est une opération en qui réorganise deux nœuds pour corriger un déséquilibre externe, tout en préservant la propriété d'ABR.

Cas 1 : Déséquilibre Gauche-Gauche (GG) et Rotation Droite

Si l'arbre est trop "lourd" à gauche (facteur d'équilibre de +2), on effectue une rotation droite.

Soit x le nœud déséquilibré et y son fils gauche. La rotation droite fait "monter" y à la place de x, et x "descend" pour devenir le fils droit de y. Le sous-arbre droit de y (qui contient des valeurs entre y et x) devient le nouveau sous-arbre gauche de x.

La vidéo suivante illustre parfaitement ce mécanisme.

10.1 AVL Tree - Insertion and Rotations

La chaîne Abdul Bari, que nous avons déjà utilisée, offre une des explications les plus claires des rotations AVL. Cette première section se concentre sur la rotation droite (appelée "LL rotation" dans la vidéo).

Regardez la section de 17:31 à 20:17. Observez comment l'insertion de 10 dans l'arbre {30, 20} crée un déséquilibre Gauche-Gauche au nœud 30, et comment la rotation simple fait pivoter l'arbre autour de l'arête {30, 20} pour restaurer l'équilibre.

Cas 2 : Déséquilibre Droite-Droite (DD) et Rotation Gauche

Ce cas est le miroir parfait du précédent. Si l'arbre est trop lourd à droite (facteur d'équilibre de -2), on effectue une rotation gauche.

Soit x le nœud déséquilibré et y son fils droit. La rotation gauche fait monter y et descendre x comme fils gauche de y. Le sous-arbre gauche de y devient le nouveau sous-arbre droit de x.

10.1 AVL Tree - Insertion and Rotations

Continuons avec la même vidéo pour visualiser la rotation gauche, qui est la symétrique de la rotation droite.

Regardez la section de 22:51 à 23:50. C'est l'illustration du déséquilibre Droite-Droite ("RR imbalance") et de sa résolution par une rotation gauche.

Ces deux rotations simples sont les briques de base du rééquilibrage.

3. Les Rotations Doubles

Lorsqu'un déséquilibre est "interne" (Gauche-Droite ou Droite-Gauche), une rotation simple ne suffit pas. Elle ne ferait que transformer le déséquilibre en son symétrique. La solution est la double rotation, qui se décompose en deux rotations simples successives.

Cas 3 : Déséquilibre Gauche-Droite (GD)

Ce déséquilibre (+2) est causé par une insertion dans le sous-arbre droit du fils gauche. Pour le corriger :

  1. On effectue une rotation gauche sur le fils gauche du nœud déséquilibré. Cela transforme le cas GD en un cas GG.
  2. On effectue une rotation droite sur le nœud déséquilibré lui-même.

10.1 AVL Tree - Insertion and Rotations

La vidéo suivante décompose la double rotation GD ("LR rotation").

Regardez la section de 20:17 à 22:51. L'auteur montre d'abord les deux étapes successives, puis la transformation directe qui en résulte. L'essentiel est de comprendre que l'on ramène le problème à un cas connu (GG).

Cas 4 : Déséquilibre Droite-Gauche (DG)

Ce cas est le miroir du GD. Un déséquilibre de -2 est causé par une insertion dans le sous-arbre gauche du fils droit. Pour le corriger :

  1. On effectue une rotation droite sur le fils droit du nœud déséquilibré. Cela transforme le cas DG en un cas DD.
  2. On effectue une rotation gauche sur le nœud déséquilibré.

10.1 AVL Tree - Insertion and Rotations

Enfin, visualisons la double rotation DG ("RL rotation").

Regardez la section de 23:50 à 24:59. C'est la procédure symétrique du cas précédent. Observez comment la rotation droite interne prépare le terrain pour la rotation gauche finale.

L'image ci-dessous illustre bien la composition de ces deux doubles rotations.

AVL Tree Double Rotations (LR and RL)
Cette image décompose la rotation GD (LR) et la rotation DG (RL) en deux étapes successives de rotations simples. C'est une excellente aide visuelle pour comprendre la mécanique interne des doubles rotations.

4. Synthèse et Application

Pour une vision d'ensemble, il est utile de mémoriser les quatre schémas de transformation. L'image suivante résume parfaitement l'état avant et après chaque type de rotation.

AVL Tree Rotations
Cette image est un memento crucial. Elle montre pour chaque cas (GG, GD, DD, DG) la configuration des trois nœuds critiques (z, y, x) et des quatre sous-arbres (T1 à T4) avant et après le rééquilibrage. On voit clairement comment les sous-arbres sont ré-attachés pour préserver la propriété d'ABR.

Appliquons ces règles à un exemple. Prenons l'exercice 2 du document de CMU (LINK). On insère la séquence : 1, 10, 5, 7, 3...

  1. Insérer 1 : (1)

    • Arbre : 1
    • Facteurs d'équilibre : BF(1)=0. L'arbre est équilibré.

  2. Insérer 10 : (1) -> (10) (fils droit)

    • Arbre : 
        1
   \
    10
    • Facteurs d'équilibre : BF(10)=0, BF(1)=-1. L'arbre est équilibré.

  3. Insérer 5 : (1) -> (10) -> (5) (fils gauche de 10)

    • Arbre : 
        1
   \
    10
   /
  5
    • Calculons les facteurs d'équilibre en remontant depuis l'insertion :
      • BF(5) = 0
      • BF(10) = hauteur(5) - hauteur(null) = 0 - (-1) = 1
      • BF(1) = hauteur(null) - hauteur(10) = -1 - 1 = -2
    • Déséquilibre ! Le nœud 1 a un facteur de -2. L'insertion a eu lieu dans le sous-arbre gauche (5) du fils droit (10). C'est un cas Droite-Gauche (DG).
    • Action : Double rotation (DG).
      1. Rotation droite sur le fils droit (10). 
          1
   \
    5
     \
      10
      2. Rotation gauche sur le nœud déséquilibré (1). 
          5
 / \
1   10
    • Le nouvel arbre est équilibré. Tous les facteurs d'équilibre sont à 0.

Pour vous entraîner sur un exemple complet, je vous recommande vivement de suivre la construction pas à pas proposée dans la vidéo suivante.

10.1 AVL Tree - Insertion and Rotations

Cette section de la vidéo d'Abdul Bari met en pratique tous les concepts que nous venons de voir. Il construit un arbre AVL complet en insérant une série de clés et en effectuant les rotations appropriées à chaque étape.

Regardez la section de 32:26 à 42:32. Prenez une feuille de papier et essayez de faire l'exercice en même temps. Pour chaque insertion, calculez les facteurs d'équilibre, identifiez le type de déséquilibre s'il y en a un, et prédisez la rotation à effectuer avant de regarder la solution.

Conclusion

Cette leçon constitue le cœur technique des arbres AVL. La maîtrise de ces mécanismes de rééquilibrage est essentielle.

Points clés à retenir :

  • L'équilibre d'un arbre AVL est restauré par des opérations de rotation dès qu'un nœud atteint un facteur d'équilibre de +2 ou -2.
  • Il existe quatre cas de déséquilibre, déterminés par le chemin de l'insertion : Gauche-Gauche (GG), Droite-Droite (DD), Gauche-Droite (GD), et Droite-Gauche (DG).
  • Les cas "externes" (GG, DD) sont résolus par une rotation simple (respectivement droite et gauche).
  • Les cas "internes" (GD, DG) sont résolus par une double rotation (respectivement GD et DG), qui se compose de deux rotations simples.
  • Chaque rotation est une opération locale en qui préserve la propriété d'ordre de l'ABR tout en réduisant la hauteur locale de l'arbre.

Le fait qu'une seule rotation (simple ou double) suffise à rééquilibrer l'arbre après une insertion garantit que le coût d'insertion reste en .

Prochaine étape :
Nous avons achevé notre étude approfondie des arbres, de la structure de base de l'ABR à la mécanique sophistiquée de l'AVL. Nous allons maintenant aborder une autre structure de données fondamentale en informatique : les graphes. Dans la prochaine leçon, nous définirons formellement ce qu'est un graphe et étudierons ses deux principales représentations en machine : la matrice d'adjacence et les listes d'adjacence.