AVL-Bäume

Definition:
Ein AVL-Baum (AVL Tree) [Adelson-Velskii, Landis] ist ein interner binärer höhenbalancierter Suchbaum, bei dem die Höhe der von jedem Knoten ausgehenden Teilbäume maximal um 1 differiert.

Definition:
Die Balance eines AVL-Baumes bezeichnet die Differenz zwischen der Höhe des linken und rechten Unterbaumes.

Operationen:

1. $Find(k,T)$: Traversierung des Baumes bis zum gesuchten Element

2. $Insert(x,T)$: neues Blatt einfügen, ggf. Rebalancierung
Eine Rebalancierung wird erforderlich, wenn die Balance $\geq 2$ oder $\leq -2$ wird. Alle möglichen Fälle lassen sich durch Rotation oder Doppelrotation darstellen. Hier wird gemäß Sortierungsbedingung die Baumstruktur angepasst (um die Wurzel rotiert).

3. $Delete(x,T)$: lösche Knoten, wobei ein innerer Knoten durch ein entsprechendes Blatt (Blatt auf rechtem Pfad über linkes Kind) ersetzt wird. Ggf. ist eine Rebalancierung erforderlich.

Analyse:
- Alle Operationen benötigen Zeit $O(\log n)$
- Ein Baum mit Höhe $h$ enthält $\geq Fib(h+2)$ Blätter
- Die Höhendifferenz der Blätter ist etwa $\leq h/2$