NSI · Terminale · Structures de données
Arbres et structure de données
Diviser l’ensemble à chaque nœud.
En bref
Un arbre organise des données par une relation hiérarchique.
Un arbre organise des données par une relation hiérarchique. Sa force : à chaque nœud, on écarte une partie de l’ensemble sans l’examiner.
Le vocabulaire
| Terme | Sa définition |
|---|---|
| La racine | L’unique nœud sans parent |
| Une feuille | Un nœud sans enfant |
| La taille | Le nombre de nœuds |
| La hauteur | Le plus long chemin racine-feuille — 0 pour un arbre réduit à sa racine, −1 pour un arbre vide |
| Un sous-arbre | Un nœud et toute sa descendance |
L’arbre binaire
Chaque nœud a au plus deux enfants.
| Relation | Ce qu’elle dit |
|---|---|
| Un arbre de hauteur h contient au plus 2^(h+1) − 1 nœuds | La croissance est exponentielle en hauteur |
| Un arbre à n nœuds a une hauteur d’au moins log₂(n) | C’est la borne qui fonde toute l’efficacité des arbres |
Sa définition est naturellement récursive : un arbre binaire est soit vide, soit un nœud portant une valeur et deux arbres binaires.
L’arbre binaire de recherche
Contrainte d’ordre : pour tout nœud, toutes les valeurs du sous-arbre gauche lui sont inférieures, toutes celles du sous-arbre droit lui sont supérieures.
Rechercher revient à descendre : comparer, choisir un côté, recommencer.
| L’arbre est… | Sa hauteur | Le coût d’une recherche |
|---|---|---|
| Équilibré | environ log₂(n) | Logarithmique |
| Dégénéré en peigne (valeurs insérées déjà triées) | n | Linéaire — tout l’intérêt disparaît |
C’est le piège classique du chapitre, et la raison d’être des arbres équilibrés.
Les quatre parcours
| Parcours | L’ordre | Son usage |
|---|---|---|
| Infixe | gauche, nœud, droite | Sur un ABR, il produit les valeurs triées |
| Préfixe | nœud, gauche, droite | Copier ou sérialiser un arbre |
| Suffixe | gauche, droite, nœud | Libérer, ou évaluer une expression |
| En largeur | Niveau par niveau | Il utilise une file |
Les trois premiers s’écrivent naturellement de façon récursive ; le dernier est itératif.
À quoi servent les arbres
Systèmes de fichiers, arborescence d’un document, arbres de décision en apprentissage automatique, index de bases de données, compression de Huffman, arbres syntaxiques d’un compilateur.
Retenir la chaîne : hauteur logarithmique → recherche logarithmique.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Qu’est-ce que la hauteur d’un arbre ?
2.Quelle propriété définit un arbre binaire de recherche ?
3.Quel parcours d’un ABR produit les valeurs triées ?
4.Quelle structure utilise-t-on pour un parcours en largeur d’un arbre ?
5.Que se passe-t-il si l’on insère des valeurs déjà triées dans un ABR ?
6.Un arbre binaire de hauteur h contient au plus 2^(h+1) − 1 nœuds.
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Arbres binaires » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
