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.

Ein 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.

Starten setzt einen pausierten Ablauf fort und beginnt einen abgeschlossenen Ablauf neu. Zurücksetzen löscht den Ablauf und erhält die Eingaben. Änderungen an Folge oder Baumtyp verwerfen das alte Ergebnis. Das Beispiel „RB-Reparatur“ wählt die Rot-Schwarz-Variante; andere Folgen erhalten den gewählten Typ. Gültige Eingaben und Tempo werden gespeichert; nach Navigation ist der Ablauf ungestartet. Große Bäume lassen sich lokal verschieben, ohne ihre Beschriftung zu verkleinern. Das Einfügen in einen balancierten Baum benötigt O(log n); unabhängige Zustandsbilder und deren Darstellung verursachen in dieser begrenzten Visualisierung zusätzliche Arbeit.

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