Idées d’apprentissage actif
Les algorithmes sur les arbres sont essentiels pour manipuler efficacement les données hiérarchiques. Ce chapitre se concentre sur les différentes manières de parcourir un arbre (préfixe, infixe, suffixe en profondeur, ou parcours en largeur) et sur les opérations spécifiques aux arbres binaires de recherche (ABR) comme l'insertion et la recherche. Ces algorithmes sont presque toujours récursifs, ce qui en fait une application parfaite du chapitre sur la récursivité.
Activité 01
Plusieurs arbres sont affichés avec une suite de valeurs. Les élèves doivent identifier quel type de parcours (infixe, préfixe...) a généré cette suite et justifier leur réponse.
Comment parcourir un arbre en profondeur ?
Activité 02
Un grand arbre est dessiné au sol. Un élève arrive avec un nouveau nombre et doit demander à chaque 'nœud' (un autre élève) s'il doit aller à gauche ou à droite pour trouver sa place.
Quel parcours permet d'obtenir les valeurs triées d'un ABR ?
Activité 03
Les élèves comparent l'ordre de visite des nœuds pour les deux types de parcours sur un même arbre. Ils discutent en binômes de l'utilité d'utiliser une file ou une pile pour l'implémentation.
Comment insérer un nœud dans un arbre binaire de recherche ?
Quelques notes pour enseigner cette unité
Attention à ces idées reçues
Confondre les ordres de parcours en profondeur (préfixe, infixe, suffixe).
La différence réside uniquement dans le moment où l'on traite la racine. Utiliser une règle visuelle (le contour de l'arbre) où l'on note la valeur à gauche, en bas ou à droite du nœud aide à ne plus se tromper.
Penser que l'insertion dans un ABR donne toujours un arbre équilibré.
Si on insère des valeurs déjà triées, l'arbre devient une simple liste (arbre dégénéré). Faire tester cette insertion 'catastrophique' aux élèves leur permet de comprendre l'importance de l'équilibre.
Méthodes utilisées dans ce dossier
Algorithmes sur les graphes
Parcours de graphes en largeur et en profondeur. Recherche de chemins, détection de cycles et applications pratiques.
8 methodologies
Méthode "Diviser pour régner"
Principe de la méthode diviser pour régner. Application au tri fusion et analyse de la complexité algorithmique.
8 methodologies
Programmation dynamique
Introduction à la programmation dynamique pour l'optimisation. Résolution de problèmes classiques comme le rendu de monnaie ou l'alignement de séquences.
8 methodologies