Équilibrage des arbres : arbres AVL

4.1 Problèmes des arbres déséquilibrés

Les arbres ordinaires (déséquilibrés) peuvent rencontrer des effets indésirables lorsqu'on y ajoute des éléments.

1. Augmentation de la hauteur de l'arbre :

Dans les arbres déséquilibrés, la hauteur peut atteindre n (où n est le nombre de nœuds), ce qui entraîne une dégradation des performances.

Le temps d'exécution des opérations principales (recherche, insertion, suppression) dans le pire des cas devient O(n).

2. Répartition inégale des nœuds :

Dans les arbres déséquilibrés, certains sous-arbres peuvent contenir beaucoup plus de nœuds que d'autres, ce qui conduit à une utilisation inefficace de la mémoire et à une augmentation du temps de traitement.

3. Dégradation du temps d'exécution des opérations :

Dans les arbres déséquilibrés, les opérations de recherche, d'insertion et de suppression prennent plus de temps en raison de l'augmentation de la hauteur de l'arbre.

Exemple d'arbre déséquilibré :

Dans cet exemple, l'arbre devient essentiellement une liste chaînée, et le temps d'exécution des opérations devient linéaire.

4.2 Définition de l'arbre AVL et ses propriétés

Un arbre AVL (nommé d'après ses inventeurs, Adelson-Velsky et Landis) est un type d'arbre binaire de recherche équilibré où, pour tout nœud, la différence de hauteur entre ses sous-arbres gauche et droit ne dépasse pas 1.

Propriétés de l'arbre AVL :

1. Équilibrage :

La différence de hauteur entre les sous-arbres gauche et droit de tout nœud ne dépasse pas 1.

Cela garantit une hauteur d'arbre de O(log n), où n est le nombre de nœuds, assurant ainsi l'efficacité des opérations de recherche, d'insertion et de suppression.

2. Arbre binaire de recherche :

L'arbre AVL possède toutes les propriétés d'un arbre binaire de recherche : pour tout nœud, toutes les clés dans le sous-arbre gauche sont inférieures à la clé du nœud, et toutes les clés dans le sous-arbre droit sont supérieures à la clé du nœud.

3. Équilibrage automatique :

Après chaque opération d'insertion ou de suppression, un équilibrage de l'arbre est effectué pour conserver ses propriétés.

4.3 Exemples d'équilibrage des arbres

Les rotations sont des opérations effectuées pour rétablir l'équilibre dans un arbre AVL après l'insertion ou la suppression de nœuds. Il existe quatre types de rotations : gauche, droite, gauche-droite et droite-gauche.

1. Rotation à gauche (Left Rotation) :

Dans une rotation à gauche, le nœud x monte, et son nœud enfant droit y devient son parent. Le sous-arbre gauche de y devient le sous-arbre droit de x.

2. Rotation à droite (Right Rotation) :

Dans une rotation à droite, le nœud x monte, et son nœud enfant gauche y devient son parent. Le sous-arbre droit de y devient le sous-arbre gauche de x.

3. Rotation gauche-droite (Left-Right Rotation) :

On effectue d'abord une rotation à gauche sur le nœud enfant gauche, puis une rotation à droite sur le nœud lui-même.

4. Rotation droite-gauche (Right-Left Rotation) :

On effectue d'abord une rotation à droite sur le nœud enfant droit, puis une rotation à gauche sur le nœud lui-même.

4.4 Opérations principales dans les arbres AVL

Les opérations principales dans les arbres AVL incluent l'insertion, la suppression et la recherche.

Insertion (Insertion)

Il faut insérer un nouveau nœud dans l'arbre AVL et le rééquilibrer si nécessaire.

Étapes :

1. Insertion du nœud :
   • On commence à partir de la racine de l'arbre et on trouve récursivement la bonne place pour le nouveau nœud en comparant sa valeur avec les nœuds actuels.
   • On insère le nouveau nœud à l'endroit trouvé, comme dans un arbre binaire de recherche classique.
2. Mise à jour des hauteurs :
   • Après l'insertion, on met à jour les hauteurs de tous les nœuds sur le chemin du nouveau nœud jusqu'à la racine.
3. Équilibrage de l'arbre :
   • On vérifie l'équilibre de chaque nœud sur le chemin du nouveau nœud jusqu'à la racine.
   • Si l'équilibre de n'importe quel nœud est rompu (la différence de hauteur entre les sous-arbres gauche et droit est supérieure à 1), on effectue la rotation appropriée pour rétablir l'équilibre.

Exemple :

2. Suppression (Deletion)

Il faut supprimer un nœud de l'arbre AVL et le rééquilibrer si nécessaire.

Étapes :

1. Recherche et suppression du nœud :

• On commence à partir de la racine de l'arbre et on trouve récursivement le nœud à supprimer.
• On supprime le nœud comme dans un arbre binaire de recherche classique :
• Si le nœud est une feuille, on le supprime simplement.
• Si le nœud a un enfant, on remplace le nœud par son enfant.
• Si le nœud a deux enfants, on trouve le nœud le plus petit dans le sous-arbre droit (ou le plus grand dans le gauche), on copie sa valeur dans le nœud à supprimer et on supprime récursivement le nœud le plus petit dans le sous-arbre droit.

2. Mise à jour des hauteurs :

• Après la suppression, on met à jour les hauteurs de tous les nœuds sur le chemin du nœud supprimé jusqu'à la racine.

3. Équilibrage de l'arbre :

• On vérifie l'équilibre de chaque nœud sur le chemin du nœud supprimé jusqu'à la racine.
• Si l'équilibre de n'importe quel nœud est rompu, on effectue la rotation appropriée pour rétablir l'équilibre.

Exemple :

3. Recherche (Search)

Il faut trouver un nœud avec une valeur donnée dans l'arbre AVL.

Étapes :

1. Recherche récursive :

• On commence à partir de la racine de l'arbre et on compare récursivement la valeur recherchée avec les nœuds actuels.
• Si la valeur est inférieure au nœud actuel, on passe au sous-arbre gauche.
• Si la valeur est supérieure au nœud actuel, on passe au sous-arbre droit.
• Si la valeur correspond au nœud actuel, on retourne ce nœud.

Exemple :