AVL-Baum

Abb. 1: AVL-Baum mit Balance-Faktoren (grün)

AVL-Baum
	Komplexität
Platz	$\scriptstyle {\mathcal {O}}(n)$
Operation	im Mittel	Worst Case
Suchen	$\scriptstyle {\mathcal {O}}(\log n)$	$\scriptstyle {\mathcal {O}}(\log n)$
Querschritt	$\scriptstyle {\mathcal {O}}(1)$	$\scriptstyle {\mathcal {O}}(\log n)$
Min, Max	$\scriptstyle {\mathcal {O}}(\log n)$	$\scriptstyle {\mathcal {O}}(\log n)$
Einfügen	$\scriptstyle {\mathcal {O}}(1)$†	$\scriptstyle {\mathcal {O}}(\log n)$
Löschen	$\scriptstyle {\mathcal {O}}(1)$†	$\scriptstyle {\mathcal {O}}(\log n)$
Verketten	$\scriptstyle {\mathcal {O}}(\log n)$	$\scriptstyle {\mathcal {O}}(\log n)$
Spalten	$\scriptstyle {\mathcal {O}}(\log n)$	$\scriptstyle {\mathcal {O}}(\log n)$
$\scriptstyle n$  Knoten im Baum †  ohne Navigation
Tab. 1: Platz- und Zeit-Komplexitäten

Der AVL-Baum ist eine Datenstruktur in der Informatik, und zwar ein binärer Suchbaum mit der zusätzlichen Eigenschaft, dass sich an jedem Knoten die Höhe der beiden Teilbäume um höchstens 1 unterscheidet. Diese Eigenschaft macht ihn zu einem balancierten binären Suchbaum und garantiert bei einer Belegung mit $\scriptstyle n$ Schlüsseln eine Höhe $\scriptstyle h$, die logarithmisch in $\scriptstyle n$ ist. Ebenso logarithmisch verhält sich die maximale Anzahl der Schritte (Vergleiche), die nötig sind, um An- oder Abwesenheit eines Schlüssels festzustellen, sowie der maximale Aufwand beim Einfügen und Löschen.

Der AVL-Baum ist benannt nach den sowjetischen Mathematikern Georgi Maximowitsch Adelson-Velski und Jewgeni Michailowitsch Landis, die die Datenstruktur im Jahr 1962 vorstellten. Damit ist der AVL-Baum die älteste Datenstruktur für balancierte Bäume.

Motivation

Suchbäume sind Lösungen des so genannten „Wörterbuchproblems“. Angenommen ist eine große Anzahl von Schlüsseln, denen jeweils ein Wert beigegeben ist. In einem Wörterbuch deutsch–englisch ist das deutsche Wort der Schlüssel und das englische Wort der gesuchte Wert bzw. beigegebene englische Wörter sind die gesuchten Werte. Ähnlich verhält es sich bei einem Telefonbuch mit Namen und Adresse als Schlüssel und der Telefonnummer als dem gesuchten Wert.

Mathematisch gesehen realisiert ein Wörterbuch eine (endliche) Funktion, mit dem Schlüssel als „Argument“ und dem Wert als „Funktionswert“. Es ordnet einem Argument einen (aus seiner Sicht) eindeutigen Funktionswert zu.

Bei beiden Beispielen sind üblicherweise die Schlüssel sortiert. Das ist sehr zweckmäßig, es erlaubt nämlich, das Buch in der Mitte aufzuschlagen, zu schauen, ob der Schlüssel gefunden ist; und wenn nicht, ob man besser weiter vorn oder weiter hinten weitersucht.

Dieses Verfahren, welches nach dem Prinzip Teile und herrsche vorgeht, hat große Vorteile in der Geschwindigkeit des Auffindens von gesuchten Werten gegenüber einem, bei dem ein ganzes Buch unter Umständen von vorn bis hinten durchsucht werden muss. Es hat in der Informatik den Namen „binäres Suchen“, während letzteres als „sequentielles Suchen“ bezeichnet wird.

Eine nahe liegende Datenstruktur für binäres Suchen ist der binäre Suchbaum. Sie ist ausführlich beschrieben im

→ Hauptartikel: Binärer Suchbaum

Die Höhe h eines Baums ist die Länge des längsten Wegs von der Wurzel zu einem Blatt. Bei einem binären Suchbaum hängen viele Leistungsindikatoren eng mit der Höhe zusammen – sie stimmt zum Beispiel überein mit der Maximalzahl an Vergleichen, die zur Feststellung der An- oder Abwesenheit eines Schlüssels nötig sind.

Da auf einer Ebene eines Binärbaums höchstens doppelt so viele Knoten untergebracht werden können wie in der Ebene darüber und sich in der obersten Ebene genau 1 Knoten, die Wurzel, befindet, enthält ein Binärbaum der Höhe h höchstens 2^h–1 Knoten. Ein solcher wird vollständiger Binärbaum (der Höhe h) genannt.

Andererseits enthält ein Binärbaum der Höhe h mindestens h Knoten, dies beispielsweise in der linearen Liste. Da bei ihnen von der Binärbaumeigenschaft nicht viel übrig geblieben ist, bezeichnet man sie als degenerierten oder entarteten Binärbaum.

Die Anzahl der Knoten n wird also eingegrenzt durch die Ungleichung

$\scriptstyle h\;\leqq \;n\;\leqq \;2^{h}-1,$

die sich exakt in folgende Ungleichung

$\scriptstyle \log _{2}(n+1)\;\leqq \;h\;\leqq \;n$

für h umrechnet. Die Höhe h = n an der Obergrenze entspricht dem sequentiellen Suchen, während die Untergrenze beim besten „binären Suchen“ erreicht wird. Der Unterschied zwischen den beiden kann dramatisch sein: Haben wir beispielsweise ein Telefonbuch mit n = 2²⁰–1 = 1'048'575 Einträgen, dann haben wir an der Obergrenze die Höhe h = 1048575, müssen also im Mittel (1048575+1)/2 = 524'288 Vergleiche durchführen. An der Untergrenze ist h = 20, das heißt wir kommen bei einem vollständigen Binärbaum nach maximal 20 Vergleichen zur selben Entscheidung.

Suchstrukturen, die auch im schlechtesten Fall eine logarithmische Höhe garantieren, gelten als „effizient“.

Unter die binären Suchbäume rechnet man nur Strukturen, die zusätzlich zum Suchen auch Einfügungen und Löschungen von Schlüsseln unterstützen – Strukturen, die dynamisch sind. Durch die Modifikationsoperationen kann ein schon erreichter effizienter Aufbau wieder zerstört werden, m. a. W.: es können lineare Listen entstehen. Wenn nun eine Datenstruktur nicht nur das Suchen, sondern auch die Modifikationsoperationen effizient unterstützen soll, muss sie bei jeder Operation der Entartung entgegenwirken und den Baum auf effiziente Weise stets an jedem einzelnen Knoten in der „Balance“ halten.

Zwischenbemerkung: Die sehr bekannte Suchstruktur Binäre Suche unterstützt effizientes Suchen durch wiederholtes Bilden des Mittelwertes zwischen zwei Indizes in einem indizierbaren Feld (Array). Sie ist die direkteste und programmtechnisch einfachste Realisierung des Prinzips Teile und herrsche – eine Art Intervallschachtelung. Die durch sie erreichte Effizienz beim Suchen entspricht dem vollständigen Binärbaum. Bei Einfügungen und Löschungen sind aber Datentransporte mit einem Aufwand proportional zur Länge des Feldes erforderlich – sie unterstützt die Dynamik also nicht effizient. Sie ist aber als ein Vorläufer der binären Suchbäume anzusehen.

Was die Dynamik anbetrifft, gehen die binären Suchbäume über das Analogon der mathematischen Funktion und des Wörterbuchs hinaus, welches man meist als statisch ansieht mit höchsten sehr trägen Änderungen. Anwendungen von dynamischen Suchbäumen, bei denen sich die Zuordnung zwischen Argument und Funktionswert mit der Zeit ändert und bei denen die exakte augenblickliche Zuordnung wesentlich ist, haben meist Sachverhalte in der Informatik selbst zum Gegenstand. Ein Beispiel ist die Menge der Symbole (Variablen) in einem Programm, das von einem Interpreter auszuführen ist: der Interpreter muss jederzeit in der Lage sein zu entscheiden, ob einer Programmvariablen momentan ein Wert zugewiesen ist und ggf. welcher. Ein anderes Beispiel findet sich im Abschnitt #Beispiel einer Anwendung mit mehreren AVL-Zugriffspfaden.

Beim AVL-Baum wird die Balance über die Höhe definiert, er ist ein höhen-balancierter binärer Suchbaum. Weitere Lösungen zur Problematik der Entartung bei dynamischen Binärbäumen finden sich im

→ Hauptartikel: Balancierter Baum

Definition

Als den Balance-Faktor BF(t) eines Knotens resp. Teilbaums t in einem Binärbaum bezeichnet man die Höhendifferenz

$BF(t):=-H(t_{l})+H(t_{r})$,

wobei H(t) die Höhe des Baums t, und t_l der linke, t_r der rechte Kindbaum von t ist.

Ein binärer Suchbaum ist genau dann ein AVL-Baum, wenn es Vorkehrungen gibt, die das Einhalten der AVL-Bedingung

$-1\;\leqq \;BF(t)\;\leqq \;+1$

an allen seinen Knoten t sicherstellen.

Diese Definition beschränkt die Höhe H(t) eines AVL-Baums t mit n Knoten durch die Ungleichung

$\log _{2}(n+1)\;\leqq \;H(t)\;\leqq \;c\log _{2}(n+2)+b$

mit c := ¹⁄_{log2 Φ} ≈ 1,440420, b := ^c⁄₂ log₂ 5 – 2 ≈ –0,327724 und Φ := ^1+√5⁄₂ ≈ 1,618034 (Zahl des goldenen Schnitts).

Die untere Schranke kommt vom vollständig balancierten Binärbaum (bei dem bis auf die unterste Ebene alle Ebenen komplett sind); die obere vom Fibonacci-Baum, der bei gegebener Höhe einen AVL-Baum mit kleinster Knotenanzahl darstellt, also am schlechtesten balanciert ist.

Operationen

Die wichtigsten Operationen bei den Suchbäumen – und damit beim AVL-Baum – sind: Suchen einerseits, sowie Einfügen und Löschen andererseits. Die Navigationsoperationen, das sind die verschiedenen Suchoperationen, das Traversieren, Aufsuchen erstes oder letztes Element und ähnliche, lassen den Baum unverändert und funktionieren im Prinzip auf jedem binären Suchbaum.

Mit der Eigenschaft, dass alle genannten Operationen im schlechtesten Fall (Worst Case) logarithmische Komplexität haben, gehört der AVL-Baum zu den höhenbalancierten binären Suchbäumen.

Suchen

Das Suchen (englisch: find, search oder locate) eines Elements anhand seines Schlüssels ist die wichtigste unter den Navigationsoperationen. Die Höhen-Balancierung des AVL-Baums versucht, auf diese Operation hin zu optimieren. Sie ermöglicht einen sogenannten direkten Zugriff (im Gegensatz zum sequentiellen Zugriff der Traversierung). Sie wird in der Regel als vorausgehende Operation sowohl beim Einfügen als auch beim Löschen eingesetzt.

Der binäre Suchbaum ist jederzeit so sortiert, dass links von jedem Knoten nur Knoten mit kleineren (oder gleichen) Schlüsseln, und rechts nur Knoten mit größeren (oder gleichen) Schlüsseln gespeichert sind. Damit das funktioniert, muss die vom Benutzer zur Verfügung gestellte Vergleichsfunktion eine Totalordnung (genauer: eine totale Quasiordnung) etablieren. In der Vergleichsfunktion steckt auch die Spezifikation des „Schlüssels“. Man findet also einen Schlüssel, indem man von der Wurzel des Baums ebenenweise nach unten wandert, und dabei nach links verzweigt, falls der gesuchte Schlüssel kleiner als der des aktuellen Knotens ist, oder nach rechts, wenn er größer ist. Stimmt ein Schlüssel überein, dann ist die Suche erfolgreich; erreicht man ein (Halb-)Blatt (das ist ein Knoten mit Ausgangsgrad 0 oder 1), dessen Schlüssel nicht übereinstimmt und dem in der geforderten Richtung ein Nachfolger fehlt, ist garantiert, dass der Schlüssel im Baum nicht existiert (siehe Suchen duplikatfrei). In diesem Fall heißt die Suche nicht erfolgreich. Das Ergebnis ist der zuletzt verglichene Knoten zusammen mit der zuletzt untersuchten Richtung, welche beide dem Anwender zurückgegeben werden, so dass er sie nach Bedarf als Einfügepunkt verwenden kann.

Sowohl duplikatfreie als auch Bäume mit Duplikaten (Elemente mit gleichen Schlüsseln) lassen sich implementieren. (Das ist weniger eine Frage der Vergleichsfunktion als eine der Anwendung.) Bei letzteren ist eine Suchoperation angebracht, die stets bis zu den (Halb-)Blättern hinab sucht und ermöglicht, ein Element gezielt je nach Anwendungssituation entweder links vom linkesten (am weitesten links liegenden) oder rechts vom rechtesten Duplikat einzufügen. Mit einer solchen Suchoperation kann die existierende Reihenfolge von Elementen mit gleichem Schlüssel bewahrt (oder eben auch umgekehrt) werden. Ist sie beispielsweise zusammen mit der Einfügeoperation Teil eines Sortieralgorithmus, dann wird dieser „stabil“ (siehe Stabilität (Sortierverfahren) mit erklärenden Beispielen). Zur Implementierung siehe Suchen mit Duplikaten.

Bei allen Varianten ist die Komplexität sowohl im Mittel als auch im schlechtesten Fall logarithmisch. Das Sortieren einer Masse von n Elementen durch wiederholtes Suchen und Einfügen kostet n-log-n, also nicht mehr als mit besten Sortierverfahren.

Traversieren (Iterieren, Enumerieren)

Die In-order-Traversierung, das heißt das Navigieren sowohl nach links wie nach rechts zum nächsten Nachbarn in der gegebenen Sortierfolge, ist besonders nützlich, wenn sie als Einzel-Operation, als Querschritt, vorliegt. So kann der Anwender eine Schleife in gewohnter Manier aufsetzen: Start mit der Suchoperation (oder dem ersten Element), Iteration mit der Traversieroperation.

Der Querschritt hat im Mittel konstanten und im schlechtesten Fall logarithmischen Aufwand. Bei einer Traversierung über den ganzen Baum wird jede Kante des Baums genau einmal absteigend und einmal aufsteigend besucht.

Aufsuchen erstes oder letztes Element

Verwandt hiermit ist die Positionierung auf das kleinste oder größte Element im Baum, welche sich sowohl im Mittel wie im schlechtesten Fall logarithmisch verhält.

Ein Intervallbegriff (sowohl eigentlich wie uneigentlich) über der total geordneten Menge der Elemente im Baum lässt sich realisieren als auch eine Art „unscharfe“ Suche, nämlich nach „größer“ oder „kleiner“ (siehe binärer Suchbaum (Proximitäts-Suche)) – ebenfalls mit logarithmischem Aufwand.

Einfügen (Eintragen)

Es sei angenommen, dass die Navigation zum Einfügepunkt bereits erfolgt ist. Ein Einfügepunkt ist ein externer Knoten und ist ganz links oder ganz rechts oder zwischen 2 internen (und Schlüssel tragenden) Knoten, kann also auf jeden Fall durch einen (internen) Knoten zusammen mit einer Richtung (links oder rechts) spezifiziert werden. Die Knoten ganz links oder ganz rechts sind immer (Halb-)Blätter, wie auch von 2 Nachbarknoten immer genau einer ein (Halb-)Blatt ist. Ein solcher Knoten sei – zusammen mit der entsprechenden Richtung – als der unmittelbare Einfügepunkt bezeichnet. So wird er auch von einer nicht erfolgreichen Suchoperation geliefert.

Zur Einfügung (englisch: insert oder add) wird der Knoten mit dem neuen Schlüssel als Blatt am Einfügepunkt eingehängt – mit anderen Worten: das externe Blatt wird zum internen Blatt. Die Höhe des aus diesem Blatt bestehenden Teilbaums erhöht sich von 0 auf 1. Beim Aufstieg zum Elterknoten gibt es entsprechend der 3 Werte des ursprünglichen Balance-Faktors des Elterknotens 3 Möglichkeiten für den neuen (temporären) Balance-Faktor:

1. Wird der Balance-Faktor zu 0, dann kommt man von einem Kindbaum, der vorher niedriger war, und die Höhe des betrachteten Knotens ändert sich nicht – mit der Folge, dass alle Balance-Faktoren weiter oben bleiben können, wie sie sind.
2. Wird der Balance-Faktor zu ±1 (er muss vorher 0 gewesen sein), erhöht sich die Höhe des Teilbaums um 1 – die Überprüfung der Balance-Faktoren weiter oben muss weitergehen.
3. Wird auf einer Ebene der Balance-Faktor zu ±2, muss der Teilbaum rebalanciert (siehe unten) werden. Danach hat bei einer Einfügeoperation der Teilbaum die gleiche Höhe wie vorher – mit der Folge, dass alle Balance-Faktoren weiter oben bleiben können, wie sie sind.

Das Einfügen des (n+1)-ten Knotens in einen AVL-Baum mit n Knoten hat im schlechtesten Fall logarithmischen Aufwand, beispielsweise wenn jede Ebene bis hinauf zur Wurzel überprüft werden muss. Da aber hierfür die Wahrscheinlichkeit von Ebene zu Ebene nach oben hin exponentiell abnimmt, ist der Bedarf für das Einfügen im Mittel konstant. Hierbei ist das Aufsuchen der Einfügeposition nicht mitgerechnet.

Löschen (Austragen, Entfernen)

Die Navigation zum zu löschenden Knoten kann mittels einer Suche, aber auch durch einen Querschritt erfolgen. Beim Löschen (englisch: delete oder remove) sind mehr Fälle zu unterscheiden als beim Einfügen (siehe auch Binärbaum). Einfach sind die Fälle, wo der zu löschende Knoten ein (Halb-)Blatt ist. Hat er aber zwei Kinder, dann müssen die beiden frei werdenden Teilbäume neu aufgehängt werden. Dazu wählt man einen der In-order-Nachbarn, also entweder den rechtesten Knoten des linken Teilbaums oder den linkesten des rechten Teilbaums (von den beiden Teilbäumen kann man den eventuell höheren bevorzugen), um die beiden Teilbäume daran wieder aufzuhängen. Der hierfür erforderliche Abstieg geht maximal über so viele Stufen, wie die Höhe beträgt, und im Mittel über genau eine. Der Ersatzknoten wird in der Hierarchie des Baums an der Stelle des gelöschten Knotens eingeklinkt, muss dabei aber selbst aus seinem Herkunftsteilbaum entfernt werden – das ist einfach, da er ein (Halb-)Blatt ist (siehe Binärbaum).

Da letztlich in jedem Fall ein internes Blatt als Kindknoten entfernt wird, vermindert sich dessen Höhe von 1 auf 0. Beim Aufstieg zum Elterknoten gibt es entsprechend der 3 Werte des ursprünglichen Balance-Faktors des Elterknotens 3 Möglichkeiten für den neuen (temporären) Balance-Faktor:

1. Wird der Balance-Faktor eines Knotens zu ±1 (er war vorher 0), dann ändert sich seine Höhe nicht – mit der Folge, dass alle Balance-Faktoren weiter oben bleiben können, wie sie sind.
2. Wird ein Balance-Faktor zu 0, hat sich die Höhe des Teilbaums um 1 verringert – die Überprüfung der Balance-Faktoren weiter oben muss weitergehen.
3. Wird ein Balance-Faktor zu ±2, muss der Teilbaum rebalanciert (siehe unten) werden. Danach kann bei der Löschoperation der neue Teilbaum eine um 1 niedrigere Höhe als haben vorher – mit der Folge, dass weiterhin überprüft und eventuell rebalanciert werden muss.
   Es kommt es aber auch vor, dass die gleiche Höhe wie vor dem Löschen herauskommt – so dass alle Balance-Faktoren weiter oben bleiben können, wie sie sind.

Der Aufwand fürs Löschen ist im schlechtesten Fall logarithmisch (mit oder ohne Suchen); im Mittel aber, wenn man das Auffinden des Löschkandidaten nicht mitrechnet, ist er konstant, da die Wahrscheinlichkeit für die Notwendigkeit, die Balance auf der nächsthöheren Ebene überprüfen zu müssen, nach oben hin exponentiell abnimmt.

Rebalancierung

Wenn bei einer Operation die AVL-Balance verloren geht, das heißt ein Höhenunterschied von mehr als 1 zwischen zwei Geschwister-Teilbäumen entsteht, muss eine Rebalancierung durchgeführt werden. Dies muss innerhalb der aufgerufenen Funktion „automatisch“ (daher die Charakterisierung als self-balancing tree im Englischen) geschehen. Geeignete Reparaturwerkzeuge sind die sogenannten Rotationen.

Für Einfügungen und Löschungen, bei denen die temporäre Höhendifferenz nie über 2 hinausgeht, werden zwei Varianten benötigt: Einfach- und Doppelrotation. Eine Einfachrotation leistet die Rebalancierung, wenn das innere Kind des um 2 höheren Geschwisters (Z in den zwei Abbildungen 2 und 3), das ist das Kind mit einer Kindesrichtung, die der von Z entgegengesetzt ist, (t₂₃ in der Abbildung 2 beziehungsweise Y in der Abbildung 3) nicht höher ist als sein Geschwister, das äußere Kind (t₄ in beiden Abbildungen). Dieser Fall wird in der Literatur als Rechts-Rechts- (resp. gespiegelt Links-Links-)Situation bezeichnet, da X rechts- und Z nicht linkslastig ist, das heißt die zwei Balance-Faktoren 2 und 1 (beim Löschen auch 0) sind, kurz: die Balance zweimal hintereinander die gleiche Richtung hat. Der andere Fall, bei dem das innere Kind höher ist, wird von einer Doppelrotation abgedeckt – in der Literatur Rechts-Links- (resp. Links-Rechts-)Situation genannt, da X rechts- und Z linkslastig ist, das heißt die zwei Balance-Faktoren 2 und –1 sind, kurz: die Balance die Richtung wechselt.

Abb. 2: Einfachrotation Links(X)

Das Prinzip der Rotation in Binärbäumen sei anhand der Abbildung 2 erläutert. Eine einzelne Rotation lässt sich durch die Rotationsrichtung Links oder Rechts und durch die Wurzel des betroffenen Teilbaums spezifizieren, zum Beispiel Links(X). Sie bewirkt die Absenkung dieses X und die Anhebung eines anderen Knotens (hier: Z). Insgesamt geht es um die folgenden 3 Aktionen:

unten:	Einhängen des zwischen Z und seinem Elter X befindlichen Teilbaums (hier: des linken Kindes t23 von Z) als (hier: rechtes) Kind bei X.
Wippe:	Einhängen von X als (hier: linkes) Kind bei Z.
oben:	Feststellen des Elters (er sei E genannt) und der Kindesrichtung von X bei E. Einhängen von Z bei E als Kind dieser Richtung.

Balkenwippe mit Kindern

Kurz: Eine Rotation „wippt“ eine Kante (hier: X→Z) des Baums in ihre andere Orientierung (Z→X). Dazu kommen die notwendigen Anpassungen an den beiden inzidenten Knoten (hier: X und Z).

Die Schlüssel bewegen sich bei diesen „Rotationen“ nur vertikal (innerhalb der senkrechten Raster). Die In-order-Reihenfolge der Knoten, die ja die Sortierreihenfolge abbildet, bleibt also vollkommen erhalten.

Eine Rotation umfasst nur eine konstante Anzahl von Verknüpfungsänderungen an einer konstanten Anzahl von Knoten.

Einfachrotation im AVL-Baum

Sie wird im Original Малое вращение kleine Drehung genannt.

Die obenstehende Abbildung 2 zeigt eine Rechts-Rechts-Situation. In der oberen Hälfte haben die beiden Teilbäume Z und t₁ des Knotens X einen Höhenunterschied von 2. Das innere Kind t₂₃ des um 2 höheren Knotens Z ist nicht höher als sein Geschwister t₄.
Dies kann nach einem Einfügen in den Teilbaum t₄ oder nach einem Löschen aus dem Teilbaum t₁ auftreten. Der in der Abbildung 2 blass gehaltene Fall, dass t₂₃ gleich hoch ist wie t₄, kommt nur beim Löschen vor.

Die Rebalancierung (gezeigt in der unteren Hälfte der Abbildung) gelingt durch eine Einfachrotation nach links. Sie ist bereits oben als einzelne Rotation beschrieben. Die anzupassenden 3 Verknüpfungen sind in der Abbildung verstärkt gezeichnet.

Die Höhe des neuen Teilbaums Z ist bei einer Einfügung gleich der von X vor der Operation, während sie bei einer Löschung um 1 vermindert oder unverändert ist, je nachdem ob Z rechtslastig war oder nicht.

Die gespiegelte, die Links-Links-Situation wird von einer Einfachrotation nach rechts behandelt.

Abb. 3: Doppelrotation RechtsLinks(Z, X)
= Rechts(Z) dann Links(X)

Doppelrotation im AVL-Baum

Sie wird im Original Большое вращение große Drehung genannt.

Die oben in der Abbildung 3 gezeigte Situation unterscheidet sich von der in Abbildung 2 darin, dass der mittlere Teilbaum (mit Wurzel Y), das ist das innere Kind des um 2 höheren Knotens Z, höher ist als sein Geschwister t₄ – eine Rechts-Links-Situation, da X rechts- und Z linkslastig ist.
Das kann nach einer Einfügung in einen der Teilbäume t₂ oder t₃ oder nach einer Löschung aus dem Teilbaum t₁ passieren. Der in der Abbildung 3 in Standardfarbe gehaltene Fall, bei dem t₂ gleich hoch ist wie t₃, kommt nur beim Löschen vor, während die 2 höhenungleichen Fälle (genau ein Teilbaum blass) sowohl beim Einfügen wie beim Löschen vorkommen. Der vierte Fall (zweimal blass) bedarf keiner Rebalancierung.

Die Doppelrotation, deren Ergebnis im unteren Drittel der Abb. gezeigt ist, ist eine Rechtsrotation durch Z (gegen die Linkslastigkeit von Z, mittleres Drittel) gefolgt von einer Linksrotation durch X (gegen die Rechtslastigkeit von X). Sie bewirkt eine zweimalige Anhebung des höheren (und inneren) Kindes Y von Z.

Die anzupassenden 5 Verknüpfungen sind in der Abbildung verstärkt gezeichnet.

Die Höhe des neuen Teilbaums Y ist nach einer Einfügung gleich wie die von X vor der Operation, während sie nach einer Löschung um 1 vermindert ist.

Bei einer Links-Rechts-Situation wird die gespiegelte Version, das heißt eine Linksrotation gefolgt von einer Rechtsrotation, benötigt.

Beispiel

Der AVL-Baum in der Abbildung 1 wird

• nach der Löschung des Knotens G durch die zwei Einfachrotationen Rechts(F), später Links(J)
• nach der Einfügung eines Knotens T durch die Doppelrotation RechtsLinks(V, P)

rebalanciert.

Operationen mit ganzen AVL-Bäumen

Verketten

Abb. 4: Verkettung von 2 AVL-Bäumen

Zwei AVL-Bäume können mit logarithmischem Aufwand verkettet (konkateniert) werden (englisch: concat oder auch nur cat). Für die Sortierfolge müssen natürlich alle Schlüssel des ersten Baums allen Schlüsseln des zweiten vorangehen.

Spalten

Abb. 5: Ein Indukti-
onsschritt beim Spalten eines AVL-Baums

Etwas komplizierter als das Verketten ist das Spalten (englisch: split) eines AVL-Baums in zwei separate AVL-Bäume an einem externen Knoten, also einer Stelle zwischen zwei internen Knoten (Schlüsseln), die als Paar (Knoten, Richtung) einschließlich des Pfades zur Wurzel gegeben sei. Links davon liegt die linke Partition mit den kleineren Schlüsseln und rechts davon die rechte mit den größeren. Die so spezifizierte Trennlinie (rot in der Abbildung 5) zerschneidet Kanten des gegebenen Baums auf dem Pfad des Knotens zur Wurzel, so dass sich links wie rechts ein Wald von „Schnipseln“ ergibt. Schließlich kann jeder der beiden Wälder mit logarithmischem Aufwand zu einem AVL-Baum zusammengefügt werden.

Anwendungsbeispiele

Die Massenlöschung von allen Schlüsseln in einem Intervall kann durch zweimaliges Spalten und einmaliges Verketten geschehen oder, wenn das kleinste oder größte Element mit dabei ist, durch einmaliges Spalten.

Eine Masseneinfügung kann durch einmaliges Spalten und zweimaliges Verketten durchgeführt werden, sofern die Menge als AVL-Baum vorbereitet ist und ihre Schlüssel in einem Intervall liegen, das im Zielbaum nicht vorkommt.

Implementierung

Zusätzlich zum Bedarf des binären Suchbaums muss in einem Knoten der Balance-Faktor mit seinen 3 Werten untergebracht werden: macht 2 Bits.

Kopf

Da die Wurzel einer Löschung oder einer Rotation anheim fallen, somit den Baum nicht repräsentieren kann, muss diese Rolle von einer anderen Datenstruktur übernommen werden, die in der Literatur Kopf genannt wird. Sie enthält den Zeiger zur Wurzel und fungiert als eine Art Elter der Wurzel.

Iterative Programmierung

In der Literatur werden die Operationen häufig in rekursiver Programmierung vorgestellt. Der Anwender hat aber mehrere Vorteile davon, wenn der Implementierer die vom Aufschreiben her eleganten Rekursionen durch simple Iterationen ersetzt hat, da dadurch $\scriptstyle \log n$ Prozeduraufrufe und -rücksprünge eingespart werden und der Speicherbedarf für den Programm-Stapelspeicher konstant gehalten wird. Es geht aber nicht nur um Ressourcenschonung. Bei der Traversieroperation wird dadurch beispielsweise die Programmierung der Anwendung wesentlich vereinfacht. Für das Aufbewahren des Rückwegs zu Wurzel und Kopf, der bei Modifikationen zur Anpassung der Balance-Faktoren, aber auch beim Traversieren gebraucht wird und der bei der rekursiven Programmierung neben anderem im Programmstapelspeicher steckt, muss dann ein anderes, explizites Konstrukt gewählt werden, welches sich im Cursor (siehe unten) subsumieren lässt. Dadurch wird eine Trennung der modifizierenden Operationen von der Navigation möglich.

Trennung der navigierenden von den modifizierenden Operationen

Einfüge- und Löschoperation sind sinnvollerweise von der Suchoperation zu trennen, wenn zum Einfügepunkt beziehungsweise Knoten auch auf andere Weise als mit der Standardsuchoperation navigiert werden soll, beispielsweise mittels eines Querschritts oder mithilfe einer zweiten Suchstruktur für dasselbe Element wie im #Beispiel einer Anwendung mit mehreren AVL-Zugriffspfaden.

Diese Modularisierung der Navigations- von den modifizierenden Operationen setzt den im Mittel unterlogarithmischen (sprich: konstanten) Aufwand der letzteren frei, denn ein Aufstieg bis zur Wurzel ist (wie in und gezeigt) nur in Ausnahmefällen erforderlich. In Anwendungen mit starkem sequentiellem Anteil kann sich das positiv auf die Laufzeit auswirken.

Cursor

Beim Suchen wird ein Paar (Knoten, Richtung) erzeugt, welches geeignet ist, beim Einfügen den Einfügepunkt zu spezifizieren. Beim Löschen wird der zu löschende Knoten durch die Komponente Knoten bezeichnet, und die Komponente Richtung spezifiziert, wohin der Cursor nach der Löschung fortschreiten soll. Beim Traversieren gibt Knoten den Ausgangspunkt und Richtung die gewünschte Richtung der Navigation an, um im Ergebnis wieder bei einem solchen Paar anzukommen. Damit erzeugen und/oder verbrauchen alle wichtigen Operationen ein Konstrukt, das (in Analogie zum Beispiel zu den Datenbanken) Cursor genannt wird.

Die Größe des Cursors hängt entscheidend davon ab, ob die AVL-Knoten einen Zeiger zum Elter enthalten oder nicht.

1. Elterzeiger vorhanden: Ein Paar (Knoten, Richtung) stellt einen vollwertigen Cursor dar.
   Ein Cursor wird nach einer (den Cursor nicht pflegenden) Operation dann und nur dann ungültig, wenn es sich um eine Löschung des Knotens dieses Cursors handelt.
   Mit dem prozentualen Aufschlag auf den Speicherbedarf für die Datenstruktur erkauft man sich auf jeden Fall eine prozentuale Einsparung an Laufzeit, da der Rückweg zu Wurzel und Kopf immer schon gesichert ist.
2. Zeiger zum Elterknoten nicht vorhanden („Cursor mit Stapel“): Zusätzlich zum Paar (Knoten, Richtung) muss der Pfad vom Knoten zu Wurzel und Kopf im Cursor gehalten werden. Die Länge des Cursors entspricht damit der maximalen Höhe des Baums.
   Bei allen Operationen ist der Zugriff zum Elterknoten über den Stapel im Cursor geringfügig teurer als über den Elterzeiger. Soll der Pfad im Cursor auch nach einer modifizierenden Operation gültig gehalten werden (beispielsweise für sequentielle Einfügungen oder Löschungen), kommt noch ein zusätzlicher prozentualer (im Mittel konstanter und im schlechtesten Fall logarithmischer) Aufschlag hinzu. Dies kann so aber nur für einen Cursor, den Eingabecursor, erbracht werden.

Benötigt eine Anwendung mehrere Cursor für ein und denselben Suchbaum und über Änderungen an ihm hinweg, dann kann das Aufrechterhalten der Konsistenz der Cursor mit Stapel (zum Beispiel durch erneutes Suchen mit im Mittel logarithmischen Kosten) so aufwändig werden, dass es wirtschaftlicher ist, dem Baum Elterzeiger zu spendieren.

Beispiel einer Anwendung mit mehreren AVL-Zugriffspfaden

Als Beispiel für eine Anwendung mit 2 Zugriffspfaden sei ein klassisches Speichermanagement gebracht. Elemente der Datenstruktur sind die freien Speicherblöcke mit den Attributen (Feldern) Größe und Ort. Für jedes der beiden Felder gebe es eine Suchstruktur. Beim Akquirieren wird ein Block von Mindestgröße gesucht, ausgetragen und ein eventueller Rest wieder eingetragen. Bei der Speicherrückgabe wird nach Ort gesucht, auf Konfliktfreiheit mit den Nachbarblöcken geprüft (ebenfalls ein Beispiel für die Nützlichkeit der Querschritts) und der zurückzugebende Block gegebenenfalls mit diesen verschmolzen. Alle Veränderungen müssen auf beiden Suchstrukturen durchgezogen werden. Sind Elterzeiger vorhanden, dann erspart das Hangeln von der einen Suchstruktur zur anderen einen Suchvorgang.

Parallelisierung

Wird iterativ programmiert, dann kann die Überprüfungs- und Reparaturschleife auch in der umgekehrten Richtung, das heißt von Kopf und Wurzel zum Blatt, durchlaufen werden. Das ist insbesondere dann interessant, wenn auf den Baum hochgradig parallel (konkurrent) zugegriffen werden soll. Zum Beispiel würde in einem Szenario „Suchen und Einfügen“ die Suchoperation sich den tiefsten (letzten) unausgewogenen Knoten auf dem Pfad merken, ab dort den Baum sperren und die Vergleichsergebnisse aufbewahren. Zum Fertigstellen der Einfügeoperation müsste dann der gesperrte Vorfahr (gegebenenfalls nach einer Rebalancierung) auf ausgewogen und alle seine Nachfahren bis zum Blatt auf die den eingeschlagenen Richtungen entsprechenden Balance-Faktoren gesetzt werden. Der Vorteil wäre, dass alle Knoten außerhalb des gesperrten Teilbaums von den anderen Prozessorkernen parallel zur laufenden Einfügung konsistent besichtigt und auch verändert werden könnten.

Vergleich mit Rot-Schwarz-Baum

Kein AVL-Baum

Die Menge der AVL-Bäume ist eine echte Teilmenge in der Menge der Rot-Schwarz-Bäume. Denn jeder Binärbaum, der in AVL-Form ist, lässt sich in einer das Rot-Schwarz-Kriterium erfüllenden Weise einfärben. Es gibt aber Rot-Schwarz-Bäume, die nicht AVL-balanciert sind. Die nebenstehende Abb. zeigt zum Beispiel einen Rot-Schwarz-Baum mit 6 (inneren) Knoten und der externen Pfadlängensumme 21, während 20 die größte externe Pfadlängensumme bei AVL-Bäumen (und zugleich die kleinstmögliche für alle Binärbäume) dieser Größe ist. Konsequenterweise ist auch die Worst-Case-Höhe des AVL-Baums kleiner als die des Rot-Schwarz-Baums, und zwar um den Faktor ^c⁄₂ ≈ 0,720. Allgemein wird das Suchzeitverhalten des AVL-Baums als günstiger angesehen.

Der Speicherplatzbedarf ist praktisch identisch: 1 Bit für die Farbe gegenüber 2 oder auch 1 Bit(s) für den Balance-Faktor.

Der Platzbedarf und das Laufzeitverhalten für die beschriebenen Operationen verhalten sich im Mittel und im Worst Case identisch. Zwar bietet der Rot-Schwarz-Baum amortisiert konstante Modifikationskosten und der AVL-Baum nur im Mittel konstante. Anwendungen von binären Suchbäumen, die nur Sequenzen von Einfügungen und Löschungen – aber keine intervenierenden Suchoperationen – enthalten, nutzen den Zweck des Suchbaums nicht aus. Sieht man also von dieser Art Anwendungen ab, ist das Gesamtverhalten einer Mischung von Suchen und Modifikation bei beiden Datenstrukturen amortisiert, im Mittel und im Worst Case logarithmisch.

Realistische Anwendungssituationen mit Performancedaten und -vergleichen – auch mit weiteren Suchalgorithmen und Spielarten der Datenstrukturen – finden sich bei Ben Pfaff. Seine Ergebnisse zeigen in 79 Messungen unter anderem die sehr große Ähnlichkeit von AVL-Bäumen (AVL) und Rot-Schwarz-Bäumen (RB) mit Laufzeitverhältnissen ^AVL⁄_RB zwischen 0,677 und 1,077 bei einem Median von ≈0,947 und einem geometrischen Mittelwert von ≈0,910.

Anwendungen

Wie Ben Pfaff zeigt, decken die dynamischen Suchbaumstrukturen AVL-Baum, Rot-Schwarz-Baum und Splay-Baum dieselben wesentlichen Funktionen ab. Große Unterschiede stellt er im Laufzeitverhalten fest, wobei der AVL-Baum in Median und Mittelwert am besten abschneidet.

In der Informatik haben die dynamischen Suchbaumstrukturen einen großen Einsatzbereich als grundlegende Hilfsmittel bei:

• Duplikatunterdrückung, Deduplizierung, Duplikaterkennung
• Elementare Mengenoperationen wie Durchschnittsbildung und Vereinigung
• Standard Template Library (STL)

In diesem Artikel sind erwähnt:

• in der #Motivation die Liste der Variablen in einem Programm, die ein Interpreter oder Compiler zu pflegen hat.
• im Abschnitt #Beispiel einer Anwendung mit mehreren AVL-Zugriffspfaden ein klassisches Speichermanagement.

Bei Ben Pfaff finden sich weitere (ähnliche) Anwendungen (alle unter x86-based Linux):

• Verwaltung von Virtual Memory Areas (VMAs) unter Einschluss von range queries zur Feststellung des Überlappens von existierenden VMAs (S. 4).
• Eindeutige Kennzeichnung von IP-Paketen (S. 7).

Historisches

Wie im Abschnitt #Motivation erwähnt, kann die sehr bekannte Suchstruktur Binäre Suche im Array als Vorläufer der dynamischen Suchbaumstrukturen gelten. Als naheliegende Umsetzung des Nachschlagens in einem (sortierten) Wörterbuch, dürfte sie mehrfach ohne Kenntnis anderer Implementierungen entwickelt und implementiert worden sein. Im dynamischen Anwendungsfall kann sie aber mit den neueren Entwicklungen nicht mithalten, obwohl sie im statischen Fall eine hervorragende Lösung ist. Es gibt Makros, die einen Compiler veranlassen, zu einer gegebenen Tabelle von (Argument, Werte)-Paaren Quelltext ohne Programmschleife für eine binäre Suche zu erzeugen.

Im Jahr 1962 erschien zum ersten Mal eine dynamische Suchbaumstruktur in Form des AVL-Baums. Seine Erfinder sind die genannten sowjetischen Mathematiker Georgi Adelson-Velski und Jewgeni Landis. Ihr Beitrag im Journal Doklady Akademii Nauk SSSR wurde schon im gleichen Jahr ins Englische übersetzt. Die Übersetzung trägt (wie entsprechend das Original) den sehr ehrgeizigen Titel „An algorithm for the organization of information“. Der Name AVL-Baum findet sich in dieser Übersetzung noch nicht.

Im Jahr 1970 veröffentlichte Rudolf Bayer seine erste Arbeit über den B-Baum. Er ist kein Binärbaum und unterstützt heterogene Speicher, beispielsweise Hauptspeicher und Hintergrundspeicher, und wird bei Datenbanksystemen eingesetzt.

Danach folgte im Jahr 1972 zunächst unter dem Namen „symmetric binary B-tree“ der Rot-Schwarz-Baum von Rudolf Bayer. Ihm war die Balance-Regel des AVL-Baums zu streng. Eine Umbenennung erfolgte 1978 von Leonidas Guibas und Robert Sedgewick in das heute übliche „red–black tree“, später auch „RB tree“.

Splay-Bäume wurden im Jahr 1985 von Daniel Sleator und Robert Tarjan unter dem Namen „Self-Adjusting Binary Search Trees“ vorgestellt. Sie sind noch dynamischer als die vorgenannten, indem sie sich auch bei Suchoperationen verändern.

Eine grobe Gegenüberstellung dynamischer Suchbäume findet sich im

→ Hauptartikel: Suchbaum

Weiterführende Informationen

Siehe auch

• Binärbaum
• Binärer Suchbaum
• Balancierter Baum
• Rot-Schwarz-Baum
• Splay-Baum
• Gewichteter binärer Suchbaum
• Fibonacci-Baum

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7. 
• Ralf Hartmut Güting, Stefan Dieker: Datenstrukturen und Algorithmen. Stuttgart 2004, ISBN 9783519221210.
• [[Donald Knuth

| Donald E. Knuth]]: The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition. Addison-Wesley, 1998, ISBN 0-201-89685-0, 6.2.3 Balanced Trees, S. 458–478. 

• Udi Manber: Introduction to Algorithms – A Creative Approach. Addison-Wesley Publishing Company 1989, Kapitel 4.3.4, S. 75ff.
• Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner Stuttgart 1988, ISBN 3-519-12255-3.
• Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin / Heidelberg 2008, ISBN 978-3-540-77977-3, doi:10.1007/978-3-540-77978-0. 
• Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Inc. Boston 2004 (PDF; 1675 kB).
• Ben Pfaff: Performance Analysis of BSTs in System Software. Stanford University 2004 (PDF; 316 kB).

Weblinks

Commons: AVL-Bäume – Sammlung von Bildern, Videos und Audiodateien

• Algorithmenvisualisierung unter anderem für AVL-Bäume
• Kurz gehaltene Beschreibung der Rotationen
• Animiertes Applet mit Sourcecode und ausführlicher Dokumentation
• Tutorial von Brad Appleton mit Implementierung in C++ (englisch)
• AvlTree.cs vom 10. August 2012