Binärer Suchbaum
Binärer Suchbaum ist ein interaktives Experiment in Datenstrukturen, einer kostenlosen Simulation aus dem StudyFi Lab, die direkt im Browser läuft.
An jedem Knoten gilt: Kleinere Werte stehen links, größere rechts. Suchen und Einfügen folgen daher einem einzigen Pfad ab der Wurzel und kosten O(h), wobei h die Baumhöhe ist – bei einem ausgeglichenen Baum h ≈ log₂ n. Löschen hat drei Fälle: Ein Blatt verschwindet einfach, ein Knoten mit einem Kind wird durch dieses ersetzt, und ein Knoten mit zwei Kindern übernimmt den Wert seines In-Order-Nachfolgers. Die In-Order-Traversierung liefert die Werte sortiert; ähnliche Bäume stecken in Datenbankindizes.
Probier das: Lösche die Wurzel – sie hat zwei Kinder, also siehst du die Nachfolgersuche. Probiere dann „Sortierte Werte einfügen“: Der Baum entartet zur Liste und die Höhe wächst auf n.
Häufige Fragen
Was zeigt das Experiment „Binärer Suchbaum“?
An jedem Knoten gilt: Kleinere Werte stehen links, größere rechts. Suchen und Einfügen folgen daher einem einzigen Pfad ab der Wurzel und kosten O(h), wobei h die Baumhöhe ist – bei einem ausgeglichenen Baum h ≈ log₂ n. Löschen hat drei Fälle: Ein Blatt verschwindet einfach, ein Knoten mit einem Kind wird durch dieses ersetzt, und ein Knoten mit zwei Kindern übernimmt den Wert seines In-Order-Nachfolgers. Die In-Order-Traversierung liefert die Werte sortiert; ähnliche Bäume stecken in Datenbankindizes.
Wie probiere ich „Binärer Suchbaum“ aus?
Lösche die Wurzel – sie hat zwei Kinder, also siehst du die Nachfolgersuche. Probiere dann „Sortierte Werte einfügen“: Der Baum entartet zur Liste und die Höhe wächst auf n.
Lernst du für eine Prüfung?
Lade deine Notizen hoch und StudyFi macht daraus Karteikarten, Tests und Podcasts.