Informatik Fibonacci Baum < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:32 Di 17.05.2011 | | Autor: | dimi727 |
| Aufgabe | Ein Fibonacci-Baum(extremaler Baum) [mm] T_{h} [/mm] der Höhe h ist ein binärer Baum, der wie folgt rekursiv definiert ist :
i) [mm] T_{-1} [/mm] ist der leere Baum.
ii) [mm] T_{0} [/mm] ist ein Baum aus genau einem Knoten
iii) [mm] T_{h} [/mm] für h [mm] \ge [/mm] 1 ist ein binärer Wurzelbaum, dessen Wurzel als einen Teilbaum einen [mm] T_{h-1} [/mm] und als anderen Teilbaum einen [mm] T_{h-2} [/mm] hat.
b(h)=b(h-1)+b(h-2) - - - gibt die Anzahl der Blätter zurück
n(h)=n(h-1)+n(h-2)+1 - - - gibt die Anzahl der Knoten im Baum zurück.
h(v) gibt die Höhe des Knotens v zurück.
Aufgabe:
Der Baum [mm] T_{h} [/mm] erfülle die Suchbaumeingenschaft. Unter der mittleren Höhe verstehen wir die Größe H(h):= [mm] \bruch{1}{n(h)}\summe_{v\in T_{h}}h_{T_{h}}(v),wobei [/mm] also [mm] \summe_{v\in T_{h}}h_{T_{h}}(v) [/mm] die Summe der Höhe aller Knoten im Baum [mm] T_{h} [/mm] angibt. Sie ist ein Maß für die erwartete Zugriffszeit auf einen zufälligen Schlüssel. Gebt eine (möglichst kleine) Konstante c < 1 an, für die gilt :
H(h) [mm] \le [/mm] c*h für alle h [mm] \ge [/mm] 0.
(Tipp: Verwendet die folgende Näherung der Fibonnaci-Zahlen für große k: [mm] F_{k} \approx \bruch{1}{\wurzel{5}}(\bruch{1+\wurzel{5}}{2})^{k}.) [/mm] |
Guten Abend Leute,
ich hoffe, mir kann bei dieser Aufgabe hier ebenfalls geholfen werden.
Ergänzend zu der obigen Aufgabenstellung wissen wir noch:
Die Summe der Höhe der Knoten kann auch als eine rekursive Funktion geschrieben werden :
f(h) = f(h-1) +f(h-2) + n(h-1) + n(h-2) , wobei f(h-1),f(h-2) die Summen der Höhen der Teilbäume von [mm] T_{h} [/mm] sind, n(h-1),n(h-2) die Anzahl der Knoten in den 2 Teilbäumen.
Ferner kann man n(h) umgeschreiben,denn wir wissen aus unserer Vorlesung:
F(h) = n(h-3) +1 , [mm] h\ge3 [/mm] (F(h) ist die Fibonacci Funktion)
F(0) = 0, F(1)=1, F(2)=1
F(h)= n(h-3)+1 [mm] \gdw [/mm] n(h) = F(h+3) - 1
Dadurch lässt sich [mm] \bruch{1}{n(h)}\summe_{v\in T_{h}}h_{T_{h}}(v) [/mm] umschreiben :
[mm] \bruch{f(h-1)+ f(h-2)+ n(h-1)+ n(h-2)}{F(h+3)-1} \le [/mm] c*h
Und für F(h) können wir die in der Aufgabe aufgeführte Abschätzung einsetzen :
[mm] \bruch{f(h-1) +f(h-2) + n(h-1) + n(h-2)}{( \bruch{1}{\wurzel{5}}(\bruch{1+\wurzel{5}}{2})^{h+3})-1} \le [/mm] c*h
So und hier weiß ich erstmal nicht weiter. Ich könnte für n(h-1), n(h-2) im Zähler einsetzen und so diese Rekursiven Funktionen eliminieren. Es bleiben aber noch die zwei rekusiven Methoden für die Höhen der Teilbäume.
Mein Tutor hat mir als Tipp mitgegeben: Es muss ganz viel abgeschätzt werden und am Ende muss man den Limes laufen lassen, sodass man c rausbekommen sollte.
Ich hoffe, man konnte alles nachvollziehen und mir kann jemand helfen.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:44 Di 17.05.2011 | | Autor: | dimi727 |
Oh Gott, wie bin ich aufs Schulforum gekommen? Wie kann man den Thread verschieben?:/
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:53 Di 17.05.2011 | | Autor: | Teufel |
Hi!
Ich habe das mal nach Hochschule/Diskrete Mathematik/Graphentheorie verschoben, obwohl es auch nicht ganz passt. :) Aber ich finde auch nichts Besseres.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Do 19.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
