MathePrisma Logo

Binäre Suchbäume

Binäre Suchbäume

AVL-Bäume

einfügen

Beim Einfügen eines Datensatzes im AVL-Baum geht man zunächst wie bei einem gewöhnlichen binären Suchbaum vor. Wenn nach dem Einfügen irgendwo die AVL-Balance verloren gegangen ist, wird geeignet rotiert.




einfügen und Balance korrigieren

Füge weitere Schlüssel ein. Beobachte, wie die Balance korrigiert wird.

erkannt?

Das Experiment zeigt:

  • Wenn überhaupt, so ändern sich Balance-Indizes nur an den Knoten auf dem Pfad vom eingefügten Knoten zur Wurzel.
  • Die Balance muss nur an den Knoten mit Balance-Index -2 oder +2 korrigiert werden.
  • Dies gelingt stets mit einer oder zwei Rotationen.
  • Bei der Balance-Korrektur startet man beim Vater des eingefügten Knotens und bewegt sich auf die Wurzel zu.

Es gibt vier verschiedene Situationen, in denen man einen Balance-Index +2 oder -2 zu korrigieren hat.



einfach und doppelt rotieren

Wähle mit dem linken Knopf verschiedene Situationen aus. Beobachte wie die AVL-Balance der Wurzel wieder hergestellt wird.

Der Algorithmus zum Einfügen in einen AVL-Baum stellt sich damit so dar:

AVL einfügen

Algorithmus zum Einfügen von Schlüssel s

  1. Füge zunächst s wie in einen gewöhnlichen binären Suchbaum ein.
    s liegt nun in einem (Blatt-) Knoten k.
  2. Falls k nicht die Wurzel ist: Aktualisiere den Balance-Index des Vaters v von k.
    • Ist b(v) = 0, so bist du fertig, denn dann hat sich die Höhe des bei v beginnenden Teilbaumes nicht geändert.
    • Ist b(v) =\(\pm\)1, so setze k = v und beginne erneut bei 2.
    • Ist b(v) =\(\pm\)2, so überprüfe anhand des folgenden Schaubildes, welche Maßnahme getroffen werden muss.



In den folgenden AVL-Bäumen wurde jeweils der dunkelgelb hinterlegte Knoten eingefügt. Ziehe mit der Maus die zum Wiederherstellen der AVL-Balance erforderliche Maßnahme und den zugehörigen korrigierten AVL-Baum an die richtige freie Stelle des Puzzles.