Implémentation d'un ABR : Insertion et Recherche

1. Définition de l'Arbre Binaire de Recherche (ABR)

Un ABR est un arbre binaire qui satisfait une contrainte d'ordre stricte, appelée "propriété de l'arbre binaire de recherche".

Pour une étude formelle de cette définition, je vous invite à lire la section suivante.

En résumé, pour n'importe quel nœud n de l'arbre possédant une clé k :

• Toutes les clés dans le sous-arbre gauche de n doivent être inférieures à k.
• Toutes les clés dans le sous-arbre droit de n doivent être supérieures à k.
• Les deux sous-arbres, gauche et droit, doivent également être des arbres binaires de recherche.
• Par convention, nous interdirons les clés dupliquées.

Cette propriété est la clé de toute l'efficacité de la structure.

2. La recherche dans un ABR

Comment la propriété de l'ABR nous aide-t-elle à trouver une valeur v ? L'algorithme est une application directe du principe "diviser pour régner" :

1. On commence à la racine de l'arbre.
2. On compare v avec la clé du nœud courant, k :
   • Si v == k, la valeur est trouvée.
   • Si v < k, la recherche continue récursivement dans le sous-arbre gauche.
   • Si v > k, la recherche continue récursivement dans le sous-arbre droit.
3. Si on atteint un sous-arbre vide (None), cela signifie que v n'est pas dans l'arbre.

La vidéo suivante illustre ce processus et analyse sa complexité.

Comme vous l'avez vu, la complexité de la recherche est proportionnelle à la hauteur h de l'arbre, soit $O(h)$. Dans un arbre raisonnablement équilibré, la hauteur est de l'ordre de $\log (n)$, où n est le nombre de nœuds. La recherche est donc très rapide. Cependant, dans un cas dégénéré (un arbre filiforme), la hauteur peut être n, et la complexité redevient linéaire, $O(n)$.

Implémentation en Python

Voici à quoi ressemble une implémentation récursive de la recherche. Elle est une traduction directe de l'algorithme.

class Noeud:
    def __init__(self, cle):
        self.cle = cle
        self.gauche = None
        self.droit = None

def rechercher(racine, cle_recherchee):



    # Cas de base : l'arbre est vide ou la clé est trouvée
    if racine is None or racine.cle == cle_recherchee:
        return racine
    



    # La clé recherchée est plus petite, on cherche à gauche
    if cle_recherchee < racine.cle:
        return rechercher(racine.gauche, cle_recherchee)
    



    # La clé recherchée est plus grande, on cherche à droite
    else: # cle_recherchee > racine.cle
        return rechercher(racine.droit, cle_recherchee)

Cette fonction retourne le Noeud s'il est trouvé, et None sinon.

3. L'insertion dans un ABR

L'insertion d'une nouvelle clé v doit préserver la propriété de l'ABR. L'algorithme est très similaire à celui de la recherche :

1. On cherche la position où v devrait se trouver si elle existait dans l'arbre.
2. Cette recherche nous mènera inévitablement à un lien None (un sous-arbre vide).
3. On crée un nouveau nœud avec la clé v et on l'attache à ce lien.

L'image suivante illustre ce processus pour l'insertion de la valeur 12.

Implémentation récursive en Python

L'implémentation récursive de l'insertion est élégante, mais comporte une subtilité importante concernant la mise à jour des pointeurs. La vidéo suivante l'explique remarquablement bien.

En nous basant sur cette explication, voici une fonction d'insertion propre.

def inserer(racine, cle_a_inserer):



    # Cas de base : si l'arbre est vide, on retourne un nouveau noeud
    if racine is None:
        return Noeud(cle_a_inserer)
    



    # Si la clé existe déjà, on ne fait rien
    if cle_a_inserer == racine.cle:
        return racine




    # La clé à insérer est plus petite, on insère dans le sous-arbre gauche
    if cle_a_inserer < racine.cle:
        racine.gauche = inserer(racine.gauche, cle_a_inserer)
    



    # La clé à insérer est plus grande, on insère dans le sous-arbre droit
    else: # cle_a_inserer > racine.cle
        racine.droit = inserer(racine.droit, cle_a_inserer)
        
    return racine

Notez que la fonction inserer retourne toujours la racine du sous-arbre (modifié ou non). C'est cette valeur de retour qui permet au parent de "raccrocher" le sous-arbre mis à jour.

4. Perspective fonctionnelle en OCaml

Votre préparation à l'Agrégation exige une maîtrise de la programmation fonctionnelle. L'implémentation d'un ABR en OCaml est un excellent exercice qui met en lumière des concepts clés comme l'immutabilité et le pattern matching.

Contrairement à l'approche impérative en Python où nous modifions l'arbre en place, l'approche fonctionnelle consiste à créer un nouvel arbre qui inclut la valeur insérée, tout en réutilisant les parties non modifiées de l'arbre original pour des raisons d'efficacité.

La fonction insert en OCaml illustre un principe fondamental :
let rec insert x bst = match bst with ...
Cette fonction ne dit pas "modifie bst", mais "laisse insert x bst être un nouvel arbre construit à partir de bst et x". Cette distinction est au cœur du paradigme fonctionnel.

5. Exercice d'application

Pour consolider votre compréhension, mettons en pratique ces algorithmes.

1. Créez une classe ABR en Python qui encapsulera la racine de votre arbre.
2. Implémentez les méthodes inserer(self, cle) et rechercher(self, cle) au sein de cette classe. Ces méthodes appelleront les fonctions récursives que nous avons définies, en utilisant la racine de l'arbre (self.racine).
3. Instanciez un ABR vide.
4. Insérez-y les clés suivantes, dans cet ordre : [50, 30, 70, 20, 40, 60, 80].
5. Dessinez l'arbre final sur papier.
6. Vérifiez avec votre méthode rechercher que la clé 40 est présente et que la clé 90 est absente.

class ABR:
    def __init__(self):
        self.racine = None

    def inserer(self, cle):
        self.racine = self._inserer_recursif(self.racine, cle)

    def _inserer_recursif(self, racine_actuelle, cle_a_inserer):



        # Reprendre le code de la fonction 'inserer' vue plus haut
        if racine_actuelle is None:
            return Noeud(cle_a_inserer)
        if cle_a_inserer < racine_actuelle.cle:
            racine_actuelle.gauche = self._inserer_recursif(racine_actuelle.gauche, cle_a_inserer)
        elif cle_a_inserer > racine_actuelle.cle:
            racine_actuelle.droit = self._inserer_recursif(racine_actuelle.droit, cle_a_inserer)
        return racine_actuelle

    def rechercher(self, cle):
        return self._rechercher_recursif(self.racine, cle) is not None

    def _rechercher_recursif(self, racine_actuelle, cle_recherchee):



        # Reprendre le code de la fonction 'rechercher' vue plus haut
        if racine_actuelle is None or racine_actuelle.cle == cle_recherchee:
            return racine_actuelle
        if cle_recherchee < racine_actuelle.cle:
            return self._rechercher_recursif(racine_actuelle.gauche, cle_recherchee)
        else:
            return self._rechercher_recursif(racine_actuelle.droit, cle_recherchee)

      50
     /  \
    30    70
   / \   / \
  20  40 60  80

Conclusion

Aujourd'hui, nous avons fait un pas décisif en ajoutant une contrainte d'ordre à la structure d'arbre binaire pour créer l'ABR.

Points clés à retenir :

• La propriété de l'ABR (gauche < racine < droit) est la règle qui gouverne toute la structure.
• Les opérations de recherche et d'insertion suivent un chemin logique le long de l'arbre, exploitant cette propriété pour une complexité moyenne en $O(\log n)$.
• La performance de l'ABR dépend crucialement de sa hauteur. Un arbre déséquilibré peut entraîner des performances linéaires en $O(n)$, ce qui annule son avantage.
• L'implémentation peut être impérative (modification en place, comme en Python) ou fonctionnelle (création de nouvelles structures, comme en OCaml), deux paradigmes que vous devez maîtriser.

Prochaine étape :
Nous avons entrevu que l'efficacité de l'ABR est liée à son "équilibre". Mais que se passe-t-il si on insère les clés dans l'ordre [20, 30, 40, 50, 60, 70, 80] ? L'arbre devient une longue chaîne. Dans la prochaine leçon, nous analyserons formellement la complexité des opérations sur un ABR dans le meilleur et le pire des cas, ce qui nous motivera à étudier, plus tard, les arbres auto-équilibrants.