NSI (Spé) — Structures de données
Arbres binaires et arbres binaires de recherche
Arbres binaires, vocabulaire, arbres binaires de recherche (ABR), opérations et propriétés
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Après les structures linéaires, voici les structures hiérarchiques. Un arbre binaire organise les données comme un arbre généalogique inversé : une racine en haut, et chaque nœud possède au plus deux fils (gauche et droit). Les nœuds sans fils sont les feuilles. L'arbre binaire de recherche (ABR) ajoute une règle d'or : à gauche, tout est plus petit que le nœud ; à droite, tout est plus grand. Cette discipline transforme la recherche en une dichotomie : à chaque comparaison, on élimine la moitié des candidats. Résultat : recherche, insertion et suppression en $O(\log n)$… à condition que l'arbre reste équilibré. Mal construit (un « peigne »), il dégénère en liste chaînée et retombe à $O(n)$.
Un arbre binaire est un ensemble de nœuds reliés hiérarchiquement : un nœud parent pointe vers au plus deux fils (gauche et droit). Tout part de la racine ; les nœuds terminaux, sans fils, sont les feuilles. Maîtriser ce vocabulaire est indispensable avant d'écrire le moindre algorithme.
- Racine : l'unique nœud sans parent, au sommet. Un arbre vide n'a pas de racine.
- Feuille : nœud sans aucun fils. Nœud interne : nœud ayant au moins un fils.
- Profondeur d'un nœud : nombre d'arêtes jusqu'à la racine (la racine est à la profondeur $0$).
- Hauteur de l'arbre : profondeur maximale d'une feuille. Une racine seule a une hauteur de $0$ ; un arbre vide, $-1$ (convention).
- Taille : nombre total de nœuds. Un arbre de hauteur $h$ a entre $h+1$ et $2^{h+1}-1$ nœuds.
Exemple
Arbre de racine 5, fils gauche 3, fils droit 7, et 3 a pour fils 1 et 4. Taille $= 5$ nœuds, feuilles $= \{1, 4, 7\}$, hauteur $= 2$ (le chemin 5 → 3 → 1 traverse 2 arêtes).
Piège à éviter
Ne confonds pas profondeur (propriété d'un nœud) et hauteur (propriété de l'arbre entier). Et attention : une racine seule a une hauteur de $0$, pas de $1$.
On représente un arbre par une classe Noeud portant une valeur et ses deux sous-arbres ; un arbre vide vaut None. Comme la structure est récursive (un arbre contient des sous-arbres), presque tous les algorithmes le sont aussi : un cas de base (arbre vide) et deux appels récursifs sur les fils.
- class Noeud avec valeur, gauche=None, droit=None ; un arbre vide vaut None.
- Taille : 0 si vide, sinon 1 + taille(gauche) + taille(droit).
- Hauteur : -1 si vide, sinon 1 + max(hauteur(gauche), hauteur(droit)).
- Un nœud est une feuille si gauche is None et droit is None.
- Tout algorithme suit le même schéma récursif : traiter le cas vide, puis combiner les résultats des deux fils.
Exemple
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def taille(a):
if a is None:
return 0
return 1 + taille(a.gauche) + taille(a.droit)
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def taille(a):
if a is None:
return 0
return 1 + taille(a.gauche) + taille(a.droit)
Piège à éviter
Oublier le cas de base (a is None) provoque une AttributeError (on lit .gauche sur None) ou une récursion sans fin. Le test du vide vient toujours en premier.
Un ABR est un arbre binaire ordonné : pour chaque nœud, toutes les valeurs à gauche sont inférieures, toutes celles à droite sont supérieures. Cet invariant, vrai à chaque niveau, permet de chercher une valeur sans explorer tout l'arbre.
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.
- Propriété ABR : pour tout nœud $n$, sous-arbre gauche $<$ $n$.valeur $<$ sous-arbre droit.
- Recherche : comparer à la racine, puis descendre à gauche (si plus petit) ou à droite (si plus grand).
- Insertion : on descend comme pour une recherche, puis on crée une feuille à la place vide trouvée.
- Le parcours infixe (gauche, racine, droit) restitue les valeurs dans l'ordre croissant.
- Suppression, 3 cas : feuille (on retire) ; un fils (on le remonte) ; deux fils (on remplace par le min du sous-arbre droit).
Exemple
Dans l'ABR (racine 5, à gauche 3 avec fils 1 et 4, à droite 7 avec fils 6 et 9), chercher 4 : 4 < 5 → gauche (3), 4 > 3 → droite (4) → trouvé en 3 comparaisons au lieu de parcourir les 7 nœuds.
Piège à éviter
Un arbre binaire quelconque n'est pas un ABR : sans la contrainte d'ordre, le parcours infixe ne donne pas de tri et la recherche dichotomique est impossible.
Toute la performance d'un ABR tient à sa hauteur : la recherche descend d'un niveau par comparaison. Bien équilibré, il offre $O(\log n)$ ; dégénéré en « peigne », il retombe à $O(n)$. L'ordre d'insertion décide de tout.
- ABR équilibré : hauteur $\approx \log_2 n$, donc recherche et insertion en $O(\log n)$.
- ABR dégénéré (peigne) : hauteur $= n-1$, recherche en $O(n)$ — autant qu'une liste chaînée.
- Insérer $1, 2, 3, 4, 5$ dans l'ordre crée un peigne droit (le pire cas).
- Insérer $3, 1, 5, 2, 4$ crée un arbre bien mieux équilibré.
- Pour garantir l'équilibre, on utilise des arbres AVL ou rouge-noir (hors programme, mais à connaître de nom).
- Un arbre binaire parfait de hauteur $h$ contient exactement $2^{h+1}-1$ nœuds.
Exemple
Avec $n = 1\,000\,000$ : un ABR équilibré a une hauteur $\approx 20$ (car $\log_2 10^6 \approx 20$), donc $\approx 20$ comparaisons ; un peigne en demanderait jusqu'à un million.
Piège à éviter
Insérer des données déjà triées dans un ABR simple est le pire scénario : on obtient un peigne et on perd tout l'avantage du $O(\log n)$.
Quiz - Arbres binaires et ABR
10 questions
S'entraîner
- Quiz : Arbres binaires et arbres binaires de recherche10 questions corrigées sur ce chapitre
- Bac 2026 NSI – MétropoleSujet officiel
- Bac 2025 NSI – MétropoleSujet officiel
- Bac 2024 NSI – MétropoleSujet officiel
- Annales du bac de NSITous les sujets officiels, par année
- Coefficient de NSI au bacPoids de l'épreuve dans la note finale
Articles utiles
Questions fréquentes
Les points clés à retenir sur Arbres binaires et arbres binaires de recherche, extraits du quiz de révision.
Qu'est-ce qu'une feuille dans un arbre binaire ?
Réponse :
Un nœud sans fils
Une feuille est un nœud sans fils (ni fils gauche, ni fils droit). C'est un nœud terminal de l'arbre.
Quelle est la hauteur d'un arbre réduit à sa racine ?
Réponse :
0
Un arbre réduit à sa racine a une hauteur de 0 : la profondeur maximale est celle de la racine, qui est 0.
Dans un ABR, où se trouvent les valeurs plus grandes que la racine ?
Réponse :
Dans le sous-arbre droit
Par définition d'un ABR, toutes les valeurs supérieures à la racine se trouvent dans le sous-arbre droit.
Quel parcours d'un ABR donne les valeurs triées en ordre croissant ?
Réponse :
Infixe
Le parcours infixe (gauche, racine, droit) visite les nœuds d'un ABR dans l'ordre croissant de leurs valeurs.