08 – AVL-Bäume (selbstbalancierte Binärbäume)

Wiederholung: Rechenzeit von Binärbäumen

Wie im Artikel Nr. 7 beschrieben, verhält sich die Rechenzeit für die Operationen im Binärbaum wie folgt:

Einfügen
- best case: O(log n)
- worst case: O(n)
Aufbau des gesamten Baumes
- best case: O(n log n)
- worst case: O(n²)

Ziel: möglichst gut “balancierter” Baum, um best case beim Rechenaufwand zu erreichen!

Balancekriterium

Der Unterschied der Höhen h_links und h_rechts der beiden Nachfolger-Teilbäume eines Knotens soll minimiert werden.

Hier ist h_rechts-h_links = -2. Dies muss verbessert werden.

Selbstbalancierte Binärbäume (AVL-Bäume)

Die Idee hinter selbstbalancierten Binärbäumen (AVL-Bäume nach Adelson-Velsky-Landis) ist es, in jedem Knoten ein Balancekriterium zu speichern. Dieser Wert wird berechnet mit der Formel

bal = h_rechts-h_links

Zulässige Werte für bal sind nur {-1, 0, 1}, das heißt der linke und der rechte Teilbaum eines Knotens dürfen sich höchstens um 1 in der Höhe unterscheiden.
Es kann nachgewiesen werden, dass in diesem Fall der Aufwand zum Einfügen eines neuen Knotens nur O(log n) ist.

Beispiel:

1. Knoten einfügen:

2. Knoten einfügen:

3. Knoten einfügen:

4. Knoten einfügen:

5. Knoten einfügen:

Operationen in AVL-Bäumen

Einfügen neuer Knoten mit insert
Wenn wir einen neuen Knoten einfügen, gehen wir wie beim normalen Binärbaum vor. Jedoch wird rückwärts, vom neuen Knoten aus, dem vorausgehenden Knoten mitgeteilt, dass der entsprechende Teilbaum gewachsen ist.
bal erhöht oder verringert sich dadurch um 1. Wenn sich bal nicht mehr im zulässigen Wertebereich befindet, muss der Baum lokal umgebaut werden.

Die Funktion heißt: insert(Comparable e, AvlNode t)

Der Funktion wird wie beim Binärbaum der Schlüssel des neuen Elementes übergeben, sowie die Stelle, an der das Element eingefügt werden soll. Beim Aufruf durch den Benutzer ist dies der Wurzelknoten. Programmintern wird die Funktion dann im weiteren Verlauf rekursiv von sich selbst mit einem anderen Parameter für t aufgerufen.

Im ersten Schritt wird geprüft, ob an der Stelle t schon ein Knoten existiert. Wenn nicht, wird an genau dieser Stelle der neue Knoten erzeugt:

if(t == null)
	t = new AvlNode(e, null, null);

Wenn der Knoten t schon existiert, muss geprüft werden, ob der neue Knoten als linker oder als rechter Nachfolger in Frage kommt. Hierfür wird der übergebene Schlüssel mit dem Schlüssel des Knotens t verglichen:

else if(e.compareTo(t.element) < 0)
	...

An dieser Stelle wollen wir nun vier verschiedene Fälle untersuchen, die beim Einfügen des Knotens auf der linken oder der rechten Seite auftreten können.

Fall 1: Durch das Einfügen des neuen Knotens wird der linke Arm zu lang:

Diese Situation ist der “Left-Left-Case”. Das Problem wird behoben durch eine einfache Rotation nach rechts:

Der linke Teilarm (Element 2) wird dabei einfach mitgezogen. Da auf dieses linke “Kind” geachtet werden muss, wird die Rotation “rotateWithLeftChild” genannt.

Fall 2: Durch das Einfügen des neuen Knotens wird der rechte Arm zu lang:

Dieser Fall (Right-Right-Case) ist analog zu Fall 1. Hier wird also auch das Problem mit der gleichen Herangehensweise gelöst: Der Baum wird nach links rotiert mit der Funktion “rotateWithRightChild”:

Fall 3: Durch das Einfügen des neuen Knotens wird der linke Arm zu lang, allerdings ist der neue Knoten nun nicht linker Nachfolger, sondern rechter Nachfolger:

Hier kann der Baum nicht einfach nach rechts rotiert werden, denn dann wäre der Knoten 3 an der Stelle der Wurzel. Sowohl Knoten 4 als auch Knoten 5 haben aber einen größeren Schlüsselwert als Knoten 3, deshalb hätte Knoten 3 zwei rechte Nachfolger. Es muss jedoch immer einen linken und einen rechten Nachfolger geben.

Die Lösung des Problems ist eine doppelte Rotation. Zuerst wird eine lokale Rotation nach links durchgeführt, anschließend folgt eine Rotation nach rechts, wobei das linke “Kind” mitgezogen wird:

Knoten 4 ist nun die neue Wurzel, er hat einen linken und einen rechten Nachfolger und der Baum ist wieder ausbalanciert. Die Funktion, die diesen beiden Rotationen kombiniert, ist “doubleWithLeftChild”.

Fall 4: Durch das Einfügen des neuen Knotens wird der rechte Arm zu lang, allerdings ist der neue Knoten nun nicht rechter Nachfolger, sondern linker Nachfolger:

Hier verfährt man wie bei Fall 3 und kombiniert nun eine Rotation nach rechts mit einer Rotation nach links, wobei das rechte Kind beachtet wird:

Die zugehörige Funktion heißt “doubleWithRightChild”.

Nun wieder zu unserem Algorithmus. Die Funktion war bisher so weit fortgeschritten:

	if(t == null)
		t = new AvlNode(e, null, null);

	else if(e.compareTo(t.element) < 0)

Wenn der übergebene Schlüssel nun also kleiner ist als der des Knotens t, dann muss der insert-Befehl an den linken Nachfolger des Knotens t weitergegeben werden (denn links sind ja immer die kleineren Elemente angehängt):

	t.left = insert(e, t.left);

Nun muss die Balancierung angepasst werden. Es wird links angefügt, es könnte also der linke Teilbaum nun 2 länger sein als der rechte (Höhe rechts-Höhe links ist dann -2). Dies wird in der nächsten if-Abfrage geprüft:

	if(height(t.right)-height(t.left) == -2)
		...

Um den “Rotationstyp” festzustellen, muss nun noch getestet werden, ob der neue Knoten links (Fall 1) oder rechts (Fall 3) an den linken Nachfolger angefügt wurde. Dementsprechend werden nach der Abfrage die Rotationsfunktionen aufgerufen:

	if(e.compareTo(t.left.element) < 0)
		t = rotateWithLeftChild(t);
	else
		t = doubleWithRightChild(t);

Damit ist der Baum fertig balanciert.

Gilt hingegen e.compareTo(t.element) > 0, dann findet das Einfügen im rechten Teilbaum statt. Die Funktion verfährt hier analog zum linken Teilbaum, nur eben auf Fall 2 und 4 angepasst:

else if(e.compareTo(t.element) > 0)
{
	t.right = insert(e, t.right);
	if( height(t.right)-height(t.left) == 2)
		if(e.compareTo(t.right.element) > 0)
			t = rotateWithRightChild(t);
		else
			t = doubleWithLeftChild(t);
}

Ganz zum Abschluss müssen noch die Werte für die Höhe der Teilbäume neu bestimmt werden. Hierfür wird rekursiv jedem Knoten das Maximum der Höhen der Nachfolgerbäume+1 zugewiesen (ein Knoten hat die Höhe seines größeren Nachfolgerbaumes+1):

t.height = max height(t.left), height(t.right))+1;

Für einen Überblick über die gesamte Funktion, auch im Zusammenhang mit den Rotationsfunktionen, die hier nicht weiter besprochen werden sollen, siehe den Programmtext unten.

Fazit

Die Links- und Rechtsrotationen sind alle lokale Operationen mit dem Aufwand O(1). Als obere Abschätzung kann man sagen, dass schlimmstenfalls bei jedem Einfügen eine Rotation durchgeführt werden muss. Dieser schlimmste Fall kann aber mathematisch nachweislich nicht auftreten, der Rechenaufwand zum Einfügen eines Knotens geht daher nicht über O(log n) hinaus.
Der Rechenaufwand, um den gesamten Baum aufzubauen ist somit O(n log n), das Optimum für einen Binärbaum.

Der fertig aufgebaute AVL-Baum ist ein perfekter Binärbaum, in dem mit minimalem Aufwand eine sortierte Traversierung durchgeführt werden kann. Zusätzlich ist der AVL-Baum eine dynamische Datenstruktur (Vorteile gegenüber statischen Feldern). Somit ist der AVL-Baum auch ein optimales Sortierverfahren.

Implementierung in Java

public class AvlTree
{ // Klasse für die Verwaltung der Knoten des AvlTrees
	public AvlNode root; // Der Wurzelknoten

	public AvlTree()
	{ // Konstruktor setzt Wurzel auf null
		root = null;
	}

	public void makeEmpty()
	{ // setzt die Wurzel wieder auf null, somit wird der Baum gelöscht
		root = null;
	}

	public boolean isEmpty()
	{ // prüft, ob der Baum leer ist
		return (root == null);
	}

	public AvlNode insert(Comparable e, AvlNode t)
	{ // Fügt einen neuen Knoten als Knoten t ein
		if(t == null)
			// Wenn der Knoten t noch nicht existiert, wird t der neue Knoten
			t = new AvlNode(e, null, null);
		// Wenn t schon existiert...
		else if(e.compareTo(t.element) < 0)
		{ // ... und der Schlüssel e des neuen Elementes < dem von t ist,
		  // geht der Befehl weiter an den linken Nachfolger:
			t.left = insert(e, t.left); 

			// Nun muss die Balancierung angepasst werden. Es wird links ange-
			// fügt, es könnte also der linke Teilbaum nun 2 länger sein als
			// der rechte (Höhe rechts-Höhe links ist dann -2)
			if(height(t.right)-height(t.left) == -2)
				// wenn der übergebene Schlüssel kleiner ist als der des linken
				// Nachfolgers, hängt am linken Nachfolger noch ein linker N.
				// es muss dann nach rechts rotiert werden, wobei der linke
				// Nachfolger berücksichtigt wird (with left child)
				if(e.compareTo(t.left.element) < 0)
					t = rotateWithLeftChild(t);
				else
					// ansonsten muss erst links rotiert werden, um den oben
					// genannten Fall zu erreichen, dann wird rechts rotiert:
					t = doubleWithRightChild(t);
		} // end else if
		else if(e.compareTo(t.element) > 0)
		{ // ... und der Schlüssel e des neuen Elementes > dem von t ist
		  // Verfahren ist analog zu dem oben genannten
			t.right = insert(e, t.right);
			if( height(t.right)-height(t.left) == 2)
				if(e.compareTo(t.right.element) > 0)
					t = rotateWithRightChild(t);
				else
					t = doubleWithLeftChild(t);
		} // end else if
		// Zum Schluss wird noch der Höhe des Knotens das neue Maximum zugew.
		t.height = max height(t.left), height(t.right))+1;
		return t;
	} // end insert

	public static int height(AvlNode t)
	{ // Wenn t == null -> gib -1 zurück, Wenn t != null -> gib t.height zurück
		return t == null ? -1 : t.height;
	}

	public static int max(int lhs, int rhs)
	{ // Wenn lhs > rhs -> gib lhs zurück, Wenn lhs <= rhs -> gib rhs zurück
		return lhs > rhs ? lhs : rhs;
	}

	public static AvlNode rotateWithLeftChild(AvlNode k2)
	{
		// Nachfolger werden vertauscht:
		AvlNode k1 = k2.left;
		k2.left = k1.right;
		k1.right = k2;
		// Neue Höhen werden angepasst
		k2.height = max(height(k2.left), height(k2.right))+1;
		k1.height = max(height(k1.left), k2.height)+1;
		return k1;
	} // end rotateWithLeftChild

	public static AvlNode rotateWithRightChild(AvlNode k1)
	{
		// Nachfolger werden vertauscht:
		AvlNode k2 = k1.right;
		k1.right = k2.left;
		k2.left = k1;
		// Neue Höhen werden angepasst
		k1.height = max(height(k1.left), height(k1.right))+1;
		k2.height = max(height(k2.right), k1.height)+1;
		return k2;
	} // end rotateWithRightChild

	public static AvlNode doubleWithRightChild(AvlNode k3)
	{ // Kombination aus Links- und Rechtsrotation
		k3.left = rotateWithRightChild(k3.left);
		return rotateWithLeftChild(k3);
	} // end doubleWithLeftChild

	public static AvlNode doubleWithLeftChild(AvlNode k1)
	{ // Kombination aus Rechts- und Linksrotation
		k1.right = rotateWithLeftChild(k1.right);
		return rotateWithRightChild(k1);
	} // end doubleWithRightChild

	private class AvlNode
    { // private Klasse zur Speicherung der Knotendaten
        AvlNode(Comparable theElement)
        { // Konstruktor 1, ruft Konstruktor 2 auf mit Standardeinstellungen
            this(theElement, null, null);
        } // end AvlNode

        AvlNode(Comparable theElement, AvlNode lt, AvlNode rt)
        { // Konstruktor 2, weist Parameter den Eigenschaften zu
            element  = theElement;
            left     = lt;
            right    = rt;
            height   = 0;
        } // end AvlNode

        Comparable element;      // Die Daten im Knoten
        AvlNode    left;         // Der linke Nachfolger
        AvlNode    right;        // Der rechte Nachfolger
        int        height;       // Die Höhe des längeren der beiden
								 // an dem Knoten hängenden Teilbäume
    } // end private class AvlNode
} // end class AvlTree

Mathematical Engineering