Trouver la salle 14
Au lycée, tu cherches la salle 14. Un panneau dit : « Petits numéros à gauche, grands numéros à droite. »
Devant chaque couloir, tu choisis un côté. Et tout l'autre côté ne sert plus.
Un arbre peut ranger des nombres de la même façon. Tu as déjà vu les arbres binaires dans la leçon « Les arbres binaires ». Cette fois, on les range avec une règle.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Arbre binaire | Un arbre où chaque nœud a au plus deux fils : un à gauche, un à droite. | Un nœud avec deux fils |
| Racine | Le nœud tout en haut. C'est là qu'on commence. | 8, dans nos exemples |
| Fils gauche, fils droit | Les deux nœuds posés juste sous un nœud, l'un à gauche, l'autre à droite. | Sous 8 : 3 à gauche, 10 à droite |
| Feuille | Un nœud sans aucun fils. C'est un bout de branche. | 1, 6 et 14 |
| Arbre vide | Un arbre sans aucun nœud. En Python, on l'écrit None. | Le fils gauche de 10 |
| Arbre de recherche | Un arbre binaire où tout ce qui est à gauche est plus petit, et tout ce qui est à droite est plus grand. | 3 est à gauche de 8 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : gauche ou droite ?
À toi de jouer
À toi : gauche ou droite ?
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
La règle de l'arbre de recherche
Prends un nœud. Tout ce qui est dans son côté gauche est plus petit que lui. Tout ce qui est dans son côté droit est plus grand.
Attention : la règle vaut pour tout le côté, pas seulement pour le fils juste dessous. Les valeurs sont toutes différentes.
Exemple travaillé : chercher 6, puis 7
| Recherche | Nœud regardé | Comparaison | On fait quoi ? |
|---|---|---|---|
| 6 | 8 | 6 < 8 | On va à gauche |
| 6 | 3 | 6 > 3 | On va à droite |
| 6 | 6 | 6 = 6 | Trouvé ! |
| 7 | 8 | 7 < 8 | On va à gauche |
| 7 | 3 | 7 > 3 | On va à droite |
| 7 | 6 | 7 > 6 | On va à droite : il n'y a rien |
| 7 | Arbre vide | - | Absent : 7 n'est pas dans l'arbre |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : chercher 14 à la main
À toi de jouer
À toi : chercher 14 à la main
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.