MINT lernen

Suchen im binären Suchbaum

Zehn Übungen zur Suchbaum-Eigenschaft, zu Suchpfaden und zum Aufwand.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.

A1
Suchbaum oder nicht?
AFB I

Die Bäume sind in der Schreibweise Wurzel(links, rechts) notiert, ∅ ist ein leerer Baum. Gib für jeden Baum an, ob er ein binärer Suchbaum ist.

Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1Suchbaum
2kein Suchbaum
Fallen sind 8(3(1, 9), 12) und 8(3, 12(7, 15)): Die 9 steht im linken Teilbaum von 8, die 7 im rechten — die Ordnung gilt für ganze Teilbäume, nicht nur für direkte Kinder.
Ansatz: Prüfe nicht nur Elternknoten und Kind, sondern jeden Knoten gegen alle seine Vorfahren.
Weiter: Alles im linken Teilbaum von 8 muss kleiner als 8 sein — auch die Enkel.
A2
Stimmt's? — Suchen in s
AFB I

Lies am Suchbaum s ab, ob die Aussagen stimmen.

Suchbaum s
1120262932415065729199
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Jeder Vergleich schließt einen ganzen Teilbaum aus — deshalb berührt die Suche nie beide Seiten.
Ansatz: Fahre den Suchpfad mit dem Finger nach.
Weiter: Zähle nur Vergleiche mit Knoten, nicht den leeren Baum am Ende.
A3
Der Suchalgorithmus in Worten
AFB I

Nenne die fehlenden Begriffe im Suchalgorithmus.

Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück.

Die Suche vergleicht x zuerst mit der . Ist x kleiner, geht sie im Teilbaum weiter, ist x größer, im Teilbaum. Erreicht sie einen , kommt x nicht vor. Sie braucht höchstens so viele Vergleiche, wie die des Baums angibt.

„Blatt“ passt nicht: Auch unter einem Blatt geht die Suche noch einen Schritt weiter — in einen leeren Teilbaum.
Ansatz: Die vier Fälle stehen in der Merke-Box.
Weiter: Die Suche endet erfolglos nicht an einem Blatt, sondern darunter.
A4
Vergleiche zählen
AFB II

Bestimme für den Suchbaum s aus A2 die Anzahl der Vergleiche mit Knoten.

Suchbaum s
1120262932415065729199
Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Suche nach 26 Vergleiche
  2. Suche nach 72 Vergleiche
  3. Suche nach 45 (fehlt) Vergleiche
  4. Suche nach 10 (fehlt) Vergleiche
26: 41, 20, 29, 26. 72: 41, 65, 91, 72. 45: 41, 65, 50 — dann der leere linke Teilbaum von 50. 10: 41, 20, 11 — dann der leere linke Teilbaum von 11.
Ansatz: Schreib den Suchpfad als Kette auf.
Weiter: Eine erfolglose Suche zählt nur die Knoten bis zum letzten Blatt.
A5
Suchpfad ordnen
AFB II

Im Suchbaum s aus A2 wird die 30 gesucht. Stelle den Suchpfad dar, indem du die Stationen in die richtige Reihenfolge bringst.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1 41
2 20
3 29
4 32
5 leerer Baum links von 32
30 < 41 → links, 30 > 20 → rechts, 30 > 29 → rechts, 30 < 32 → links: leerer Baum, 30 kommt nicht vor. Beim Einfügen (5.3.4) würde 30 genau dort landen.
Ansatz: Beginne an der Wurzel.
Weiter: Bei jedem Knoten: kleiner → links, größer → rechts.
A6
Reihung oder Suchbaum?
AFB II

1023 Kundennummern sollen durchsucht werden: einmal unsortiert in einer DynArray mit linearer Suche, einmal in einem ausgeglichenen Suchbaum der Höhe 10. Vergleiche die Anzahl der Vergleiche im ungünstigsten Fall.

Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. lineare Suche in der DynArray Vergleiche
  2. Suche im ausgeglichenen Suchbaum Vergleiche
  3. Faktor (gerundet auf ganze Zahl)
Die lineare Suche muss im ungünstigsten Fall alle 1023 Elemente ansehen. Der Suchbaum braucht höchstens h = 10 Vergleiche, weil 210 − 1 = 1023. Das ist etwa 102-mal weniger.
Ansatz: Linear: jedes Element einmal. Baum: ein Vergleich pro Ebene.
Weiter: Faktor = 1023 : 10, auf eine ganze Zahl gerundet.
A7
Fall und Folge
AFB II

Ordne jedem Fall der Suche nach x die passende Folge zu.

Klicke links ein Element an und dann rechts das passende — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Die Reihenfolge der Prüfung ist wichtig: Zuerst isEmpty(), sonst liefert getItem() auf dem leeren Baum einen Laufzeitfehler.
Ansatz: Überlege für jeden Fall, was die Methode enthaelt tut.
Weiter: Das kleinste Element hat keinen linken Nachbarn mehr.
A8
Suchen ohne Rekursion
AFB III

Die Methode soll iterativ prüfen, ob x im Suchbaum b vorkommt. Überprüfe sie und markiere die fehlerhaften Zeilen.

In diesem Code stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Die Schleife ersetzt die Rekursion: b wandert als Variable den Suchpfad hinab. Sie endet mit return true beim Treffer oder am leeren Baum.
Ansatz: Setze ein Beispiel ein: x ist kleiner als die Wurzel.
Weiter: Wann wird die Schleife verlassen, ohne dass return true ausgeführt wurde?
A9
Die längste erfolglose Suche
AFB III

Analysiere den Suchbaum s aus A2: Wie viele Vergleiche mit Knoten braucht eine erfolglose Suche dort höchstens?

Rechne selbst und trage das Ergebnis ein — Enter prüft direkt.
Höchstens 4 — so viele Ebenen hat s. Wer 5 antwortet, zählt den leeren Baum mit: Dort wird aber kein Wert verglichen, nur isEmpty() geprüft.
Ansatz: Die erfolglose Suche endet unter einem Blatt.
Weiter: Die tiefsten Blätter liegen auf Ebene 4 — der leere Baum darunter enthält keinen Wert zum Vergleichen.
A10
Werte austauschen
AFB III

Im Suchbaum s aus A2 soll jeweils ein Wert mit setItem ersetzt werden. Beurteile, nach welchen Änderungen s noch ein Suchbaum ist.

Suchbaum s
1120262932415065729199
Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Jeder Knoten hat einen erlaubten Bereich aus seinen Vorfahren: 26 liegt zwischen 20 und 29, 32 zwischen 29 und 41, 99 über 91. Die 50 muss zwischen 41 und 65 liegen, die 11 unter 20, die 72 zwischen 65 und 91.
Ansatz: Schreib für jeden Knoten auf, zwischen welchen Werten er liegen muss.
Weiter: Die Grenzen kommen von allen Vorfahren, bei denen der Pfad links oder rechts abbiegt.