04 — Les arbres binaires de recherche

Ce que tu vas apprendre

• L'invariant d'un arbre binaire de recherche
• Insertion, recherche et parcours en ordre
• Pourquoi les opérations sont en O(hauteur)
• Le problème de la dégénérescence en O(n)

Prérequis

• 03 — Listes chaînées

Les structures vues jusqu'ici sont linéaires. L'arbre binaire de recherche (BST, binary search tree) est la première structure arborescente de la série. Il combine deux qualités qu'aucune structure précédente n'avait ensemble : une recherche rapide, comme la dichotomie, et le maintien des éléments dans l'ordre trié, ce que la hashmap ne fait pas. C'est la base conceptuelle des index de bases de données et des structures ordonnées.

L'invariant

Un BST est un arbre où chaque nœud a au plus deux enfants, gauche et droite, et respecte une règle stricte : pour tout nœud, toutes les valeurs du sous-arbre gauche sont inférieures à sa valeur, et toutes celles du sous-arbre droit sont supérieures. Cet invariant tient à tous les niveaux.

typescriptclass NoeudBST {
  valeur: number;
  gauche: NoeudBST | null = null;
  droite: NoeudBST | null = null;
  constructor(valeur: number) { this.valeur = valeur; }
}

La conséquence directe de l'invariant : chercher une valeur revient à descendre l'arbre en éliminant la moitié à chaque nœud, exactement comme la recherche dichotomique de la série Recherche, mais sur une structure dynamique qu'on peut modifier.

Recherche et insertion

Pour chercher, on compare la cible au nœud courant : si elle est plus petite, on descend à gauche ; plus grande, à droite ; égale, on a trouvé. L'insertion suit le même chemin jusqu'à une place libre.

pythonclass NoeudBST:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

def rechercher(racine, cible):
    while racine is not None:
        if cible == racine.valeur:
            return True
        racine = racine.gauche if cible < racine.valeur else racine.droite
    return False

def inserer(racine, valeur):
    if racine is None:
        return NoeudBST(valeur)
    if valeur < racine.valeur:
        racine.gauche = inserer(racine.gauche, valeur)
    elif valeur > racine.valeur:
        racine.droite = inserer(racine.droite, valeur)
    return racine  # les doublons sont ignorés ici

Chaque opération descend d'un niveau à chaque étape. Le coût est donc O(hauteur de l'arbre). Si l'arbre est équilibré, la hauteur est log n, et la recherche est O(log n). C'est là toute la promesse du BST.

Le parcours en ordre

L'invariant offre un bonus que la hashmap n'a pas : parcourir les éléments dans l'ordre trié, gratuitement. Il suffit de visiter le sous-arbre gauche, puis le nœud, puis le sous-arbre droit. C'est le parcours infixe (in-order).

pythondef parcours_ordonne(racine, resultat):
    if racine is not None:
        parcours_ordonne(racine.gauche, resultat)
        resultat.append(racine.valeur)        # nœud entre gauche et droite
        parcours_ordonne(racine.droite, resultat)
    return resultat

Ce parcours visite tous les nœuds une fois, en O(n), et les sort triés. Le BST permet aussi de trouver efficacement le minimum (descendre toujours à gauche), le maximum (toujours à droite), ou le successeur d'une valeur. Ce sont ces opérations ordonnées qui distinguent un BST d'une hashmap.

Le problème : la dégénérescence

Voici le défaut majeur du BST de base. Les opérations sont en O(hauteur), pas en O(log n). Et la hauteur dépend de l'ordre d'insertion. Si on insère des valeurs déjà triées (1, 2, 3, 4, 5), chaque nouvelle valeur va systématiquement à droite. L'arbre dégénère en une liste chaînée verticale, de hauteur n. La recherche devient O(n), on perd tout l'intérêt.

Insertion de 1,2,3,4,5 dans un BST naïf :

1
 \
  2
   \
    3
     \
      4
       \
        5      hauteur = n, recherche en O(n)

C'est un cas fréquent en pratique : les données arrivent souvent partiellement triées. Le BST naïf est donc fragile. C'est exactement le même piège que le pire cas du tri rapide : une entrée triée, censée être facile, devient le pire cas.

La solution est de forcer l'arbre à rester équilibré quoi qu'il arrive, en réorganisant sa structure à chaque insertion. C'est exactement le rôle des arbres équilibrés, AVL et rouge-noir, qui font l'objet de l'article suivant.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 12 "Binary Search Trees". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 3.2 "Binary Search Trees". Addison-Wesley.
• Knuth, D. E. (1998). The Art of Computer Programming, Vol. 3, Section 6.2.2. Addison-Wesley.