Matematické Fórum

doomed · 27. 02. 2012 17:28

Ahoj, v tomto případě jde spíše o matematický dotaz, ale úzce to souvisí s algoritmy. Případně prosím o přesunutí do odpovídající sekce.

Mám binární strom s nejmenší možnou výškou $H$ , tj. od první do předposlední hladiny má tento strom plný počet uzlů a na poslední hladině má minimálně jeden a maximálně všech $2^{H-1}$ uzlů.
Celkový počet uzlů $N$ tohoto stromu tedy je větší nebo roven:
$1+2+4+ \ldots +2^{H-2} + 1=2^{H-1}$
a současně menší nebo roven:
$1+2+4+ \ldots +2^{H-1}=2^{H}-1$
No a mě by zajímalo, jak jsem v obou těch rovnostech dospěl k tomu výrazu vpravo. Určitě je to triviální počítání s posloupnostmi, ale jakmile tam vidím tu výpustku, nevím si s tím rady. Počítal jsem to sice na papíře, ale k ničemu kloudnému jsem nedošel.
Děkuji

doomed · 28. 02. 2012 14:23

↑ doomed: Tak už to mám. Jde o běžný součet prvních $n$ členů geometrické posloupností pomocí vzorce $s_n = \frac{q^n - 1}{q - 1}$

Matematické Fórum

#1 27. 02. 2012 17:28

Počet uzlů binárního stromu

#2 28. 02. 2012 14:23

Re: Počet uzlů binárního stromu

Zápatí