Aller au contenu
Algorithmique avancée et structures de données · L2

Leçon 4 sur 5

Arbres binaires et arbres binaires de recherche

Je sais représenter un arbre binaire en Python, le parcourir dans les quatre ordres classiques, et utiliser un arbre binaire de recherche pour rechercher, insérer et supprimer une clé en un temps proportionnel à sa hauteur.

  • 1 h 30
  • 5 exercices corrigés
  • QCM de 6 questions

À la fin de la leçon, vous saurez :

  • Utiliser le vocabulaire des arbres (racine, feuille, hauteur, sous-arbre)
  • Écrire les parcours préfixe, infixe, postfixe et en largeur
  • Calculer récursivement la taille et la hauteur d'un arbre
  • Rechercher, insérer et supprimer une clé dans un arbre binaire de recherche
  • Relier le coût des opérations à la hauteur et expliquer le cas dégénéré

Avant de commencer : Leçons 1 à 3 (listes chaînées, piles et files, récursivité).

1Je découvre

Le service de la scolarité d'une université de Conakry conserve les dossiers de 12 000 étudiants, rangés par matricule. Quand un étudiant se présente au guichet, l'agent parcourt la liste depuis le début : en moyenne, il examine des milliers de dossiers avant de trouver le bon. Trier la liste et faire une recherche dichotomique accélérerait la recherche, mais chaque nouvel inscrit obligerait à décaler une grande partie du tableau.

Mamadou propose une structure intermédiaire : chaque dossier « connaît » deux autres dossiers, l'un de matricule plus petit, l'autre de matricule plus grand. À chaque comparaison, l'agent élimine d'un coup toute une partie des dossiers, comme dans la dichotomie, et un nouvel inscrit se range sans rien décaler.

Comment organiser des données en arbre pour combiner une recherche rapide et des insertions faciles, et comment parcourir un tel arbre ?

La suite se lit avec votre compte Kharandi Université

La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.

Voir toutes les leçons de Algorithmique avancée et structures de données

Signaler une erreur dans cette leçon

Toutes les leçons de Algorithmique avancée et structures de données

Pose ta question à Karamö