Höhenbalancierte binäre Suchbäume (AVL-Bäume)

Definition: Ein AVL-Baum ist ein spezieller binärer Suchbaum, der neben den Sortierungsbedingungen auch die folgende Höhenbalancierungen erfüllt. Für den Knoten v gilt:
| Höhe(lUB^v) - Höhe(rUB^v) | $\leq 1$

Lemma: Ein AVL-Baum der Höhe h hat mindestens n_h= Fib(h+2) Blätter.

Beweis: Induktion nach h:

I)

$h=1; \Rightarrow n_h = 2 =$ Fib(3);
$h=2 \Rightarrow n_h = 3 =$ Fib(4);

II)

$h\geq 3; \Rightarrow n_h \geq n_{h-1} + n_{h-2}$
Bei einem bzgl. der Blätterzahl minimalen AVL-Baum der Höhe h darf nur einer der Unterbäume der Höhe h-1 haben. Der andere muß kürzer sein, aber wegen der Balancierungsbedingung mindestens Höhe h-2 haben. Beide sind natürlich minimale AVL-Bäume. Also gilt n_h = n_h-1+n_h-2. Dies ist genau die Bestimmungsgleichung für Fib(h+1).

$\Diamond$
Folgerung:

• AVL-Bäume der Höhe h haben mindestens Fib(h+2) Blätter, also Fib(h+2)-1 interne Knoten.
• Da anderseits gilt: Fib(n) $\approx$ $\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n$, hat ein AVL-Baum mit n-Blättern (oder interne Knoten) die Höhe $\mathcal{O}(\log{n})$. Dies ist ein bedeutender Fortschritt gegenüber der bisweilen bei natürlichen Suchbäumen entstehenden Zeitkomplexität von $\Omega(n)$ für die Suchoperation IsElement .

Operationen auf AVL-Bäumen:

1.

IsElement : Diese Operation wird wie bei den natürlichen Suchbäumen implementiert. Wie oben ausgeführt, haben aber AVL-Bäume mit n Datenelementen eine Höhe von $\mathcal{O}(\log{n})$, woraus logarithmische Zeit für das Suchen folgt.

2.

Insert : Zunächst wird eine IsElement -Operation ausgeführt, die für den Fall, daß das einzufügende Element nicht bereits enthalten ist, zu einem Blatt führt. Dies ist die Stelle, an der das neue Element einzufügen ist. Dabei ergeben sich 2 Fälle:

1. Fall:

(Balance $-1 \rightarrow 0$: symmetrisch)

2. Fall:

Hier ist eventuell eine Rebalancierung auf dem Pfad zur Wurzel notwendig, denn die Höhe eines Unterbaums ändert sich derart, daß die Balance nicht zu wird, sondern zu +1 oder -1. Zur Rebalancierung ($T_1 \leq T_2 \leq T_3 \leq T_4$):

Fall 2-a)

Fall 2-b)

3.

Delete : Auch diese Operation wird wie bei natürlichen Suchbäumen implementiert. Doch am Ende hat ggf. noch eine Rebalancierung auf dem Pfad vom gelöschten Blatt (das an die Stelle des zu löschenden Elements geschrieben wird) zur Wurzel zu erfolgen.

Siehe auch:

• Aho, Hopcroft, Ullmann
• Sedgewick/Flajolet
• Info IV Skript SS94, Prof. Mayr

In der Theorie: Sehr schöne Eigenschaften.
In der Praxis: Sehr aufwendig zu implementieren.