Matematické Fórum

Zdravím,
mám potíž s odvozením počtu hladin pro x prvkovou binární haldu.

Jde celkem hezky vykoukat, že nová hladina přibude pokaždé, když počet vrcholů dosáhne mocniny dvojky. Jakmile je počet vrcholů např. 4, 5, 6, nebo 7, tak jsem stále v 2. hladině. V okamžik, kdy přidávám 8. vrchol, tak musím přidat i novou hladinu. Z toho se snadno vykouká, že pro výpočet počtu hladin je nutné použít log(x) v dolní celé části. Problém je, že když se to pokouším ukázat trochu formálněji, tak nějak se nemůžu dobrat cíle.

Definice dolní celé části:


Vím, že binární strom s h hladinami (zcela zaplněnými) má 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1 prvků (viz součet geometrické posloupnosti).
Tedy maximální počet vrcholů v binárním stromě o h hladinách je: 2^h - 1
Dále minimální počet vrcholů v binárním stromě o h hladinách je: 2^(h-1) (zaplněno mám zcela h-1 hladin + jeden vrchol leží v h-té hladině).

Tedy    2^(h - 1) <= x  <= 2^h - 1
           2^(h - 1) <= x  < 2^h       // zlogaritmujeme
           h-1          <= log(x) < h

Přijde mi, že jsem spíš vyrobil hybrida pro horní celou část. Dokázal by mi někdo prosím říct, kde je chyba?