AVL- und Rot-Schwarz-Bäume

1–31 vorzeichenbehaftete ganze Dezimalzahlen von −9999 bis 9999 einfügen, insgesamt höchstens 512 Zeichen. Kommas oder Leerraum trennen Schlüssel; leere Kommaeinträge und ein abschließendes Komma sind ungültig. Führende Nullen und ein optionales Pluszeichen sind erlaubt. Dezimalpunkte, Exponenten, Hexadezimalschreibweise und unvollständige Zahlen werden abgelehnt. Doppelte Schlüssel werden gelesen, aber übersprungen: Der Baum stellt eine Menge dar.

Schritt zeigt eine tatsächliche Operation: einen neuen Knoten anhängen, eine einzelne Links- oder Rechtsrotation, eine Gruppe von Farbwechseln, den Abschluss einer Einfügung oder ein übersprungenes Duplikat. Eine Doppelrotation hat zwei getrennte Rotationsbilder. Der Rotationszähler zählt einzelne Rotationen; der Farbwechselzähler zählt Gruppen tatsächlich geänderter Farben, einschließlich der Wiederherstellung einer schwarzen Wurzel. „Schlüssel gelesen“ zählt den aktuellen Schlüssel bereits ab seinem Einfügebild. „Verschiedene Schlüssel“ zählt ohne Duplikate.

Rotationen erhalten die Suchbaumordnung: Links stehen kleinere, rechts größere Schlüssel. Inorder listet sie von links nach rechts. Die AVL-Balance ist linke Höhe minus rechte Höhe und liegt nach jeder abgeschlossenen Einfügung zwischen −1 und 1. Hier hat ein leerer Teilbaum die Höhe 0, ein Blatt die Höhe 1.

Die Rot-Schwarz-Variante verwendet die klassische Einfügereparatur, nicht die linkslehnende Variante. Wurzel und nicht gezeichnete NIL-Blätter sind schwarz; rote Knoten haben keine roten Kinder; jeder Pfad von einem Knoten zu einem NIL-Blatt hat gleich viele schwarze Knoten. Die Knotentabelle zählt den aktuellen Knoten mit, wenn er schwarz ist, sowie das abschließende NIL-Blatt. NIL allein hat somit Schwarzhöhe 1. Ein Strich kennzeichnet ungleiche Schwarzhöhen während einer Reparatur. Farbbuchstaben ergänzen die Knotenfarben.

Zwischenbilder dürfen Balance- oder Rot-Schwarz-Eigenschaften vorübergehend verletzen. Die Zusammenfassung bestätigt sie nur nach einer abgeschlossenen Einfügung oder einem Duplikat. Umrandungen markieren betroffene Knoten; ein gestrichelter Rand markiert die alte Teilbaumwurzel einer Rotation. Das aufgerückte Kind und eine gegebenenfalls verschobene Teilbaumwurzel werden unter der Aktion benannt.

Start setzt einen pausierten Ablauf fort und beginnt einen abgeschlossenen Ablauf neu. Zurück und Schritt zeigen einzelne Operationen in beide Richtungen. Leeren leert den Ablauf und erhält die Eingaben. Änderungen an Folge oder Baumtyp verwerfen das alte Ergebnis. RB-Reparatur wählt Rot-Schwarz; andere Beispiele erhalten den Typ. Enter fügt einen Zeilenumbruch ein; Strg/Command+Enter startet. Rohe Eingaben, Auswahl, Tempo, Detailbereiche und aktueller Schritt werden lokal gespeichert, auch unfertige Entwürfe. Neuladen oder Rückkehr innerhalb der App stellt einen gültigen Schritt pausiert wieder her; die Wiedergabe startet nie automatisch. Große Bäume lassen sich lokal verschieben, ohne Beschriftungen zu verkleinern. Balanciertes Einfügen benötigt O(log n); unabhängige Zustandsbilder und Darstellung verursachen zusätzliche Arbeit in dieser begrenzten Visualisierung.

Quellen: MIT 6.006 (2011), Vorlesung 6, AVL-Bäume; MIT 6.046 (2005), Vorlesung 10, Rot-Schwarz-Bäume.

Die aktuelle Operation und der Baum stehen im Vordergrund. Verlaufdetails enthalten Zähler und die sortierte Schlüsselliste; Knotendetails öffnen die lokal scrollbare Tabelle. Pause erscheint nur während der Wiedergabe. Der Schrittzähler erscheint solange weitere Operationen ausstehen und entfällt am Ende.

Lokal werden höchstens 100000 Zeichen im serialisierten Zustand gespeichert. Darüber bleibt die zuvor gespeicherte Kopie erhalten; die vollständige Folge vor Neuladen oder Verlassen der Seite herunterladen. App-interne Navigation erhält den laufenden Entwurf. Ein Ablauf verwendet höchstens 31 Schlüssel und 512 Zeichen; längere Entwürfe bleiben editierbar, werden beim Start aber abgewiesen. Alte gespeicherte Eingaben bleiben lesbar; frühere Versionen speicherten keine Schritte.