Anzahl aller avl bäume bei gleicher höhe

AVL-Bäume - Eigenschaften - Höhenabschätzung

Im folgenden wollen wir die maximale Höhe h eines AVL-Baums bei einer gegebenen Anzahl N von Knoten ausrechnen und dieses Ergebnis mit der Höhe eines binären Suchbaums vergleichen.

Für binäre Suchbäume haben wir bereits festgestellt, daß im ungünstigsten Fall der Baum zu einer linearen Liste entarten kann. Die Höhe eines solchen Baums beträgt dann gerade N.

Um die maximale Höhe eines AVL-Baums zu berechnen, überlegen wir nun umgekehrt, wieviele Knoten n ein AVL-Baum minimal haben kann. Wir betrachten also knotenminimale AVL-Bäume Th zu einer vorgegebenen Höhe h:

Höhe h	0	1	2	3
Beispielbaum Th
Minimale Anzahl Knoten nh	1	2	4	7

Allgemein:

Ist v die Wurzel eines knotenminimalen AVL-Baums der Höhe h, so ist h(Tl(v)) = h - 1 und h(Tr(v)) = h - 2, oder umgekehrt.
Dabei müssen Tl(v) und Tr(v) auch wieder knotenminimale AVL-Bäume zu ihrer jeweiligen Höhe sein.

Damit erhalten wir für die Anzahl Knoten eines knotenminimalen AVL-Baums der Höhe h die folgende Rekursionsformel:

n0 = 1, n1 = 2, nh = 1 + nh-1 + nh-2

Diese Formel erinnert an die Rekursionsformel

f0 = 0, f1 = 1, fh = fh-1 + fh-2 für die Fibonacci-Zahlen 0, 1, 1, 2, 3, 5, 8, ...

Durch vollständige Induktion können die folgenden beiden Formeln bewiesen

werden:

Durch Einsetzen der Formel für die fh erhalten wir für die Anzahl Knoten eines knotenminimalen AVL-Baums der Höhe h:

Knotenminimale AVL-Bäume zu einer Höhe h sind aber gleichzeitig höhenmaximale AVL-Bäume zu einer vorgegebenen Knotenanzahl n.
Wenn wir diese Gleichung logarithmieren und nach h auflösen, so erhalten wir folglich die maximale Höhe h eines AVL-Baums mit n Knoten:

Die folgende Tabelle zeigt die Ergebnisse im Überblick.