NSI (Spé) — Algorithmique
Algorithmes sur les arbres
Parcours d'arbres (préfixe, infixe, suffixe, largeur), insertion et recherche dans un ABR
Résumé synthétiqueFiche en 5 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Un arbre se définit lui-même en plus petit : un nœud, plus un sous-arbre gauche et un sous-arbre droit… qui sont à leur tour des arbres. Voilà pourquoi presque **tout algorithme sur les arbres est récursif**. On distingue les **parcours en profondeur** — **préfixe** (racine, gauche, droit), **infixe** (gauche, racine, droit) et **suffixe** (gauche, droit, racine) — et le **parcours en largeur (BFS)**, qui visite niveau par niveau à l'aide d'une **file**. Sur un **arbre binaire de recherche (ABR)**, la **recherche** descend à gauche ou à droite selon la comparaison : une véritable **dichotomie**. L'**insertion** descend de même et accroche une **feuille**. Tout cela coûte $O(h)$, la **hauteur** de l'arbre — soit $O(\log n)$ s'il est équilibré, mais $O(n)$ s'il dégénère en peigne.
Un **parcours en profondeur** plonge dans un sous-arbre avant de passer au suivant. Selon **le moment** où l'on traite la racine par rapport à ses fils, on obtient trois ordres : **préfixe**, **infixe** et **suffixe**. Tous suivent le même schéma récursif.
- **Préfixe (préordre) :** racine → gauche → droit. Pratique pour **copier** ou sérialiser un arbre.
- **Infixe (inordre) :** gauche → racine → droit. Sur un **ABR**, donne les valeurs en **ordre croissant**.
- **Suffixe (postordre) :** gauche → droit → racine. Pratique pour **libérer** (supprimer) l'arbre des feuilles vers la racine.
- **Schéma récursif commun :** cas de base (arbre vide → on ne fait rien), puis appels sur les deux sous-arbres.
- Seul **l'ordre** de la ligne « traiter la racine » change entre les trois parcours.
- **Complexité : $O(n)$** — chaque nœud est visité exactement une fois.
Exemple
def infixe(arbre):
if arbre is None: # cas de base
return
infixe(arbre.gauche) # 1) sous-arbre gauche
print(arbre.valeur) # 2) racine
infixe(arbre.droit) # 3) sous-arbre droit
# Pour passer en préfixe : déplacer le print AVANT l'appel gauche.
Piège à éviter
Les trois parcours ne diffèrent **que** par la position de la ligne qui traite la racine. Inverser par erreur l'ordre des appels gauche/droit change le résultat : sur un ABR, seul l'infixe **gauche puis droit** donne l'ordre croissant.
Le **parcours en largeur** visite l'arbre **étage par étage** : d'abord la racine, puis tous les nœuds de niveau 1, puis ceux de niveau 2. Contrairement aux parcours en profondeur, il n'est **pas récursif** : il s'appuie sur une **file**.
- Visite **niveau par niveau** : racine (niveau 0), ses fils (niveau 1), les petits-fils (niveau 2), etc.
- **Outil : une file (FIFO)** — on enfile la racine, puis on défile, on traite, et on enfile les fils.
- **Algorithme :** tant que la file n'est pas vide : noeud = defiler() ; traiter(noeud) ; enfiler le fils gauche puis le fils droit s'ils existent.
- Sur l'arbre de la fiche précédente, le BFS donne **5, 3, 7, 1, 4**.
- **Complexité : $O(n)$** en temps ; mémoire en $O(w)$ où $w$ est la **largeur maximale** (un niveau entier dans la file).
- Application : trouver le nœud le plus proche de la racine vérifiant une condition.
Exemple
from collections import deque
def bfs(racine):
file = deque([racine])
while file:
noeud = file.popleft() # on défile (FIFO)
print(noeud.valeur)
if noeud.gauche: file.append(noeud.gauche)
if noeud.droit: file.append(noeud.droit)
Piège à éviter
Remplacer la **file** par une **pile** (utiliser pop() au lieu de popleft()) transforme le BFS en parcours en **profondeur** : on n'explore plus par niveaux. La structure de données fait toute la différence.
Dans un **ABR**, tout ce qui est à gauche d'un nœud lui est **inférieur**, tout ce qui est à droite lui est **supérieur**. La recherche exploite cette règle pour **éliminer la moitié** de l'arbre à chaque comparaison.
- **Principe :** comparer v à la racine. v < racine → descendre à gauche ; v > racine → à droite ; v = racine → trouvé.
- **Cas de base :** arbre vide → la valeur n'y est pas (retourner False).
- Versions **récursive** et **itérative** (une boucle while qui descend) donnent le même résultat.
- **Complexité : $O(h)$** (hauteur) — donc $O(\log n)$ si équilibré, $O(n)$ si dégénéré en peigne.
- **Analogie :** c'est une **recherche dichotomique** matérialisée par la forme de l'arbre.
- À chaque étape, on ne descend que d'**un** niveau : on ne revient jamais en arrière.
Exemple
def recherche(arbre, v):
if arbre is None:
return False # absent
if v == arbre.valeur:
return True
if v < arbre.valeur:
return recherche(arbre.gauche, v)
return recherche(arbre.droit, v)
Piège à éviter
La recherche n'est rapide que si l'**ABR est équilibré**. Inséré dans le désordre il l'est souvent ; mais construit à partir de données **déjà triées**, il devient un peigne et la recherche retombe à $O(n)$.
Insérer revient à **chercher** la valeur : on descend comme pour une recherche jusqu'à tomber sur une place vide (None), où l'on accroche le nouveau nœud. Le nouvel élément devient **toujours une feuille**.
- **Descendre puis accrocher :** suivre le chemin de recherche jusqu'au premier sous-arbre vide.
- Le nouvel élément est **toujours inséré comme une feuille** (jamais au milieu).
- L'insertion **préserve** la propriété d'ABR (gauche < nœud < droit).
- **L'ordre d'insertion fixe la forme :** 3, 1, 5, 2, 4 donne un arbre équilibré ; 1, 2, 3, 4, 5 donne un **peigne**.
- **Complexité : $O(h)$**, comme la recherche : on ne modifie qu'**un chemin** de la racine à la feuille.
- La version récursive **renvoie** le sous-arbre éventuellement modifié, que le parent réaffecte.
Exemple
def inserer(arbre, v):
if arbre is None:
return Noeud(v) # place vide trouvée : nouvelle feuille
if v < arbre.valeur:
arbre.gauche = inserer(arbre.gauche, v)
else:
arbre.droit = inserer(arbre.droit, v)
return arbre
Piège à éviter
Oublier de **réaffecter** le résultat (arbre.gauche = inserer(arbre.gauche, v)) fait que l'insertion est **perdue** : la fonction crée bien la feuille, mais personne ne la raccroche à l'arbre.
La plupart des mesures sur un arbre se calculent par la **même recette récursive** : un **cas de base** pour l'arbre vide ou la feuille, puis une **combinaison** des résultats des deux sous-arbres.
- **Taille :** 0 si vide, sinon 1 + taille(gauche) + taille(droit).
- **Hauteur :** -1 si vide, sinon 1 + max(hauteur(gauche), hauteur(droit)).
- **Nombre de feuilles :** 1 si pas de fils, sinon feuilles(gauche) + feuilles(droit).
- **Somme des valeurs :** 0 si vide, sinon valeur + somme(gauche) + somme(droit).
- **Schéma unique :** cas de base + décomposition en deux sous-problèmes plus petits.
- On peut aussi vérifier qu'un arbre est un **ABR** ou qu'il est **équilibré** par le même principe.
Exemple
def hauteur(arbre):
if arbre is None:
return -1 # convention : arbre vide
hg = hauteur(arbre.gauche)
hd = hauteur(arbre.droit)
return 1 + max(hg, hd)
Piège à éviter
Oublier le **cas de base** (if arbre is None) provoque une descente sans fin et une **RecursionError**. Tout algorithme récursif sur un arbre commence par traiter l'arbre vide.
Quiz - Algorithmes sur les arbres
10 questions
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Questions fréquentes
Les points clés à retenir sur Algorithmes sur les arbres, extraits du quiz de révision.
Dans quel ordre le parcours infixe visite-t-il les nœuds ?
Réponse :
Gauche, racine, droit
Le parcours infixe visite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Dans un ABR, cela donne les valeurs en ordre croissant.
Quelle structure de données utilise le parcours en largeur ?
Réponse :
Une file
Le parcours en largeur (BFS) utilise une file (FIFO) pour traiter les nœuds niveau par niveau.
Quelle est la complexité de la recherche dans un ABR équilibré de n nœuds ?
Réponse :
O(log n)
Dans un ABR équilibré, la hauteur est O(log n), et la recherche descend d'un niveau à chaque comparaison, soit O(log n) au total.
Le parcours suffixe (postordre) visite les nœuds dans l'ordre :
Réponse :
Gauche, droit, racine
Le parcours suffixe visite d'abord le sous-arbre gauche, puis le sous-arbre droit, et enfin la racine. Il est utile pour évaluer des expressions arithmétiques en notation postfixée.