 Erwartete Höhe von Binärbäumen ausrechnen |
John D Dorian
unregistriert
 |
|
| 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.
|
|
25.04.2011 12:46 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
|
26.04.2011 09:32 |
|
|
John D Dorian
unregistriert
|
|
heute in der Vorlesung meinte der, dass es wohl mit 3log(n) + O(1/n) geht oder so, aber auch hier danke schön ^^
|
|
|
26.04.2011 21:59 |
|
|
|
Denke das ist auch nicht ganz so einfach...