# AVL-Baum

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

Er bildet eine Datenstruktur in der Informatik in Form eines binären Suchbaums mit der zusätzlichen Eigenschaft, dass sich an jedem Knoten die Höhe der beiden Teilbäume um höchstens eins unterscheidet. Diese Eigenschaft lässt seine Höhe nur logarithmisch mit der Zahl der Schlüssel wachsen und macht ihn zu einem balancierten binären Suchbaum. Die maximale (und mittlere) Anzahl der Schritte (Vergleiche), die nötig sind, um An- oder Abwesenheit eines Schlüssels festzustellen, hängt direkt mit der Höhe zusammen. Ferner ist der maximale Aufwand für Operationen zum Einfügen und Entfernen eines Schlüssels proportional zur Höhe des Baums und damit ebenfalls logarithmisch in der Zahl der Schlüssel; der mittlere Aufwand ist sogar konstant, wenn das Positionieren auf das Zielelement nicht mitgerechnet wird.
Viele Operationen, insbesondere die Navigationsoperationen, sind direkt von den binären Suchbäumen zu übernehmen. Bei den modifizierenden Operationen muss jedoch das AVL-Kriterium beobachtet werden, womit auf jeden Fall kleine Anpassungen durchzuführen sind, die bis zu Höhenkorrekturen durch sogenannte Rotationen reichen können.


## Motivation
Suchbäume – und damit auch die AVL-Bäume – sind Lösungen des sogenannten „Wörterbuchproblems“. Eine prinzipielle Erläuterung findet sich im Abschnitt Motivation im Artikel Binärer Suchbaum.
Den Suchbäumen gemeinsam ist, dass sie Dynamik unterstützen, das heißt, dass Einfügen und/oder Löschen von Elementen wichtig ist. Da bei diesen Operationen die Gefahr besteht, dass die Balance des Baums verloren geht, wurden verschiedene Balance-Kriterien für Binärbäume entwickelt. Bei den meisten sind die Aufwände für das Suchen, Einfügen und Löschen zumindest im Mittel logarithmisch, wenn auch mit unterschiedlichen konstanten Faktoren.
Beim AVL-Baum wird die Balance über die Höhe definiert, er ist ein höhen-balancierter binärer Suchbaum.


## Das AVL-Kriterium
Als den Balance-Faktor 
  
    
      
        
          B
          F
        
        (
        t
        )
      
    
    {\displaystyle \mathrm {BF} (t)}
  
 eines Knotens resp. Teilbaums 
  
    
      
        t
      
    
    {\displaystyle t}
  
 in einem Binärbaum bezeichnet man die Höhendifferenz

  
    
      
        
          B
          F
        
        (
        t
        )
        :=
        
          H
          e
          i
          g
          h
          t
        
        (
        
          t
          
            r
          
        
        )
        −
        
          H
          e
          i
          g
          h
          t
        
        (
        
          t
          
            l
          
        
        )
      
    
    {\displaystyle \mathrm {BF} (t):=\mathrm {Height} (t_{r})-\mathrm {Height} (t_{l})}
  
,
wobei 
  
    
      
        
          H
          e
          i
          g
          h
          t
        
        (
        t
        )
      
    
    {\displaystyle \mathrm {Height} (t)}
  
 die Höhe des Baums 
  
    
      
        t
      
    
    {\displaystyle t}
  
, und 
  
    
      
        
          t
          
            l
          
        
      
    
    {\displaystyle t_{l}}
  
 der linke, 
  
    
      
        
          t
          
            r
          
        
      
    
    {\displaystyle t_{r}}
  
 der rechte Kindbaum von 
  
    
      
        t
      
    
    {\displaystyle t}
  
 ist. Ein Knoten 
  
    
      
        t
      
    
    {\displaystyle t}
  
 mit 
  
    
      
        
          B
          F
        
        (
        t
        )
        =
        0
      
    
    {\displaystyle \mathrm {BF} (t)=0}
  
 wird als höhengleich oder ausgewogen, einer mit 
  
    
      
        
          B
          F
        
        (
        t
        )
        <
        0
      
    
    {\displaystyle \mathrm {BF} (t)<0}
  
 als links- und einer mit 
  
    
      
        
          B
          F
        
        (
        t
        )
        >
        0
      
    
    {\displaystyle \mathrm {BF} (t)>0}
  
 als rechtslastig bezeichnet.
Ein binärer (Such-)Baum ist genau dann ein AVL-Baum, wenn die AVL-Bedingung

  
    
      
        −
        1
        
        ≤
        
        
          B
          F
        
        (
        t
        )
        
        ≤
        
        +
        1
      
    
    {\displaystyle -1\;\leq \;\mathrm {BF} (t)\;\leq \;+1}
  

an jedem Knoten 
  
    
      
        t
      
    
    {\displaystyle t}
  
 eingehalten wird.


### Eigenschaften
Diese Definition beschränkt die Höhe 
  
    
      
        
          H
          e
          i
          g
          h
          t
        
        (
        t
        )
      
    
    {\displaystyle \mathrm {Height} (t)}
  
 eines AVL-Baums 
  
    
      
        t
      
    
    {\displaystyle t}
  
 mit 
  
    
      
        n
      
    
    {\displaystyle n}
  
 Knoten (Schlüsseln) durch die Ungleichung

  
    
      
        
          log
          
            2
          
        
        ⁡
        (
        n
        +
        1
        )
        
        ≤
        
        
          H
          e
          i
          g
          h
          t
        
        (
        t
        )
        
        <
        
        c
        
          log
          
            2
          
        
        ⁡
        (
        n
        +
        2
        )
        +
        b
      
    
    {\displaystyle \log _{2}(n+1)\;\leq \;\mathrm {Height} (t)\;<\;c\log _{2}(n+2)+b}
  

mit 
  
    
      
        c
        :=
        
          
            1
            
              
                log
                
                  2
                
              
              ⁡
              Φ
            
          
        
        ≈
        1,440
        420
      
    
    {\displaystyle c:={\frac {1}{\log _{2}\Phi }}\approx 1{,}440420}
  
, 
  
    
      
        b
        :=
        
          
            c
            2
          
        
        
          log
          
            2
          
        
        ⁡
        5
        −
        2
        ≈
        
        −
        0,327
        724
      
    
    {\displaystyle b:={\frac {c}{2}}\log _{2}5-2\approx \;-0{,}327724}
  
 und 
  
    
      
        Φ
        :=
        
          
            
              1
              +
              
                
                  5
                
              
            
            2
          
        
        ≈
        1,618
        034
      
    
    {\displaystyle \Phi :={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618034}
  
 (Zahl des goldenen Schnitts).
Die untere Schranke kommt vom vollständigen Binärbaum (bei dem bis auf die unterste Ebene alle Ebenen komplett sind); die obere vom Fibonacci-Baum, der bei gegebener Höhe einen AVL-Baum mit kleinster Knotenanzahl darstellt – also bei gleicher Knotenzahl die größte Höhe hat – somit (in Bezug auf die Höhe) am schlechtesten balanciert ist. Dabei ist die Höhe gemittelt über alle zufälligen Einfügungen in einen AVL-Baum vorgegebener Größe näher bei der unteren als bei der oberen Grenze des Intervalls.


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


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


### Navigieren
Die Navigationsoperationen, das sind die verschiedenen Suchoperationen, das Traversieren und Iterieren, Aufsuchen erstes oder letztes Element und ähnliche, lassen den Baum unverändert und funktionieren im Prinzip auf jedem binären Suchbaum. Die dortigen Angaben zur Komplexität gelten genauso für AVL-Bäume, mit der Präzisierung, dass die Höhe des AVL-Baums sich logarithmisch zur Anzahl der Knoten verhält.
Das Suchen (englisch: find, search, lookup oder locate) eines Elements anhand seines Schlüssels ist die wichtigste unter den Navigationsoperationen. Die Höhen-Balancierung des AVL-Baums versucht, auf diese Operation hin zu optimieren. Sie ermöglicht einen sogenannten direkten Zugriff (im Gegensatz zum sequentiellen Zugriff der Traversierung). Sie wird in der Regel als vorausgehende Operation sowohl beim Einfügen als auch beim Löschen eingesetzt.
Das Suchen setzt eine totale Quasiordnung auf der Menge der Schlüssel voraus, die am flexibelsten durch eine Vergleichsfunktion bereitgestellt wird.
Das mittlere Laufzeitverhalten des Suchens in einem binären Suchbaum wird durch die Pfadlängensumme wiedergegeben, welche geteilt durch die Knotenzahl die mittlere Suchtiefe definiert. Diese verhält sich beim AVL-Baum proportional zur optimalen Suchtiefe – mit einem Proportionalitätsfaktor nur wenig größer als 1.


### Einfügen (Eintragen)
Es sei angenommen, dass die Navigation zum Einfügepunkt bereits erfolgt ist. Ein Einfügepunkt ist ein externes Blatt und liegt ganz links oder ganz rechts oder zwischen 2 internen (und Schlüssel tragenden) Knoten, kann also auf jeden Fall durch einen (internen) Knoten zusammen mit einer Richtung (links oder rechts) spezifiziert werden. Die Knoten ganz links oder ganz rechts sind immer (Halb-)Blätter, wie auch von 2 Nachbarknoten wenigstens einer ein (Halb-)Blatt ist. Ein solcher Knoten sei – zusammen mit der entsprechenden Richtung – als der unmittelbare Einfügepunkt bezeichnet. So wird er auch von einer nicht erfolgreichen Suchoperation geliefert.
Zur Einfügung (englisch: insert oder add) wird der Knoten mit dem neuen Schlüssel als Blatt am Einfügepunkt eingehängt – mit anderen Worten: das externe Blatt wird zum internen Blatt. Die Höhe des aus diesem Blatt bestehenden Teilbaums erhöht sich von 0 auf 1. Für die Reparatur des Baumes oberhalb des Einfügepunktes gibt es 2 verschiedene Vorgehensweisen:

Man geht den Pfad der Elterknoten zurück bis u. U. zur Wurzel („retracing“ in der englischen Literatur). Hier muss ein Stapelspeicher (bei rekursiver Programmierung meist der Programm-Stapelspeicher) vorher mit den Knoten im Pfad gefüllt worden sein.
Man hat sich beim Suchen im Abstieg einen (dann den letzten, tiefsten) nicht-ausgewogenen (also links- oder rechtslastigen) Knoten gemerkt („Top-Down-Strategie“). 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.
Wir zeigen hier die „einfachere“ Variante, die der Abfolge bei rekursiver Programmierung entspricht.
Beim Aufstieg zum Elterknoten, und später bei jedem weiteren Aufstieg, gibt es entsprechend der 3 Werte des ursprünglichen Balance-Faktors dieses Knotens 3 Möglichkeiten für den neuen (temporären) Balance-Faktor:

Wird der Balance-Faktor zu 0, dann kommt man von einem Kindbaum, der vorher niedriger war, und die Höhe des Knotens ändert sich nicht – mit der Folge, dass oberhalb alle Balance-Faktoren bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum erfüllt ist.
Wird der Balance-Faktor zu ±1 (er muss vorher 0 gewesen sein), erhöht sich die Höhe des Teilbaums um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen.
Wird auf einer Ebene der Balance-Faktor zu ±2, muss der Teilbaum rebalanciert werden (siehe Rebalancierung weiter unten). Danach hat bei einer Einfügeoperation der Teilbaum die gleiche Höhe wie vorher – mit der Folge, dass oberhalb alle Balance-Faktoren bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum auch schon erfüllt ist.
Das Einfügen des 
  
    
      
        (
        n
        +
        1
        )
      
    
    {\displaystyle (n+1)}
  
-ten Knotens in einen AVL-Baum mit 
  
    
      
        n
      
    
    {\displaystyle n}
  
 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.
Es kann sogar gezeigt werden, dass der Modifikationsaufwand in einem reinen Einfügeszenario amortisiert konstant ist.


### 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). 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 In-order-Nachbarn, also entweder den rechtesten Knoten des linken Kindbaums oder den linkesten des rechten Kindbaums, als Ersatzelter, 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.
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.
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 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.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.


## Rebalancierung
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 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), das ist das Kind mit einer Kindesrichtung, die der von Z entgegengesetzt ist, (t23 in der Abbildung 2 beziehungsweise Y in der Abbildung 3) nicht höher ist als sein Geschwister, das äußere Kind (t4 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 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 2 zeigt eine Rechts-Rechts-Situation. In der oberen Hälfte haben die beiden Teilbäume Z und t1 des Knotens X einen Höhenunterschied von +2. Das innere Kind t23 des um 2 höheren Knotens Z ist nicht höher als sein Geschwister t4.
Dies kann nach einem Einfügen in den Teilbaum t4 oder nach einem Löschen aus dem Teilbaum t1 auftreten.
Der in der Abbildung 2 blass gehaltene Fall, dass t23 gleich hoch ist wie t4, 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.


### Doppelrotation
Sie wird im Original Большое вращение (große Drehung) genannt.
Die in der Abbildung 3 gezeigte Situation unterscheidet sich von der in Abbildung 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 t4: eine Rechts-Links-Situation, da X rechts- und Z linkslastig ist.
Das kann nach der Einfügung des Knotens Y oder einer Einfügung in einen der Teilbäume t2 oder t3 oder nach einer Löschung aus dem Teilbaum t1 passieren.
Der Fall, bei dem die Teilbäume t2 und t3 gleich hoch sind und der Teilbaum Y höher als t4, 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.
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.


### Beispiel
Der AVL-Baum in der Abbildung 1 wird

nach der Löschung des Knotens »G« durch die zwei Einfachrotationen Rechts(»F«), später Links(»J«)
nach der Einfügung eines Knotens »T« durch die Doppelrotation LinksRechts(»V«, »S«)
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
Zwei AVL-Bäume können mit logarithmischem Aufwand verkettet (konkateniert) werden (englisch: concat oder auch nur cat). Für die Sortierfolge müssen natürlich alle Schlüssel des ersten Baums allen Schlüsseln des zweiten vorangehen.


### Spalten
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 5) zerschneidet Kanten des Baums auf dem Pfad des Knotens zur Wurzel, so dass sich links wie rechts ein 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.


### Anwendungsbeispiele
Die Massenlöschung von allen Schlüsseln in einem zusammenhängenden Bereich (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ären Suchbaums muss in einem Knoten der Balance-Faktor mit seinen 3 Werten untergebracht werden: macht 2 Bits.
Insbesondere wenn der Prozessor korrekt ausgerichtete 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ä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ü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 Datenbanken) Cursor genannt wird.
Die Größe des Cursors hängt entscheidend davon ab, ob die AVL-Knoten einen Zeiger zum Elter enthalten oder nicht.

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


### 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)  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 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. Das ist insbesondere dann interessant, wenn auf den Baum hochgradig parallel (konkurrent) zugegriffen werden soll. Zum Beispiel würde in einem Szenario „Suchen und Einfügen“ die Suchoperation sich den tiefsten (letzten) höhenungleichen Knoten auf dem Pfad merken, ab dort den Baum sperren und die Vergleichsergebnisse aufbewahren. Zum Fertigstellen der Einfügeoperation müsste dann der gesperrte Vorfahr (gegebenenfalls nach einer Rebalancierung) auf 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 Prozessorkernen parallel zur laufenden Einfügung 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 , ist ein erweiterter AVL[k]-Baum bei dem
Die Balance der Knoten die erweiterte AVL-Bedingung

  
    
      
        −
        k
        
        ≤
        
        
          B
          F
        
        (
        t
        )
        
        ≤
        
        +
        k
      
    
    {\displaystyle -k\;\leq \;\mathrm {BF} (t)\;\leq \;+k}
  
 für ein festes 
  
    
      
        k
        ∈
        
          N
        
      
    
    {\displaystyle k\in \mathbb {N} }
  
 an jedem Knoten 
  
    
      
        t
      
    
    {\displaystyle t}
  
 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.


## Vergleich mit Rot-Schwarz-Baum
Die Menge der AVL-Bäume ist eine 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-Kriterium erfüllenden Weise einfärben.

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 externen Pfadlängensumme 21, während 20 die größte externe Pfadlängensumme bei AVL-Bäumen (und zugleich die kleinstmögliche für alle Binärbäume) dieser Größe ist. Konsequenterweise ist auch die Worst-Case-Höhe des AVL-Baums kleiner als die des Rot-Schwarz-Baums, und zwar um den Faktor 
  
    
      
        
          
            c
            2
          
        
        ≈
        0,720
      
    
    {\displaystyle {\frac {c}{2}}\approx 0{,}720}
  
 mit obigem 
  
    
      
        c
        :=
        
          
            1
            
              
                log
                
                  2
                
              
              ⁡
              Φ
            
          
        
      
    
    {\displaystyle c:={\frac {1}{\log _{2}\Phi }}}
  
 und dem Faktor 2 aus dem 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) 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 amortisiert konstanten Modifikationskosten beim Einfügen. Zwar bietet der Rot-Schwarz-Baum amortisiert konstante Modifikationskosten auch beim Löschen und der AVL-Baum dort nur 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. Seine Ergebnisse zeigen in 79 Messungen unter anderem die sehr große Ähnlichkeit von AVL-Bäumen (AVL) und Rot-Schwarz-Bäumen (RB) mit Laufzeitverhältnissen AVL⁄RB zwischen 0,677 und 1,077 bei einem Median von ≈0,947 und einem geometrischen Mittelwert von ≈0,910.


## Anwendungen
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
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7 (englisch). 
Ralf Hartmut Güting, Stefan Dieker: Datenstrukturen und Algorithmen. Stuttgart 2004, ISBN 978-3-519-22121-0.
Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Band 3: Sorting and Searching. Addison-Wesley, 1998, ISBN 0-201-89685-0, 6.2.3 Balanced Trees, S. 458–478. 
Udi Manber: Introduction to Algorithms – A Creative Approach. Addison-Wesley Publishing Company 1989, Kapitel 4.3.4, S. 75ff.
Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner Stuttgart 1988, ISBN 3-519-12255-3.
Bernhard Wagner: Effiziente höhenbalancierte Binärbäume: Die neuen Algorithmen mit Beweis ihrer Korrektheit, 1 Auflage 2022, ISBN 979-8-35722559-7.


## Weblinks
Paul E. Black: AVL tree. In: Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology (NIST), 7. Juli 2014, abgerufen am 27. Juli 2016 (englisch). 
Algorithmenvisualisierung unter anderem für AVL-Bäume
Kurz gehaltene Beschreibung der Rotationen
Simulation des AVL-Baumes inkl. Berechnung Balance-Faktor
AvlTree.cs vom 10. August 2012
Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Boston 2004, gnu.org (PDF gzip; 1675 kB).
Ben Pfaff: Performance Analysis of BSTs in System Software. Stanford University, 2004, stanford.edu (PDF; 316 kB).


## Einzelnachweise
## Anmerkungen