Kleiner links, größer rechts

Auf dem Bild

1. 1Die Wurzel: der erste Schlüssel, mit dem jede Suche vergleicht
2. 2Linkes Kind: kleiner als die Wurzel, deshalb links
3. 3Rechtes Kind: größer als die Wurzel, deshalb rechts
4. 4Ein Blatt im rechten Teilbaum: größer als die Wurzel, aber kleiner als sein Elternknoten, deshalb links von diesem

Beispiele

• Beim Raten einer Zahl von 1 bis 100 mit den Antworten „höher“ oder „tiefer“ fällt jedes Mal die Hälfte des Rests weg
• Ein Wort in einem gedruckten Wörterbuch suchen, indem man es in der Mitte aufschlägt und dann vor- oder zurückblättert

Quiz: Kleiner links, größer rechts (Alter 17)

1. 1

   Welche Schlüssel dürfen in einem binären Suchbaum irgendwo im linken Teilbaum eines Knotens mit dem Schlüssel 50 stehen?

   • Schlüssel kleiner als 50 direkt unter dem Knoten, weiter unten aber beliebige
   • Nur Schlüssel, die kleiner als 50 sind
   • Beliebige Schlüssel, solange das direkte linke Kind des Knotens kleiner als 50 ist
2. 2

   Ein binärer Suchbaum hat die Wurzel 50, und das rechte Kind der Wurzel ist 80. Wohin kommt ein neuer Schlüssel 60?

   • In den rechten Teilbaum, links von 80
   • In den rechten Teilbaum, rechts von 80
   • In den linken Teilbaum, weil 60 kleiner als 80 ist
3. 3

   Wie viele Knoten prüfst du ungefähr, wenn du in einem gut ausbalancierten binären Suchbaum nach einem Schlüssel suchst?

   • Jeden Knoten im Baum
   • Jeden Knoten einer Ebene, bevor du zur nächsten hinabgehst
   • Etwa einen Knoten pro Ebene

Die Antworten mit Erklärung stehen in der App. Diese Lektion hat die freie Woche verlassen, ihr Quiz gehört deshalb zum Abo.