Quelltext der Seite AVL-Baum

[[Datei:AVL-tree-wBalance K.svg|mini|237px|Abb. 1: AVL-Baum mit [[#Balance|Balance-Faktoren]] (grün)]]Der '''AVL-Baum''' ist  nach den [[Sowjetunion|sowjetischen]] Mathematikern [[Georgi Maximowitsch Adelson-Welski|Georgi Maximowitsch '''A'''delson-'''W'''elski]] und [[Jewgeni Michailowitsch Landis|Jewgeni Michailowitsch '''L'''andis]] benannt, die die Datenstruktur im Jahr 1962 vorstellten.<ref>{{cite journal |author=[[Georgi Maximowitsch Adelson-Welski|G. M. Adelson-Velsky]], [[Jewgeni Michailowitsch Landis|E. M. Landis]] |title=Один алгоритм организации информации |journal=Doklady Akademii Nauk SSSR |volume=146 |pages=263–266 |year=1962}} (russisch)<br />Englische Übersetzung von Myron J. Ricci: {{Webarchiv |url=http://monet.skku.ac.kr/course_materials/undergraduate/al/lecture/2006/avl.pdf |text=''An algorithm for the organization of information.'' |wayback=20140201150909}} (PDF) In: ''Soviet Mathematics'' 3, 1962, S. 1259–1263.</ref> Damit ist der AVL-Baum die älteste Datenstruktur für [[Balancierter Baum|balancierte Bäume]].
{| class="wikitable float-right"
|-
! colspan="3" style="background:#C0C0FF"| AVL-Baum
|-
!
| colspan="2" style="text-align:center" | [[Landau-Symbole|Komplexität]]
|-
! style="text-align:left"| Platz
| colspan="2" style="text-align:right" | <math>\mathcal{O}(n)</math>
|-
| Operation
| style="text-align:right" | im Mittel
| style="text-align:right" | [[Worst Case]]
|-
! style="text-align:left"| [[#Suchen|Suchen]]
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
|-
! style="text-align:left"| [[#Traversieren|Querschritt]]
| style="text-align:right" | <math>\mathcal{O}(1)</math>
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
|-
! style="text-align:left"| [[#Aufsuchen erstes oder letztes Element|Min, Max]]
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
|-
! style="text-align:left"| [[#Einfügen|Einfügen]]
| style="text-align:right" | <math>\mathcal{O}(1)</math>{{FN|†}}
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
|-
! style="text-align:left"| [[#Löschen|Löschen]]
| style="text-align:right" | <math>\mathcal{O}(1)</math>{{FN|†}}
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
|-
! style="text-align:left"| [[#Verketten|Verketten]]
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
|-
! style="text-align:left"| [[#Spalten|Spalten]]
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
| style="text-align:right" | <math>\mathcal{O}(\log n)</math>
|-
| colspan="3" | <math>n</math>&nbsp;Knoten im Baum<br />{{FNZ|†|ohne [[#Navigieren|Navigation]]}}
|-
| colspan="3" | <small>Platz- und Zeit-Komplexitäten</small>
|}

Er bildet eine [[Datenstruktur]] in der [[Informatik]] in Form eines [[binärer Suchbaum|binären Suchbaums]] mit der zusätzlichen Eigenschaft, dass sich an jedem [[Knoten (Graphentheorie)|Knoten]] die [[Höhe (Graphentheorie)|Höhe]] der beiden Teilbäume um höchstens eins unterscheidet.<ref>Thomas H. Cormen u.&nbsp;a.: ''Introduction to Algorithms''. 2. Auflage, MIT Press, Cambridge (Massachusetts) 2001, S. 296.</ref> Diese Eigenschaft lässt seine [[Binärbaum#Begriffe|Höhe]] nur [[Komplexitätstheorie#Anforderungen an Schrankenfunktionen|logarithmisch]] mit der Zahl der [[Binärer Suchbaum|Schlüssel]] wachsen und macht ihn zu einem [[Balancierter Baum|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|Einfügen]] und [[#Löschen|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 [[#Rebalancierung|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 [[Binärer Suchbaum#Motivation|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 ==

{{Anker|Balance-Faktor|Balance}}Als den '''Balance-Faktor'''<ref>In 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.</ref> <math>\mathrm{BF}(t)</math> eines Knotens resp. Teilbaums<ref group="Anm">Da einem Knoten in [[Bijektive Funktion|umkehrbar eindeutiger]] Weise der von ihm [[Gewurzelter Baum|gewurzelte]] maximale Unterbaum, „sein“ ''Teilbaum'', zugeordnet werden kann, sollen der Kürze halber Eigenschaften wie Höhe, Balance, [[Gewurzelter Baum#Weitere Begriffe|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.<br />
Umgekehrt fungiert, zum Beispiel beim Umhängen eines Teilbaums, dessen Wurzel als „Henkel“.</ref> <math>t</math> in einem [[Binärbaum]] bezeichnet man die Höhendifferenz
:<math>\mathrm{BF}(t) := \mathrm{Height}(t_r) - \mathrm{Height}(t_l)</math>,<ref group="Anm">Im Prinzip kann man auch die gespiegelte Differenz nehmen. Der Text folgt Knuth und vielen weiteren Autoren.</ref>
wobei <math>\mathrm{Height}(t)</math> die Höhe des Baums <math>t</math>, und <math>t_l</math> der linke, <math>t_r</math> der rechte Kindbaum von <math>t</math> ist.<ref group="Anm">Die Rekursionsgleichung für die Höhe ist
:<math>\mathrm{Height}(t) := 1+\max(\mathrm{Height}(t_r), \mathrm{Height}(t_l))</math>.</ref> Ein Knoten <math>t</math> mit <math>\mathrm{BF}(t) = 0</math> wird als höhengleich oder ausgewogen, einer mit <math>\mathrm{BF}(t) < 0</math> als links- und einer mit <math>\mathrm{BF}(t) > 0</math> als rechtslastig bezeichnet.

Ein binärer (Such-)Baum ist genau dann ein AVL-Baum, wenn die '''AVL-Bedingung'''
:<math>-1 \; \leq \; \mathrm{BF}(t) \; \leq \; +1</math>
an jedem Knoten <math>t</math> eingehalten wird.<ref group="Anm">Aus den Balance-Faktoren ([[#BF 1 Bit|≤ 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.</ref>

=== Eigenschaften ===
Diese Definition beschränkt die Höhe <math>\mathrm{Height}(t)</math><ref group="Anm">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</ref> eines AVL-Baums <math>t</math> mit <math>n</math> Knoten (Schlüsseln) durch die Ungleichung<ref>Donald E. Knuth: ''The Art of Computer Programming.'' Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 460.</ref>
:<math>\log_2 (n + 1) \; \leq \; \mathrm{Height}(t) \; < \; c \log_2 (n + 2) + b </math>
mit {{Anker|ObereSchranke}}<math>c := \frac 1{\log_2 \Phi} \approx 1{,}440420</math>, <math>b := \frac{c}2 \log_2 5 - 2 \approx \; -0{,}327724</math> und <math>\Phi := \frac{1+\sqrt 5}2 \approx 1{,}618034</math> (Zahl des [[Goldener Schnitt|goldenen Schnitts]]).

Die untere Schranke kommt vom [[Binärbaum#Vollständiger Binärbaum und vollständig balancierter Binärbaum|''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.<ref>Ben Pfaff: ''Performance Analysis of BSTs in System Software.'' S. 2.</ref>

=== 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 [[Abstrakter Datentyp|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 [[Suchbaum|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]]) [[Komplexitätstheorie#Anforderungen an Schrankenfunktionen|logarithmische]] Komplexität haben, gehört der AVL-Baum zu den [[Balancierter Baum#Höhenbalance|höhenbalancierten]] binären Suchbäumen.

=== Navigieren ===

Die ''Navigationsoperationen'', das sind die verschiedenen Suchoperationen, das {{Anker|Traversieren}}'''Traversieren''' und '''Iterieren''', {{Anker|Aufsuchen erstes oder letztes Element}}'''Aufsuchen erstes oder letztes Element''' und ähnliche, lassen den Baum unverändert und funktionieren im Prinzip auf jedem [[Binärer Suchbaum|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.

{{Anker|Suchen}}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 [[Wahlfreier Zugriff|direkten Zugriff]] (im Gegensatz zum [[Sequentieller Zugriff|sequentiellen Zugriff]] der [[Binärbaum#Traversierung|Traversierung]]). Sie wird in der Regel als vorausgehende Operation sowohl beim Einfügen als auch beim Löschen eingesetzt.

Das Suchen setzt eine [[Quasiordnung#Totale Quasiordnung|totale Quasiordnung]] auf der Menge der Schlüssel voraus, die am flexibelsten durch eine [[Binärer Suchbaum#Ordnungsrelation|Vergleichsfunktion]] bereitgestellt wird.

Das mittlere Laufzeitverhalten des Suchens in einem binären Suchbaum wird durch die [[Binärer Suchbaum#Suchtiefen und Pfadlängensummen|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 {{nowrap|als 1.<ref group="Anm">Strebt beim Fibonacci-Baum die Anzahl <math>n</math> der Knoten gegen unendlich, dann verhält sich seine [[Fibonacci-Baum#Suchtiefe|mittlere Suchtiefe]] [[Asymptote|asymptotisch]] wie
: <math>a \log_2 n</math> &nbsp; &nbsp; mit &nbsp; &nbsp; <math>a := \frac {c \Phi}{\sqrt 5} = \frac {\Phi}{\sqrt 5 \; \log_2 \Phi} \approx 1{,}042298</math>,
weicht also nur um etwa 4&nbsp;Prozent von der idealen eines vollständigen Binärbaums ab. (Allerdings sind hinsichtlich der Suchtiefe nicht notwendigerweise die Fibonacci-Bäume am schlechtesten balanciert; bspw. gibt es einen AVL-Baum der Höhe 5 mit 20 Knoten (linker Teilbaum vollständig der Höhe 4, rechter Fibonacci der Höhe 3) und der externen Pfadlängensumme 97, im Vergleich zu 96 beim Fibonacci-Baum der Höhe 6 mit gleicher Knotenzahl. Diese AVL-Bäume sind aber schwieriger zu charakterisieren als die Fibonacci-Bäume.)</ref>}}

=== {{Anker|Einfügen}}Einfügen (Eintragen) ===
Es sei angenommen, dass die Navigation zum '''Einfügepunkt''' bereits erfolgt ist. Ein Einfügepunkt ist ein [[Binärer Suchbaum#Knotenorientierte Speicherung|externes Blatt]]<ref> Donald E. Knuth: ''The Art of Computer Programming.'' Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 460.</ref> 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.

{{Anker|EinfügenÜ}}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 [[Weg (Graphentheorie)|Pfad]] der [[Binärer Suchbaum#Begriffsklärung|Elterknoten]] zurück bis u.&nbsp;U. zur [[Binärer Suchbaum#Terminologie|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“).<ref>Diesen Weg geht Donald Knuth in Donald E. Knuth: ''The Art of Computer Programming.'' S. 462.</ref> 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.<ref>Ben Pfaff: ''An Introduction to Binary Search Trees and Balanced Trees.'' §&nbsp;34.</ref>
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|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 <math>(n+1)</math>-ten Knotens in einen AVL-Baum mit <math>n</math> 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.<ref group="Anm" name="ISRT">{{Anker|Wahrscheinlichkeit_u}}
Sei <math>G</math> die Anzahl der Knoten, die nicht Blätter sind und die zwei Kindbäume ''gleicher'' Höhe haben, und <math>U</math> die Anzahl der Knoten mit verschieden hohen Kindbäumen, dann ist <math>u:=\tfrac {U}{G+U} \in [0,1]</math> der Anteil der höhenungleichen.
(Nur die [[Fibonacci-Baum|Fibonacci-Bäume]] und die [[Fibonacci-Baum#Andere dünnste AVL-Bäume|anderen dünnsten AVL-Bäume]] erreichen exakt <math>u=1.</math> Dagegen kommen nur die [[Binärbaum#Begriffe|vollständigen Binärbäume]] (mit <math>2^{h-1}-1 </math> inneren Knoten) auf exakt <math>u=0.</math>
Der Mittelwert über alle möglichen Formen von AVL-Bäumen liegt bei {{nowrap|<math>u \approx 0{,}3</math>.)}}<br />
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:
{| class="wikitable left" style="text-align:center;"
|-
|''BF''<br />vor<br />Einfügung||&nbsp;|| style="width:8.9em;" |Häufigkeit||vorläu-<br />figer<br />''BF''||Rebalan-<br />cierung<br />erforderlich||''BF''<br />da-<br />nach|| style="width:5em;" |Teilbaum<br />wird<br />höher&nbsp;um||Ebene&nbsp;ober-<br />halb zu<br />überprüfen
|-
|−1||links höher||<math>\tfrac u2</math>||0|| colspan="2" |Nein||0||Nein
|-
|0||höhengleich||<math>1-u</math>||+1|| colspan="2" |Nein||1||Ja
|-
| +1||rechts höher||<math>\tfrac u2</math>||+2||Ja||0||0||Nein
|-
| colspan="8" style="text-align:left" |<small>Tab. 2: Nach dem Einfügen: Die neuen [[#Balance|Balance-Faktoren]] (''BF'') in Abhängigkeit von den alten</small>
|}
Die Wahrscheinlichkeit, bei einer Einfügung ausgehend von einer Ebene die nächsthöhere überprüfen zu müssen, ist also <math>q:=1-u.</math> Unter der Annahme, dass diese Wahrscheinlichkeiten für alle Ebenen gleich sind, ist die Wahrscheinlichkeit, dass wenigstens <math>n</math> Ebenen überprüft werden müssen, gleich <math>q^n</math> und, dass genau <math>n</math> Ebenen überprüft werden müssen, gleich <math>q^n-q^{n+1}=(1-q) \, q^n.</math>
Somit summiert sich die Anzahl der zu überprüfenden Ebenen im Mittel auf
:<math>
\begin{align}(1-q)(q+2q^2+3q^3+...)\;&=\;q+q^2+q^3+...\;
\\&=\;\frac{q}{1-q}\;=\;\frac{1-u}{1-(1-u)}\;=\;\frac{1-u}{u}.
\end{align}</math>
Diese Funktion in <math>u</math> [[Monotone reelle Funktion|fällt monoton]] von <math>+\infty</math> (für <math>u=0</math> und vollständige Binärbäume) auf <math>0</math> (für <math>u=1</math> und Fibonacci-Bäume).
Nach dem Einfügen (mit Korrektur des Balance-Faktors) ist für <math>u \in [0{,}25 ; 0{,}5] </math> die mittlere Anzahl der nachträglich zu überprüfenden Ebenen zwischen 3 und 1.</ref>
Es kann sogar gezeigt werden, dass der Modifikationsaufwand in einem reinen Einfügeszenario [[Amortisierte Laufzeitanalyse|amortisiert]] konstant ist.<ref name="Dinesh">Dinesh P. Mehta, Sartaj Sahni (Hrsg.) ''Handbook of Data Structures and Applications'' 10.4.2</ref>
{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;"
|style="text-align:left; font-size: 95%;"| '''Code-Schnipsel'''&nbsp;&nbsp;
|-
|
Bei der Einfügung des neuen Knotens Z als Kind von X wächst die Höhe dieses Teilbaums Z von 0 auf 1.

'''[[Schleifeninvariante]] bei der Einfügung'''

Die Höhe des Teilbaums Z erhöht sich um 1. Er ist in AVL-Form.
<syntaxhighlight lang="d">
 // Schleife vom Blatt bis möglicherweise zur Wurzel:
 for (X = Z->parent; X != null; X = Z->parent) {
     if (Z == X->childR) { // Der rechte Teilbaum ist es, der höher wird.
         if (X->BF <= 0) {    // X ist nicht rechtslastig
             if (X->BF < 0) { // X ist linkslastig
                 X->BF = 0; // Z’s Höhenzunahme aufgefangen bei X
                 break; // Verlassen der Schleife
             }
             X->BF = +1;
             Z = X; // Height(Z) wird höher um 1
             continue;
         }
         else {              // X ist rechtslastig
             // ===> X->BF temporär == +2
             // ===> Rebalancierung erforderlich
             G = X->parent; // Retten X->parent vor Rotation
             if (Z->BF < 0)                 // Rechts-Links-Situation   (s. Abbildung 3)
                 N = rotate_RightLeft(X,Z); // Doppelrotation: Right(Z) dann Left(X)
             else                           // Rechts-Rechts-Situation  (s. Abbildung 2)
                 N = rotate_Left(X,Z);      // Einfachrotation Left(X)
         }
     }
     else { // Z == X->childL: der linke Teilbaum wird höher
         if (X->BF >= 0) {    // X ist nicht linkslastig
             if (X->BF > 0) { // X ist rechtslastig
                 X->BF = 0; // Z’s Höhenzunahme aufgefangen bei X
                 break; // Verlassen der Schleife
             }
             X->BF = –1;
             Z = X; // Height(Z) wird höher um 1
             continue;
         }
         else {               // X ist linkslastig
             // ===> X->BF temporär == –2
             // ===> Rebalancierung erforderlich
             G = X->parent; // Retten X->parent vor Rotation
             if (Z->BF > 0)      // Links-Rechts-Situation
                 N = rotate_LeftRight(X,Z); // Doppelrotation: Left(Z) dann Right(X)
             else                           // Links-Links-Situation
                 N = rotate_Right(X,Z);     // Einfachrotation Right(X)
         }
     }
     // Nach der Rotation die Anpassung der Verknüpfung N<->G:
     // N ist die neue Wurzel des rebalancierten Teilbaums
     // Höhe ändert sich nicht: Height(N) == alte Height(X)
     N->parent = G;
     if (G != null) {
         if (X == G->childL)
             G->childL = N;
         else
             G->childR = N;
     }
     else
         tree->root = N; // N ist die neue Wurzel des ganzen Baums
     break;

     // Da ist kein fall thru, nur break; oder continue;
 }
 // Wird die Schleife nicht durch ein break; beendet,
 //   dann wird der ganze Baum um 1 höher.
</syntaxhighlight>
|}

=== {{Anker|Löschen}} 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 (s. [[Binärer Suchbaum#Löschen|Binärer Suchbaum]]). Einfach sind die Fälle, wo der zu löschende Knoten ein (Halb-)Blatt ist. Hat er aber zwei Kinder, müssen die beiden frei werdenden Teilbäume neu aufgehängt werden. Dazu wählt man einen der [[Binärbaum#Traversierung|In-order]]-Nachbarn, also entweder den rechtesten Knoten des linken Kindbaums oder den linkesten des rechten Kindbaums, als Ersatzelter,<ref>Laut [[Robert Sedgewick (Informatiker)|Robert Sedgewick]], Kevin Wayne: [https://bank.engzenon.com/tmp/5e7f6ee5-d4dc-4aa8-9b0a-42d3c0feb99b/6062caf3-c600-4fc2-b413-4ab8c0feb99b/Algorithms-4th-Edition.pdf ''Algorithms Fourth Edition.''] (PDF)https://bank.engzenon.com/tmp/5e7f6ee5-d4dc-4aa8-9b0a-42d3c0feb99b/6062caf3-c600-4fc2-b413-4ab8c0feb99b/Algorithms-4th-Edition.pdf (PDF) Pearson Education, 2011, ISBN 978-0-321-57351-3, S. 410 (englisch, abgerufen am 25. März 2018) stammt der Vorschlag aus dem Jahr 1962 von T. Hibbard. In Ben Pfaff: ''An Introduction to Binary Search Trees and Balanced Trees.'' S. 39 wählt Ben Pfaff –&nbsp;so vorhanden&nbsp;– stets den letzteren. Man kann aber auch den ersteren nehmen oder von beiden Teilbäumen den eventuell höheren.</ref> 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.

{{Anker|LöschenÜ}}Wenn ein Blatt, das ist ein Teilbaum bestehend aus 1 Knoten, entfernt wird, vermindert sich dessen Höhe von 1 auf 0, und wenn ein Blatt an die Stelle eines Halb-Blatts nachrückt, vermindert sich dessen Höhe von 2 auf 1.
Alle Höhenänderungen müssen wenigstens in den AVL-Balance-Faktoren reflektiert werden.<ref group="Anm">Wie beim Einfügen kann der Baum auch beim Löschen von oben nach unten („top-down“) repariert werden. Der Einfachheit halber sei hier nur die Reparatur von unten nach oben („bottom-up“) erläutert. So spielt sie sich auch bei rekursiver Programmierung ab.</ref>
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 ±1 (er war vorher 0), dann ändert sich die Höhe nicht – mit der Folge, dass die Balance-Faktoren oberhalb bleiben können, wie sie sind, und das AVL-Kriterium für den ''ganzen'' Baum erfüllt ist.
# Wird der Balance-Faktor zu 0, verringert sich die Höhe des Teilbaums um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen.
# Wird der Balance-Faktor zu ±2, muss der Teilbaum rebalanciert werden (siehe [[#Rebalancierung|Rebalancierung]] weiter unten). Danach kann bei der Löschoperation der neue Teilbaum eine um 1 niedrigere Höhe als vorher haben – mit der Folge, dass weiterhin überprüft und gegebenenfalls rebalanciert werden muss.<br />Es kommt aber auch vor, dass sich die gleiche Höhe wie vor dem Löschen ergibt, sodass die Balance-Faktoren oberhalb bleiben können, wie sie sind, und das AVL-Kriterium für den ''ganzen'' Baum auch schon erfüllt ist.

Der Aufwand fürs Löschen ist im schlechtesten Fall logarithmisch (mit oder ohne Suchen); im Mittel aber – bspw. wenn das Auffinden des Löschkandidaten nicht mitgerechnet werden muss, weil es anderweitig bewerkstelligt werden kann – 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.<ref group="Anm" name="DLET">Über den Anteil der höhenungleichen Knoten seien dieselben Annahmen wie bei der [[#Wahrscheinlichkeit u|Einfügung]] gemacht.<br />
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 [[ohne Beschränkung der Allgemeinheit]] um einen linken Kindbaum. Bei der Überprüfung der Lage im Elterknoten dieses Teilbaums sind die folgenden Fälle zu unterscheiden:
{| class="wikitable" style="text-align:center;"
|-
|''BF''<br />vor<br />Löschung||&nbsp;|| colspan="2" |Häufigkeit||vorläu-<br />figer<br />''BF''||Rebalan-<br />cierung<br />erforderlich||''BF''<br />da-<br />nach|| style="width:5em;" |Teilbaum<br />wird&nbsp;nied-<br />riger&nbsp;um||Ebene&nbsp;ober-<br />halb zu<br />überprüfen
|-
|−1||links höher|| colspan="2" |<math>\tfrac u2</math>||0|| colspan="2" |Nein||1||Ja
|-
|0||höhengleich|| colspan="2" |<math>1-u</math>||+1|| colspan="2" |Nein||0||Nein
|-
| rowspan="2" | +1|| rowspan="2" |rechts höher|| rowspan="2" style="width:1.7em;" |<math>\tfrac u2</math>|| style="width:6.6em;" |<math>\tfrac u2 (1-u)</math>|| rowspan="2" |+2|| rowspan="2" |Ja||+1||0&nbsp;{{FN|1}}||Nein
|-
|<math>\tfrac u2 (\tfrac u2 + \tfrac u2)</math>||0||1&nbsp;{{FN|2}}||Ja
|-
| colspan="9" style="text-align:left" |{{FNZ|1|Die vorletzte Zeile bezieht sich auf den Fall der Einfachrotation mit [[#EinfachrotationGleicheHöhe|gleich hohen Kindern]] und}}
{{FNZ|2|die letzte auf Rotationen mit nicht gleich hohen Kindern des höheren Knotens ''Z'' (s. Abb. 2 und 3), d.&nbsp;h.<br />&nbsp; [[#Doppelrotation|Doppelrotation]] (linkes Kind ''Y'' höher) resp. Einfachrotation mit dem rechten Kind ''t<sub>4</sub>'' höher.}}
|-
| colspan="9" style="text-align:left" |<small>Tab. 3: Nach dem Löschen: Die neuen [[#Balance|Balance-Faktoren]] (''BF'') in Abhängigkeit von den alten</small>
|}
Bei einer Löschung ergibt sich eine Wahrscheinlichkeit <math>q := \tfrac{u}2(1+u) </math> für das Erfordernis, die nächsthöhere Ebene überprüfen zu müssen. Unter der Annahme, dass diese Wahrscheinlichkeiten für alle Ebenen gleich sind, summiert sich die mittlere Anzahl der zu überprüfenden Ebenen auf
:<math>\frac q{1-q} = \frac {u(1+u)}{(2+u)(1-u)}</math>.
Diese Funktion in <math>u</math> [[Monotone reelle Funktion|wächst monoton]] von <math>0</math> (für <math>u=0</math> und vollständige Binärbäume) auf <math>+\infty</math> (für <math>u=1</math> und Fibonacci-Bäume).
Nach dem Löschen (mit Korrektur des Balance-Faktors) muss für <math>u < \Phi-1 \approx 0{,}618 </math> im Mittel weniger als ungefähr eine weitere Ebene überprüft werden.</ref>
{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;"
|style="text-align:left; font-size: 95%;"| '''Code-Schnipsel'''&nbsp;&nbsp;
|-
|
Bei der Löschung eines Knotens N als Kind von X geht der entsprechende Teilbaum von X von Höhe 1 auf 0 oder von Höhe 2 auf 1, wenn N noch ein (inneres) Kind hatte.

'''Schleifeninvariante bei der Löschung'''

Die Höhe des Teilbaums N verringert sich um 1. Er ist in AVL-Form.
<syntaxhighlight lang="d">
 // Schleife vom Blatt bis möglicherweise zur Wurzel:
 for (X = N->parent; X != null; X = G) {
     G = X->parent; // Retten X->parent vor Rotation
     if (N == X->childL) { // Der linke Teilbaum ist es, der niedriger wird.
         if (X->BF <= 0) {    // X ist nicht rechtslastig
             if (X->BF < 0) { // X ist linkslastig
                 X->BF = 0;
                 N = X;       // Height(N) wird niedriger um 1
                 continue;
             } // X->BF == 0
             X->BF = +1;      // N’s Höhenabnahme aufgefangen bei X
             break; // Verlassen der Schleife
         }
         else { // X ist rechtslastig
             // ===> X->BF temporär == +2
             // ===> Rebalancierung erforderlich
             Z = X->childR; // das Geschwister von N (höher um 2)
             b = Z->BF;
             if (b < 0)                     // Rechts-Links-Situation   (s. Abbildung 3)
                 N = rotate_RightLeft(X,Z); // Doppelrotation: Right(Z) dann Left(X)
             else                           // Rechts-Rechts-Situation  (s. Abbildung 2)
                 N = rotate_Left(X,Z);      // Einfachrotation Left(X)
         }
     }
     else { // (N == X->childR): Der rechte Teilbaum wird niedriger
         if (X->BF >= 0) {    // X ist nicht linkslastig
             if (X->BF > 0) { // X ist rechtslastig
                 X->BF = 0;
                 N = X;       // Height(N) wird niedriger um 1
                 continue;
             } // X->BF == 0
             X->BF = –1;      // N’s Höhenabnahme aufgefangen bei X
             break; // Verlassen der Schleife
         }
         else { // X ist linkslastig
             // ===> X->BF temporär == –2
             // ===> Rebalancierung erforderlich
             Z = X->childL; // das Geschwister von N (höher um 2)
             b = Z->BF;
             if (b > 0)                     // Links-Rechts-Situation
                 N = rotate_LeftRight(X,Z); // Doppelrotation: Left(Z) dann Right(X)
                else                        // Links-Links-Situation
                 N = rotate_Right(X,Z);     // Einfachrotation Right(X)
         }
     }
     // Nach der Rotation die Anpassung der Verknüpfung N<->G:
     // N ist die neue Wurzel des rebalancierten Teilbaums
     N->parent = G;
     if (G != null) {
         if (X == G->childL)
             G->childL = N;
         else
             G->childR = N;
     }
     else
         tree->root = N; // N ist die neue Wurzel des ganzen Baums

     if (b == 0) // der in Abbildung 2 blass gehaltene Fall
         break;  // Die Höhe ändert sich nicht: Verlassen der Schleife.

     // Height(N) wird niedriger um 1 (== alte Height(X)-1)
 }
 // Wird die Schleife durch (N->parent == null) beendet,
 //   dann verringert sich die Höhe des ganzen Baums um 1.
</syntaxhighlight>
|}

== Rebalancierung ==
{{Anker|Abb_simple}}[[Datei:AVL-simple-left K.svg|mini|182px|Abb. 2: Einfachrotation<br />''Links''(''X'')]]

Wenn bei einer Operation ein Höhenunterschied von mehr als 1 zwischen zwei Geschwister-Teilbäumen entsteht, ist beim Elterknoten das AVL-Kriterium verletzt. Eine entsprechende Korrektur heißt „Rebalancierung“. Als Werkzeuge hierfür eignen sich die sogenannten [[Binärbaum#Rotation in binären Bäumen|Rotationen]].

Für Einfügungen und Löschungen, bei denen die temporäre Höhendifferenz absolut 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<ref>Die Abbildungen entsprechen Donald E. Knuth: ''The Art of Computer Programming.'' Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 461 Case1 (Einfachrotation) und Case2 (Doppelrotation).</ref>), das ist das Kind mit einer Kindesrichtung, die der von ''Z'' entgegengesetzt ist, (''t<sub>23</sub>'' in der Abbildung&nbsp;2 beziehungsweise ''Y'' in der Abbildung&nbsp;3) ''nicht höher'' ist als sein Geschwister, das äußere Kind (''t<sub>4</sub>'' 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.

Die Schlüssel bewegen sich bei Rotationen nur „vertikal“ (innerhalb der senkrechten Raster). Die [[Binärbaum#Traversierung|In-order-Reihenfolge]] der Knoten, die ja die Sortierreihenfolge („horizontal“) abbildet, bleibt also vollkommen erhalten.

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

=== Einfachrotation ===
Sie wird im Original Малое вращение ''(kleine Drehung)'' genannt.

Die obenstehende Abbildung&nbsp;2 zeigt eine Rechts-Rechts-Situation. In der oberen Hälfte haben die beiden Teilbäume ''Z'' und ''t<sub>1</sub>'' des Knotens ''X'' einen Höhenunterschied von <span style="color:#FF0000;">+2</span>. Das innere Kind ''t<sub>23</sub>'' des um 2 höheren Knotens ''Z'' ist ''nicht höher'' als sein Geschwister ''t<sub>4</sub>''.<br />
Dies kann nach einem Einfügen in den Teilbaum ''t<sub>4</sub>'' oder nach einem Löschen aus dem Teilbaum ''t<sub>1</sub>'' auftreten.
{{Anker|EinfachrotationGleicheHöhe}}Der in der Abbildung&nbsp;2 blass gehaltene Fall, dass ''t<sub>23</sub>'' gleich hoch ist wie ''t<sub>4</sub>'', kommt nur beim Löschen vor.

Die Rebalancierung (gezeigt in der unteren Hälfte der Abbildung) gelingt durch eine Einfachrotation nach links. Die anzupassenden 3 Verknüpfungen sind in der Abbildung verstärkt gezeichnet, und bei beiden Knoten ''X'' und ''Z'' ändern sich die Balance-Faktoren.

Die Höhe des neuen Teilbaums ''Z'' ist bei einer Einfügung gleich der von ''X'' vor der Operation. Dies ist bei einer Löschung genauso, wenn ''Z'' nicht rechtslastig war. Bei rechtslastigem ''Z'' vermindert sich jedoch die Höhe um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen.

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

{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;"
|style="text-align:left; font-size: 95%;"| '''Code-Beispiel rotate_Left'''&nbsp;&nbsp;
|-
|
{|
|-
|style="width:9em;"| Eingabe: || X = Wurzel des Teilbaums, der nach links rotiert werden soll
|-
| || Z = sein rechtes Kind, <ins>nicht</ins> linkslastig
|-
| || &nbsp; &nbsp; mit Höhe <math>\mathrm{Height}(Z) == \mathrm{Height}(X\to\text{childL}) + 2</math>
|-
|Rückgabewert: || die neue Wurzel des rebalancierten Teilbaums
|}
<syntaxhighlight lang="d">
 node* rotate_Left(node* X,node* Z) {
     // Z is um 2 höher als sein Geschwister
     t23 = Z->childL; // das innere Kind von Z
     X->childR = t23;
     if (t23 != null)
         t23->parent = X;

     Z->childL = X;
     X->parent = Z;

     // Kommt bei einer Einfügung nicht vor:
     if (Z->BF == 0) { // t23 war gleich hoch wie t4
         X->BF = +1;   // t23 jetzt höher
         Z->BF = –1;   // t4  jetzt niedriger als X
     } else
     // Ende: Nicht bei Einfügung
     {
         X->BF = 0;
         Z->BF = 0;
     }

     return Z; // return neue Wurzel des rebalancierten Teilbaums
 }
</syntaxhighlight>
|}

=== Doppelrotation ===
[[Datei:AVL-double-rl K.svg|mini|229px|Abb. 3: Doppelrotation<br />''RechtsLinks''(''X'', ''Z'') = ''Rechts''(''Z'') + ''Links''(''X'')]]
Sie wird im Original Большое вращение ''(große Drehung)'' genannt.

Die in der Abbildung&nbsp;3 gezeigte Situation unterscheidet sich von der in Abbildung&nbsp;2 darin, dass der mittlere Kindbaum (mit Wurzel ''Y''), das ist das innere Kind des um 2 höheren Knotens ''Z'', ''höher'' ist als sein Geschwister ''t<sub>4</sub>'': eine Rechts-Links-Situation, da ''X'' rechts- und ''Z'' linkslastig ist.<br />
Das kann nach der Einfügung des Knotens ''Y'' oder einer Einfügung in einen der Teilbäume ''t<sub>2</sub>'' oder ''t<sub>3</sub>'' oder nach einer Löschung aus dem Teilbaum ''t<sub>1</sub>'' passieren.
Der Fall, bei dem die Teilbäume ''t<sub>2</sub>'' und ''t<sub>3</sub>'' gleich hoch sind und der Teilbaum ''Y'' höher als ''t<sub>4</sub>'', kommt nur bei der Löschung vor.

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, und bei allen 3 Knoten ''X'', ''Y'' und ''Z'' ändern sich die Balance-Faktoren.<ref group="Anm">Man beachte, dass im Fall eines rechtslastigen ''Y'' die erste Teilrotation einer Doppelrotation die Situation im betroffenen Teilbaum ''Y'' sogar verschlechtert; erst die zweite mit einer Rotationsachse außerhalb bringt die Sache in Ordnung. Somit entspricht, was die Balance-Faktoren angeht, weder die erste noch die zweite Teilrotation einer AVL-[[#Einfachrotation]].</ref>

Die Höhe des neuen Teilbaums ''Y'' ist nach einer Einfügung gleich der von ''X'' vor der Operation. Bei einer Löschung ist die Höhe jedoch um 1 vermindert, mit der Folge, dass oberhalb die Überprüfung der Balance-Faktoren weitergehen muss.

Bei einer Links-Rechts-Situation wird die gespiegelte Version, das heißt eine Linksrotation gefolgt von einer Rechtsrotation, benötigt.
{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;"
|style="text-align:left; font-size: 95%;"| '''Code-Beispiel rotate_RightLeft'''&nbsp;&nbsp;
|-
|
{|
|-
|style="width:9em;"| Eingabe: || X = Wurzel des Teilbaums, der rotiert werden soll
|-
| || Z = sein rechtes Kind, <ins>linkslastig</ins>
|-
| || &nbsp; &nbsp; mit Höhe <math>\mathrm{Height}(Z) == \mathrm{Height}(X\to\text{childL}) + 2</math>
|-
|Rückgabewert: || die neue Wurzel des rebalancierten Teilbaums
|}
<syntaxhighlight lang="d">
 node* rotate_RightLeft(node* X,node* Z) {
     // Z is um 2 höher als das Geschwister
     Y = Z->childL; // das innere Kind von Z
     // Y is um 1 höher als das Geschwister
     t3 = Y->childR;
     Z->childL = t3;
     if (t3 != null)
         t3->parent = Z;
     Y->childR = Z;
     Z->parent = Y;
     t2 = Y->childL;
     X->childR = t2;
     if (t2 != null)
         t2->parent = X;
     Y->childL = X;
     X->parent = Y;
     if (Y->BF == 0) { // t2 und t3 gleich hoch
                       // (beide null im Fall der Einfügung von Y)
         X->BF = 0;
         Z->BF = 0;
     } else
     // Ende: Nicht bei Einfügung
     if (Y->BF > 0) {  // t3 war höher
         X->BF = –1;   // t1 jetzt höher
         Z->BF = 0;
     } else
     {                 // t2 war höher
         X->BF = 0;
         Z->BF = +1;   // t4 jetzt höher
     }
     Y->BF = 0;

     return Y; // return neue Wurzel des rebalancierten Teilbaums
 }
</syntaxhighlight>
|}

=== Beispiel ===
Der AVL-Baum in der Abbildung&nbsp;1 wird
* nach der Löschung des Knotens »G« durch die zwei Einfachrotationen <span style="white-space:nowrap">''Rechts''(»F«)</span>, später <span style="white-space:nowrap">''Links''(»J«)</span>
* nach der Einfügung eines Knotens »T« durch die Doppelrotation <span style="white-space:nowrap">''LinksRechts''(»V«, »S«)</span>
rebalanciert.

== Operationen mit ganzen AVL-Bäumen ==

Die folgenden zwei Operationen haben ganze AVL-Bäume als Ein- und Ausgabeoperanden. Sie gehören nicht zum Standardsatz und fehlen in manchen Implementierungen. Es soll aber hier gezeigt werden, dass auch sie mit logarithmischem Aufwand durchgeführt werden können.

=== Verketten ===
[[Datei:AVL-concat.svg|mini|216px|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.<ref name="Knuth-S474">Donald E. Knuth: ''The Art of Computer Programming'', Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 474</ref>
{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;"
|style="text-align:left; font-size: 95%;"| '''Algorithmus'''&nbsp;&nbsp;
|-
|
Man steigt an der rechten Flanke des ersten Baums (siehe Abbildung&nbsp;4 – die grauen Pfeile zeigen den Weg durch den Graphen) und an der linken des zweiten bis zu den Blättern hinab und merkt sich die Knoten auf den Pfaden zusammen mit ihren Höhen.<br />Ohne Beschränkung der Allgemeinheit sei der erste Baum der höhere (wie in der Abbildung). Dem zweiten Baum wird sein erstes Element ''H'' in AVL-Manier entnommen. Es spielt nachher die Rolle eines „Bindeglieds“. Die Höhe des zweiten Baums sei jetzt ''h'' (möglicherweise 0). Man sucht nun in der rechten Flanke des ersten Baums nach einem Knoten ''G'' der Höhe ''h''+1 oder ''h'' (einen von beiden muss es geben; gibt es beide, wird der höhere bevorzugt). Man macht ''G'' zum Kind des Bindeglieds ''H'' und den zweiten Baum zum zweiten Kind von ''H'', was bei ''H'' einen AVL-konformen Balance-Faktor von 0 oder −1 ergibt. Dann wird ''H'' beim Elter ''F'' von ''G'' an ''G''s Stelle als Kind eingehängt. Der Höhenunterschied zwischen dem neuen ''H'' und ''E'' ist zwischen 0 und +2 (wenn ''E'' die Höhe ''h''–1 hat, dann hat ''G'' die Höhe ''h'', und das neue ''H'' die Höhe ''h''+1). Nach einer ersten Anpassung mit eventueller (Doppel-)Rotation müssen noch aufsteigend die Balance-Faktoren [[#EinfügenÜ|wie bei einer Einfügung überprüft]] und gegebenenfalls korrigiert werden.

Dabei kann die Höhe des Baums um 1 zunehmen.
|}

=== Spalten ===
[[Datei:BST-split.svg|mini|links|214px|Abb. 5: Spalten eines Binärbaums.<br />Dick rot gestrichelt: Trennlinie, spezifiziert durch (''Knoten'', ''Richtung'')<br /><math>I-\to-H</math>: aufzulösende Kind-Elter-Beziehung zwischen ''I''<sub>''n''</sub> und ''H<sub>n+1</sub>''<br /><math>H\!\cdot\!\cdot\!\cdot\!\cdot\!\cdot\!\cdot I</math>: Pfad ohne Überquerung der Trennlinie (von ''H<sub>n</sub>'' nach ''I''<sub>''n''</sub>=:''A'')<br /><math>I\!\cdot\;\cdot\;\cdot\;\cdot H</math>: Pfad trifft die Trennlinie zweimal (von ''I<sub>n</sub>'' nach ''H<sub>n+2</sub>'')]]

Etwas komplizierter als das Verketten ist das Aufspalten (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 definierte Trennlinie (dick rot gestrichelt in der Abbildung&nbsp;5) zerschneidet Kanten des Baums auf dem Pfad des Knotens zur Wurzel, so dass sich links wie rechts ein [[Wald (Graphentheorie)|Wald]] von „Schnipseln“ ergibt.

Jeder der so definierten zwei Wälder kann mit logarithmischem Aufwand zu einem AVL-Baum zusammengefügt werden derart, dass das Ergebnis einer nachfolgenden ''Verkettung'' dieser zwei AVL-Bäume in Bezug auf Einträge und deren Reihenfolge zum ursprünglichen Baum äquivalent ist.<ref name="Knuth-S474" />
{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;"
|style="text-align:left; font-size: 95%;"| '''Algorithmus'''&nbsp;&nbsp;
|-
|
Die Schnipsel sind Bäume, die bis auf eventuell einen Knoten („Stummel“) (''H'' in den Abbildungen&nbsp;5 und&nbsp;6) auf hoher Ebene mit Ausgangsgrad 1 (nicht unbedingt die Wurzel des Schnipsels) in AVL-Form sind. Dieser fungiert beim Verketten mit dem nächstniedrigeren Schnipsel auf der gleichen Seite als Bindeglied.

Im Folgenden ist die Indizierung der Knoten so gewählt, dass auf der einen Seite der Trennlinie sich nur geradzahlige, auf der anderen sich nur ungeradzahlige Indizes befinden. Die Indizes wachsen beim Aufstieg in Richtung Wurzel.

'''[[Vollständige Induktion]] auszuführen aufsteigend auf beiden Seiten der Trennlinie'''

Induktionsanfang (Abbildung&nbsp;5):

Hat der gegebene (die Trennlinie definierende) ''Knoten'' ein Kind in der gegebenen ''Richtung'', dann befindet sich dieses auf der anderen Seite der Trennlinie, ist in AVL-Form und werde ''I''<sub>1</sub> genannt. Der gegebene Knoten (nunmehr ein Stummel) werde ''H''<sub>2</sub> genannt. ''H''<sub>2</sub> ist mit einem Schnipsel ''I''<sub>0</sub>, welcher in diesem Fall leer ist, zu verketten.

Hat der gegebene ''Knoten'' kein Kind in der gegebenen ''Richtung'', dann sei ''H''<sub>2</sub> sein niedrigster Vorfahr in jener ''Richtung'' (also auf der anderen Seite der Trennlinie). ''I''<sub>1</sub> sei dessen Kind auf der Seite des gegebenen ''Knoten''s – es ist in AVL-Form. ''H''<sub>2</sub> ist ein Stummel, der mit einem Schnipsel ''I''<sub>0</sub>, welcher in diesem Fall leer ist, zu verketten ist.

Damit ist ''I''<sub>0</sub> (der leere Baum) der niedrigste Schnipsel auf der einen und ''I''<sub>1</sub> auf der anderen Seite. Beide sind in AVL-Form. Der Stummel ''H''<sub>2</sub> ist ursprünglicher Elter von ''I''<sub>1</sub> auf der Gegenseite der Trennlinie und niedrigster Vorfahr von ''I''<sub>0</sub> auf der gleichen Seite.

[[Datei:AVL-split.svg|mini|216px|Abb. 6: Ein Induktionsschritt beim Spalten eines AVL-Baums]]
Induktionsschritt (siehe Abbildungen&nbsp;5 und&nbsp;6):

Beim ''n''-ten Induktionsschritt heißt der niedrigste Schnipsel ''I<sub>n</sub>''. Obwohl die Seite bei jedem Induktionsschritt wechselt, sei der Einfachheit der Erläuterung halber angenommen, dass ''I<sub>n</sub>'' wie ''I'' in der Abbildung&nbsp;6 sich ''links'' von der Trennlinie befindet.

''I'' ist nach Induktionsvoraussetzung ein AVL-Baum. Sein niedrigster Vorfahr auf der linken Seite ist der Stummel ''H'' (=:''H<sub>n+2</sub>''). (Dessen rechtes Kind liegt auf der anderen Seite der Trennlinie, ist auch schon in AVL-Form und hat den Namen ''I''<sub>''n''+1</sub>.) Die ursprüngliche Höhe von ''H'' sei ''h'' (Abbildung&nbsp;6 oben). Zerschnittene Elter-Kanten (schwarz gestrichelt mit Pfeil) und die zurückbleibenden Stummel erkennt man am Wechsel der Kindesrichtung beim Aufstieg im Pfad. Dabei sind die (ursprünglichen) Höhen anhand der Balance-Faktoren aufs genaueste mitzuschreiben. Der Teilbaum des Einzelkindes ''D'' von ''H'' wird mit dem Schnipsel ''I'' unter Einsatz von ''H'' als Bindeglied [[#Verketten|verkettet]]. Bei der Verkettung spielen die Knoten ''D'', ''F'', ''H'' und ''I'' in der Abbildung&nbsp;6 dieselbe Rolle wie die Knoten gleichen Namens in der Abbildung&nbsp;4. Dabei kann ''D''s Höhe um 1 zunehmen.

Falls nun ''H'' die Wurzel war, ist der Algorithmus beendet mit ''D'', welches in AVL-Form ist, als der neuen Wurzel des linken Baums. Falls ''H'' linkes Kind war, wird ''D'' zum neuen niedrigsten Schnipsel auf der linken Seite, erhält den Namen ''I''<sub>''n''+2</sub>, und der Induktionsschritt ''n'' ist beendet.

War ''H'' rechtes Kind, dann wird ''D'' zum dementsprechend rechten Kind bei seinem vormaligen Großelter ''C'' gemacht, damit zum Geschwister seines vormaligen Onkels ''B''. Die Höhendifferenz zu letzterem ist maximal 3. Die AVL-Balance von ''C'' lässt sich durch Rotationen herstellen, wobei die Höhe von ''C'' um 1 abnehmen kann. (Die Vorgehensweise bei einem Höhenunterschied von 3 ähnelt der bei einem von 2: Ist das innere Kind des höheren Geschwisters niedriger als das äußere Kind, kann man die AVL-Balance mit einer [[#Einfachrotation|Einfachrotation]] herstellen. Ist es höher, kommt man mit einer [[#Doppelrotation|Doppelrotation]] durch. Sind beide Kinder gleich hoch, hängt es vom Balance-Faktor des inneren Kindes ab: ist der höhengleich, macht’s eine Doppelrotation; ist er außenlastig, schaffen’s zwei Rotationen; ist er innenlastig, geht’s mit drei Rotationen.)

Man sucht auf der linken Seite aufsteigend nach dem ersten Vorfahr ''A''(=:''I<sub>n+2</sub>'') im Pfad, der ''linkes'' Kind (oder Wurzel) ist. Sein Elter ''H''<sub>''n''+3</sub> ist niedrigster Vorfahr von ''I''<sub>''n''+1</sub> auf der rechten Seite. Links, auf den Ebenen hinauf bis ''A'' sind die Balance-Faktoren [[#LöschenÜ|wie bei einer Löschung zu überprüfen]] und gegebenenfalls anzupassen, wobei die Höhe um 1 abnehmen kann. Damit ist ''I''<sub>''n''</sub> so in den Schnipsel ''A'' integriert, dass ''A'' (oder ein anderer Knoten, der sich bei einer eventuellen Rotation als Wurzel in den Pfad geschoben hat) wieder ein AVL-Baum ist – und den niedrigsten Schnipsel ''I''<sub>''n''+2</sub> des Induktionsschrittes ''n''+2 auf dieser linken Seite darstellt.

Für den folgenden Induktionsschritt ''n''+3 aber werden die Seiten gewechselt, rechts mit links vertauscht und den Knoten ''I''<sub>''n''+1</sub>, ''H''<sub>''n''+3</sub> und ''I''<sub>''n''+3</sub> die Rollen von ''I<sub>n</sub>'', ''H<sub>n+2</sub>'' und ''I<sub>n+2</sub>'' zugewiesen.

Die innerhalb eines Induktionsschrittes besuchten Kanten (graue Pfeile in der Abbildung&nbsp;6) betreffen nur Ebenen zwischen den Wurzeln von zwei Schnipseln, die auf derselben Seite übereinander liegen (''I''<sub>''n''+2</sub> über ''I''<sub>''n''</sub> respektive ''I''<sub>''n''+3</sub> über ''I''<sub>''n''+1</sub>). Die Induktionsschritte auf der linken und rechten Seite greifen reißverschlussartig ineinander: der Aufstieg auf der rechten wird auf der linken Seite beim Verketten ab- und wieder aufgestiegen, woran sich ein Aufstieg anschließt, der auf der rechten Seite ab- und wieder aufgestiegen wird usw. Eine Ebene wird höchstens dreimal besucht, jedes Mal mit konstantem Aufwand. Damit ist der Gesamtaufwand fürs Spalten proportional zur Gesamthöhe.<ref>Costin S, der in seinem Projekt AVL-Bäume mit Concat- und Split-Operationen implementiert, fordert dazu die Aufzeichnung der vollen absoluten Höhe in jedem Knoten. Man kann aber – wie gezeigt – mit den Balance-Faktoren auskommen, ohne den Aufwand zu erhöhen.</ref>
|}

=== Anwendungsbeispiele ===
Die ''Massenlöschung'' von allen Schlüsseln in einem zusammenhängenden Bereich [[Quasiordnung#Intervalle|(Intervall)]] kann durch zweimaliges Spalten und einmaliges Verketten geschehen oder, wenn das kleinste oder größte Element mit dabei ist, durch einmaliges Spalten. In ähnlicher Weise lässt sich ein Intervall mit logarithmischem Aufwand als AVL-Baum aus einem AVL-Baum herauspräparieren.

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ärer Suchbaum|binären Suchbaums]] muss in einem Knoten der [[#Balance|Balance-Faktor]] mit seinen 3 Werten untergebracht werden: {{Anker|BF_1_Bit}}macht 2 [[Bit]]s.<ref group="Anm" name="1 Bit">1 Bit, wenn bei den Kindern aufgezeichnet. Wird dem Bit die Bedeutung „Höhensprung oberhalb“ gegeben, dann kann die Höhe im Pfad ohne Kenntnis der Kindesrichtung berechnet werden. Dennoch: es ist für die Modifikationsoperationen geschickter, die 2 Balance-Bits in einem Byte nebeneinander zu haben.</ref>

Insbesondere wenn der [[Prozessor]] korrekt [[Speicherausrichtung|ausgerichtete]] [[Zeiger (Informatik)|Zeiger]] bevorzugt oder erzwingt, können die Balance-Bits von einem Zeigerfeld im Knoten absorbiert werden, so dass sie kein extra Speicherwort benötigen.

Ansonsten gelten für die Implementierung von AVL-Bäumen dieselben Empfehlungen wie für die [[Binärer Suchbaum#Implementierung|binären Suchbäume]] im Allgemeinen. Auf die Besonderheiten des AVL-Cursors sei im Folgenden explizit eingegangen.

=== Cursor ===
Beim Suchen wird ein Paar (''Knoten'', ''Richtung'') erzeugt, welches geeignet ist, beim Einfügen den [[#Einfügen|Einfügepunkt]] zu spezifizieren. Beim Löschen wird der zu löschende Knoten durch die Komponente ''Knoten'' bezeichnet, und die Komponente ''Richtung'' kann zur Angabe verwendet werden, 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 [[Relationale Datenbank|Datenbanken]]) '''[[Cursor]]''' genannt wird.<ref>Ben Pfaff gibt einem Objekt mit sehr ähnlicher Funktionalität den Namen „traverser“ und offeriert für Suchen, Einfügen und Löschen eine Standard- und eine Traverser-Variante. (Ben Pfaff: ''An Introduction to Binary Search Trees and Balanced Trees.'' Free Software Foundation, Boston 2004 S. 15. und Ben Pfaff: ''Performance Analysis of BSTs in System Software'' Stanford University, 2004, S. 3.)</ref>

Die Größe des Cursors hängt entscheidend davon ab, ob die AVL-Knoten einen [[Zeiger (Informatik)|Zeiger]] zum Elter enthalten oder nicht.
# '''Elterzeiger''' vorhanden: Ein Paar (''Knoten'', ''Richtung'') stellt einen vollwertigen Cursor dar.<br />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.<br />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 [[Binärer Suchbaum#Kopf|Kopf]] immer schon gesichert ist.<!-- <br />Wird die Wurzel durch ein besonderes Bit gekennzeichnet, dann kommen die meisten Operationen ohne separate Angabe des Kopfes aus, da sie erkennen können, wann ein Elterknoten zum Kopf wird. -->
# Zeiger zum Elterknoten '''nicht''' vorhanden („Cursor mit Stapel“): Zusätzlich zum Paar (''Knoten'', ''Richtung'') muss der ''[[Weg (Graphentheorie)|Pfad]] vom Knoten zu Wurzel und Kopf'' im Cursor gehalten werden. Die Länge des Cursors entspricht damit der maximalen Höhe des Baums.<ref group="Anm">Als eine [[Datenstruktur]], die im homogenen [[Arbeitsspeicher]] (Hauptspeicher) untergebracht ist, ist der AVL-Baum durch dessen Größe beschränkt, also auch die Höhe des Baums und die Längen der Pfade von Blatt zu Wurzel. Gängig sind Hauptspeicher mit 32 Bit und 64 Bit breiten [[Byte|8-Bit-Byte]]-Adressen.{{Anker|Beschränkung der Pfadlänge}}<br />
{| class="wikitable left" style="text-align:right;width:36em;"
|-
| Breite<br />eines<br />Zeigers<br />in Bit || maximale Anzahl adressierbarer Bytes || minimale Knotenlänge<br />(2&nbsp;Zeiger+1&nbsp;Byte<br />+Nutzdaten&nbsp;{{FN|1}})|| maxi-<br />male Anzahl Knoten || Knotenzahl des nächstgrößeren Fibonacci-Baums … || … der Höhe
|-
| 32 || 4294967296 || 2·4+1+3 = 12 || 3,6·10<sup>8</sup> || 433494436 || 41
|-
| 64 || 18446744073709551616 || 2·8+1+7 = 24 || 7,7·10<sup>18</sup> || 1100087778366101930 || 86
|-
|colspan="6" style="text-align:left"| {{FNZ|1|inklusive Schlüssel. Bei mehr Nutzdaten und weniger Hauptspeicher<br />&nbsp;verringert sich die maximale Knotenzahl und Höhe entsprechend.}}
|-
|colspan="6" style="text-align:left"| <small>Tab. 4: Maximale Höhe in Abhängigkeit von der Adressierungsbreite</small>
|}
Fazit: Es ist bei AVL-Bäumen vertretbar, Cursor mit Stapeln bereitzustellen, die so groß sind, dass ein Überlauf nicht auftreten kann.</ref><br /> 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. <!-- <br />Das Programm kann an der Position im Stapel erkennen, ob die Position der Wurzel erreicht ist. -->

In seinem technischen Bericht ''AVL dags''<ref>{{cite journal|author=[[Eugene Myers|Eugene W. Myers]]|year=1982|title=AVL dags|journal=Technical Report, Department of Computer Science, U. of Arizona|volume=82-9}} Zitiert nach: {{cite journal
  | author = Neil Sarnak, [[Robert Tarjan|Robert E. Tarjan]]
  | title = Planar Point Location Using Persistent Search Trees
  | journal = Communications of the ACM
  | volume = 29
  | issue = 7
  | pages = 669–679
  | year = 1986
  | url = http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf
  | doi = 10.1145/6138.6151
  | accessdate = 2014-12-25
  | archiveurl = https://web.archive.org/web/20151010204956/http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf
  | archivedate = 2015-10-10
  }}</ref><ref group="Anm">dag für „Directed Acyclic Graph“, deutsch: [[Graph (Graphentheorie)#Gerichteter azyklischer Graph|Gerichteter azyklischer Graph]]</ref> beschreibt G. Myers ein Verfahren, wie mehrere Versionen ein und desselben AVL-Baums in eine Reihenfolge gebracht und in einer Weise miteinander verflochten werden können, die einen logarithmischen Zeit- und Speicherbedarf pro Version nicht überschreitet. Der AVL-Baum ist dann eine so genannte „[[persistente Datenstruktur]]“ (englisch ''persistent data structure'').

=== {{Anker|Modularisierung}}Trennung der navigierenden von den modifizierenden Operationen ===
Die Einführung des Cursors erlaubt die Modularisierung der Navigations- von den modifizierenden Operationen. Diese setzt den ''im Mittel'' unterlogarithmischen (sprich: konstanten) Aufwand der letzteren frei, denn ein Aufstieg bis zur Wurzel ist (wie in den Anmerkungen gezeigt)<ref group="Anm" name="ISRT" /><ref group="Anm" name="DLET" />  nur in Ausnahmefällen erforderlich. In Anwendungen mit starkem sequentiellem Anteil kann sich das positiv auf die Laufzeit auswirken.

=== Parallelisierung ===
Das wesentlichen Probleme bei paralleler Verarbeitung von AVL-Bäumen ist, dass der Zugriff auf den Baum nicht nur von der Wurzel zu den Blättern des Baumes erfolgt, sondern auch von den Blättern zur Wurzel. Dieses hat zur Folge, dass Deadlocks entstehen können, falls sich ein oder mehrere von „Oben nach Unten“ und von „Unten nach Oben“ arbeitende Prozesse in einem Knoten treffen. Ganze Teile des Baumes müssen daher also gesperrt werden, wenn Rebalancierungen von Knoten erfolgen können.
* Bei [[Iterative Programmierung|iterativer Programmierung]] kann die Überprüfungs- und Reparaturschleife auch in der umgekehrten Richtung, das heißt „antizipierend“ von Kopf und Wurzel zum Blatt, durchlaufen werden.<ref>„Top-Down-Strategie“ bei Kurt Mehlhorn: ''Datenstrukturen und effiziente Algorithmen''. Teubner, Stuttgart 1988, S. 197–198.</ref> Das ist insbesondere dann interessant, wenn auf den Baum hochgradig [[Parallele Programmierung|parallel]] (konkurrent) zugegriffen werden soll. Zum Beispiel würde in einem Szenario „Suchen und Einfügen“ die Suchoperation sich den tiefsten (letzten) höhenungleichen Knoten auf dem Pfad merken, ab dort den Baum [[Spinlock|sperren]]<ref group="Anm">Genau genommen bedarf es einer Kette mit den Gliedern ''Sperren(Kind)'' und ''Entsperren(Elter)'' bis zum ersten höhenungleichen Knoten, der zunächst gesperrt bleibt, bis er in ein neues Wechselspiel mit den Gliedern ''Sperren(höhenungleichen Knoten)'' und ''Entsperren(Vorfahr)'' eintritt. (Dabei bedeutet ''Sperren(Knoten)'' eigentlich ''Sperren(Teilbaum)''. Und: bei einer potentiellen 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 Parallelität wieder in einer Kind-Elter-Kette.<br /> Wenn alle nebenläufigen Mitspieler diese Gerichtetheit des [[Sperrverfahren|Sperrprotokolls]] einhalten, kann eine [[zirkuläre Abhängigkeit]] und damit eine [[Verklemmung]] (''deadlock'') nicht entstehen.</ref> und die Vergleichsergebnisse aufbewahren. Zum Fertigstellen der Einfügeoperation müsste dann der gesperrte Vorfahr (gegebenenfalls nach einer Rebalancierung) auf höhengleich 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 [[Prozessorkern]]en parallel zur laufenden Einfügung [[Kritischer Abschnitt|konsistent]] besichtigt und auch verändert werden könnten.
* Dieses Verhalten vermeiden die verzögerten AVL-Bäume die völlig ohne Stack oder Rekursion auskommen und den Baum nur in einer Richtung von der Wurzel zu den Blättern durchlaufen. Das Rebalancieren erfolgt dann verzögert beim nächsten Suchen. Daher muss nicht nur die Balance eines Knotens gespeichert werden, sondern ebenfalls die noch in Richtung der Wurzel des Baumes weiterzureichende Tiefenänderung. Ein '''verzögerter AVL-Baum<ref>{{Literatur |Autor=Bernhard Wagner |Titel=Effiziente höhenbalancierte Binärbäume |Auflage=1. |Datum=2022 |ISBN=979-8-35722559-7 |Kapitel=Kapitel 5.2.6 |Seiten=120 ff.}}</ref> ''', ist ein erweiterter AVL[k]-Baum bei dem

# Die Balance der Knoten die erweiterte '''AVL-Bedingung'''
#:<math>-k \; \leq \; \mathrm{BF}(t) \; \leq \; +k </math> für ein festes <math>k \in \N</math> an jedem Knoten <math>t</math> eingehalten wird.
# In den Knoten wird zusätzlich zur Balance die weiterzureichende Tiefenänderung des Knotens gespeichert wird.
# Bei den Operationen Einfügen oder Löschen eines Knotens wird nur der direkte Vorgänger, wegen einer notwendigen Zeigeränderung, berichtigt.
# Beim Suchen eines Knotens wird für jeden Knoten des Suchweges die Balance aus der Tiefe der beiden Teilbäume berechnet, oder die Tiefenänderung aus dem rechten oder linken Teilbaum weitergegeben. Falls die Balance nicht im erlaubten Bereich liegt, wird dieser Knoten dann rebalanciert. Die resultierende Tiefenänderung wird direkt in den Knoten gespeichert, aber nicht mehr in Richtung der Wurzel weitergegeben.

Da verzögerte AVL-Bäume nur in einer Richtung durchlaufen werden, kann die Bedingung für eine Deadlock „Circular Wait“ hier nicht eintreten. Die Balancierung der Knoten erfolgt dadurch verzögert beim Suchen. Mit einer atomaren Compare-and-Swap Operation (CAS, englisch für Vergleichen und Tauschen) ist eine Locking- und Synchronisationsoperationen auf den zu sperrenden Knoten leicht zu implementieren.

== {{Anker|VergleichRB}}Vergleich mit Rot-Schwarz-Baum ==
Die Menge der AVL-Bäume ist eine [[Teilmenge|echte Teilmenge]] in der Menge der Rot-Schwarz-Bäume. Denn jeder Binärbaum, der das AVL-Kriterium erfüllt, lässt sich in einer das [[Rot-Schwarz-Baum#Definition|Rot-Schwarz-Kriterium]] erfüllenden Weise einfärben.<ref>{{Internetquelle |autor=Paul E. Black |url=https://xlinux.nist.gov/dads//HTML/avltree.html |titel=AVL tree |werk=Dictionary of Algorithms and Data Structures |hrsg=[[National Institute of Standards and Technology]] |datum=2015-04-13 |sprache=en |abruf=2016-07-02}}</ref>

{| class="wikitable mw-collapsible mw-collapsed font-size: 105.3%;"
|-
|style="text-align:left; font-size: 95%;"| '''Beweis'''&nbsp;&nbsp;
|-
|
[[Datei:4 small AVL trees as RB trees.svg|mini|183px|4 kleine AVL-Bäume in Rot-Schwarz-Färbung.<br />Bei den geteilten Knoten gehen beide Farben.]]
Behauptung: Hat der AVL-Baum eine gerade Höhe <math>h</math>, dann lässt er sich mit [[Rot-Schwarz-Baum#Definition|Schwarztiefe]] <math>\tfrac{h}2</math> bei schwarzer Wurzel einfärben; ist <math>h</math> ungerade, dann mit Schwarztiefe <math>\tfrac{h-1}2</math> bei einer roten oder mit Schwarztiefe <math>\tfrac{h+1}2</math> bei einer schwarzen Wurzel. (Die [[Rot-Schwarz-Baum#Definition|NIL-Knoten]] sind dabei nicht mitgezählt.)

Beweis: Die Behauptung ist richtig für <math>h \leq 1</math> (siehe Abbildung).<br />Bei größerem geradem <math>h</math> gibt es einen Kindbaum mit der ungeraden Höhe <math>h-1</math>, der sich nach [[Induktionsvoraussetzung]] mit roter Wurzel und Schwarztiefe <math>\tfrac{h-2}2</math> einfärben lässt. Hat der andere Kindbaum dieselbe Höhe, so gilt für ihn dasselbe. Ist er niedriger, dann ist seine Höhe <math>h-2</math> und gerade; er lässt sich also mit der gleichen Schwarztiefe (bei schwarzer Wurzel) einfärben. Nachdem die neue Wurzel schwarz eingefärbt ist, ist die Schwarztiefe im zusammengesetzten Baum <math>\tfrac{h}2.</math><br />Bei größerem ungeradem <math>h</math> hat einer der Kindbäume oder beide die gerade Höhe <math>h-1,</math> die sich mit schwarzer Wurzel bei Schwarztiefe <math>\tfrac{h-1}2</math> einfärben lässt. Ist der andere Kindbaum niedriger, dann ist seine Höhe <math>h-2</math> und ungerade, lässt sich also mit glücklicherweise derselben Schwarztiefe <math>\tfrac{h-1}2</math> bei schwarzer Wurzel einfärben. Alle Kindbäume haben schwarze Wurzeln, also kann die neue Wurzel rot eingefärbt werden und es ergibt sich eine Schwarztiefe von <math>\tfrac{h-1}2 .</math> Wird die neue Wurzel jedoch schwarz eingefärbt, dann ist die neue Schwarztiefe <math>\tfrac{h+1}2 .</math> &nbsp;&nbsp;■
|}
[[Datei:Red-black, but not AVL tree.svg|mini|110px|Kein AVL-Baum]]
Es gibt aber Rot-Schwarz-Bäume, die das AVL-Kriterium nicht erfüllen. Die nebenstehende Abb. zeigt zum Beispiel einen Rot-Schwarz-Baum mit 6 (inneren) Knoten und der [[Binärer Suchbaum#Suchtiefen und Pfadlängensummen|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 <math>\frac c2 \approx 0{,}720</math> mit [[#ObereSchranke|obigem]] <math>c := \frac 1{\log_2 \Phi}</math> und dem Faktor 2 aus dem [[Rot-Schwarz-Baum#Höhenbeweis|Höhenbeweis des Rot-Schwarz-Baums]]. Allgemein werden AVL-Bäume als besser balanciert und ihr Suchzeitverhalten als günstiger angesehen.

Der Speicherplatzbedarf ist praktisch identisch: 1 Bit für die Farbe gegenüber 2 oder auch 1 Bit(s)<ref group="Anm" name="1 Bit" /> für den Balance-Faktor.

Der Platzbedarf und das Laufzeitverhalten für die angeführten Operationen ist im Mittel und im Worst Case identisch. Das gilt auch für die [[Amortisierte Laufzeitanalyse|amortisiert]] konstanten Modifikationskosten beim Einfügen.<ref name="Dinesh" /> Zwar bietet der Rot-Schwarz-Baum amortisiert konstante Modifikationskosten auch beim Löschen<ref>{{BibISBN|978-3-540-77977-3}} S. 165.</ref> und der AVL-Baum dort nur<ref group="Anm">Bei einem vollständigen Binärbaum bedingt eine {{nowrap|<math>m</math>-fache}} [[Schleife (Programmierung)|Schleife]] bestehend aus Einfügung eines zusätzlichen Knotens und Löschung desselben jedes Mal die Anpassung von <math>h = \log_2 (n+1)</math> Balance-Faktoren bis hinauf zur Wurzel und damit einen Aufwand in <math>\mathcal{O}(m \log n)</math>, also amortisiert <math>\mathcal{O}(\log n)</math>.</ref> im Mittel konstante.
Anwendungen von binären Suchbäumen, die nur Sequenzen von Einfügungen und Löschungen – ganz ohne intervenierende Suchoperationen – enthalten, gehen am Zweck des Suchbaums vorbei. 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.<ref name="Pfaff_b">Ben Pfaff: ''Performance Analysis of BSTs in System Software.'' Stanford University 2004.</ref> 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 {{Bruch|''AVL''|''RB''}} zwischen 0,677 und 1,077 bei einem [[Median]] von ≈0,947 und einem [[Geometrisches Mittel|geometrischen Mittelwert]] von ≈0,910.

== Anwendungen ==
Als grundlegende Hilfsmittel der Informatik haben die binären Suchbäume ein großes Einsatzgebiet, in welchem sie aber auch hochgradig untereinander austauschbar sind. Konkrete Beispiele und Auswahlkriterien finden sich in [[Binärer Suchbaum#Anwendungen]].

== Weitere Baumstrukturen ==
* [[Binärbaum]]
* [[Binärer Suchbaum]]
* [[Balancierter Baum]]
* [[Rot-Schwarz-Baum]]
* [[Splay-Baum]]
* [[Gewichteter binärer Suchbaum]]
* [[Fibonacci-Baum]]

== Literatur ==
* {{Anker|Cormen}}{{BibISBN|0-262-03293-7}}
* Ralf Hartmut Güting, Stefan Dieker: ''Datenstrukturen und Algorithmen.'' Stuttgart 2004, ISBN 978-3-519-22121-0.
* {{Literatur |Autor=[[Donald Knuth|Donald E. Knuth]] |Titel=[[The Art of Computer Programming]] |Band=Band 3: ''Sorting and Searching'' |Auflage=2. |Verlag=Addison-Wesley |Ort= |Datum=1998 |ISBN=0-201-89685-0 |Kapitel=6.2.3 Balanced Trees |Seiten=458–478}}
* Udi Manber: ''Introduction to Algorithms – A Creative Approach.'' Addison-Wesley Publishing Company 1989, Kapitel 4.3.4, S.&nbsp;75ff.
* {{Anker|Mehlhorn 1988}}[[Kurt Mehlhorn]]: ''Datenstrukturen und effiziente Algorithmen.'' Teubner Stuttgart 1988, ISBN 3-519-12255-3.
* Bernhard Wagner: Effiziente höhenbalancierte Binärbäume: Die neuen Algorithmen mit Beweis ihrer Korrektheit, 1 Auflage 2022, ISBN 979-8-35722559-7.

== Weblinks ==
{{Commonscat|AVL-trees|AVL-Bäume}}
* {{Internetquelle |autor=Paul E. Black |url=https://xlinux.nist.gov/dads//HTML/avltree.html |titel=AVL tree |werk=Dictionary of Algorithms and Data Structures |hrsg=[[National Institute of Standards and Technology]] (NIST) |datum=2014-07-07 |sprache=en |abruf=2016-07-27}}
* [http://sourceforge.net/projects/j-algo Algorithmenvisualisierung unter anderem für AVL-Bäume]
* [http://www-lehre.informatik.uni-osnabrueck.de/~ainf/2000/skript/node60.html Kurz gehaltene Beschreibung der Rotationen]
* [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html Simulation des AVL-Baumes inkl. Berechnung Balance-Faktor]
* {{Anker|Costin S}}[http://code.google.com/p/self-balancing-avl-tree/downloads/detail?name=AvlTree.v1.0.zip AvlTree.cs vom 10.&nbsp;August 2012]
* {{Anker|Pfaff_a}}Ben Pfaff: ''An Introduction to Binary Search Trees and Balanced Trees.'' [[Free Software Foundation]], Boston 2004, [ftp://ftp.gnu.org/gnu/avl/avl-2.0.2.pdf.gz gnu.org] (PDF gzip; 1675&nbsp;kB).
* {{Anker|Pfaff_b}}Ben Pfaff: ''Performance Analysis of BSTs in System Software.'' [[Stanford University]], 2004, [https://web.stanford.edu/~blp/papers/libavl.pdf stanford.edu] (PDF; 316&nbsp;kB).

== Einzelnachweise ==
<references responsive />

== Anmerkungen ==
<references group="Anm" />

{{Lesenswert|5. Februar 2014|127211389}}

[[Kategorie:Suchbaum]]