Numérique et sciences informatiques (spécialité) · TerminaleBac
Arbres binaires de recherche : quiz de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Un ABR range les clés plus petites à gauche et plus grandes à droite de chaque nœud.
- La recherche descend d'un seul côté à chaque nœud, comme une dichotomie.
- Un nouveau nœud inséré devient toujours une feuille.
- Supprimer un nœud à deux enfants : on le remplace par son successeur ou son prédécesseur.
- Taille = nombre de nœuds ; hauteur = nombre de niveaux (convention de l'énoncé).
Avant de commencer
Ce quiz couvre l'essentiel du chapitre sur les arbres binaires de recherche (ABR) : la définition, la recherche d'une clé, l'insertion, la suppression, les parcours en profondeur, ainsi que la taille et la hauteur d'un arbre. Les questions de calcul s'appuient sur un arbre que tu peux reconstruire à la main : prends une feuille de brouillon et dessine-le avant de répondre.
L'arbre de référence (appelé « arbre A » dans plusieurs questions) est obtenu en insérant dans l'ordre les clés entières 8, 3, 10, 1, 6 et 14 dans un ABR initialement vide, sans doublon. Concrètement :
| Nœud | Enfant gauche | Enfant droit |
|---|---|---|
| 8 (racine) | 3 | 10 |
| 3 | 1 | 6 |
| 10 | aucun | 14 |
| 1, 6, 14 | aucun | aucun |
Quiz
15 questions · correction immédiate · ton score reste sur ton appareil.
-
Un ABR est un arbre binaire dont chaque nœud porte une clé, avec des clés plus petites (ou égales) dans le sous-arbre gauche et plus grandes (ou égales) dans le sous-arbre droit 6. La propriété 2 décrit un tas, pas un ABR, et elle ne compare qu'un nœud à ses enfants directs. La propriété 3 parle de remplissage, ce qui est une autre notion. La propriété 4 est tentante mais fausse : dans l'arbre A, la racine 8 est plus grande que son enfant 3.
-
On commence par examiner la racine : 6 est strictement inférieur à 8, donc on continue dans le sous-arbre gauche 6. On arrive en 3 : 6 est strictement supérieur, donc on va dans le sous-arbre droit, où l'on trouve 6. Le chemin 8, 10, 6 est faux car 10 appartient au sous-arbre droit de la racine. Le chemin passant par 1 est faux aussi : 1 est le fils gauche de 3, or 6 > 3. Enfin, la recherche part toujours de la racine, jamais d'un nœud intermédiaire.
-
On compare 7 à la racine 8 : 7 est plus petit, on va à gauche. On compare à 3 : 7 est plus grand, on va à droite. On compare à 6 : 7 est plus grand, mais 6 n'a pas de fils droit. La recherche s'arrête donc sans avoir trouvé 7 : arriver au bout d'une branche sans rencontrer la clé prouve qu'elle est absente 6. On a examiné 3 nœuds. Compter 6 serait une erreur : on ne parcourt pas tout l'arbre, on ne visite qu'une seule branche.
-
La taille est le nombre de nœuds de l'arbre 4. L'arbre A contient les clés 8, 3, 10, 1, 6 et 14, soit 6 nœuds. Ne confonds pas la taille avec la hauteur : la hauteur compte les niveaux, pas les nœuds.
-
La racine 8 est au niveau 1, ses enfants 3 et 10 au niveau 2, et les nœuds 1, 6 et 14 au niveau 3. Aucun nœud n'a de descendant plus bas, donc la hauteur vaut 3. Avec la convention qui donne -1 à l'arbre vide et 0 à un nœud seul 5, on obtiendrait 2 : la convention compte autant que le calcul.
-
Dans cette convention, un arbre à un seul nœud a pour hauteur 1 et l'arbre vide a pour hauteur 0 4. L'erreur tentante est de croire que l'arbre vide vaut forcément -1 : cette valeur existe bien dans d'autres énoncés 5, mais elle appartient à une autre convention, dans laquelle un nœud seul a pour hauteur 0.
-
On descend : 5 < 8 donc à gauche ; 5 > 3 donc à droite, on arrive en 6 ; 5 < 6 donc à gauche, et cet emplacement est libre. Le nouveau nœud devient une feuille, fils gauche de 6 6. Remplacer 6 par 5 écraserait une clé existante. Placer 5 sous 1 est faux : 5 > 3, donc 5 ne peut pas appartenir au sous-arbre gauche de 3. Après cette insertion, la hauteur de l'arbre A passe de 3 à 4.
-
Chaque nouveau nœud prend place en bout de branche, comme feuille 6. On ne réorganise pas les nœuds existants : on descend jusqu'à un emplacement vide et on y accroche le nouveau nœud. Il peut ensuite arriver qu'une insertion ultérieure lui donne un enfant, mais au moment de l'ajout c'est bien une feuille.
-
Pour supprimer un nœud à deux enfants, on l'échange avec son successeur le plus proche (nœud le plus à gauche du sous-arbre droit) ou avec son plus proche prédécesseur (nœud le plus à droite du sous-arbre gauche) ; cela conserve la structure d'ABR 6. Ici, le sous-arbre droit de 3 est réduit à 6, et le sous-arbre gauche à 1 : les deux choix 6 et 1 conviennent. 14 et 10 sont dans l'autre moitié de l'arbre, sous la racine 8 : les placer à la position de 3 violerait la règle gauche-droite.
-
Un ABR se parcourt en profondeur de trois façons : infixe, préfixe ou postfixe 6. Ces algorithmes sont en général écrits de manière récursive. La dichotomie est une méthode de recherche dans un tableau, pas un ordre de parcours d'arbre. Le parcours en largeur d'abord existe aussi, mais il n'est pas un parcours en profondeur 5.
-
Explorer un ABR ressemble à une dichotomie : à chaque étape, une comparaison écarte une partie des données. La différence est que la dichotomie accède directement à chaque élément d'un tableau, alors que l'ABR suit des liens entre nœuds 6. Les réponses 2 et 3 sont fausses : la dichotomie ne balaie pas tout. La réponse 4 inverse la situation : l'ABR est justement une structure de nœuds, pas un tableau.
-
Plusieurs arbres de formes différentes peuvent ranger exactement les mêmes clés 2. Par exemple, insérer 1, 3, 6 dans cet ordre ou 3, 1, 6 donne deux formes différentes pour les mêmes clés : dans le premier cas une chaîne qui descend vers la droite, dans le second un arbre de hauteur 2. La forme dépend de l'ordre d'insertion, ce qui influe sur la hauteur et donc sur le nombre de comparaisons à effectuer.
-
Dans un ABR, il faut pouvoir comparer deux clés quelconques 3 : sans comparaison, impossible de choisir entre gauche et droite. Des entiers positifs ne sont pas exigés : on peut ranger des chaînes de caractères, des nombres décimaux, etc., tant qu'un ordre existe. Quant aux doublons, ils peuvent être acceptés ou refusés selon l'implantation choisie 6. Enfin, insérer dans l'ordre croissant est permis, mais produit un arbre en forme de chaîne.
-
Faux. Les doublons sont tolérés ou bannis selon la façon dont on programme l'ABR 6. C'est pourquoi la définition parle de clés « inférieures ou égales » à gauche et « supérieures ou égales » à droite. L'erreur tentante vient des exemples de cours, souvent écrits sans doublons : ce choix de présentation n'est pas une règle générale.
-
Comme son nom l'indique, cette fonction repère la plus petite valeur du sous-arbre droit, retire le nœud qui la porte et renvoie cette valeur 2. Elle sert directement à la suppression d'un nœud à deux enfants : la valeur renvoyée est le successeur, qui prend la place du nœud supprimé. Les autres propositions confondent min et max, ou lui attribuent un effet (tri, suppression de la racine) qu'elle n'a pas.
Les questions qu'on se pose
Comment savoir si un arbre binaire est un ABR ?
Vérifie, pour chaque nœud, que toutes les clés de son sous-arbre gauche sont inférieures ou égales à sa clé, et toutes celles de son sous-arbre droit supérieures ou égales 6. Comparer un nœud seulement à ses deux enfants ne suffit pas : une clé très grande peut se cacher dans le sous-arbre gauche, plus bas. Exemple : si 12 est fils droit de 3 dans le sous-arbre gauche de 8, l'arbre n'est pas un ABR, car 12 > 8.
Pourquoi la hauteur change-t-elle selon les énoncés, et que faut-il retenir pour l'examen ?
Deux conventions coexistent : arbre vide de hauteur 0 et nœud seul de hauteur 1 4, ou arbre vide de hauteur -1 et nœud seul de hauteur 0 5. À l'examen, l'énoncé précise celle qu'il utilise ; le réflexe est de la relire avant tout calcul, puis de la garder du début à la fin de l'exercice. Pour les questions de taille, aucune ambiguïté : c'est le nombre de nœuds 4.
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.