Einfügen

Im letzten Abschnitt haben wir gesehen, dass der AVL-Baum eine Datenstruktur ist, die ein effizientes Suchen ermöglicht.

Leider muss bei jeder Änderungsoperation (Einfügen und Löschen eines Knotens) die AVL-Baum-Eigenschaft erhalten bleiben. Daraus resultiert, dass beim Einfügen ein paar Mechanismen eingehalten werden müssen, die im Folgenden erklärt werden. Wir beschränken uns in PST jedoch nur auf das Einfügen von Knoten in einen AVL-Baum.

Es gibt drei unterscheidbare Fälle beim Einfügen von Knoten in einen AVL-Baum, die im Folgenden skizziert werden.

Der einfachste Fall liegt vor, wenn durch das Einfügen des Knotens in den Baum kein Balancewert irgendeines inneren Knotens nicht -1,0 oder 1 wird. In diesem Fall ist keine Neuorganisation des Baumes notwendig.

Beispiel: Der Schlüssel 5 wird in den Baum eingefügt.

Komplizierter wird es dagegen beim folgenden Beispiel:

Hier führt das Einfügen des Schlüssels 6 zu einer AVL-Kriteriumsverletzung in Knoten 3. In diesem Fall schaut man sich die Richtungen der Kanten des Teilbaumes von Knoten 3 an, in dem der Knoten 6 eingefügt wurde: Wenn nach rechts gegangen wird, notiert man ein R; wenn nach links verzweigt wird, dann ein L. Man notiert beide Buchstaben hintereinander (in diesem Fall RR) und schließt daraus auf eine Vorgehensweise anhand folgender Fälle:

Kantenfolge	Vorgehensweise
LL	Einfache Rechtsrotation des verletzten Knotens
RR	Einfache Linksrotation des verletzten Knotens
LR	Linksrotation des Nachfolgerknotens, gefolgt von einer Rechtsrotation des verletzten Knotens (wird im nächsten Abschnitt erklärt)
RL	Rechtsrotation des Nachfolgerknotens, gefolgt von einer Linksrotation des verletzten Knotens (wird im nächsten Abschnitt erklärt)

In dem oben gezeigten Beispiel gehen die beiden Kanten jeweils nach rechts, deswegen tritt Fall RR ein. Wir lesen ab, das eine einfache Linksrotation des verletzten Knotens durchgeführt werden muss.

Das bedeutet konkret in dem Beispiel nun, dass der Teilbaum 3,5,6 links (also gegen den Uhrzeigersinn) rotiert wird. Das heißt, dass die Aufhängung von Knoten 3 an Knoten 5 tritt und Knoten 3 der linke Teilbaum vom Knoten 5 wird. Vollziehen Sie diesen Schritt an der oben gezeigten Abbildung nach.

Der Fall LL ist dem Fall RR spiegelsymmetrisch. Probieren Sie dieses an folgendem Beispiel aus:

Aufgabe: In den folgenden AVL-Baum soll ein Schlüssel 3 eingefügt werden. Stellen Sie sicher, dass die Datenstruktur des AVL-Baumes nach dem Einfügen konsistent bleibt.

Die Fälle LL und RR konnten durch eine Einfachrotation abgedeckt werden. Für die Fälle LR und RL müssen jeweils zwei Rotationen durchgeführt werden. Die Vorgehensweise wird im folgenden Abschnitt beschrieben.

Die Wiederherstellung der AVL-Eigenschaft im Falle von LR bzw. RL erfolgt in zwei hintereinander ausgeführten Einfachrotationen.­­­­ Dazu sehen wir uns die Situation am besten an einem kleinen Beispiel an:

In den gezeigten AVL-Baum wird ein Schlüssel 4 eingefügt. Damit wird die Balance am Knoten 5 zu -2, d.h. das AVL-Kriterium ist am Knoten 5 nicht mehr erfüllt. Da der Schlüssel 4 als rechter Nachfolger des linken Nachfolgers von Knoten 5 eingefügt wurde, tritt der Fall LR ein.

Die Vorgehensweise bei Fall LR zeigt, dass zunächst eine Linksrotation bei dem nachfolgenden Knoten (hier im Beispiel Knoten 3) ausgeführt wird. Dadurch tritt der Fall LL ein.

 

Die Behandlung des Falls LL kennen wir schon. Also rotieren wir den verletzenden Knoten (hier Knoten 5) nach rechts.

Nach der Rotation nach rechts erhält man als Endzustand den AVL-Baum.

Aufgabe: In den folgenden AVL-Baum soll ein Schlüssel 6 eingefügt werden. Stellen Sie sicher, dass die Datenstruktur des AVL-Baumes nach dem Einfügen konsistent bleibt.