AVL-Baum

Abbildung 1: AVL-Baum mit Balance-Werten (grün)

AVL-Baum
	Komplexität
Platz	O(n)
Operation	bei 1 Operation		bei m Ope- rationen
	im Mittel	pessimal
Suchen	O(log n)	O(log n)	O(m log n)
Traversieren	O(1)	O(log n)	O(m)
Min, Max	O(log n)	O(log n)
Einfügen	O(1)†	O(log n)	O(m)
Löschen	O(1)†	O(log n)	O(m)
n  Knoten im Baum m (≤ n) Operationen; bei Einfügen oder     Löschen nur mit benachbarten Schlüsseln †  vorausgehende Navigation nicht enthalten
Tabelle 1: AVL-Baum: Platz- und Zeit-Komplexitäten

Der AVL-Baum ist eine Datenstruktur in der Informatik, nämlich ein balancierter binärer Suchbaum. Er hat als Invariante, dass sich für jeden Knoten die Höhen der beiden Teilbäume um höchstens 1 unterscheiden. Diese Bedingung verhindert (bei einem moderaten Aufwand), dass der Baum zu sehr aus der Balance gerät. Die Höhe eines AVL-Baums mit n Knoten liegt in O(log n) und damit auch die maximale Anzahl der Schritte, um ein Element zu finden oder festzustellen, dass es nicht enthalten ist.

Der Name AVL leitet sich von den Erfindern Adelson-Welski und Landis ab, die diese Datenstruktur 1962 entwickelten.^{[Ref 1]} Der AVL-Baum ist damit die älteste Datenstruktur für balancierte Bäume. Eine Alternative mit schwächeren Bedingungen ist der Rot-Schwarz-Baum.

Balance

Ein binärer Suchbaum heißt AVL-Baum, wenn für jeden seiner Teilbäume die Höhen des rechten und linken Astes sich um höchstens 1 unterscheiden. Die Höhe eines Baumes ist die maximale Anzahl Stufen von seiner Wurzel bis zu einem tiefsten Knoten, also einem tiefsten Blatt. Der „Balance-Wert“ eines Knotens t ist:

$\operatorname{bal}(t) = H(t_r) - H(t_l)$,

wobei H(t_r) die Höhe des rechten Teilbaumes des Knotens t bezeichnet, H(t_l) analog die des linken Teilbaumes.

Ein binärer Suchbaum B ist genau dann ein AVL-Baum, wenn stets für alle Knoten t von B das „AVL-Kriterium“

$\operatorname{bal}(t) \in \{ -1,0,1 \}$

eingehalten wird.

Die Höhe H(t)^{[Anm 1]} des AVL-Baums t mit n Knoten ist beschränkt durch:^{[Ref 2]}

$\log_2 (n + 1) \leqq H(t) \leqq a \log_2 (n + 2) + b$

mit  $a:=\tfrac{1}{\log_2 \Phi} \approx 1{,}440420$,  $b:=\tfrac{a}{2} \log_2 5 -2 \approx -0{,}327724$  und  $\Phi:=\tfrac{1+\sqrt 5}{2} \approx 1{,}618034$  (Zahl des goldenen Schnitts).

Die obere Schranke kommt vom Fibonacci-Baum, der zu einer gegebenen Höhe einen AVL-Baum mit minimaler Knotenanzahl darstellt, also am schlechtesten balanciert ist. Strebt die Anzahl n seiner Knoten gegen unendlich, so verhält sich seine mittlere Pfadlänge (bei Einheits-Zugriffswahrscheinlichkeiten über alle Knoten)

$\bar P_{n} := \sum_{k \in t} \tfrac{T(k)}n$    asymptotisch wie    $c \log_2 n \$

mit  $c := \tfrac{a \Phi}{\sqrt 5} \approx 1{,}042298$.

Ähnlich wie es bei einem unbalancierten binären Suchbaum eine relativ hohe Wahrscheinlichkeit gibt, dass er bei zufälligen Einfügungen eine gewisse Balanciertheit erlangt, ist auch beim AVL-Baum die Wahrscheinlichkeit sehr hoch, dass er besser balanciert herauskommt als seine am schlechtesten balancierte Ausprägung, der Fibonacci-Baum. Wie obige Rechnung zeigt, kommt selbst letzterer beim Suchen im Mittel schon auf eine Effizienz, die nur um 4% von der idealen eines vollständig (höhen-)balancierten Binärbaums abweicht. Wird über alle AVL-Bäume gemittelt, beträgt der Unterschied zum Ideal weniger als 2%.

Operationen

Beim AVL-Baum gibt es drei wesentliche Grundoperationen, das Suchen eines Elements, sowie das Einfügen und das Löschen eines Elements. Die Navigationsoperationen, d. h. die verschiedenen Suchoperationen, das Traversieren, Aufsuchen erstes oder letztes Element u. ä., lassen den AVL-Baum unverändert und funktionieren im Prinzip auf jedem binären Suchbaum. Wesentliche Eigenschaft des AVL-Baums ist, dass alle genannten Operationen im schlechtesten (pessimalen) Fall (worst case) die Komplexität O(log n) haben.

Suchen

Das Suchen eines Elements steht beim AVL-Baum ganz im Zentrum der Navigations-Operationen. Die Höhen-Balancierung versucht, auf diese Operation hin zu optimieren. Sie ermöglicht einen sog. direkten Zugriff (i. Ggs. zum sequenziellen Zugriff der in-order-Traversierung). Sie wird i. d. R. als vorausgehende Operation sowohl beim Einfügen als auch beim Löschen eingesetzt.

Der binäre Suchbaum ist jederzeit so sortiert, dass rechts von jedem Knoten nur Knoten mit größeren (oder gleichen) Schlüsseln, und links nur Knoten mit kleineren (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. Implizit steckt in ihr auch die Spezifikation des „Schlüssels“.) Man findet also einen Schlüssel, indem man von der Wurzel des Baumes ebenenweise nach unten wandert, und dabei jeweils nach rechts verzweigt, falls der gesuchte Schlüssel größer als der des aktuellen Knotens ist, oder links, wenn er kleiner ist. Stimmt ein Schlüssel überein, hat man ihn gefunden; erreicht man ein (Halb-)Blatt (d. h. einen 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 (s. Suchen duplikatfrei).

Sowohl duplikatfreie als auch Bäume mit Duplikaten (u. U. gleichen Schlüsseln) lassen sich implementieren. (Das ist weniger eine Frage der Vergleichsfunktion als der Anwendungssituation.) Bei letzteren ist eine Suchoperation angebracht, die stets bis zu den (Halb-)Blättern hinab sucht und ermöglicht, ein Element gezielt rechts vom rechtesten (am weitesten rechts liegenden) bzw. links vom linkesten Duplikat einzufügen. Eine solche Suchoperation ist insbesondere dann interessant, wenn im Suchbaum nicht nur gesucht und gefunden werden soll, sondern auch sequenziell navigiert wird. Ferner erlaubt sie z. B., eine (möglicherweise unbekannte) Vorsortierung in einem Bereich zu retten, wo eine Einordnung nach dem aktuellen Sortiervergleichsschlüssel nur Duplikate produziert. Man nennt ein solches Verhalten „stabil“ (s. Stabilität (Sortierverfahren) mit erklärenden Beispielen). Zur Implementierung bei binären Suchbäumen s. Suchen mit Duplikaten.

Bei allen Ausprägungen ist die Komplexität sowohl im Mittel wie auch im schlechtesten Fall O(log n). Das Sortieren einer Masse von n Elementen durch wiederholtes Suchen und Einfügen kostet O(n log n), also nicht mehr als mit den besten Sortierverfahren.

Suchen per Index

Wird in jedem Knoten die Anzahl der Elemente des ihm zugehörigen Unterbaums gehalten, kann das Aufsuchen eines Elements vermöge seines in-order-Index in O(log n) bewerkstelligt werden.

Allerdings dürften die Anwendungssituationen, wo dieses Verfahren günstiger herauskommt als ein Zeigervektor, der den Zugriff in konstanter Zeit schafft, in der Praxis nicht allzu häufig anzutreffen sein.

Traversieren (Iterieren, Enumerieren)

Die in-order-Traversierung (Querung), d. h. das Navigieren sowohl nach rechts als auch nach links zum nächsten Nachbarn in der gegebenen (Sortier-)Folge, ist besonders nützlich, wenn sie als Einzel-Operation vorliegt. So kann der Anwender eine Schleife in gewohnter Manier aufsetzen: Start mit der Suchfunktion (oder dem ersten Element), Iteration mit der Traversierfunktion.

Sie verhält sich im Mittel wie O(1) und im schlechtesten Fall wie O(log n). Eine Traversierung über den ganzen Baum kostet O(n).^{[Anm 2]}

Aufsuchen erstes oder letztes Element

Verwandt hiermit ist die Suche nach dem größten oder kleinsten Element im Baum, welche sowohl im Mittel wie auch im schlechtesten Fall O(log n) kostet.

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

Einfügen (Eintragen)

Es sei angenommen, dass die Navigation zum „Einfügepunkt“ bereits erledigt ist. Ein Einfügepunkt ist ganz rechts oder ganz links oder zwischen 2 Knoten, kann also auf jeden Fall durch einen Knoten zusammen mit einer Richtung (rechts oder links) spezifiziert werden. Von 2 Nachbarknoten ist immer einer ein Halb-Blatt, den wir zusammen mit der entsprechenden Richtung als unmittelbaren Einfügepunkt bezeichnen wollen. So wird er bspw. auch von einer nicht erfolgreichen Suchoperation geliefert.

Der Knoten mit dem neuen Schlüssel wird als Blatt am Einfügepunkt aufgehängt. Beim Rücksprung aus der rekursiven Einfüge-Funktion wird geprüft, ob der Balance-Wert angepasst und der Teilbaum rebalanciert werden muss. Wird der Balance-Wert zu 0, dann kommen wir von einem Ast, der vorher niedriger war; es hat sich die Höhe des Teilbaumes also nicht verändert. Wird der Balance-Wert zu − 1 oder 1 (er muss vorher 0 gewesen sein), hat sich die Höhe des Teilbaumes um 1 erhöht. Die rekursiv aufgerufene Funktion teilt dies dem Aufrufer mit, so dass es in die Überprüfung der nächsthöheren Ebene einbezogen werden kann. Wird auf einer Ebene der Balance-Wert zu 2 oder − 2, muss der Teilbaum des aktuellen Knotens rebalanciert werden. Nach einer Rebalancierung hat der neue Teilbaum die gleiche Höhe wie vor der Einfügeoperation, danach ist die Balance des ganzen Baums auch schon in Ordnung.^{[Anm 3]}

Wird die Wahrscheinlichkeit für die Notwendigkeit, die Balance auf der nächsthöheren Ebene überprüfen zu müssen, als < 1 angenommen, dann verhält sich das Einfügen (ohne das Finden der Einfügeposition) im Mittel wie O(1)^{[Anm 4]} und im schlechtesten Fall wie O(log n).

Eine Massen-Einfügung von m vorsortierten Elementen mit nahe beieinander liegenden Schlüsseln kommt bei günstiger Implementierung auf O(m).

Löschen (Austragen, Entfernen)

Die Navigation zum betroffenen Knoten kann z. B. mittels einer Suche erfolgen. Wie beim Binärbaum gezeigt, sind beim Löschen mehr Fälle zu unterscheiden als beim Einfügen. Recht übersichtlich sind die Fälle, wo der zu löschende Knoten ein Blatt oder Halb-Blatt ist. Hat er aber zwei Söhne, dann müssen die beiden frei gewordenen Teilbäume neu aufgehängt werden. Dazu wählt man einen der in-order-Nachbarn, also entweder den linkesten Knoten des rechten Teilbaums oder den rechtesten des linken Teilbaums (von den beiden Teilbäumen kann man den evtl. höheren bevorzugen), um die beiden Teilbäume daran wieder aufzuhängen. Der Knoten nimmt den Platz des gelöschten Knotens ein und muss dabei natürlich selbst aus seinem Herkunftsteilbaum entfernt werden – das ist einfach, da er ein (Halb-)Blatt ist (s. Binärbaum).

Im nun folgenden Rücksprung werden die Balance-Werte überprüft, ggf. adjustiert und nötigenfalls Rebalancierungen durchgeführt. Die rekursiv aufgerufene Funktion teilt ihrem Aufrufer mit, ob sich die Höhe verringert hat, so dass dies in die Überprüfung der nächsthöheren Ebene einbezogen werden kann. Diese Überprüfung kann beendet werden, wenn der Balance-Wert eines Knotens zu 1 oder − 1 wird (er war vorher 0). Wenn ein Balance-Wert zu 0 wird, hat sich die Höhe des Teilbaumes um 1 verringert und die Überprüfung muss weitergehen. Wird ein Balance-Wert zu 2 oder − 2, muss der Teilbaum rebalanciert werden. Nach einer Rebalancierung mit Doppelrotation hat der neue Teilbaum eine um 1 niedrigere Höhe als vor der Löschoperation. Bei einer Einfachrotation kommt es aber auch vor, dass der neue Teilbaum die gleiche Höhe hat wie vor dem Löschen.^{[Anm 5]}

Wird die Wahrscheinlichkeit für die Notwendigkeit, die Balance auf der nächsthöheren Ebene überprüfen zu müssen, als < 1 angenommen, dann verhält sich das Löschen (ohne das Aufsuchen des zu löschenden Knotens) im Mittel wie O(1)^{[Anm 4]} und im schlechtesten Fall wie O(log n).

Das Löschen einer Masse von m benachbarten Elementen kommt bei günstiger Implementierung auf O(m).

Rebalancierung

Wenn durch eine Einfüge- bzw. Löschoperation die AVL-Balance zerstört wurde, d. h. ein Höhenunterschied von mehr als 1 zwischen zwei Bruder-Teilbäumen entstanden ist, ist eine Rebalancierung durchzuführen. Zur besseren Orientierung wollen wir die Wurzel des niedrigeren der beiden Teilbäume (in den Abbildungen 2 und 3 jeweils t₁) als Angelknoten bezeichnen. Zwei Fälle kommen vor, die Einfachrotation und die Doppelrotation. (Obwohl es nur recht wenige Analogien gibt, hat sich die Metapher von der Rotation in der Literatur festgesetzt.) Eine Einfachrotation leistet die Rebalancierung, wenn der innere Sohn (in der Abbildung 2 die Wurzel von t₂₃; in der Abbildung 3 der Knoten Y) des höheren Bruders, d. h. der innere (= nähere) Neffe des Angelknotens, nicht höher ist als sein Bruder, der äußere (= fernere) Neffe. Der andere Fall, bei dem der innere Neffe höher ist, wird von einer Doppelrotation abgedeckt.

Eine Rotation (einfach oder doppelt) ändert nicht die vorhandene in-order-Reihenfolge, auch nicht gegenüber dem Rest des Baumes. (Die Kleiner-Zeichen am oberen Rand der Abbildungen 2 und 3 sollen dies verdeutlichen.)

Eine Rotation (einfach oder doppelt) benötigt nur eine konstante Anzahl von Verknüpfungsänderungen an einer konstanten Anzahl von Knoten.

Nach einer Einfügeoperation kann die AVL-Balance des ganzen Baums immer mit 1 (einer) Einfach- oder Doppelrotation wiederhergestellt werden. Nach einer Löschoperation können mehrere Rebalancierungen vom jeweiligen Teilbaum aus bis hinauf zur Wurzel nötig sein, um die AVL-Balance wiederherzustellen.

Einfachrotation

Abbildung 2: Einfachrotation Links(X)

Die nebenstehende Abbildung 2 zeigt eine Einfachrotation. Auf der linken Seite ist ein Höhenunterschied von ${ \color{Red} 2 }$ bei den beiden Teilbäumen von Knoten X dargestellt. Der innere Neffe t₂₃ des Angelknotens t₁ ist nicht höher als sein Bruder, der äußere Neffe t₄. (Eine solche Situation kann z. B. nach einem Einfügen in den Teilbaum t₄ oder nach einem Löschen aus dem Teilbaum t₁ auftreten. Der in der Abbildung blass gehaltene Fall, dass t₂₃ gleich hoch ist wie t₄, kommt nur beim Löschen vor.)

Die Rebalancierung (gezeigt auf der rechten Seite der Abbildung) ändert lokal die Baumstruktur. Dazu werden einzelne Knoten und Teilbäume in der Hierarchie angehoben und andere abgesenkt. Dieses ist in der Abbildung durch senkrechte rote Pfeile dargestellt. Bei der gezeigten Rotation nach links wird Knoten Z und Teilbaum t₄ um eine Ebene erhöht und Knoten X und Teilbaum t₁ um eine abgesenkt. Die Verknüpfungen werden entsprechend angepasst, so dass Teilbaum t₂₃ seinen Vaterknoten von Z zu X wechselt und Knoten X und Z ihre Position in der Hierarchie tauschen. Im resultierenden Baum ist die Balance wieder hergestellt.

Die Höhe des neuen Baums Z ist nach einer Einfügeoperation gleich wie die von X vor der Operation, während sie nach einer Löschoperation um 1 vermindert oder unverändert ist, je nachdem ob Z rechtslastig war oder nicht.

Zur dargestellten Rotation nach links wird die gespiegelte Version (mit dem Angelknoten auf der rechten Seite) gleichermaßen benötigt.

Doppelrotation

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

Die in der Abbildung 3 gezeigte Situation unterscheidet sich von der aus Abbildung 2 darin, dass der mittlere Teilbaum (mit Wurzel Y), d. i. der innere Neffe des Angelknotens t₁, höher ist als sein Bruder t₄. (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 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.) Eine Einfachrotation wie in Abbildung 2, die den linken Teilbaum absenkt und dafür den rechten anhebt, löst das Problem nicht, dagegen eine Rechtsrotation gefolgt von einer Linksrotation. Diese Doppelrotation, deren Ergebnis auf der rechten Seite von Abbildung 3 gezeigt ist, teilt den mittleren Teilbaum eine Ebene höher auf an die zwei Väter X und Z, senkt dafür X mit dem linken Teilbaum um eine Ebene ab und hebt Y um zwei Ebenen an, wobei Y neuer Vater von X und Z wird.

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

Auch von der Doppelrotation wird die gespiegelte Version benötigt.

Beispiel

Der AVL-Baum in der Abbildung 1 wird

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

rebalanciert.

Implementierung

Jeder Knoten des Baums muss neben den Informationen für den binären Suchbaum einen Balance-Wert enthalten, der angibt, ob der von ihm gewurzelte Unterbaum ausgewogen, rechts- oder linkslastig ist (2 Bits; 1 Bit bei Aufzeichnung bei den Söhnen).

Nach jedem Einfügen oder Löschen eines Knotens wird in seinen Vorfahren auf dem Pfad bis zur Wurzel der Balance-Wert überprüft, berichtigt und ggf. auf AVL-Niveau gebracht. Erreicht man eine Ebene, bei der sich die Höhe des betroffenen Teilbaums nicht mehr ändert, ist die Operation abgeschlossen. Die Anpassungs- und Reparatur-Welle hat pro Ebene einen Dämpfungsfaktor von $\approx \tfrac12$ (gemäß der Annahme, dass etwa die Hälfte der Knoten ausgewogen ist, die andere Hälfte nicht), so dass die Summe der Aufwände für Einfügung und Überprüfung^{[Anm 3]} sowie für Löschung und Überprüfung^{[Anm 5]} jeweils im Mittel konstant ist.

Iterative Programmierung

Der Anwender hat Vorteile davon, wenn der Programmierer die vom Aufschreiben her eleganten Rekursionen durch simple Iterationen ersetzt, da dadurch zunächst einmal der Speicherbedarf für den Programm-Stapelspeicher konstant gehalten werden kann. Für das Aufbewahren des Rückwegs zur Wurzel, der bei der rekursiven Programmierung meist im Programmstapelspeicher steckt, muss dann ein anderes (sparsameres) Konstrukt gewählt werden – eine Art „Cursor“. Ein solches Objekt kann sowohl als Einfügepunkt, als Spezifikation des Löschkandidaten wie auch als Navigationsvehikel bei Traversierungen dienen. Dadurch wird eine Trennung der modifizierenden Operationen von der Navigation möglich.

Trennung der Navigation von den modifizierenden Operationen

Einfüge- und Löschfunktion sind sinnvollerweise von der Suchfunktion zu trennen bei:

• Einsatz weiterer Navigationsfunktionen, z. B. einer in-order-Traversierung
• Datenstrukturen, die mehrere Zugriffspfade besitzen, u. U. mehrere AVL-Strukturen

Vom Vorhandensein zusätzlicher Zugriffspfade hängt es auch ab, ob es genügt, den Pfad zur Wurzel im Cursor zu halten, oder ob ein Zeiger auf den Vaterknoten in jedem Knoten gebraucht wird – somit der Cursor nur aus Knotenzeiger und Richtung besteht.

Beschränktheit der Pfadlänge

Aber auch im ersten Fall ist die Länge des Pfades zur Wurzel durch das exponentielle Anwachsen der Fibonacci-Zahlen f_i beschränkt: maximal 41 Einträge bei 32 Bit und 85 bei 64 Bit breiten 8-Bit-Byte-Adressen. Begründung: Ist die Knotenzahl des AVL-Baums kleiner als beim Fibonacci-Baum der Stufe  h, also  $< \; f_{h+2}-1$, dann ist seine Höhe < h. In einem Adressraum mit 32 Bit breiten Adressen kann man höchstens  $2^{32}/(32/8 \cdot 2 +1) \approx 4{,}8\cdot 10^8$ AVL-Knoten mit 2 Zeigern und 1 Byte unterbringen, das sind weniger als  $701408732 = \, f_{42+2}-1$. Also haben wir bei 32 Bit für die Höhe auf jeden Fall h < 42. Die Ungleichung für 64 Bit breite Adressen lautet:

Knotenzahl  $\leq \frac{2^{64}}{\frac{64}8 \cdot 2+1} \approx 1{,}09 \cdot 10^{18} \,\, < \,\, 1100087778366101930 = f_{86+2}-1$.

Es kostet sowohl bei der Einfüge- wie bei der Löschfunktion nur sehr wenige zusätzliche Maschinenbefehle, den gegebenen Cursor gültig zu halten. Dies ermöglicht bei Massen-Einfügungen und -Löschungen von m benachbarten Schlüsseln Laufzeiten in O(m).

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 Blöcke mit den Attributen (Feldern) Größe und Ort. Für beide Felder gebe es je eine Suchstruktur. Beim Akquirieren wird ein Block von Mindestgröße gesucht, ausgetragen und ein evtl. 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 Einzel-Traversierung) und der zurückgegebene Block ggf. mit diesen verschmolzen. Alle Veränderungen müssen auf beiden Suchstrukturen durchgezogen werden. Wird in beiden Suchstrukturen der Zeiger zum Vaterknoten im Knoten gehalten, dann kann das Hangeln von der einen Suchstruktur zur anderen einen Suchvorgang, d. h. den Aufbau eines Cursors, ersparen.

Parallelisierung

Bei iterativer Programmierung kann man die Anpassungs- und Reparaturschleife auch in der umgekehrten Richtung, d. h. von oben nach unten, durchlaufen. Das ist insbesondere dann relevant, wenn auf den Baum hochgradig parallel (konkurrent) zugegriffen werden soll. Z. B. würde in einem Szenario „Suchen und Einfügen“ die Suchfunktion sich den tiefsten (letzten) unausgewogenen Knoten auf dem Pfad merken, ab dort den Baum sperren^{[Anm 6]} und die Vergleichsergebnisse aufbewahren. Zum Fertigstellen der Einfügeoperation müsste dann der gesperrte Vorfahr (nötigenfalls nach einer Rebalancierung) auf ausgewogen und alle Knoten auf dem Pfad bis zum Blatt auf die den eingeschlagenen Richtungen entsprechenden Balance-Werte gesetzt werden. Der Vorteil wäre, dass alle Knoten außerhalb des gesperrten Teilbaums von den anderen Prozessorkernen gleichzeitig mit der laufenden Einfügung besucht und auch verändert werden könnten.

Realistische Anwendungssituationen mit Performancedaten und -vergleichen mit anderen Suchalgorithmen sind zu finden bspw. bei Ben Pfaff.

Anmerkungen

1. ↑ Bei Binärbäumen wird zweckmäßigerweise dem leeren Baum die Höhe 0 und einem Blatt die Höhe 1 gegeben.
2. ↑ Jeder Bogen des Baums wird genau einmal absteigend und einmal aufsteigend besucht.
3. ↑ ^{a b} Wenn wir $u\in{[{0,1}]}$ als Wahrscheinlichkeit dafür annehmen, dass die Teilbäume ungleiche Höhe haben, dann ist die Wahrscheinlichkeit für gleiche Höhe 1 − u. Ferner wollen wir annehmen, dass der gespiegelte Baum gleich häufig vorkommt wie das Original.
   Nur die Fibonacci-Bäume und alle anderen dünnsten AVL-Bäume erreichen ein $\textstyle u$ nahe $\textstyle 1$. Dagegen kommen nur die vollständig höhenbalancierten Binärbäume mit Knotenzahl $\textstyle 2^h-1$ auf exakt $\textstyle u=0$.
   Wir nehmen folgende Situation rekursiv an: Bei einer Einfügung habe sich ergeben, dass die Höhe des Teilbaums, in dem die Einfügung stattfand, um 1 zugenommen hat. Beim Aufstieg zum Vaterknoten stellen wir fest, von welcher Seite wir kommen. Wir nehmen an: von rechts (das passt zu den Abbildungen 2 und 3; die gespiegelte Alternative führt überdies zu denselben Werten). Wir überprüfen nun die Lage im Vaterknoten und haben die folgenden Fälle zu unterscheiden:

   $\operatorname{bal}$ vor Einfügung		Häufigkeit	$\operatorname{bal}$ nach Einfügung	Rebalan- cierung erforderlich	$\operatorname{bal}$ da- nach	Teilbaum wird höher um	Nächste Ebene zu überprüfen
   − 1	links höher	u / 2	0	Nein		0	Nein
   0	ausgewogen	1 − u	1	Nein		1	Ja
   1	rechts höher	u / 2	2	Ja	0	0	Nein
   Tabelle 2: Zu unterscheidende Fälle nach einer Einfügung

   Die Wahrscheinlichkeit, bei einer Einfügung ausgehend von einer Ebene die nächsthöhere überprüfen zu müssen, ist also q: = 1 − u. Die Wahrscheinlichkeit, dass wenigstens n Ebenen überprüft werden müssen, ist qⁿ und, dass genau n Ebenen überprüft werden müssen, ist qⁿ − q^{n + 1} = (1 − q)qⁿ. Die Anzahl der zu überprüfenden Ebenen summiert sich dann im Mittel auf

   $(1-q)(q+2q^2+3q^3+...)\;=\;\tfrac{(1-q)\,q}{(1-q)^2}\;=\;\tfrac{q}{1-q}\;=\;\tfrac{1-u}{1-(1-u)}\;=\;\tfrac{1-u}{u}$,

   was bei dem plausiblen $u\approx \tfrac12$ ergibt, dass im Mittel etwa eine weitere Ebene überprüft werden muss.
4. ↑ ^{a b} Dieser Vorteil kann nur bei iterativer Programmierung (und Modularisierung der Navigation) ausgeschöpft werden.
5. ↑ ^{a b} Bezüglich der Wahrscheinlichkeitsverteilung treffen wir dieselben Annahmen wie oben.
   Folgende Situation sei rekursiv angenommen: Nach einer Löschung habe sich die Höhe des Teilbaums, in dem die Löschung stattfand, um 1 vermindert. Ferner handele es sich o. B. d. A. um einen linken Teilbaum. Wir überprüfen nun die Lage im Vaterknoten dieses Teilbaums und unterscheiden die folgenden Fälle:

   $\operatorname{bal}$ vor Löschung		Häufigkeit		$\operatorname{bal}$ nach Löschung	Rebalan- cierung erforderlich	$\operatorname{bal}$ da- nach	Teilbaum wird nied- riger um	Nächste Ebene zu überprüfen
   − 1	links höher	u / 2		0	Nein		1	Ja
   0	ausgewogen	1 − u		1	Nein		0	Nein
   1	rechts höher	u / 2	u2 / 2	2	Ja	0	$1^{\;\mathsf 2}$	Ja
   			u(1 − u) / 2			− 1	$0^{\;\mathsf 1}$	Nein
   1 Die letzte Zeile bezieht sich auf den Fall der Einfachrotation mit gleich hohen Neffen und 2 die vorletzte auf Rotationen mit nicht gleich hohen Neffen, d. h. Doppelrotation   (linker Neffe höher) oder Einfachrotation mit dem rechten Neffen höher.
   Tabelle 3: Zu unterscheidende Fälle nach einer Löschung

   Bei einer Löschung ergibt sich eine Wahrscheinlichkeit von weniger als u für die Erfordernis, die nächsthöhere Ebene überprüfen zu müssen. Die Anzahl der zu überprüfenden Ebenen summiert sich dann im Mittel auf weniger als $\tfrac{u}{1-u}$, was beim plausiblen $u\approx \tfrac12$ bedeutet, dass im Mittel weniger als $\approx 1$ Ebene eines Niveaus ≥ 2 überprüft werden muss.
6. ↑ Genau genommen bedarf es einer Kette mit den Gliedern Sperren Sohn und Entsperren Vater bis zum ersten unausgewogenen Knoten, der zunächst gesperrt bleibt, bis er in ein neues Wechselspiel mit den Gliedern Sperren unausgewogenen Knoten und Entsperren Vorfahr eintritt. (Bei einer potenziellen Rebalancierung muss die Sperre sogar eine Ebene höher gehalten werden.) Ist der Einfügepunkt erreicht, kann auch schon mit der Korrektur- und Entsprerrschleife begonnen werden – für maximale Parellelität wieder in einer Sohn-Vater-Kette.
   Wenn alle Mitspieler diese Gerichtetheit des Sperrprotokolls einhalten, kann eine Verklemmung (deadlock) nicht auftreten.
   Für diese Parallelisierung ist auch die Eintrittsinvarianz des Programmcodes erforderlich, was aber bei den modernen Programmiersprachen und Laufzeitsystemen keinerlei Schwierigkeiten bereitet.

Siehe auch

• Rot-Schwarz-Baum
• Splay-Baum
• gewichteter binärer Suchbaum
• B-Baum

Literatur

• Ralf Hartmut Güting, Stefan Dieker: Datenstrukturen und Algorithmen. Stuttgart 2004, ISBN 9783519221210.
• Udi Manber: Introduction to Algorithms – A Creative Approach. 1989, Kapitel 4.3.4, S.75ff, Addison-Wesley Publishing Company.

Weblinks

• Algorithmenvisualisierung u.a. für AVL Bäume
• Ausführlichere Beschreibung mit Delphi-Programm
• Kurz gehaltene Beschreibung der Rotationen
• Animiertes Applet mit Sourcecode und ausführlicher Dokumentation
• Tutorial von Brad Appleton mit Implementierung in C++ (englisch)

• Ben Pfaff „Performance Analysis of BSTs in System Software“ Stanford University, 2004 (englisch)

Referenzen

1. ↑ G. M. Adelson-Velsky, E. M. Landis: An algorithm for the organization of information (Englische Übersetzung aus Doklady Akademii Nauk SSSR 146). In: Soviet Math. Doklady. 3, 1962, S. 1259-1263.
2. ↑ 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.