backend / algorithmes-structures-donnees
Arbres binaires de recherche (BST)
Explication
Ce que vous allez apprendre
- Formuler la règle d'invariant d'un BST (sous-arbre gauche inférieur, sous-arbre droit supérieur, à chaque noeud)
- Rechercher, insérer et supprimer une valeur dans un BST en suivant le bon chemin de décision
- Distinguer O(h) et O(log n), et expliquer dans quel cas ils coïncident ou divergent
- Résoudre le cas délicat de la suppression d'un noeud à deux enfants via son successeur immédiat
- Reconnaître à l'avance les signes qu'un BST est en train de dégénérer en liste chaînée
Dans quel contexte ?
Un développeur construit un BST pour indexer des utilisateurs par identifiant, en insérant les IDs dans l'ordre où ils sont créés en base — donc déjà triés par construction. Après quelques mois, les recherches qui devraient prendre O(log n) prennent en réalité un temps proportionnel au nombre total d'utilisateurs : sans le savoir, il a construit une liste chaînée déguisée en arbre, parce que chaque nouvel ID, toujours plus grand que tous les précédents, s'est systématiquement accroché à droite.
D'abord, une seule règle qui change tout
Un arbre binaire de recherche (BST) ajoute une seule contrainte à un arbre binaire ordinaire : pour chaque noeud, toutes les valeurs de son sous-arbre gauche lui sont inférieures, et toutes celles de son sous-arbre droit lui sont supérieures. Cette règle doit rester vraie à CHAQUE noeud, pas seulement entre voisins immédiats.
Prérequis
Cette leçon suppose acquis les parcours d'arbres binaires de la leçon précédente ainsi que la notation Big O (leçon 1), notamment la distinction entre O(h) et O(log n) introduite ci-dessous.
Étape 1 : ce que cette règle permet de faire
Grâce à cet invariant, chercher une valeur revient à répéter la même décision à chaque noeud : plus petit, aller à gauche ; plus grand, aller à droite ; égal, trouvé. C'est le même principe que la recherche binaire dans un tableau trié, mais matérialisé directement dans la forme de l'arbre.
Pourquoi c'est rapide
Chaque descente élimine tout un sous-arbre entier de la recherche d'un seul coup. Le coût total est donc proportionnel à la hauteur de l'arbre, notée h, pas au nombre total d'éléments.
| Opération | Arbre équilibré (h ≈ log n) | Arbre dégénéré (h = n) |
|---|---|---|
| Recherche | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Suppression | O(log n) | O(n) |
Un piège essentiel à ne pas confondre
O(h) n'est PAS la même chose que O(log n). Si les valeurs sont insérées dans un ordre déjà trié, chaque nouveau noeud n'a qu'un seul enfant, et l'arbre dégénère en une simple liste chaînée.
Piège fréquent
Insérer des valeurs déjà triées (ou déjà triées à l'envers) dans un BST naïf produit systématiquement une chaîne dégénérée, car chaque nouvelle valeur devient l'enfant unique de la précédente. C'est le scénario "pire cas" à tester explicitement avant de faire confiance à un BST en production.
La conséquence de ce piège
Dans ce cas dégénéré, h devient égal à n, et toutes les opérations retombent à O(n) : un BST n'est rapide QUE s'il reste raisonnablement équilibré, un problème que la prochaine leçon résout formellement.
Étape 2 : insérer et rechercher restent simples
Insérer une nouvelle valeur suit exactement le même chemin de décision que la recherche, jusqu'à trouver la place vide où l'accrocher.
Étape 3 : la suppression, l'opération la plus délicate
Supprimer un noeud sans enfant ou avec un seul enfant est trivial : on le retire ou on le remplace directement par son unique enfant. Mais supprimer un noeud à DEUX enfants pose un vrai problème, car on ne peut pas simplement le retirer sans casser l'invariant d'ordre.
La solution à ce cas délicat
On le remplace par son successeur immédiat, c'est-à-dire le minimum de son sous-arbre droit (qui est garanti n'avoir aucun enfant gauche), puis on supprime ce successeur à sa position d'origine — une suppression qui, elle, est toujours simple.
Vers la suite
Ce risque de dégénérescence en liste chaînée n'est pas qu'une curiosité : la prochaine leçon montre comment les arbres AVL et rouge-noir garantissent, eux, un équilibre permanent, quel que soit l'ordre d'insertion.
Commandes & code
Arbres binaires de recherche (BST)
class NoeudBST:
def __init__(self, valeur):
self.valeur = valeur
self.gauche: "NoeudBST | None" = None
self.droite: "NoeudBST | None" = None
class ArbreBinaireDeRecherche:
def __init__(self):
self.racine: NoeudBST | None = None
def inserer(self, valeur) -> None:
# Invariant BST : tout noeud du sous-arbre gauche < noeud, tout noeud du sous-arbre droit > noeud
self.racine = self._inserer_recursif(self.racine, valeur)
def _inserer_recursif(self, noeud: NoeudBST | None, valeur) -> NoeudBST:
if noeud is None:
return NoeudBST(valeur)
if valeur < noeud.valeur:
noeud.gauche = self._inserer_recursif(noeud.gauche, valeur)
elif valeur > noeud.valeur:
noeud.droite = self._inserer_recursif(noeud.droite, valeur)
# si valeur == noeud.valeur : on ignore (pas de doublons dans ce BST)
return noeud
def contient(self, valeur) -> bool:
# O(h) où h = hauteur -- O(log n) si équilibré, O(n) au pire cas (arbre dégénéré)
courant = self.racine
while courant is not None:
if valeur == courant.valeur:
return True
courant = courant.gauche if valeur < courant.valeur else courant.droite
return False
def minimum(self, noeud: NoeudBST | None = None) -> "NoeudBST | None":
courant = noeud or self.racine
if courant is None:
return None
while courant.gauche is not None:
courant = courant.gauche # le minimum est toujours le plus à gauche
return courant
def maximum(self, noeud: NoeudBST | None = None) -> "NoeudBST | None":
courant = noeud or self.racine
if courant is None:
return None
while courant.droite is not None:
courant = courant.droite
return courant
def supprimer(self, valeur) -> None:
self.racine = self._supprimer_recursif(self.racine, valeur)
def _supprimer_recursif(self, noeud: NoeudBST | None, valeur) -> NoeudBST | None:
if noeud is None:
return None
if valeur < noeud.valeur:
noeud.gauche = self._supprimer_recursif(noeud.gauche, valeur)
elif valeur > noeud.valeur:
noeud.droite = self._supprimer_recursif(noeud.droite, valeur)
else:
# Noeud trouvé -- 3 cas de suppression
if noeud.gauche is None:
return noeud.droite # 0 ou 1 enfant (droit) : remonte l'enfant
if noeud.droite is None:
return noeud.gauche # 1 enfant (gauche) : remonte l'enfant
# 2 enfants : remplace par le successeur (minimum du sous-arbre droit)
successeur = self.minimum(noeud.droite)
noeud.valeur = successeur.valeur
noeud.droite = self._supprimer_recursif(noeud.droite, successeur.valeur)
return noeud
def parcours_infixe(self) -> list:
resultat = []
def _parcourir(n):
if n is not None:
_parcourir(n.gauche)
resultat.append(n.valeur)
_parcourir(n.droite)
_parcourir(self.racine)
return resultat
def est_bst_valide(self) -> bool:
def _verifier(n, minimum, maximum) -> bool:
if n is None:
return True
if not (minimum < n.valeur < maximum):
return False
return _verifier(n.gauche, minimum, n.valeur) and _verifier(n.droite, n.valeur, maximum)
return _verifier(self.racine, float("-inf"), float("inf"))
def kieme_plus_petit(self, k: int):
# utilise le parcours infixe : le k-ième élément d'un ordre trié
compteur = [0]
resultat = [None]
def _parcourir(n):
if n is None or resultat[0] is not None:
return
_parcourir(n.gauche)
compteur[0] += 1
if compteur[0] == k:
resultat[0] = n.valeur
return
_parcourir(n.droite)
_parcourir(self.racine)
return resultat[0]
bst = ArbreBinaireDeRecherche()
for v in [5, 3, 8, 1, 4, 7, 9]:
bst.inserer(v)
assert bst.parcours_infixe() == [1, 3, 4, 5, 7, 8, 9]
assert bst.contient(7) is True
assert bst.contient(6) is False
assert bst.est_bst_valide() is True
assert bst.kieme_plus_petit(3) == 4
bst.supprimer(5) # suppression d'un noeud à 2 enfants
assert bst.est_bst_valide() is TrueRésumé
- L'invariant BST (gauche < noeud < droite) permet recherche, insertion, suppression en O(h), soit O(log n) si équilibré.
- Un BST non équilibré (insertions déjà triées) dégénère en liste chaînée : O(n) au pire cas -- voir la leçon sur les arbres équilibrés.
- La suppression d'un noeud à 2 enfants se résout en le remplaçant par son successeur (minimum du sous-arbre droit).
- Le parcours infixe d'un BST produit un ordre trié, ce qui permet de résoudre le "k-ième plus petit élément" efficacement.
Exercices pratiques
Mission : sauver l'index d'utilisateurs qui rame après la migration
Objectif : Diagnostiquer un BST dégénéré causé par un ordre d'insertion trié et raisonner sur la suppression d'un noeud à deux enfants.
Contexte
Une équipe a migré 50 000 utilisateurs vers un nouvel index construit comme un BST, en insérant les identifiants dans l'ordre croissant où ils existaient déjà en base (donc déjà triés). Depuis la migration, les recherches par identifiant sont devenues aussi lentes qu'un parcours de liste complète, et personne ne comprend pourquoi le BST "ne sert à rien".