Numérique et sciences informatiques (spécialité) · TerminaleBac

Arbres binaires de recherche : cours de Terminale NSI

Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur

L'essentiel

Un arbre binaire de recherche (ABR) est un arbre binaire dont les clés sont comparables : à gauche d'un nœud les clés plus petites, à droite les clés plus grandes ⁶.
La recherche descend depuis la racine en comparant la clé cherchée à celle du nœud : à gauche si elle est plus petite, à droite si elle est plus grande ⁶.
Un nouveau nœud est toujours inséré comme feuille ⁶ ; la forme de l'arbre dépend de l'ordre des insertions ².
La suppression d'un nœud à deux enfants demande de le remplacer par son successeur (ou son prédécesseur) pour garder la propriété d'ABR ⁶.
Le parcours infixe d'un ABR donne les clés dans l'ordre croissant ; le coût des opérations dépend de la hauteur de l'arbre.

Pourquoi organiser des données dans un arbre ?

Imagine que tu doives stocker des milliers d'identifiants de clients et retrouver très vite l'un d'entre eux. Dans une liste non triée, tu parcours les éléments un par un. Dans un tableau trié, tu peux chercher par dichotomie, mais insérer un nouvel élément oblige à décaler les suivants. Les arbres binaires de recherche (ABR) proposent un compromis : ils gardent les données ordonnées tout en acceptant facilement de nouveaux éléments.

Un ABR sert à ranger un ensemble de données, ou un tableau associatif, à condition que toutes les clés puissent être comparées selon un ordre total ⁶. Il rend rapides les trois opérations de base : chercher, ajouter et retirer une clé ⁶. Les arbres binaires sont d'ailleurs fondamentaux dans beaucoup de domaines, par exemple la gestion des fichiers ³.

Dans ce cours, tu vas :

rappeler le vocabulaire des arbres binaires ;
définir précisément un ABR ;
écrire en Python une classe de nœuds, puis la recherche, l'insertion et la suppression ;
parcourir un ABR de trois façons ;
comprendre pourquoi la hauteur de l'arbre décide de son efficacité.

Ce chapitre s'appuie sur la programmation orientée objet (pour les nœuds), sur les listes chaînées (des nœuds reliés entre eux) et sur la récursivité.

Rappels sur les arbres binaires

Définition d'un arbre binaire de recherche

Des arbres de formes différentes peuvent ranger exactement les mêmes données ordonnées ². Par exemple, les clés 1, 2 et 3 peuvent donner un arbre de racine 2 avec deux feuilles, ou une « chaîne » de racine 1, de fils droit 2, lui-même de fils droit 3. Les deux sont des ABR valides. La forme dépend de l'ordre dans lequel on insère les clés, nous y reviendrons.

Implanter un ABR en Python

On représente chaque nœud par un objet, comme pour une liste chaînée, mais avec deux liens au lieu d'un. L'arbre vide est représenté par None.

MéthodeLa classe Noeud

class Noeud:
    def __init__(self, cle):
        self.cle = cle
        self.gauche = None   # sous-arbre gauche
        self.droit = None    # sous-arbre droit

Un ABR est alors désigné par son nœud racine (ou par None s'il est vide). Chaque sous-arbre est lui-même un ABR : c'est ce qui rend les algorithmes récursifs naturels.

Rechercher une clé

Examiner le nœudComparer la clé cherchée à la clé du nœud courant.
ÉgalitéSi les clés sont égales, la recherche réussit.
DescendrePlus petite : sous-arbre gauche. Plus grande : sous-arbre droit.
Arbre videSi on atteint un arbre vide, la clé est absente.

Rechercher une clé dans un ABR · La recherche suit une seule branche.

MéthodeRecherche en Python

def rechercher(arbre, cle):
    if arbre is None:
        return False
    if cle == arbre.cle:
        return True
    if cle < arbre.cle:
        return rechercher(arbre.gauche, cle)
    return rechercher(arbre.droit, cle)

À chaque appel récursif, on élimine tout un sous-arbre : on ne parcourt qu'une seule branche, de la racine vers une feuille au plus.

Insérer une clé

MéthodeInsertion en Python

def inserer(arbre, cle):
    """Renvoie la racine de l'arbre après insertion."""
    if arbre is None:
        return Noeud(cle)
    if cle < arbre.cle:
        arbre.gauche = inserer(arbre.gauche, cle)
    elif cle > arbre.cle:
        arbre.droit = inserer(arbre.droit, cle)
    return arbre

La fonction renvoie la racine, ce qui permet de rattacher le nouveau nœud à son parent par l'affectation arbre.gauche = ... ou arbre.droit = .... Si la clé existe déjà, aucune branche n'est modifiée.

Parcourir un ABR

PropriétéTrois parcours en profondeur

Un ABR se parcourt en profondeur de trois manières : les parcours infixe, préfixe et postfixe, qui s'écrivent d'ordinaire de façon récursive ⁶. Il existe aussi un parcours en largeur d'abord, niveau par niveau ⁵.

La différence tient au moment où l'on traite la racine du sous-arbre courant :

Parcours	Ordre de traitement
Préfixe	nœud, puis sous-arbre gauche, puis sous-arbre droit
Infixe	sous-arbre gauche, puis nœud, puis sous-arbre droit
Postfixe	sous-arbre gauche, puis sous-arbre droit, puis nœud

Supprimer une clé

La suppression est l'opération la plus délicate, car il faut conserver la propriété d'ABR. On distingue trois cas selon le nombre d'enfants du nœud N à supprimer.

Les trois cas de suppression
Nombre d'enfants	Action
0 (feuille)	On retire simplement le nœud.
1	On le remplace par son unique sous-arbre.
2	On le remplace par son successeur ou son prédécesseur, puis on supprime ce dernier.

Les trois cas de suppression · Le cas à deux enfants se ramène à un cas simple.

MéthodeSuppression en Python

def minimum(arbre):
    while arbre.gauche is not None:
        arbre = arbre.gauche
    return arbre.cle

def supprimer(arbre, cle):
    """Renvoie la racine de l'arbre après suppression."""
    if arbre is None:
        return None
    if cle < arbre.cle:
        arbre.gauche = supprimer(arbre.gauche, cle)
    elif cle > arbre.cle:
        arbre.droit = supprimer(arbre.droit, cle)
    else:
        if arbre.gauche is None:
            return arbre.droit
        if arbre.droit is None:
            return arbre.gauche
        arbre.cle = minimum(arbre.droit)
        arbre.droit = supprimer(arbre.droit, arbre.cle)
    return arbre

Dans le cas à deux enfants, on recopie la clé du successeur dans le nœud, puis on supprime le successeur du sous-arbre droit. Ce successeur n'a pas de fils gauche (c'est le plus à gauche), donc sa suppression tombe dans un cas simple.

Hauteur et efficacité

Dans les algorithmes précédents, on suit une seule branche de la racine jusqu'à un nœud. Le nombre de comparaisons est donc au plus la hauteur de l'arbre. Toute la question de l'efficacité se ramène à la hauteur : plus l'arbre est ramassé, plus les opérations sont rapides.

MéthodeCalculer la hauteur et la taille

def taille(arbre):
    if arbre is None:
        return 0
    return 1 + taille(arbre.gauche) + taille(arbre.droit)

def hauteur(arbre):
    if arbre is None:
        return 0
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

Ces fonctions utilisent la convention du cours : arbre vide de hauteur 0, nœud seul de hauteur 1 ⁴. Avec la convention où l'arbre vide vaut $-1$ ⁵, il suffit de remplacer la valeur renvoyée dans le cas de base.

Exercices corrigés

Exercice 1 Construire un ABR et chercher une clé

★☆☆Environ 10 min

On insère dans cet ordre, dans un ABR initialement vide, les clés : 14, 6, 20, 3, 9, 17, 25.

Dessine (ou décris) l'arbre obtenu.
Donne son parcours infixe.
Combien de nœuds examine-t-on pour rechercher la clé 17 en partant de la racine ?

Indice 1

Chaque nouvelle clé suit le chemin de recherche jusqu'à un emplacement vide.

Indice 2

Pour la recherche, compte la racine et tous les nœuds rencontrés jusqu'à 17 inclus.

Voir la correction pas à pas

14 est la racine. 6 < 14 : fils gauche. 20 > 14 : fils droit. 3 < 14 puis 3 < 6 : fils gauche de 6. 9 < 14 puis 9 > 6 : fils droit de 6. 17 > 14 puis 17 < 20 : fils gauche de 20. 25 > 14 puis 25 > 20 : fils droit de 20.
Le parcours infixe traite le sous-arbre gauche, la racine, puis le sous-arbre droit : 3, 6, 9, 14, 17, 20, 25. La liste est triée, ce qui confirme que l'arbre est un ABR.
Recherche de 17 : on examine 14 (17 > 14, à droite), puis 20 (17 < 20, à gauche), puis 17 (trouvé). Cela fait 3 nœuds.

La recherche a suivi une seule branche de longueur 3, soit la hauteur de l'arbre.

Exercice 2 Effet de l'ordre d'insertion

★★☆Environ 12 min

On dispose des clés 2, 5, 7, 9, 11, 13, 16.

On les insère dans l'ordre croissant. Décris l'arbre et donne sa hauteur (convention : un nœud seul vaut 1).
Propose un ordre d'insertion de ces mêmes clés qui donne un arbre de hauteur 3.
Quelle est la taille de ces arbres ?

Indice 1

Dans l'ordre croissant, chaque clé est plus grande que toutes celles déjà insérées.

Indice 2

Pour une hauteur de 3 avec 7 clés, il faut remplir complètement les trois niveaux : commence par la clé médiane.

Voir la correction pas à pas

Dans l'ordre croissant, chaque clé part au fils droit de la précédente. On obtient une chaîne 2, 5, 7, 9, 11, 13, 16 : la hauteur est 7.
Pour obtenir la hauteur 3, on insère d'abord la médiane 9 (racine), puis 5 et 13 (ses fils), puis 2, 7, 11 et 16 (les feuilles). Ordre possible : 9, 5, 13, 2, 7, 11, 16.
Dans les deux cas, on a inséré sept clés distinctes : la taille vaut 7. La taille ne dépend pas de l'ordre, contrairement à la hauteur.

Le même ensemble de clés donne ici des arbres de hauteur 7 ou 3 : c'est l'ordre d'insertion qui décide de l'équilibre.

Exercice 3 Supprimer la racine d'un ABR

★★★Environ 15 min

On considère l'ABR de racine 30 dont le sous-arbre gauche est réduit à la feuille 10, et dont le fils droit est 50. Le nœud 50 a pour fils gauche 40 (qui a lui-même pour fils gauche 35) et pour fils droit 60.

Vérifie que c'est bien un ABR.
On supprime la clé 30 en utilisant le successeur. Quelle clé devient la nouvelle racine ?
Donne le parcours infixe de l'arbre final.

Indice 1

Le successeur est le nœud le plus à gauche du sous-arbre droit.

Indice 2

Après avoir recopié la clé du successeur à la racine, il reste à supprimer le nœud du successeur.

Voir la correction pas à pas

Le parcours infixe de l'arbre initial est 10, 30, 35, 40, 50, 60 : il est trié, donc c'est un ABR.
La racine 30 a deux enfants. Dans son sous-arbre droit (racine 50), on descend à gauche : 50 → 40 → 35. Le nœud 35 n'a plus de fils gauche : c'est le successeur, de clé 35.
On recopie 35 à la racine, puis on supprime l'ancien nœud 35, qui est une feuille : on la retire simplement.
Parcours infixe final : 10, 35, 40, 50, 60, trié : l'arbre reste un ABR.

Le successeur d'un nœud est la plus petite clé de son sous-arbre droit : la prendre comme remplaçante conserve l'ordre.

Les questions qu'on se pose

Quelle est la différence entre un arbre binaire et un arbre binaire de recherche ?

Un arbre binaire est une simple structure où chaque nœud a au plus deux enfants. Un ABR ajoute une contrainte d'ordre : les clés doivent être comparables ³, et les clés du sous-arbre gauche sont inférieures à celle du nœud, celles du sous-arbre droit supérieures ⁶. Tout ABR est un arbre binaire, mais l'inverse est faux.

Pourquoi utiliser un ABR plutôt qu'un tableau trié ?

Dans un tableau trié, la dichotomie est rapide mais l'insertion oblige à décaler des éléments. L'ABR se parcourt en suivant des liens au lieu d'accéder directement aux cases ⁶, mais il permet d'insérer et de supprimer en modifiant seulement quelques liens. Il garde les données ordonnées sans retrier.

Que se passe-t-il si on insère une clé déjà présente ?

Cela dépend de la mise en œuvre : certaines acceptent des clés égales, d'autres les interdisent ⁶. À l'examen, l'énoncé précise le choix. Dans ce cours, on ignore simplement l'insertion.

Comment prouver qu'un arbre binaire est un ABR ?

Vérifie la propriété pour tous les nœuds, pas seulement pour les parents directs. Un moyen simple : faire le parcours infixe (gauche, nœud, droite) et vérifier que la liste obtenue est strictement croissante. Un arbre dont le parcours infixe n'est pas trié n'est pas un ABR.

Taille, hauteur : que me demande-t-on au bac ?

Les sujets demandent souvent la taille (nombre de nœuds) et la hauteur d'un arbre, parfois avec l'insertion de nouvelles valeurs dans un ABR ⁴. La convention de hauteur est donnée dans l'énoncé (arbre vide à 0 ⁴, ou à $-1$ ⁵) : applique-la strictement.

Sources

Programme visé : Numérique et Sciences Informatiques (NSI) - Structures de données : Arbres et arbres binaires de recherche · Éduscol - Ministère de l'Éducation Nationale

Numérique et Sciences Informatiques (NSI) - Structures de données : Arbres et arbres binaires de recherche, Éduscol - Ministère de l'Éducation Nationale. Consulté le 7 novembre 2026.
Ressource pédagogique - Arbres binaires de recherche, Éduscol. Consulté le 7 novembre 2026.
Arbres binaires - Ressource d'accompagnement, Éduscol. Consulté le 7 novembre 2026.
Sujets et corrigés d'examen - NSI 2023, Éduscol. Consulté le 7 novembre 2026.
Formation MEEF NSI - Université Grenoble Alpes, Université Grenoble Alpes. Consulté le 7 novembre 2026.
Arbre binaire de recherche, Wikipédia. Consulté le 7 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

Arbres binaires de recherche : cours de Terminale NSI

L'essentiel

Pourquoi organiser des données dans un arbre ?

Rappels sur les arbres binaires

Définition d'un arbre binaire de recherche

Implanter un ABR en Python

Rechercher une clé

Insérer une clé

Parcourir un ABR

Supprimer une clé

Hauteur et efficacité

Exercices corrigés

Exercice 1 Construire un ABR et chercher une clé

Exercice 2 Effet de l'ordre d'insertion

Exercice 3 Supprimer la racine d'un ABR

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur