Question transversaleMathsNSIArbres et structures de données

Pourquoi peut-on retrouver une donnée parmi un million en une vingtaine d'étapes seulement ?

Q: Combien de feuilles au maximum ?

$2^(h)$, toutes au dernier niveau.

Q: Démontrez 1 + 2 + … + 2^(h) = 2⁽h+1) − 1.

Somme géométrique de raison 2 : (2⁽h+1) − 1)/(2 − 1). Ou par récurrence.

Un arbre binaire de hauteur h contient au plus 2^(h+1) − 1 nœuds. Pour ranger un million de données, il faut donc une hauteur d'au moins 19 : dans un arbre bien équilibré, une recherche descend au plus d'une vingtaine de niveaux, comme une dichotomie.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En NSI, nous avons construit des arbres binaires et calculé leur hauteur. J'ai été frappé par le fait qu'un arbre de hauteur 20 peut contenir plus d'un million de nœuds. Cela m'a fait comprendre comment les bases de données et les systèmes de fichiers retrouvent une information si vite, et j'ai voulu établir la relation exacte entre le nombre de nœuds et la hauteur.

L'enjeu et les notions du programme

Majorer le nombre de nœuds d'un arbre par une somme géométrique, puis inverser la relation par le logarithme.

Mathématiques

Somme des termes d'une suite géométrique (première)
Logarithme, inéquations (terminale)
Raisonnement par récurrence (terminale)

Numérique et sciences informatiques

Arbres binaires : nœuds, feuilles, hauteur (terminale)
Arbres binaires de recherche (terminale)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Un arbre binaire est formé de nœuds ayant chacun au plus deux enfants. Sa hauteur est le nombre de niveaux sous la racine. Problématique : combien de nœuds peut contenir un arbre d'une hauteur donnée, et qu'en déduire pour la recherche d'une donnée ?
2. Mathématiques : une somme géométrique
4 min
Au niveau 0, il y a la racine : 1 nœud. Chaque nœud a au plus 2 enfants : au niveau $k$ k, il y a au plus $2^{k}$ 2^(k) nœuds (récurrence immédiate). Un arbre de hauteur $h$ h contient donc au plus $1 + 2 + 4 + \dots + 2^{h} = 2^{h + 1} - 1$ 1+2+4+…+2^(h)=2^(h+1)-1 nœuds (somme géométrique de raison 2).
Inversement, si l'arbre contient $n$ n nœuds, $n \leq 2^{h + 1} - 1$ n≤2^(h+1)-1, donc $h \geq lo g_{2} (n + 1) - 1$ h≥log₂(n+1)-1. Pour $n = 1 0^{6}$ n=10⁶ : $lo g_{2} (1 0^{6} + 1) - 1 \approx 18, 9$ log₂(10⁶+1)-1≈18,9, donc $h \geq 19$ h≥19.
À l'autre extrême, un arbre « filiforme » où chaque nœud n'a qu'un enfant a une hauteur $n - 1$ n-1. La hauteur d'un arbre à $n$ n nœuds est donc comprise entre $⌈ lo g_{2} (n + 1)⌉ - 1$ ⌈log₂(n+1)⌉-1 et $n - 1$ n-1 : entre 19 et 999 999 pour un million de nœuds.
3. NSI : la recherche dans un arbre
3 min
Dans un arbre binaire de recherche, chaque nœud a des valeurs plus petites à gauche et plus grandes à droite. Chercher une valeur, c'est descendre de la racine en choisissant à gauche ou à droite : au plus $h + 1$ h+1 comparaisons.
Si l'arbre est équilibré, $h \approx lo g_{2} n$ h≈log₂n : une vingtaine de comparaisons pour un million de données. S'il est filiforme, la recherche devient une lecture séquentielle. Les bases de données utilisent des arbres maintenus équilibrés (arbres AVL, arbres B) pour garantir la hauteur logarithmique, même après de nombreuses insertions.
4. Conclusion
1,5 min
Un arbre binaire de hauteur $h$ h contient au plus $2^{h + 1} - 1$ 2^(h+1)-1 nœuds : la hauteur nécessaire ne croît que comme $lo g_{2} n$ log₂n. C'est pourquoi un arbre équilibré retrouve une donnée parmi un million en vingt étapes. J'ouvre sur les arbres B des bases de données, où chaque nœud a des centaines d'enfants.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

1 + 2 + \dots + 2^{h} = 2^{h + 1} - 1 n \leq 2^{h + 1} - 1 ⟺ h \geq lo g_{2} (n + 1) - 1 1+2+\dots+2^(h)=2^(h+1)-1 n\leq2^(h+1)-1\Leftrightarrow h\geqlog₂(n+1)-1 n = 1 0^{6} : h \geq 18, 9 \Rightarrow h \geq 19 ⌈ lo g_{2} (n + 1)⌉ - 1 \leq h \leq n - 1 n=10⁶: h\geq18,9\Rightarrow h\geq19 ⌈log₂(n+1)⌉-1\leq h\leq n-1

Conclusion : la réponse à la question

Une somme géométrique majore le nombre de nœuds, et le logarithme donne la hauteur minimale. Un arbre bien construit transforme une recherche parmi un million en une vingtaine de choix gauche-droite.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Combien de nœuds au maximum dans un arbre binaire de hauteur 3 ?

$2^{4} - 1 = 15$ 2⁴-1=15.

Combien de feuilles au maximum ?

$2^{h}$ 2^(h), toutes au dernier niveau.

Démontrez 1 + 2 + … + 2^h = 2^(h+1) − 1.

Somme géométrique de raison 2 : (2^(h+1) − 1)/(2 − 1). Ou par récurrence.

Qu'est-ce qu'un arbre équilibré ?

Un arbre où, pour chaque nœud, les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1 (arbres AVL).

Quel lien avec la recherche dichotomique ?

Chaque comparaison élimine la moitié des données restantes, comme chaque descente dans un arbre équilibré.

Les pièges qui coûtent des points

Confondre hauteur et nombre de nœuds.
Oublier le « − 1 » de la somme géométrique.
Croire que tout arbre binaire de recherche est équilibré.

Revoir les notions

Autres questions : arbres et structures de données

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →