---

Geschrieben von John D Dorian am 25.04.2011 um 12:46:

  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.

---

Geschrieben von Karlito am 26.04.2011 um 09:32:

 

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

---

Geschrieben von John D Dorian am 26.04.2011 um 21:59:

 

heute in der Vorlesung meinte der, dass es wohl mit 3log(n) + O(1/n) geht oder so, aber auch hier danke schön ^^