AVL-Bäume und Fibonacci-Zahlen

Erste Frage Aufrufe: 291     Aktiv: 23.01.2022 um 20:26
0

Zeige mit vollständiger Induktion, dass ein AVL-Baum der Höhe h mindestens Fh+2 − 1 Knoten enthält.

(Hinweis: Fn beschreibt die n-te Fibonacci-Zahl mit F0 = 0, F1 = 1 und Fn = Fn−1 +Fn−2.)

kann mir jemand weiterhelfen wie ich den Induktionsschritt rechne ?

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0
Um einen Baum um eine Stufe zu vergrößern, fügst du einen weiteren Knoten als Wurzel hinzu. Der linke (oder rechte) Teilbaum hat dann die Höhe $h$. Welche Höhe muss dann der andere Teilbaum mindestens haben? Dann wendest du die Induktionsvoraussetzung auf beide Teilbäume an und berechnest damit die Mindestzahl an Knoten.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 30.55K

 
also ich habe es so :
h>=2 der Wurzel hat Unterbäume der Höhe h-1 oder h-2 , weil AVL-Baum ist
F_h = 1 + mind. Knotenanzahl des Baums der Höhe h
F_h = 1 + F_h-1 -1 + F_h-2 -1
F_h = F_h-1 + F_h-2 -1
Nun ich weiß nicht ob mein erster Schritt hier korrekt ist.   ─   user2dd77a 23.01.2022 um 11:14

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Cauchy wurde bereits informiert.