Aller au contenu
Head of Science
L'arbre binaire de rechercheChapitre 9/12

Le jeu du plus ou moins

Je pense à un nombre entre 1 et 100. Tu proposes 50, je réponds « plus petit ». Tu viens d'éliminer la moitié des possibilités d'un coup. Tu proposes 25, « plus grand »... En 7 questions maximum, tu trouves.

Un arbre binaire de recherche (ABR) range les nombres pour que chaque nœud joue ce rôle de question. La règle, valable pour chaque nœud :

  • toutes les valeurs de son sous-arbre gauche sont plus petites que lui ;
  • toutes les valeurs de son sous-arbre droit sont plus grandes que lui.
20304050607080

50 est à la racine. À sa gauche, 30, 20 et 40 : tous plus petits que 50. À sa droite, 70, 60 et 80 : tous plus grands. Et la règle se vérifie aussi sous 30 (20 à gauche, 40 à droite) et sous 70.

DéfinitionUn arbre binaire de recherche
Programme complet du cours structures de données (12 chapitres, gratuit)
  1. 1. Ranger des données dans la mémoire : La RAM est un gros tableau de cases numérotées de 0 à N - 1 : 8 milliards pour 8 Go. Impossible de tout relire pour trouver une donnée, d'où les structures de données : un ordre connu à l'avance et des règles pour y accéder. Interface et implémentation.
  2. 2. Le tableau : des cases côte à côte : Des cases contiguës numérotées : accès direct par l'indice en une seule étape, mais insérer ou supprimer au début oblige à tout décaler.
  3. 3. La liste chaînée : des maillons reliés : Des maillons éparpillés dans la mémoire, chacun connaît l'adresse du suivant : insérer ou supprimer revient à raccrocher une flèche, mais lire le 100e oblige à passer par les 99 premiers.
  4. 4. La pile : dernier arrivé, premier sorti : La pile d'assiettes : on pose en haut, on prend en haut. Empiler, dépiler, sommet, LIFO, et une pile en Python avec append et pop.
  5. 5. La file : premier arrivé, premier servi : La file d'attente : on arrive à la fin, on sort par le début. Enfiler, défiler, FIFO, la différence avec la pile, et une file en Python.
  6. 6. Devine la structure : Le retour d'Insta, Ctrl+Z, la file d'impression, la playlist « à suivre », le distributeur de Pez, la pile d'appels : reconnaître la structure cachée derrière des situations réelles.
  7. 7. Les arbres : ranger en hiérarchie : Arborescence de fichiers, arbre généalogique, tournoi : une racine, des nœuds, des feuilles. Vocabulaire, hauteur, taille et arbre binaire.
  8. 8. Parcourir un arbre : Visiter tous les nœuds d'un arbre, chacun une fois : le parcours en largeur (avec une file), et les parcours en profondeur préfixe, infixe et suffixe.
  9. 9. L'arbre binaire de recherche : Plus petit à gauche, plus grand à droite : chercher une valeur en éliminant la moitié de l'arbre à chaque comparaison, insérer, et pourquoi l'arbre doit rester équilibré.
  10. 10. Pile et file en programmation objet : Écrire les classes Pile et File, puis une file fabriquée avec deux piles : même interface, autre implémentation.
  11. 11. La liste chaînée en programmation objet : Les classes Maillon et ListeChainee : ajouter en tête, parcourir, compter, lire le k-ième, ajouter en queue, supprimer. Puis une pile implémentée par une liste chaînée.
  12. 12. Les arbres en programmation objet : La classe Noeud, la récursivité pour la taille et la hauteur, les parcours préfixe, infixe, suffixe et en largeur, puis l'insertion et la recherche dans un ABR.