AVL-Baum
In diesem Abschnitt lernen Sie die Datenstruktur des AVL-Baums kennen.
Binäre Suchbäume
Sie haben in der Vorlesung ja schon die Datenstruktur der binären Suchbäume kennengelernt.
Ein binärer Suchbaum ist ein spezieller zyklenfreier, ungerichteter Graph, bei dem ein Knoten, die sogenannte Wurzel, keinen Vorgänger hat und bei dem jeder innere Knoten höchstens zwei Nachfolger hat. Binäre Suchbäume besitzen die Eigenschaft, dass die Komplexität der Operationen (Suchen, Einfügen, Löschen von Knoten) von der Höhe des Baumes abhängt. Daher ist es optimal, wenn die Bäume möglichst ausgeglichen sind und dadurch eine geringe Höhe besitzen.
Leider ist es relativ häufig der Fall, dass die binären Suchbäume, die durch die Einfügesequenz der Schlüssel in den Baum entstehen, nicht optimal ausgeglichen sind. Ein Beispiel könnte eine absteigend sortierte Liste von Schlüsseln sein, die der Reihe nach eingefügt werden:
Beispiel: Sie fügen die Schlüssel 15,10,8,7,4,3,1 in einen binären Suchbaum ein. Das Ergebnis sehen Sie in der Abbildung auf der linken Seite.
In diesem Fall entsteht ein degenerierter Baum, besser bekannt als Liste, deren Komplexität beim Suchen, Einfügen und Löschen natürlich linear mit der Anzahl der Knoten ist. Mit der Datenstruktur des Binärbaums wollte man aber gerade eine logarithmische Komplexität erreichen (in der Abbildung auf der rechten Seite), daher muss der Baum immer möglichst ausgeglichen gehalten werden, unabhängig von der Einfügesequenz der Schlüssel.
Ein Ansatz dafür bietet der sogenannte AVL-Baum. Um den AVL-Baum zu verstehen, benötigen wir ein paar Definitionen:
Definitionen
Die Höhe eines Knotens
Die Höhe eines Knotens k in einem Baum ist definiert durch die Anzahl der Kanten auf dem längsten Weg von k zu einem Blatt, das ein Nachfolger von k ist.
Beispiel:
Balance eines Knotens
Die Balance eines Knotens k ist definiert als die Differenz der Höhe des rechten und des linken Teilbaums von k.
Beispiel:
Nachdem nun die Begriffe Höhe und Balance definiert wurden, können wir nun definieren, was wir unter einem AVL-Baum verstehen:
AVL-Baum
Ein AVL-Baum ist ein binärer Suchbaum mit der Balance -1, 0 oder 1 in allen inneren Knoten.
Beispiel: Der bereits oben gezeigte Baum ist ein AVL-Baum.
Man sieht allein schon an diesem Beispiel, dass AVL-Bäume deutlich ausgeglichener sind als die binären Suchbäume, die keine AVL-Bäume sind. Wenn nun bei jeder Änderungsoperation (Einfügen und Löschen von Knoten) die AVL-Baum Eigenschaft geprüft und ggf. wiederhergestellt wird, dann hat man immer einen relativ ausgeglichenen Baum. Dies ermöglicht ein effizientes Suchen.
Sobald an einem Knoten die AVL-Eigenschaft nicht erfüllt ist, ist es kein AVL-Baum mehr.
Beispiel: Binärer Suchbaum, aber kein AVL-Baum, da die AVL-Eigenschaft (Balance ist -1, 0 oder 1) am Knoten 3 nicht erfüllt ist.
