Question transversaleMathsNSIArbres et structures de données

Pourquoi l'ordre dans lequel on range des données dans un arbre change-t-il tout ?

Insérer 1, 2, 3, …, n dans cet ordre donne un arbre filiforme de hauteur n − 1, où chercher coûte jusqu'à n comparaisons. Dans un ordre aléatoire, la profondeur moyenne d'un nœud est environ 2 ln n ≈ 1,39 log₂ n : environ 28 pour un million, au lieu de 500 000 en moyenne.

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, j'ai inséré les élèves de ma classe dans un arbre binaire de recherche par ordre alphabétique, et j'ai obtenu une longue chaîne au lieu d'un bel arbre. En les insérant dans le désordre, l'arbre était beaucoup plus compact. J'ai voulu comprendre l'effet de l'ordre d'insertion, et pourquoi le hasard, ici, aide plutôt qu'il ne nuit.

L'enjeu et les notions du programme

Comparer le pire cas et le cas moyen d'une structure de données à l'aide des sommes et de l'espérance.

Mathématiques

Somme d'une suite arithmétique (première)
Espérance, linéarité (terminale)
Logarithme népérien (terminale)

Numérique et sciences informatiques

Arbres binaires de recherche : insertion, recherche (terminale)
Coût d'un algorithme dans le pire et le meilleur cas (première)

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

1. Introduction
1 min
Dans un arbre binaire de recherche, on insère chaque valeur en descendant depuis la racine jusqu'à une place libre. La forme de l'arbre dépend donc de l'ordre d'arrivée. Problématique : à quel point cet ordre influe-t-il sur le coût des recherches ?
2. Mathématiques : pire cas et cas moyen
4 min
Pire cas : on insère $1, 2, \dots, n$ 1,2,…,n dans l'ordre. Chaque valeur est plus grande que toutes les précédentes et se place à droite de la dernière : l'arbre est une chaîne de hauteur $n - 1$ n-1. Le nœud $k$ k est à la profondeur $k - 1$ k-1 ; la profondeur moyenne vaut $\frac{0 + 1 + \dots + ( n - 1 )}{n} = \frac{n - 1}{2}$ (0+1+…+(n-1))/n=(n-1)/2, soit environ 500 000 pour un million de valeurs.
Cas moyen : si l'ordre d'insertion est aléatoire, on montre (calcul admis, analogue à celui du tri rapide) que la profondeur moyenne d'un nœud est environ $2 ln n$ 2ln n. Pour $n = 1 0^{6}$ n=10⁶, $2 ln n \approx 27, 6$ 2ln n≈27,6.
Comme $ln n = ln 2 \times lo g_{2} n$ ln n=ln2×log₂n, on a $2 ln n \approx 1, 39 lo g_{2} n$ 2ln n≈1,39log₂n : un arbre aléatoire n'est que 39 % plus profond en moyenne qu'un arbre parfaitement équilibré. L'écart entre 28 et 500 000 est spectaculaire.
3. NSI : se protéger du pire cas
3 min
Les données réelles arrivent souvent triées (dates, numéros croissants) : le pire cas n'est pas rare. Deux solutions : mélanger les données avant insertion, ou utiliser un arbre qui se rééquilibre à chaque insertion par des « rotations » (arbres AVL ou rouge-noir), qui garantissent une hauteur logarithmique.
On peut vérifier en Python : on insère $10000$ 10 000 valeurs triées puis mélangées, et on mesure la hauteur. On obtient 9 999 dans le premier cas, et une trentaine dans le second. La version récursive de l'insertion dépasse d'ailleurs la profondeur de récursion autorisée sur l'arbre filiforme.
4. Conclusion
1,5 min
L'ordre d'insertion décide de la forme de l'arbre : trié, il donne une chaîne de profondeur moyenne $\frac{n - 1}{2}$ (n-1)/2 ; aléatoire, une profondeur moyenne de $2 ln n$ 2ln n. Le hasard protège du pire cas. J'ouvre sur les arbres AVL, qui imposent l'équilibre quel que soit l'ordre.

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.

ins \overset{e}{ˊ} r \overset{e}{ˊ} tri \overset{e}{ˊ} : profondeur moyenne = \frac{0 + 1 + \dots + ( n - 1 )}{n} = \frac{n - 1}{2} \approx 5 \times 1 0^{5} inséré trié : profondeur moyenne =(0+1+\dots+(n-1))/n=(n-1)/2\approx5\times10⁵ ins \overset{e}{ˊ} r \overset{e}{ˊ} au hasard : \approx 2 ln n \approx 27, 62 ln n = 2 ln 2 lo g_{2} n \approx 1, 39 lo g_{2} n inséré au hasard : \approx2ln n\approx27,6 2ln n=2ln2 log₂n\approx1,39log₂n

Conclusion : la réponse à la question

Un arbre binaire de recherche est rapide en moyenne mais vulnérable aux données triées. Le calcul de la profondeur moyenne, par une somme ou par l'espérance, mesure l'écart.

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.

Insérez 4, 2, 6, 1, 3, 5, 7. Quelle est la hauteur ?

2 : l'arbre est parfaitement équilibré (4 à la racine, 2 et 6, puis 1, 3, 5, 7).

Pourquoi l'ordre trié donne-t-il une chaîne ?

Chaque nouvelle valeur est plus grande que toutes les autres : elle descend toujours à droite jusqu'au bout.

Calculez 0 + 1 + … + 9.

45, soit 9 × 10/2.

Qu'est-ce qu'une rotation dans un arbre AVL ?

Une réorganisation locale de trois nœuds qui diminue la hauteur d'un côté sans casser l'ordre de l'arbre.

Combien de comparaisons pour chercher une valeur absente dans l'arbre filiforme ?

Jusqu'à n, si elle est plus grande que toutes.

Les pièges qui coûtent des points

Croire qu'un arbre binaire de recherche est toujours équilibré.
Confondre profondeur moyenne et hauteur maximale.
Penser que le hasard rend les recherches incorrectes : il ne change que leur coût.

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 →