Zum Inhalt
Alle Apps

Suchbaum-Werkstatt

Über diese App

Zahlen in einen binären Suchbaum einfügen, suchen und löschen: Der Vergleichsweg leuchtet Knoten für Knoten mit dem Satz der Folien (‚22 > 21: rechts‘). Darunter läuft der Zeiger einer sortierten verketteten Liste mit, zwei Zähler vergleichen Baum und Liste. Die Knoten stehen in Inorder-Reihenfolge und rücken beim Einfügen nur zur Seite. 1 2 3 4 5 lässt den Baum zur Liste entarten (Tiefe 5 statt 3). Dazu die drei Löschfälle, eine Objektansicht mit Knoten-Karten und die Übungen max, tiefe und Suchbaum von Hand.

Wie ein binärer Suchbaum ordnet

In einem binären Suchbaum liegen alle kleineren Werte im linken, alle größeren im rechten Teilbaum eines Knotens. Zum Suchen oder Einfügen vergleicht man ab der Wurzel und geht je nach Ergebnis nach links oder rechts. Ist der Baum ausgeglichen, braucht das etwa log₂(n) Vergleiche. Fügt man die Werte aber in sortierter Reihenfolge ein, entartet der Baum zu einer Liste, und die Suche wird so langsam wie in einer verketteten Liste. Ein Inorder-Durchlauf gibt die Werte immer sortiert aus.

Was die App zeigt

Die Knoten stehen nach ihrer Inorder-Position nebeneinander und nach ihrer Tiefe übereinander; beim Einfügen rücken sie deshalb nur zur Seite. Der Vergleichsweg leuchtet Knoten für Knoten, dazu Sätze wie „22 > 21: rechts“. Darunter läuft der Zeiger einer sortierten verketteten Liste mit denselben Werten mit, Balken vergleichen die Zahl der Vergleiche. Anzeigen nennen Knotenzahl, Tiefe und die bestmögliche Tiefe.

Selbst ausprobieren

Füge Zahlen von 1 bis 99 einzeln oder als ganze Folge ein, suche und lösche sie; sieben Folgen stehen bereit. Gib 1 2 3 4 5 ein und sieh, wie der Baum zur Liste entartet: Tiefe 5 statt 3. Die drei Löschfälle (Blatt, ein Kind, zwei Kinder) lassen sich einzeln abspielen. Eine Objektansicht zeigt die Knoten als Karten mit Pfeilen, das Code-Panel den laufenden Python-Code, und Aufgaben zu Inorder, Maximum und Tiefe vertiefen das Thema.

Häufige Fragen

Was ist ein binärer Suchbaum?
Ein Binärbaum, in dem für jeden Knoten gilt: Alle Werte im linken Teilbaum sind kleiner, alle im rechten größer. Dadurch kann man beim Suchen an jedem Knoten eine Hälfte ausschließen, ähnlich wie bei der binären Suche im sortierten Array.
Warum kann ein binärer Suchbaum entarten?
Die Form hängt von der Einfügereihenfolge ab. Kommen die Werte sortiert, etwa 1, 2, 3, 4, 5, hängt jeder neue Knoten rechts am vorigen. Der Baum wird zur Kette mit Tiefe n, und Suchen kostet O(n) statt O(log n). Selbstbalancierende Bäume wie AVL- oder Rot-Schwarz-Bäume verhindern das.
Wie löscht man einen Knoten aus einem binären Suchbaum?
Ein Blatt wird einfach entfernt. Hat der Knoten ein Kind, rückt dieses an seine Stelle. Hat er zwei Kinder, ersetzt man seinen Wert durch den nächstgrößeren Wert (das Minimum des rechten Teilbaums) und löscht diesen dort.
Was kann ich in der Suchbaum-Werkstatt ausprobieren?
Einfügen, Suchen und Löschen mit leuchtendem Vergleichsweg, den Vergleich mit einer sortierten Liste, entartete Bäume, die drei Löschfälle, eine Objektansicht mit Knoten-Karten und Übungen zu Inorder, Maximum und Tiefe.

Fach: Informatik

Mehr aus Informatik

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps