backend / algorithmes-structures-donnees
Arbres binaires
Explication
Ce que vous allez apprendre
- Distinguer une structure linéaire (liste, pile, file) d'une structure hiérarchique (arbre)
- Nommer et appliquer les trois parcours en profondeur (préfixe, infixe, suffixe) et choisir le bon selon le besoin
- Expliquer pourquoi le parcours infixe d'un arbre binaire de recherche produit directement les valeurs triées
- Différencier parcours en profondeur (DFS) et parcours en largeur (BFS)
- Expliquer pourquoi la hauteur de l'arbre détermine le coût réel des opérations, et ce qu'est un arbre dégénéré
Dans quel contexte ?
Une application de gestion de fichiers doit exporter l'arborescence d'un disque dur en JSON pour la sérialiser, puis la reconstruire ailleurs à l'identique. Un parcours préfixe (racine avant les enfants) permet d'écrire chaque dossier avant son contenu, dans un ordre qui permet de tout reconstruire simplement en relisant le flux dans le même ordre. À l'inverse, un parcours suffixe sert à libérer proprement la mémoire ou supprimer un dossier : on supprime toujours d'abord les sous-dossiers, jamais un dossier parent avant d'avoir traité son contenu.
D'abord, une nouvelle forme, différente de tout ce qu'on a vu
Tableaux, listes, piles et files sont tous des structures linéaires : un élément a au plus un successeur. Un arbre introduit une dimension nouvelle, la hiérarchie, où un élément peut avoir plusieurs "enfants".
Prérequis
Cette leçon suppose la récursivité acquise (leçon 4) : les parcours d'arbres s'expriment presque toujours de façon récursive, avec un appel par sous-arbre.
Étape 1 : le cas le plus simple, l'arbre binaire
Un arbre binaire est une structure où chaque noeud a au plus deux enfants, appelés "gauche" et "droite". C'est le squelette qui sous-tend les systèmes de fichiers, les arbres de décision, ou l'organisation d'un tournoi à élimination directe.
Il reste un problème : comment visiter tous les noeuds ?
Contrairement à une liste, un arbre n'a pas d'ordre de lecture naturel. Il faut donc choisir une convention pour le parcourir, et il en existe plusieurs, chacune utile pour un but différent.
| Parcours | Ordre de visite | Cas d'usage typique |
|---|---|---|
| Préfixe (pre-order) | Racine, gauche, droite | Dupliquer ou sérialiser un arbre |
| Infixe (in-order) | Gauche, racine, droite | Obtenir les valeurs triées d'un BST |
| Suffixe (post-order) | Gauche, droite, racine | Supprimer un arbre en toute sécurité |
| Largeur (BFS) | Niveau par niveau | Plus court chemin en nombre d'arêtes |
Étape 2 : le parcours préfixe, racine d'abord
Visiter la racine, puis le sous-arbre gauche, puis le droit. Cet ordre est utile pour dupliquer ou sérialiser la structure d'un arbre, puisqu'on connaît le parent avant ses enfants.
Étape 3 : le parcours suffixe, racine en dernier
Visiter les deux sous-arbres avant la racine. Cet ordre convient pour supprimer un arbre en toute sécurité : on ne coupe jamais une branche à laquelle on doit encore accéder.
Étape 4 : le parcours infixe, un ordre particulier
Visiter gauche, puis la racine, puis droite. Sur un arbre binaire DE RECHERCHE (vu à la prochaine leçon), cet ordre précis produit directement les valeurs triées, ce qui n'est pas un hasard.
Une autre façon d'explorer : par niveaux
Le parcours en profondeur (les trois ordres ci-dessus) explore une branche jusqu'au bout avant de revenir en arrière. Le parcours en largeur (BFS), lui, explore niveau par niveau grâce à une file, ce qui est plus naturel pour trouver le chemin le plus court en nombre d'arêtes.
Le piège à connaître : la hauteur de l'arbre
La hauteur détermine directement le coût des opérations. Un arbre "équilibré" (hauteur proche de log2(n)) reste rapide, mais un arbre dégénéré en chaîne (chaque noeud n'a qu'un seul enfant) perd tout l'avantage de la structure arborescente et retombe à une complexité linéaire.
Piège fréquent
Un arbre binaire n'est efficace que s'il reste équilibré. Insérer des valeurs déjà triées dans un arbre binaire de recherche naïf, sans rééquilibrage, produit une chaîne dégénérée où chaque noeud n'a qu'un seul enfant : toutes les opérations retombent alors en O(n), exactement comme une liste chaînée.
Vers la suite
Ce risque de dégénérescence n'est pas qu'une curiosité théorique : la prochaine leçon montre comment un arbre binaire de recherche exploite cette hiérarchie pour accélérer la recherche, et pourquoi il peut justement dégénérer de cette façon.
Commandes & code
Arbres binaires
from collections import deque
class NoeudArbre:
def __init__(self, valeur):
self.valeur = valeur
self.gauche: "NoeudArbre | None" = None
self.droite: "NoeudArbre | None" = None
# --- Parcours en profondeur (DFS) : préfixe, infixe, suffixe ---
def parcours_prefixe(noeud: NoeudArbre | None, resultat: list | None = None) -> list:
# Racine -> Gauche -> Droite -- utile pour dupliquer/sérialiser un arbre
if resultat is None:
resultat = []
if noeud is not None:
resultat.append(noeud.valeur)
parcours_prefixe(noeud.gauche, resultat)
parcours_prefixe(noeud.droite, resultat)
return resultat
def parcours_infixe(noeud: NoeudArbre | None, resultat: list | None = None) -> list:
# Gauche -> Racine -> Droite -- donne un ordre TRIÉ sur un arbre binaire de recherche
if resultat is None:
resultat = []
if noeud is not None:
parcours_infixe(noeud.gauche, resultat)
resultat.append(noeud.valeur)
parcours_infixe(noeud.droite, resultat)
return resultat
def parcours_suffixe(noeud: NoeudArbre | None, resultat: list | None = None) -> list:
# Gauche -> Droite -> Racine -- utile pour supprimer un arbre (enfants avant parent)
if resultat is None:
resultat = []
if noeud is not None:
parcours_suffixe(noeud.gauche, resultat)
parcours_suffixe(noeud.droite, resultat)
resultat.append(noeud.valeur)
return resultat
# --- Parcours en largeur (BFS) : niveau par niveau, avec une file ---
def parcours_largeur(racine: NoeudArbre | None) -> list:
if racine is None:
return []
resultat = []
file = deque([racine])
while file:
noeud = file.popleft()
resultat.append(noeud.valeur)
if noeud.gauche:
file.append(noeud.gauche)
if noeud.droite:
file.append(noeud.droite)
return resultat
# BFS par niveau : regroupe les valeurs de chaque profondeur séparément
def parcours_par_niveaux(racine: NoeudArbre | None) -> list[list]:
if racine is None:
return []
resultat = []
file = deque([racine])
while file:
taille_niveau = len(file)
niveau = []
for _ in range(taille_niveau):
noeud = file.popleft()
niveau.append(noeud.valeur)
if noeud.gauche:
file.append(noeud.gauche)
if noeud.droite:
file.append(noeud.droite)
resultat.append(niveau)
return resultat
# --- Hauteur et propriétés de l'arbre ---
def hauteur(noeud: NoeudArbre | None) -> int:
if noeud is None:
return -1 # convention : hauteur d'un arbre vide = -1, feuille seule = 0
return 1 + max(hauteur(noeud.gauche), hauteur(noeud.droite))
def est_equilibre(noeud: NoeudArbre | None) -> bool:
# équilibré = la différence de hauteur gauche/droite ne dépasse jamais 1, récursivement
def verifier(n) -> tuple[bool, int]:
if n is None:
return True, -1
eq_gauche, h_gauche = verifier(n.gauche)
eq_droite, h_droite = verifier(n.droite)
equilibre = eq_gauche and eq_droite and abs(h_gauche - h_droite) <= 1
return equilibre, 1 + max(h_gauche, h_droite)
return verifier(noeud)[0]
def sont_identiques(a: NoeudArbre | None, b: NoeudArbre | None) -> bool:
if a is None and b is None:
return True
if a is None or b is None:
return False
return a.valeur == b.valeur and sont_identiques(a.gauche, b.gauche) and sont_identiques(a.droite, b.droite)
# Construire un arbre d'exemple pour les tests
racine = NoeudArbre(5)
racine.gauche = NoeudArbre(3)
racine.droite = NoeudArbre(8)
racine.gauche.gauche = NoeudArbre(1)
racine.gauche.droite = NoeudArbre(4)
assert parcours_prefixe(racine) == [5, 3, 1, 4, 8]
assert parcours_infixe(racine) == [1, 3, 4, 5, 8]
assert parcours_largeur(racine) == [5, 3, 8, 1, 4]
assert hauteur(racine) == 2
assert est_equilibre(racine) is TrueRésumé
- Trois parcours en profondeur (préfixe, infixe, suffixe) selon l'ordre racine/gauche/droite ; tous en O(n) temps, O(h) espace (h = hauteur).
- Le parcours en largeur (BFS) nécessite une file explicite et traite l'arbre niveau par niveau.
- Le parcours infixe d'un arbre binaire de recherche produit les valeurs triées.
- La hauteur et l'équilibre se calculent récursivement en une seule passe O(n) en combinant les résultats des sous-arbres.
Exercices pratiques
Mission : reconstituer un arbre de sérialisation corrompu
Objectif : Choisir le bon parcours pour une tâche donnée, puis diagnostiquer un arbre dégénéré.
Contexte
Un service de sauvegarde sérialise un arbre binaire de configuration en enregistrant l'ordre dans lequel les noeuds sont visités. Un bug a fait sauvegarder le mauvais type de parcours, ce qui empêche de reconstituer l'arbre à l'identique sans connaître la structure d'origine, et une seconde équipe se plaint que les opérations sur un autre arbre sont devenues linéaires.
Tu dois identifier le bon parcours pour chaque tâche, puis diagnostiquer la dégénérescence signalée.