Matematické Fórum

slender

Zdravím,
přednášející nám říkal, že průměrná hloubka průměrného vyhledávacího stromu je následující:

$\frac{1}{n}\frac{1}{n!}\sum_{\pi\in S_n}P(\pi)$

Kde $P(\pi)$ je součet délek cest z kořene stromu do všech jeho vrcholů, kdy strom je určen permutací $\pi\in S_n$ , kde $S_n$ je množina n prvkových permutací $\{1,\dots,n\}$ .

Pochopil bych, kdyby vzorečkem pro průměrnou hloubku byl tento bez toho prvního zlomku:

$\frac{1}{n!}\sum_{\pi\in S_n}P(\pi)$

Mohl by mi prosím někdo poradit, kde se tam to $\frac{1}{n}$ vzalo?

Mám k dispozici i důkaz věty, ale je anglicky a nějak mu právě moc nerozumím. Ač chápu význam jednotlivých slov, nějak mi uniká myšlenkový pochod autora.

Edit: Dobrý, už to asi chápu. Zkusím se v tom rozkoukat, pak si sám sem odpovím, třeba to někomu pak pomůže. ;)

SuckLips · 30. 05. 2016 13:19

Snažíš se najít průměrnou hloubku BST. Takže děláš průměr přes všechny možné stromy $\frac{1}{n!}$ . Dále průměr přes všechny vrcholy stromu, kterých bude n. Tedy $\frac{1}{n}$ . Jinak by si dostal pruměrný součet všech hloubek vrcholů pro strom.

Matematické Fórum

#1 28. 05. 2016 17:30 — Editoval slender (28. 05. 2016 17:37)

Průměrná hloubka průměrného binárního vyhledávacího stromu

#2 30. 05. 2016 13:19

Re: Průměrná hloubka průměrného binárního vyhledávacího stromu

Zápatí