Numérique et sciences informatiques (spécialité) · TerminaleBac
Arbres binaires de recherche : fiche de révision 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 chaque nœud porte une clé : les clés du sous-arbre gauche sont inférieures, celles du sous-arbre droit supérieures 6.
- La recherche part de la racine et descend à gauche ou à droite selon la comparaison, comme une dichotomie 6.
- Un nœud ajouté devient toujours une feuille 6.
- La suppression d'un nœud à deux enfants passe par son successeur ou son prédécesseur 6.
- Les parcours en profondeur sont préfixe, infixe et suffixe 6. Pour la hauteur, suis la convention de l'énoncé 4.
Définition et propriété fondamentale
Rechercher une clé
Insérer et supprimer
Parcours, hauteur et taille
Implantation et questions du bac
En NSI, un ABR s'implante avec la programmation objet : un nœud possède une clé et deux fils, et l'arbre expose des opérations comme est_vide, ce que reprennent les sujets d'examen 4. Les fonctions récursives suivent la structure de l'arbre : un cas de base (arbre vide) et un appel sur chaque sous-arbre utile.
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
-
Les clés plus petites que la racine sont dans le sous-arbre gauche 6. Le sous-arbre droit contient les clés plus grandes, c'est l'erreur tentante.
-
Les nœuds ajoutés deviennent des feuilles 6. Les placer à la racine casserait la règle d'ordre.
-
En visitant le sous-arbre gauche, puis la racine, puis le sous-arbre droit, on lit les clés de la plus petite à la plus grande, d'après la règle d'ordre. Le parcours préfixe, lui, ne trie pas.
-
Ce sont les deux échanges qui conservent la structure d'ABR 6. Prendre la racine ou n'importe quelle feuille profonde ne respecte pas l'ordre des clés.
Les questions qu'on se pose
Quel est le lien entre ABR et dichotomie ?
La recherche dans un ABR procède à peu près comme la dichotomie : à chaque comparaison, on écarte un sous-arbre. La différence est qu'on suit des liens au lieu d'accéder directement aux éléments d'un tableau 6.
Pourquoi deux ABR différents peuvent-ils contenir les mêmes valeurs ?
Les mêmes valeurs peuvent être rangées dans des arbres de formes différentes 2. L'ordre dans lequel on insère les clés change la forme de l'arbre.
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.