AVL-Bäume

Sei $T$ ein binärer Suchbaum und $p$ ein Knoten in $T$. Weiter sei $T_l$ der linke und $T_r$ der rechte Teilbaum des Knotens $p$. Die Balance in Knoten $p$ ist der Wert:

$$\textrm{bal}(p) = \textrm{H\uml ohe}(T_l) - \textrm{H\uml ohe}(T_r)$$ (1)

Ein AVL-Baum ist ein binärer Suchbaum $T$ mit Knoten $p$, genau dann, wenn gilt:

$$\forall p: \textrm{bal}(p) \in \{-1,0,1\}$$ (2)

AVL-Bäume werden wie Suchbäume implementiert, wobei für jeden Knoten $p$ die Balance in Knoten $p$ als zusätzliche Komponente gespeichert wird. Abbildung 6 veranschaulicht dies.

Abbildung 6: Höhenbalance

Für AVL-Bäume $T$ mit $n$ Knoten gilt (ohne Beweis):

$$\textrm{H\uml ohe}(T) = O(\log n)$$ (3)

Genauer: $\textrm{H\uml ohe}(T) \leq 1.44 \log n$