Insertion et recherche dans un ABR

Chercher : suivre le bon chemin

Rechercher une valeur dans un ABR consiste à descendre depuis la racine, en choisissant à chaque noeud d'aller à gauche (si la valeur cherchée est plus petite) ou à droite (si elle est plus grande), jusqu'à trouver la valeur ou tomber sur un sous-arbre vide.

Schéma : recherche de 7

                   (8)
                  /   \
               (3)     10
               / \        \
              1  (6)       14
                 / \       /
                4  (7)   13

chemin suivi : 8 -> 3 -> 6 -> 7
   7 < 8  : on va a gauche
   7 > 3  : on va a droite
   7 > 6  : on va a droite
   7 = 7  : trouve !

Insérer : même logique, jusqu'à une place vide

Insérer une valeur suit exactement le même chemin que la recherche, mais quand on arrive sur un sous-arbre vide, on y crée le nouveau noeud.

Schéma : insertion de 5

descente :
   5 < 8  : on va a gauche       (noeud 8)
   5 > 3  : on va a droite       (noeud 3)
   5 < 6  : on va a gauche       (noeud 6)
   5 > 4  : sous-arbre droit vide, on insere ici (noeud 4)

apres insertion :
                    8
                  /   \
                 3     10
                / \       \
               1   6        14
                  / \      /
                 4   7    13
                  \
                   5

Implémentation en Python

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

def inserer(noeud, valeur):
    if noeud is None:
        return Noeud(valeur)
    if valeur < noeud.valeur:
        noeud.gauche = inserer(noeud.gauche, valeur)
    else:
        noeud.droit = inserer(noeud.droit, valeur)
    return noeud

def rechercher(noeud, valeur):
    if noeud is None:
        return False
    if valeur == noeud.valeur:
        return True
    if valeur < noeud.valeur:
        return rechercher(noeud.gauche, valeur)
    return rechercher(noeud.droit, valeur)

Piège classique

Oublier de réaffecter le résultat de l'appel récursif (noeud.gauche = inserer(...)) est une erreur très fréquente : sans cette réaffectation, le nouveau noeud est bien créé, mais jamais réellement rattaché à l'arbre existant.