Erwartete Höhe von Binärbäumen ausrechnen |
| 25.04.2011, 12:46 | Auf diesen Beitrag antworten » |
| John D Dorian | Erwartete Höhe von Binärbäumen ausrechnen Meine Frage: Ich würde gerne wissen ob es eine Formel gibt mit der man die erwartete Höhe von Binärbäumen ausrechnen kann. Also meine Aufgabe ist die erwartete Höhe eines Binärbaums zu ermitteln, bei dem die Zahlen 1,2,3 und 4 in zufälliger Reihenfolge eingefügt werden. Meine Ideen: In der Aufgabe steht schon, dass die erwartete Höhe die durchschnittliche Höhe der Suchbäume über alle möglichen Einfügereihenfolgen ist. Die Anzahl aller möglichen Reihenfolgen habe ich mit der Formel n!/((n-k)!) herausgefunden... die habe ich dann einfach alle aufgemalt und geschaut wie hoch die sind, zusammen gezählt und dann den Durchschnitt genommen. Da kam dann (8*4(höhe 4)+16*3(höhe 3))/24(anzahl der Möglichkeiten) = 80/24 = 10/3 raus... also die Aufgabe an sich habe ich gelöst, jedoch würde ich gerne wissen obs dafür auch eine Formel gibt, da es bei 5 Zahlen (120 Möglichkeiten) dann schon recht schwer werden würde alle aufzumalen und die Höhe anzuschauen. |
|
|
|
| 26.04.2011, 09:32 | Auf diesen Beitrag antworten » |
| Karlito | vlt hilft dir das weiter: http://www.matheboard.de/archive/239914/thread.html Ich bin gerade zu faul mir Gedanken über ne allgemeine Lösung zu machen, sorry 
Denke das ist auch nicht ganz so einfach...VG, Karlito |
| 26.04.2011, 21:59 | Auf diesen Beitrag antworten » |
| John D Dorian | heute in der Vorlesung meinte der, dass es wohl mit 3log(n) + O(1/n) geht oder so, aber auch hier danke schön ^^ |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |