Binärer Suchbaum – Visualisierung
Sieh genau, wie sich ein binärer Suchbaum beim Einfügen, Löschen und Suchen verändert. Wechsle zwischen einem einfachen BST, einem selbstbalancierenden AVL-Baum und einem Rot-Schwarz-Baum, verfolge jeden Vergleich, jede Rotation und jede Umfärbung Schritt für Schritt als Animation und durchlaufe den Baum in In-Order, Pre-Order, Post-Order oder Ebene für Ebene.
Zuletzt aktualisiert:
Der Baum ist leer. Füge einen Wert ein oder erzeuge einen Zufallsbaum.
Baumstatistik
Traversierungsausgabe
Schrittprotokoll
Liste von Werten einfügen
Ganze Zahlen von -999 bis 9999, getrennt durch Kommas oder Leerzeichen. Duplikate werden übersprungen. Bis zu 63 Knoten. Das Einfügen von 10, 20, 30 … in Reihenfolge zeigt, warum einfache BSTs ausbalanciert werden müssen.
Anleitung: Binärer Suchbaum – Visualisierung
- Wähle einen Baumtyp: binärer Suchbaum, AVL-Baum oder Rot-Schwarz-Baum. Deine Werte werden in der neuen Struktur neu aufgebaut.
- Gib eine ganze Zahl ein und klicke auf Einfügen, Löschen oder Suchen. Jeder Vergleich wird unter dem Baum hervorgehoben und erklärt.
- Verfolge das Ausbalancieren: AVL-Bäume zeigen Balancefaktoren und rotieren, sobald einer ±2 erreicht; Rot-Schwarz-Bäume färben um und rotieren, um ihre Farbregeln einzuhalten.
- Klicke auf eine Traversierungs-Schaltfläche, um die Knoten in In-Order, Pre-Order, Post-Order oder Level-Order zu besuchen und die Folge zu kopieren.
- Öffne „Liste von Werten einfügen“, um einen Baum aus vielen Zahlen auf einmal zu erstellen, und lade ihn dann als SVG-Bild herunter.
Zeitkomplexität binärer Suchbäume
| Baum | Suche | Einfügen | Löschen | Höhe im schlechtesten Fall | Rotationen pro Einfügen |
|---|---|---|---|---|---|
| Binärer Suchbaum (unbalanciert) | O(h), schlechtester Fall O(n) | O(h), schlechtester Fall O(n) | O(h), schlechtester Fall O(n) | n − 1 | 0 |
| AVL-Baum | O(log n) | O(log n) | O(log n) | etwa 1.44·log₂(n + 2) | Höchstens 1 Einfach- oder Doppelrotation |
| Rot-Schwarz-Baum | O(log n) | O(log n) | O(log n) | 2·log₂(n + 1) | Höchstens 2 |
h ist die Höhe des Baums und n die Anzahl der Schlüssel. Ein perfekt balancierter Baum mit n Schlüsseln hat eine Höhe von ⌈log₂(n + 1)⌉ − 1 Kanten; das Statistikfeld zeigt dies als „Bestmöglich“, damit du es mit dem aktuellen Baum vergleichen kannst.
Die vier AVL-Rotationsfälle
| Fall | Wann er auftritt | Korrektur | Zum Ausprobieren einfügen |
|---|---|---|---|
| Links-Links | Knoten ist +2 und sein linkes Kind ist 0 oder +1 | Einfache Rechtsrotation am Knoten | 30, 20, 10 |
| Rechts-Rechts | Knoten ist −2 und sein rechtes Kind ist 0 oder −1 | Einfache Linksrotation am Knoten | 10, 20, 30 |
| Links-Rechts | Knoten ist +2 und sein linkes Kind ist −1 | Linksrotation am Kind, dann Rechtsrotation am Knoten | 30, 10, 20 |
| Rechts-Links | Knoten ist −2 und sein rechtes Kind ist +1 | Rechtsrotation am Kind, dann Linksrotation am Knoten | 10, 30, 20 |
Tipps zum Lernen mit der Visualisierung
- Entartung sehen: Leere den Baum, wähle „Binärer Suchbaum“ und füge 10, 20, 30, 40, 50 der Reihe nach ein. Wechsle dann zu AVL, um dieselben Schlüssel mit Höhe 2 statt 4 neu aufgebaut zu sehen.
- Rot-Schwarz-Umfärbung: Füge 10, 20, 30, 15, 25, 5 in einen leeren Rot-Schwarz-Baum ein, um eine Rotation gefolgt von Umfärbungsfällen mit rotem Onkel zu sehen.
- Löschfälle: Lösche ein Blatt, einen Knoten mit einem Kind und einen Knoten mit zwei Kindern, um die drei Löschfälle im BST zu vergleichen.
- Hausaufgaben prüfen: Gib die Schlüssel aus einer Übung unter „Liste von Werten einfügen“ ein und vergleiche jede Traversierung mit deiner eigenen Lösung.
Häufige Fragen
Was ist ein binärer Suchbaum?
Ein binärer Suchbaum (BST) ist ein Binärbaum, in dem der Schlüssel jedes Knotens größer ist als alle Schlüssel in seinem linken Teilbaum und kleiner als alle Schlüssel in seinem rechten Teilbaum. Durch diese Ordnung findest, fügst oder löschst du einen Schlüssel, indem du einem einzigen Pfad von der Wurzel folgst – jede Operation dauert also proportional zur Höhe des Baums.
Warum müssen BSTs ausbalanciert werden?
Kommen die Schlüssel in sortierter Reihenfolge, entartet ein einfacher BST zu einer verketteten Liste der Höhe n − 1, und die Suche wird O(n). Selbstbalancierende Bäume wie AVL- und Rot-Schwarz-Bäume strukturieren sich mit Rotationen um, sodass die Höhe O(log n) bleibt und Suchen, Einfügen und Löschen auch im schlechtesten Fall schnell sind.
Was ist der Unterschied zwischen einem AVL-Baum und einem Rot-Schwarz-Baum?
Ein AVL-Baum hält die Höhen der beiden Teilbäume jedes Knotens höchstens 1 auseinander, ist also strenger balanciert (Höhe höchstens etwa 1.44·log₂ n), und Suchen sind etwas schneller. Ein Rot-Schwarz-Baum nutzt Knotenfarben und erlaubt eine Höhe bis 2·log₂(n + 1), braucht aber beim Einfügen und Löschen weniger Rotationen. Viele Standardbibliotheken verwenden Rot-Schwarz-Bäume für geordnete Maps und Sets.
Wie funktioniert das Löschen eines Knotens mit zwei Kindern?
Der Knoten wird durch seinen In-Order-Nachfolger ersetzt, den kleinsten Schlüssel in seinem rechten Teilbaum. Der Nachfolger hat kein linkes Kind, lässt sich also leicht aushängen und an die Stelle des gelöschten Knotens setzen. So bleibt die BST-Ordnung erhalten. (Der In-Order-Vorgänger, der größte Schlüssel im linken Teilbaum, funktioniert genauso gut.)
Was bedeutet der Balancefaktor?
In einem AVL-Baum ist der Balancefaktor eines Knotens Höhe(linker Teilbaum) − Höhe(rechter Teilbaum). Gültige AVL-Knoten haben einen Balancefaktor von −1, 0 oder +1. Wird er durch Einfügen oder Löschen +2 oder −2, führt der Baum an diesem Knoten eine Einfach- oder Doppelrotation aus, um die Balance wiederherzustellen.
Welche Traversierung liefert die Schlüssel in sortierter Reihenfolge?
Die In-Order-Traversierung (linker Teilbaum, Knoten, rechter Teilbaum) besucht die Schlüssel eines binären Suchbaums in aufsteigender Reihenfolge. Pre-Order (Knoten zuerst) eignet sich zum Kopieren oder Serialisieren eines Baums, Post-Order (Knoten zuletzt) zum Löschen oder zum Auswerten von Ausdrucksbäumen, und Level-Order besucht den Baum Ebene für Ebene mithilfe einer Warteschlange.
Welche Regeln gelten für Rot-Schwarz-Bäume?
Jeder Knoten ist rot oder schwarz, die Wurzel ist schwarz, ein roter Knoten hat nie ein rotes Kind, und jeder Pfad von einem Knoten hinunter zu einem leeren (nil) Blatt führt durch gleich viele schwarze Knoten – die sogenannte Schwarzhöhe. Leere Blätter zählen als schwarz. Diese Regeln garantieren, dass der längste Pfad höchstens doppelt so lang ist wie der kürzeste.
Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?
Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.