Un nouveau venu
Tu as un arbre de recherche. Un nouveau nombre arrive. Où le poser, sans rien déplacer ?
Bonne nouvelle : tu connais déjà le chemin. C'est celui de la recherche. Tu descends, et tu t'arrêtes à la première place vide.
Mais attention : l'ordre d'arrivée change la forme de l'arbre. Et la forme change la vitesse.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Insérer | Ranger une nouvelle valeur à sa place dans l'arbre. | Insérer 5 dans l'arbre |
| Hauteur | Le nombre de niveaux sous la racine, jusqu'à la feuille la plus basse. | Un seul nœud : hauteur 0 |
| Niveau | Une rangée de nœuds, à la même distance de la racine. La racine est au niveau 0. | Le niveau 1 : 3 et 10 |
| Équilibré | Un arbre bien rempli, large et pas trop haut. | Six nœuds, hauteur 2 |
| Déséquilibré | Un arbre qui ressemble à un long couloir : très haut et très étroit. | Six nœuds, hauteur 5 |
| Doublon | Une valeur qui est déjà dans l'arbre. On ne la range pas deux fois. | Insérer 8 une deuxième fois |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : où va le 5 ?
À toi de jouer
À toi : où va le 5 ?
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Chercher, puis poser
Insérer, c'est chercher la valeur. Quand tu tombes sur un arbre vide, tu y poses un nouveau nœud.
Ce nouveau nœud est toujours une feuille. On ne déplace aucun autre nœud. Si la valeur est déjà là, on ne fait rien.
Exemple travaillé : ranger six nombres
| Valeur | Chemin suivi | Place choisie |
|---|---|---|
| 8 | Arbre vide | Racine |
| 3 | 3 < 8 : gauche | Fils gauche de 8 |
| 10 | 10 > 8 : droite | Fils droit de 8 |
| 1 | 1 < 8 : gauche, 1 < 3 : gauche | Fils gauche de 3 |
| 6 | 6 < 8 : gauche, 6 > 3 : droite | Fils droit de 3 |
| 14 | 14 > 8 : droite, 14 > 10 : droite | Fils droit de 10 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : ranger 5, 2, 9, 7
À toi de jouer
À toi : ranger 5, 2, 9, 7
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.