🔍 Arbres Binaires de Recherche (ABR)

🎯 Définition et Propriétés

🔍 Arbre Binaire de Recherche

Un Arbre Binaire de Recherche (ABR) est un arbre binaire qui respecte la propriété d'ordre :

• Toutes les valeurs du sous-arbre gauche sont inférieures à la racine
• Toutes les valeurs du sous-arbre droit sont supérieures à la racine
• Cette propriété s'applique récursivement à tous les sous-arbres

📊

Propriété d'Ordre

La structure maintient automatiquement un ordre qui permet des recherches efficaces en O(log n).

⚡

Efficacité

Recherche, insertion et suppression en O(log n) dans le cas équilibré, O(n) dans le pire cas.

🔄

Parcours Infixe

Le parcours infixe d'un ABR produit automatiquement les valeurs en ordre croissant.

🔍 Opération de Recherche

🎯 Principe de la Recherche

La recherche exploite la propriété d'ordre pour éliminer la moitié des possibilités à chaque étape, similaire à la recherche dichotomique.

🔍 Recherche dans un ABR

Algorithme récursif qui compare la valeur recherchée avec le nœud courant.

💻 Implémentation Recherche

def rechercher(self, valeur, noeud=None):
    """
    Recherche une valeur dans l'ABR
    Retourne True si trouvée, False sinon
    """
    if noeud is None:
        noeud = self.racine

    # Cas de base : nœud vide
    if noeud is None:
        return False

    # Valeur trouvée
    if valeur == noeud.valeur:
        return True

    # Recherche dans le sous-arbre approprié
    elif valeur < noeud.valeur:
        return self.rechercher(valeur, noeud.gauche)
    else:
        return self.rechercher(valeur, noeud.droite)

📍 Recherche avec Nœud

Version qui retourne le nœud trouvé plutôt qu'un booléen.

💻 Recherche Avancée

def rechercher_noeud(self, valeur, noeud=None):
    """
    Recherche et retourne le nœud contenant la valeur
    Retourne None si non trouvé
    """
    if noeud is None:
        noeud = self.racine

    if noeud is None or noeud.valeur == valeur:
        return noeud

    if valeur < noeud.valeur:
        return self.rechercher_noeud(valeur, noeud.gauche)
    else:
        return self.rechercher_noeud(valeur, noeud.droite)

➕ Opération d'Insertion

📥 Principe de l'Insertion

L'insertion trouve la position correcte en suivant la propriété d'ordre, puis ajoute le nouveau nœud comme feuille.

➕ Insertion dans un ABR

Algorithme récursif qui maintient la propriété d'ordre lors de l'ajout.

💻 Implémentation Insertion

def inserer(self, valeur, noeud=None):
    """
    Insère une valeur dans l'ABR en maintenant la propriété d'ordre
    Retourne la racine du sous-arbre modifié
    """
    # Premier appel : initialiser avec la racine
    if noeud is None and self.racine is not None:
        self.racine = self._inserer_recursif(valeur, self.racine)
        return

    # Arbre vide : créer la racine
    if self.racine is None:
        self.racine = NoeudBinaire(valeur)
        return

    self.racine = self._inserer_recursif(valeur, self.racine)

def _inserer_recursif(self, valeur, noeud):
    """
    Méthode auxiliaire récursive pour l'insertion
    """
    # Cas de base : position trouvée
    if noeud is None:
        return NoeudBinaire(valeur)

    # Insertion selon la propriété d'ordre
    if valeur < noeud.valeur:
        noeud.gauche = self._inserer_recursif(valeur, noeud.gauche)
    elif valeur > noeud.valeur:
        noeud.droite = self._inserer_recursif(valeur, noeud.droite)
    # Si valeur == noeud.valeur, on ne fait rien (pas de doublons)

    return noeud

🏗️ Exemple d'Insertion

Construction progressive d'un ABR par insertions successives.

💻 Construction d'ABR

# Création et construction d'un ABR
abr = ArbreBinaireRecherche()

# Insertions successives
valeurs = [50, 30, 70, 20, 40, 60, 80]
for valeur in valeurs:
    abr.inserer(valeur)

# Résultat :
#       50
#      /  \
#     30   70
#    / \   / \
#   20 40 60 80

print("ABR construit avec succès")
print("Parcours infixe :", abr.parcours_infixe())  # [20, 30, 40, 50, 60, 70, 80]

➖ Opération de Suppression

🗑️ Principe de la Suppression

La suppression est l'opération la plus complexe car elle doit maintenir la propriété d'ordre après avoir retiré un nœud. Trois cas distincts existent selon le nombre d'enfants du nœud à supprimer.

1️⃣

Cas 1 : Feuille

Nœud sans enfants
Suppression directe - le plus simple des trois cas.

2️⃣

Cas 2 : Un Enfant

Nœud avec un seul enfant
Remplacer le nœud par son unique enfant.

3️⃣

Cas 3 : Deux Enfants

Nœud avec deux enfants
Remplacer par le successeur (ou prédécesseur) dans l'ordre infixe.

🗑️ Suppression Complète

Implémentation gérant les trois cas de suppression.

💻 Implémentation Suppression

def supprimer(self, valeur):
    """
    Supprime une valeur de l'ABR
    """
    self.racine = self._supprimer_recursif(valeur, self.racine)

def _supprimer_recursif(self, valeur, noeud):
    """
    Méthode auxiliaire récursive pour la suppression
    """
    # Cas de base : valeur non trouvée
    if noeud is None:
        return noeud

    # Recherche du nœud à supprimer
    if valeur < noeud.valeur:
        noeud.gauche = self._supprimer_recursif(valeur, noeud.gauche)
    elif valeur > noeud.valeur:
        noeud.droite = self._supprimer_recursif(valeur, noeud.droite)
    else:
        # Nœud trouvé - traiter les 3 cas

        # Cas 1 : Nœud feuille (aucun enfant)
        if noeud.gauche is None and noeud.droite is None:
            return None

        # Cas 2a : Seulement enfant droit
        elif noeud.gauche is None:
            return noeud.droite

        # Cas 2b : Seulement enfant gauche
        elif noeud.droite is None:
            return noeud.gauche

        # Cas 3 : Deux enfants
        else:
            # Trouver le successeur (minimum du sous-arbre droit)
            successeur = self._trouver_minimum(noeud.droite)

            # Remplacer la valeur du nœud par celle du successeur
            noeud.valeur = successeur.valeur

            # Supprimer le successeur
            noeud.droite = self._supprimer_recursif(successeur.valeur, noeud.droite)

    return noeud

def _trouver_minimum(self, noeud):
    """
    Trouve le nœud avec la valeur minimale dans un sous-arbre
    """
    while noeud.gauche is not None:
        noeud = noeud.gauche
    return noeud

📝 Exemple de Suppression

Démonstration des différents cas de suppression.

💻 Test de Suppression

# ABR initial : [20, 30, 40, 50, 60, 70, 80]
#       50
#      /  \
#     30   70
#    / \   / \
#   20 40 60 80

# Cas 1 : Supprimer une feuille (20)
abr.supprimer(20)
print("Après suppression de 20 :", abr.parcours_infixe())  # [30, 40, 50, 60, 70, 80]

# Cas 2 : Supprimer un nœud avec un enfant (30)
abr.supprimer(30)
print("Après suppression de 30 :", abr.parcours_infixe())  # [40, 50, 60, 70, 80]

# Cas 3 : Supprimer un nœud avec deux enfants (50 - racine)
abr.supprimer(50)
print("Après suppression de 50 :", abr.parcours_infixe())  # [40, 60, 70, 80]

📊 Analyse de Complexité

⚡ Complexités des Opérations ABR

Opération	Cas Moyen	Pire Cas	Remarques
Recherche	O(log n)	O(n)	Arbre équilibré vs dégénéré
Insertion	O(log n)	O(n)	Dépend de l'ordre d'insertion
Suppression	O(log n)	O(n)	Cas 3 le plus complexe
Parcours	O(n)	O(n)	Visite tous les nœuds

⚡ Avantage clé : Un ABR équilibré offre des opérations en O(log n), soit une efficacité comparable à la recherche dichotomique sur un tableau trié, mais avec l'avantage d'insertions et suppressions dynamiques efficaces.

🎯 Points Clés à Retenir

📊

Propriété Fondamentale

La propriété d'ordre (gauche < racine < droite) est la clé de l'efficacité des ABR et doit être maintenue à tout moment.

⚡

Performance Optimale

Les ABR équilibrés offrent O(log n) pour les opérations principales, mais peuvent dégénérer en O(n) si mal construits.

🔄

Tri Automatique

Le parcours infixe d'un ABR produit automatiquement les valeurs en ordre croissant, offrant un tri efficace.

🗑️

Suppression Complexe

La suppression nécessite une attention particulière aux trois cas possibles pour maintenir la structure et les propriétés de l'ABR.