Antwort mit KI erzeugt
Vollständige Induktion – AVL Baum mit Höhe h
Zu zeigen: Ein AVL–Baum der Höhe \(h\) hat mindestens \(F_{h+2} - 1\) Knoten.
Induktionsbasis:
Für \(h = 0\) (der geringstmögliche Höhe, da Höhe des leeren Baumes als \(-1\) definiert ist):
\( F_{0+2} - 1 = F_2 - 1 = 1 - 1 = 0\)
Ein AVL-Baum der Höhe \(0\) hat genau einen Knoten (\(0\) Knoten, falls der Baum leer ist), was der Behauptung entspricht.
Für \(h = 1\):
\( F_{1+2} - 1 = F_3 - 1 = 2 - 1 = 1\)
Ein AVL-Baum der Höhe \(1\) hat mindestens zwei Knoten, was ebenfalls der Behauptung entspricht, da ein AVL-Baum mit einer Höhe von \(1\) mindestens einen Wurzelknoten und mindestens einen Kindknoten besitzen muss.
Induktionsannahme:
Angenommen, die Aussage gilt für alle Höhen bis \(h\), d.h. ein AVL-Baum mit Höhe bis \(h\) hat mindestens \(F_{h+2} - 1\) Knoten.
Induktionsschritt:
Zu zeigen ist, dass die Aussage auch für die Höhe \(h + 1\) gilt.
Ein AVL-Baum der Höhe \(h+1\) muss aus zwei geringer hohen AVL-Bäumen aufgebaut sein, deren Höhenunterschied höchstens 1 beträgt (aufgrund der AVL-Bedingung). Diese zwei AVL-Bäume können Höhen \(h\) und \(h-1\) haben.
Gemäß der Induktionsannahme hat der Baum der Höhe \(h\) mindestens \(F_{h+2} - 1\) Knoten und der Baum der Höhe \(h-1\) mindestens \(F_{h+1} - 1\) Knoten.
Rechnung:
\( F_{(h+1)+2} - 1 = F_{h+3} - 1\)
Wir verwenden die Eigenschaft der Fibonacci-Zahlen: \(F_{h+3} = F_{h+2} + F_{h+1}\). Das setzen wir in die obige Formel ein:
\( F_{h+3} - 1 = (F_{h+2} + F_{h+1}) - 1\)
Der AVL-Baum der Höhe \(h+1\) enthält:
- Einen Wurzelknoten
- Mindestens \(F_{h+2} - 1\) Knoten vom linken oder rechten Unterbaum der Höhe \(h\)
- Mindestens \(F_{h+1} - 1\) Knoten vom anderen Unterbaum der Höhe \(h-1\)
Zusammengefasst ergibt er:
\( 1 + (F_{h+2} - 1) + (F_{h+1} - 1) = F_{h+2} + F_{h+1} - 1\)
Was durch die Fibonacci-Relation genau \(F_{h+3} - 1\) ergibt.
Damit ist gezeigt, dass auch für die Höhe \(h + 1\) die Anzahl der Knoten in einem AVL-Baum mindestens \(F_{h+3} - 1 = F_{(h+1)+2} - 1\) entspricht.
Da die Aussage für die Basisfälle \(h = 0\) und \(h = 1\) sowie unter der Annahme, dass sie für ein beliebiges \(h\) gilt, auch für \(h+1\) bewiesen werden konnte, folgt nach dem Prinzip der vollständigen Induktion, dass ein AVL-Baum der Höhe \(h\) stets mindestens \(F_{h+2} - 1\) Knoten enthält.
