Plus petit à gauche, plus grand à droite

Sur l’image

1. 1La racine : la première clé à laquelle toute recherche compare
2. 2Enfant gauche : plus petit que la racine, donc placé à gauche
3. 3Enfant droit : plus grand que la racine, donc placé à droite
4. 4Une feuille du sous-arbre droit : plus grande que la racine mais plus petite que son parent, donc à gauche de celui-ci

Exemples

• Deviner un nombre entre 1 et 100 quand chaque réponse est « plus » ou « moins » élimine la moitié des possibilités restantes
• Chercher un mot dans un dictionnaire papier en l’ouvrant au milieu, puis en allant avant ou après

Quiz : Plus petit à gauche, plus grand à droite (17 ans)

1. 1

   Dans un arbre binaire de recherche, quelles clés peuvent se trouver n’importe où dans le sous-arbre gauche d’un nœud dont la clé est 50 ?

   • Des clés plus petites que 50 juste sous le nœud, mais n’importe quelle clé plus bas
   • Uniquement des clés plus petites que 50
   • N’importe quelles clés, tant que l’enfant gauche direct du nœud est plus petit que 50
2. 2

   Un arbre binaire de recherche a pour racine 50, et l’enfant droit de la racine est 80. Où va une nouvelle clé 60 ?

   • Dans le sous-arbre droit, à gauche de 80
   • Dans le sous-arbre droit, à droite de 80
   • Dans le sous-arbre gauche, car 60 est plus petit que 80
3. 3

   Quand on cherche une clé dans un arbre binaire de recherche bien équilibré, combien de nœuds vérifie-t-on à peu près ?

   • Tous les nœuds de l’arbre
   • Tous les nœuds d’un niveau avant de descendre au suivant
   • Environ un nœud par niveau

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.