Binární strom: Porovnání verzí
Smazaný obsah Přidaný obsah
m robot přidal: ca:Arbre binari |
přeloženo z anglické wikipedie |
||
Řádek 9:
<center>[[Soubor:Binary_tree_in_array.svg|300px]]</center>
Binární strom je nejčastěji používán jako [[binární vyhledávací strom]] a [[halda (datová struktura)|halda]].
== Typy binární stromů ==
* '''Binární strom''' obsahuje uzly které mají nejvíce dva syny
* '''Plný binární strom''' každý vnitřní uzel má dva syny.
* '''Úplný binární strom''' všechny jeho listy jsou ve stejné hloubce.
* '''Vyvážený binární strom''' hloubka listů se od sebe liží maximálně o jedna.
== Vlastnosti stromů ==
poznámka: pro níže uvedené rovnice platí: ''<math>h</math>'' – hloubka stromu, <math>n</math> – počet uzlů, <math>n_0</math> – počet listů , <math>n_2</math> – počet vnitřních uzlů, <math>ni</math> – počet nillů,
*Plný binární strom
**minimální počet uzlů získáme z rovnice <math>n = {2^h}+1</math> a maximální počet <math>n=2^{h+1}-1</math>.
**počet nillů (NULL ukazatelů) roven <math>ni=n+1</math>.
**počet listů roven <math>\lceil \frac{n}{2} \rceil </math> ''(n/2 zaokrouhleno nahoru)''.
*Úplný binární strom
**počet uzlů získáme z rovnice <math>n=2^{h+1}-1</math>.
**počet uzlů v úplném binárním získáme <math>2n_0-1</math>.
{{Pahýl - algoritmus}}
| |||