Simulic
Français

Arbres binaires de recherche – insertion, recherche, suppression et parcours

InformatiqueAlgorithmique et résolution de problèmes17–18 ans

Chargement…

Utiliser avec ma classe ✨ Personnaliser avec l'IA Signaler un problème

Insérez, recherchez et supprimez des clés dans un arbre binaire de recherche et suivez le chemin des comparaisons de nœud en nœud, la hauteur de l’arbre et le nombre de comparaisons ; la suppression d’un nœud à 0, 1 ou 2 enfants utilise le successeur infixe. Insérer des clés triées fait dégénérer l’arbre en liste, ce qu’un tableau de résultats compare avec des ordres d’insertion aléatoire et équilibré. Un mode Parcours d’arbre déroule pas à pas les parcours préfixe, infixe, suffixe et en largeur, et un mode Arbre d’expression donne les notations préfixe, infixe et postfixe.

Leçon : Arbres binaires et arbres binaires de recherche (ABR) ; parcours préfixe, infixe, suffixe et en largeur ; arbres d’expression et notation polonaise

Ce qu’elle montre

Dans un arbre binaire de recherche, toutes les clés du sous-arbre gauche sont plus petites et celles du sous-arbre droit plus grandes que la clé du nœud. Rechercher, insérer et supprimer suivent donc un seul chemin depuis la racine et demandent au plus h + 1 comparaisons, où h est la hauteur. Un ordre d’insertion aléatoire donne des arbres bas, mais des clés triées produisent une chaîne aussi lente qu’une recherche séquentielle. Les parcours visitent chaque nœud une fois : les parcours en profondeur utilisent la pile d’appels d’une fonction récursive, le parcours en largeur une file, et sur un arbre d’expression ils donnent les notations préfixe, infixe et postfixe.

Mode d’emploi

En mode Arbre binaire de recherche, saisissez une Clé et cliquez sur Insérer, Rechercher ou Supprimer ; les comparaisons s’affichent pas à pas. Choisissez un Ordre d’insertion et un Nombre de clés, puis cliquez sur Nouvel arbre pour ajouter une ligne au tableau comparatif. En mode Parcours d’arbre, choisissez un Parcours et cliquez sur Lecture ou Pas à pas. En mode Arbre d’expression, choisissez une expression ou saisissez la vôtre.

Paramètres modifiables

  • Mode Arbre binaire de recherche, Parcours d’arbre, Arbre d’expression
  • Ordre d’insertion initial Aléatoire, Croissant (trié), Clé médiane d’abord (équilibré)
  • Nombre initial de clés 3–15 clés
  • Clés initiales à insérer (nombres de 1 à 99, ex. 50 30 70 ; vide = générées)
  • Parcours Préfixe (NLR), Infixe (LNR), Suffixe (LRN), En largeur (BFS)
  • Expression d’exemple (3 + 4) * 5, 3 + 4 * 5, (8 - 2) / (1 + 2), 2 * (x + 3) - y / 4, (a + b) * (c - d) ^ 2, Personnalisée
  • Expression personnalisée (vide = expression d’exemple)
  • Vitesse d’exécution 0,5–4 pas/s

Questions à explorer

  1. Quelle hauteur a l’arbre après l’insertion de sept clés dans l’ordre croissant, et combien de comparaisons faut-il pour trouver la plus grande ?
  2. Pourquoi le parcours infixe d’un arbre binaire de recherche donne-t-il toujours les clés dans l’ordre croissant ?
  3. Comment écrit-on (3 + 4) * 5 en notation postfixe, et pourquoi les parenthèses y sont-elles inutiles ?

Simulations associées