Arbre de recherche binaire

Sur l’image

1. 1Disque racine : la première clé comparée
2. 2Fil gauche : la recherche va à gauche car la clé cible est plus petite
3. 3Disque enfant gauche : la clé suivante comparée
4. 4Disque inférieur gauche : une clé feuille au bout du trajet lumineux

Exemples

• Chercher un mot dans un dictionnaire papier
• Suivre des choix dans un arbre de compétences de jeu vidéo

Quiz : Arbre de recherche binaire (17 ans)

1. 1

   Dans un arbre binaire de recherche, où se trouvent les clés plus petites qu’un nœud ?

   • Dans le sous-arbre droit de ce nœud
   • Dans le sous-arbre gauche de ce nœud
   • Seulement à la racine
2. 2

   Pendant une recherche dans un arbre binaire de recherche, qu’est-ce qui détermine si l’on va à gauche ou à droite après avoir comparé la cible à un nœud ?

   • Si la clé cible est plus petite ou plus grande que la clé du nœud actuel
   • Si la recherche a déjà visité l’enfant gauche
   • Si le nœud actuel est la racine ou une feuille
3. 3

   Qu’est-ce que chaque comparaison écarte lors d’une recherche dans un arbre binaire de recherche ?

   • Toutes les clés à la même profondeur
   • Tout un côté de l’arbre
   • Seulement le nœud actuel

Les réponses, avec leur explication, sont dans l’application. Cette leçon est sortie de la semaine en accès libre : son quiz fait partie de l’abonnement.