AVL-Baum

mini|237px|Abb. 1: AVL-Baum mit Balance-Faktoren (grün)

Der AVL-Baum ist nach den sowjetischen Mathematikern Georgi Maximowitsch Adelson-Welski und Jewgeni Michailowitsch Landis benannt, die die Datenstruktur im Jahr 1962 vorstellten.Englische Übersetzung von Myron J. Ricci: (PDF) In: Soviet Mathematics 3, 1962, S. 1259–1263. Damit ist der AVL-Baum die älteste Datenstruktur für balancierte Bäume. AVL-Baum Komplexität Platz Operation im Mittel Worst Case Suchen Querschritt Min, Max Einfügen Löschen Verketten Spalten  Knoten im Baum Platz- und Zeit-Komplexitäten

Er bildet eine Datenstruktur in der Informatik in Form eines binären Suchbaums mit der zusätzlichen Eigenschaft, dass sich an jedem Knoten die Höhe der beiden Teilbäume um höchstens eins unterscheidet.Thomas H. Cormen u. a.: Introduction to Algorithms. 2. Auflage, MIT Press, Cambridge (Massachusetts) 2001, S. 296. Diese Eigenschaft lässt seine Höhe nur logarithmisch mit der Zahl der Schlüssel wachsen und macht ihn zu einem balancierten binären Suchbaum. Die maximale (und mittlere) Anzahl der Schritte (Vergleiche), die nötig sind, um An- oder Abwesenheit eines Schlüssels festzustellen, hängt direkt mit der Höhe zusammen. Ferner ist der maximale Aufwand für Operationen zum Einfügen und Entfernen eines Schlüssels proportional zur Höhe des Baums und damit ebenfalls logarithmisch in der Zahl der Schlüssel; der mittlere Aufwand ist sogar konstant, wenn das Positionieren auf das Zielelement nicht mitgerechnet wird.

Viele Operationen, insbesondere die Navigationsoperationen, sind direkt von den binären Suchbäumen zu übernehmen. Bei den modifizierenden Operationen muss jedoch das AVL-Kriterium beobachtet werden, womit auf jeden Fall kleine Anpassungen durchzuführen sind, die bis zu Höhenkorrekturen durch sogenannte Rotationen reichen können.

Motivation

Suchbäume – und damit auch die AVL-Bäume – sind Lösungen des sogenannten „Wörterbuchproblems“. Eine prinzipielle Erläuterung findet sich im Abschnitt Motivation im Artikel Binärer Suchbaum.

Den Suchbäumen gemeinsam ist, dass sie Dynamik unterstützen, das heißt, dass Einfügen und/oder Löschen von Elementen wichtig ist. Da bei diesen Operationen die Gefahr besteht, dass die Balance des Baums verloren geht, wurden verschiedene Balance-Kriterien für Binärbäume entwickelt. Bei den meisten sind die Aufwände für das Suchen, Einfügen und Löschen zumindest im Mittel logarithmisch, wenn auch mit unterschiedlichen konstanten Faktoren.

Beim AVL-Baum wird die Balance über die Höhe definiert, er ist ein höhen-balancierter binärer Suchbaum.

Das AVL-Kriterium

Als den Balance-FaktorIn der englischen Literatur meist „balance factor“, so bei Donald E. Knuth: The Art of Computer Programming. Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 459; „Höhenbalance“ bei Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner, Stuttgart 1988, S. 295. eines Knotens resp. TeilbaumsDa einem Knoten in umkehrbar eindeutiger Weise der von ihm gewurzelte maximale Unterbaum, „sein“ Teilbaum, zugeordnet werden kann, sollen der Kürze halber Eigenschaften wie Höhe, Balance, Elter-Kind-und-Geschwister-Beziehung usw. einem Knoten und einem solchen Teilbaum in gleicher Weise zukommen. Spielt dabei die Beziehung zum Elter eine Rolle, so sei noch spezifischer vom linken (oder rechten) Kindbaum die Rede. Umgekehrt fungiert, zum Beispiel beim Umhängen eines Teilbaums, dessen Wurzel als „Henkel“. in einem Binärbaum bezeichnet man die Höhendifferenz ,Im Prinzip kann man auch die gespiegelte Differenz nehmen. Der Text folgt Knuth und vielen weiteren Autoren. wobei die Höhe des Baums , und der linke, der rechte Kindbaum von ist.Die Rekursionsgleichung für die Höhe ist . Ein Knoten mit wird als höhengleich oder ausgewogen, einer mit als links- und einer mit als rechtslastig bezeichnet.

Ein binärer (Such-)Baum ist genau dann ein AVL-Baum, wenn die AVL-Bedingung

an jedem Knoten eingehalten wird.Aus den Balance-Faktoren (≤ 2 Bits pro Knoten) lassen sich alle relevanten Daten für Einfügen und Löschen berechnen, es bedarf nicht der Kenntnis der absoluten Höhen.

Eigenschaften Diese Definition beschränkt die Höhe gemäß der Definition Binärer Suchbaum#Abb1A, bei der die Knotenebenen gezählt werden und der nur aus der Wurzel bestehende Baum die Höhe 1 hat eines AVL-Baums mit Knoten (Schlüsseln) durch die UngleichungDonald E. Knuth: The Art of Computer Programming. Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 460.

mit , und (Zahl des goldenen Schnitts).

Die untere Schranke kommt vom vollständigen 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 bei gleicher Knotenzahl die größte Höhe hat – somit (in Bezug auf die Höhe) am schlechtesten balanciert ist. Dabei ist die Höhe gemittelt über alle zufälligen Einfügungen in einen AVL-Baum vorgegebener Größe näher bei der unteren als bei der oberen Grenze des Intervalls.Ben Pfaff: Performance Analysis of BSTs in System Software. S. 2.

Datenstruktur

Werden der Datenstruktur AVL-Baum Operationen zum Zugriff und zur Verwaltung beigegeben, so werden diese nur dann als zugehörig angesehen, wenn sie die AVL-Eigenschaft aufrechterhalten. So erweitert wird die Datenstruktur zu einem Abstrakten Datentyp (ADT). Bei Suchbäumen gibt es im Englischen dafür auch die Charakterisierung als self-balancing tree.

Operationen

Die wichtigsten Operationen bei den Suchbäumen – und damit beim AVL-Baum – sind: Suchen einerseits sowie Einfügen und Löschen andererseits. Mit der Eigenschaft, dass alle diese Operationen im schlechtesten Fall (Worst Case) logarithmische Komplexität haben, gehört der AVL-Baum zu den höhenbalancierten binären Suchbäumen.

Navigieren

Die Navigationsoperationen, das sind die verschiedenen Suchoperationen, das Traversieren und Iterieren, Aufsuchen erstes oder letztes Element und ähnliche, lassen den Baum unverändert und funktionieren im Prinzip auf jedem binären Suchbaum. Die dortigen Angaben zur Komplexität gelten genauso für AVL-Bäume, mit der Präzisierung, dass die Höhe des AVL-Baums sich logarithmisch zur Anzahl der Knoten verhält.

Das Suchen (englisch: find, search, lookup 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.

Das Suchen setzt eine totale Quasiordnung auf der Menge der Schlüssel voraus, die am flexibelsten durch eine Vergleichsfunktion bereitgestellt wird.

Das mittlere Laufzeitverhalten des Suchens in einem binären Suchbaum wird durch die Pfadlängensumme wiedergegeben, welche geteilt durch die Knotenzahl die mittlere Suchtiefe definiert. Diese verhält sich beim AVL-Baum proportional zur optimalen Suchtiefe – mit einem Proportionalitätsfaktor nur wenig größer

Einfügen (Eintragen) Es sei angenommen, dass die Navigation zum Einfügepunkt bereits erfolgt ist. Ein Einfügepunkt ist ein externes Blatt Donald E. Knuth: The Art of Computer Programming. Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 460. und liegt 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 wenigstens 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. Für die Reparatur des Baumes oberhalb des Einfügepunktes gibt es 2 verschiedene Vorgehensweisen: Man geht den Pfad der Elterknoten zurück bis u. U. zur Wurzel („retracing“ in der englischen Literatur). Hier muss ein Stapelspeicher (bei rekursiver Programmierung meist der Programm-Stapelspeicher) vorher mit den Knoten im Pfad gefüllt worden sein. Man hat sich beim Suchen im Abstieg einen (dann den letzten, tiefsten) nicht-ausgewogenen (also links- oder rechtslastigen) Knoten gemerkt („Top-Down-Strategie“).Diesen Weg geht Donald Knuth in Donald E. Knuth: The Art of Computer Programming. S. 462. Die finale Reparatur ist dann ein zweiter Abstieg ab diesem Elterknoten. Man kann für dieses Teilstück die Vergleiche wiederholen oder man hat sich die Vergleichsergebnisse vorher in einem Stapelspeicher (mit einem Bit pro Eintrag) gemerkt.Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. § 34. Wir zeigen hier die „einfachere“ Variante, die der Abfolge bei rekursiver Programmierung entspricht. Beim Aufstieg zum Elterknoten, und später bei jedem weiteren Aufstieg, gibt es entsprechend der 3 Werte des ursprünglichen Balance-Faktors dieses Knotens 3 Möglichkeiten für den neuen (temporären) Balance-Faktor: Wird der Balance-Faktor zu 0, dann kommt man von einem Kindbaum, der vorher niedriger war, und die Höhe des Knotens ändert sich nicht – mit der Folge, dass oberhalb alle Balance-Faktoren bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum erfüllt ist. Wird der Balance-Faktor zu ±1 (er muss vorher 0 gewesen sein), erhöht sich die Höhe des Teilbaums um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen. Wird auf einer Ebene der Balance-Faktor zu ±2, muss der Teilbaum rebalanciert werden (siehe Rebalancierung weiter unten). Danach hat bei einer Einfügeoperation der Teilbaum die gleiche Höhe wie vorher – mit der Folge, dass oberhalb alle Balance-Faktoren bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum auch schon erfüllt ist.

Das Einfügen des -ten Knotens in einen AVL-Baum mit Knoten hat im schlechtesten Fall (mit oder ohne Suchen) 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 reine Modifikationsaufwand (Ändern von Balance-Faktoren und Rotationen) beim Einfügen im Mittel konstant.Sei die Anzahl der Knoten, die nicht Blätter sind und die zwei Kindbäume gleicher Höhe haben, und die Anzahl der Knoten mit verschieden hohen Kindbäumen, dann ist der Anteil der höhenungleichen. (Nur die Fibonacci-Bäume und die anderen dünnsten AVL-Bäume erreichen exakt Dagegen kommen nur die vollständigen Binärbäume (mit inneren Knoten) auf exakt Der Mittelwert über alle möglichen Formen von AVL-Bäumen liegt bei Von folgender Situation sei rekursiv ausgegangen: Bei einer Einfügung habe sich ergeben, dass die Höhe des Teilbaums, in dem die Einfügung stattfand, um 1 zugenommen hat. Ferner sei angenommen, dass es sich um einen rechten Kindbaum handelt (dazu passen die Abbildungen 2 und 3; die gespiegelte Alternative linker Kindbaum sei dem Leser überlassen, sie führt zu denselben Werten). Bei der Überprüfung der Lage im Elterknoten dieses Teilbaums sind die folgenden Fälle zu unterscheiden: BFvorEinfügung Häufigkeitvorläu-figerBFRebalan-cierungerforderlichBFda-nachTeilbaumwirdhöher umEbene ober-halb zuüberprüfen−1links höher0Nein0Nein0höhengleich+1Nein1Ja +1rechts höher+2Ja00NeinTab. 2: Nach dem Einfügen: Die neuen Balance-Faktoren (BF) in Abhängigkeit von den alten