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.

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

Er bildet eine Datenstruktur in der Informatik in Form eines binären Suchbaums mit der zusätzlichen Eigenschaft, dass sich an jedem Knoten die Höhe der beiden Teilbäume um höchstens eins unterscheidet. 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.

1. ↑ G. M. Adelson-Velsky, E. M. Landis: Один алгоритм организации информации. In: Doklady Akademii Nauk SSSR. 146. Jahrgang, 1962, S. 263–266 (russisch). 
   Englische Übersetzung von Myron J. Ricci: An algorithm for the organization of information. (Memento vom 1. Februar 2014 im Internet Archive) (PDF) In: Soviet Mathematics 3, 1962, S. 1259–1263.
2. ↑ Thomas H. Cormen u. a.: Introduction to Algorithms. 2. Auflage, MIT Press, Cambridge (Massachusetts) 2001, S. 296.