🌲 AVL Trees : Arbres Binaires de Recherche Équilibrés

Les AVL Trees sont des arbres binaires de recherche qui maintiennent un équilibre pour garantir des opérations efficaces de recherche, d'insertion et de suppression en O(log n).

📚 Qu'est-ce qu'un AVL Tree ?

Un AVL Tree est un arbre binaire de recherche qui s'auto-équilibre. La différence de hauteur entre les sous-arbres gauche et droit de chaque nœud ne dépasse jamais 1.

Illustration d'un AVL Tree

🔄 Types de Rotations

Les rotations sont utilisées pour rééquilibrer l'arbre :

  • Rotation Droite : Pour corriger un déséquilibre à gauche.
  • Rotation Gauche : Pour corriger un déséquilibre à droite.
  • Double Rotation Gauche-Droite : Déséquilibre gauche-droit.
  • Double Rotation Droite-Gauche : Déséquilibre droite-gauche.

🛠️ Opérations sur un AVL Tree

Les principales opérations sont :

  • Insertion : Ajout d'un nouvel élément suivi d'un rééquilibrage si nécessaire.
  • Suppression : Suppression d'un élément suivi d'un rééquilibrage.
  • Recherche : Similaire à celle dans un BST classique.

💻 Implémentation en Python

class Node:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None
        self.hauteur = 1

class AVLTree:
    def get_height(self, noeud):
        if not noeud:
            return 0
        return noeud.hauteur

    def get_balance(self, noeud):
        if not noeud:
            return 0
        return self.get_height(noeud.gauche) - self.get_height(noeud.droite)

    def rotate_right(self, y):
        x = y.gauche
        T2 = x.droite
        x.droite = y
        y.gauche = T2
        y.hauteur = 1 + max(self.get_height(y.gauche), self.get_height(y.droite))
        x.hauteur = 1 + max(self.get_height(x.gauche), self.get_height(x.droite))
        return x

    def rotate_left(self, x):
        y = x.droite
        T2 = y.gauche
        y.gauche = x
        x.droite = T2
        x.hauteur = 1 + max(self.get_height(x.gauche), self.get_height(x.droite))
        y.hauteur = 1 + max(self.get_height(y.gauche), self.get_height(y.droite))
        return y

    def insert(self, noeud, valeur):
        if not noeud:
            return Node(valeur)
        elif valeur < noeud.valeur:
            noeud.gauche = self.insert(noeud.gauche, valeur)
        else:
            noeud.droite = self.insert(noeud.droite, valeur)

        noeud.hauteur = 1 + max(self.get_height(noeud.gauche), self.get_height(noeud.droite))
        balance = self.get_balance(noeud)

        # Rotation Droite
        if balance > 1 and valeur < noeud.gauche.valeur:
            return self.rotate_right(noeud)

        # Rotation Gauche
        if balance < -1 and valeur > noeud.droite.valeur:
            return self.rotate_left(noeud)

        # Rotation Gauche-Droite
        if balance > 1 and valeur > noeud.gauche.valeur:
            noeud.gauche = self.rotate_left(noeud.gauche)
            return self.rotate_right(noeud)

        # Rotation Droite-Gauche
        if balance < -1 and valeur < noeud.droite.valeur:
            noeud.droite = self.rotate_right(noeud.droite)
            return self.rotate_left(noeud)

        return noeud

# Exemple d'utilisation
avl_tree = AVLTree()
racine = None
valeurs = [10, 20, 30, 40, 50, 25]
for valeur in valeurs:
    racine = avl_tree.insert(racine, valeur)

Explication du Code :

  • get_height : Retourne la hauteur d'un nœud.
  • get_balance : Calcule le facteur d'équilibre d'un nœud.
  • rotate_left et rotate_right : Effectuent les rotations nécessaires.
  • insert : Insère un nouvel élément et rééquilibre l'arbre.

🎉 Conclusion

Les AVL Trees sont essentiels pour garantir des performances optimales dans les opérations sur les arbres binaires de recherche. Ils maintiennent l'arbre équilibré, assurant ainsi une complexité en O(log n) pour les opérations principales.

💪 Exercices

Testez vos connaissances avec ces exercices :

# Exercices :

# 1. Implémentez la fonction de suppression dans l'AVL Tree en maintenant l'équilibre de l'arbre.

# 2. Écrivez une fonction pour afficher l'AVL Tree de manière structurée (par exemple, un parcours en largeur).

# 3. Modifiez l'implémentation pour que l'AVL Tree prenne en charge des données génériques avec une fonction de comparaison personnalisée.

# 4. Comparez les performances de l'AVL Tree avec celles d'un BST non équilibré pour des opérations de recherche, insertion et suppression.

# 5. Implémentez une fonction pour vérifier si un arbre binaire est un AVL Tree valide.