PPT-Folie
Balancierte Bäume wurden als Kompromiss zwischen ausgeglichenen und natürlichen Suchbäumen eingeführt, wobei logarithmischer Suchaufwand im schlechtesten Fall gefordert wurde.
Für die Höhe hb eines AVL-Baumes mit n Knoten gilt: [log2 ( n )] + 1 ? hb ? 1.44 * log2 ( n + 1 ) Die obere Schranke lässt sich durch sog. Fibonacci-Bäume, eine Unterklasse der AVL-Bäume, herleiten.
Definition: Fibonacci-Bäume
1. Der leere Baum ist ein Fibonacci-Baum der Höhe 0: B0
2. Ein einzelner Knoten ist ein Fibonacci-Baum der Höhe 1: B1
3. Sind Bh-1 und Bh-2 Fibonacci-Bäume der Höhe h-1 und h-2, so ist Bh = (Bh-1, x, Bh-2 ) mit x ~ Vater von Bh-1, Bh-2 ein Fibonacci-Baum der Höhe h .
Zusammenhang zwischen minimaler Knotenzahl eines AVL-Baumes und Fibonacci-Bäumen: Zu gegebener Baumhöhe sind entsprechende Fibonacci-Bäume die AVL-Bäume mit jeweils minimaler Knotenzahl.