Kleiner links, groter rechts

Op de afbeelding

1. 1De wortel: de eerste sleutel waarmee elke zoektocht vergelijkt
2. 2Linkerkind: kleiner dan de wortel, dus links
3. 3Rechterkind: groter dan de wortel, dus rechts
4. 4Een blad in de rechterdeelboom: groter dan de wortel maar kleiner dan zijn ouder, dus links van die ouder

Voorbeelden

• Een getal van 1 tot 100 raden met als antwoord steeds "hoger" of "lager" schrapt telkens de helft van wat overblijft
• Een woord opzoeken in een papieren woordenboek door het in het midden open te slaan en dan naar voren of naar achteren te bladeren

Quiz: Kleiner links, groter rechts (17 jaar)

1. 1

   Welke sleutels mogen in een binaire zoekboom ergens in de linkerdeelboom staan van een knoop met sleutel 50?

   • Sleutels kleiner dan 50 direct onder de knoop, maar dieper elke sleutel
   • Alleen sleutels kleiner dan 50
   • Willekeurige sleutels, zolang het directe linkerkind van de knoop kleiner is dan 50
2. 2

   Een binaire zoekboom heeft wortel 50, en het rechterkind van de wortel is 80. Waar komt een nieuwe sleutel 60?

   • In de rechterdeelboom, links van 80
   • In de rechterdeelboom, rechts van 80
   • In de linkerdeelboom, omdat 60 kleiner is dan 80
3. 3

   Hoeveel knopen controleer je ongeveer als je in een goed gebalanceerde binaire zoekboom naar een sleutel zoekt?

   • Elke knoop in de boom
   • Elke knoop op een niveau voordat je naar het volgende afdaalt
   • Ongeveer één knoop per niveau

De antwoorden, met uitleg, staan in de app. Deze les is uit de vrije week, dus de quiz hoort bij het abonnement.