Strom (datová struktura): Porovnání verzí
Smazaný obsah Přidaný obsah
Řádek 4:
== Uzly ve stromu ==
Uzel stromu (anglicky „node“) může:
* obsahovat hodnotu (popř. tzv. klíč)
* obsahovat podmínku
* reprezentovat strukturu oddělených dat
* obsahovat vlastní strom
Uzly jsou navzájem spojeny „hranami“. Neexistuje osamocený uzel, ke kterému by nevedla žádná hrana (s výjimkou stromu s pouze jedním uzlem). Pokud jsou hrany orientované, nazývají se uzly připojené k jednomu uzlu jako „potomci uzlu“, nadřazený uzel je potom „rodičovský uzel“. Uzel může mít pouze jednoho rodiče, ale více potomků. Počet všech potomků nějakého uzlu se nazývá „stupeň uzlu“.
Vztahy mezi uzly naleznete na {{Viz též|Strom (graf)#Vztahy mezi uzly}}.
[[Soubor:Strom(informatika).jpg|thumb|right|270px|Strom v informatice]]
* Nejvyšší uzel ve stromu se nazývá „kořen stromu“ (anglicky „root“)
* Kořen stromu je jediným uzlem ve stromu bez rodiče
* V každém stromu se nachází právě jeden kořen
* Uzel, který není koncovým uzlem se nazývá „vnitřní uzel“ (anglicky „internal node“ nebo „inner node“). Někteří autoři z množiny vnitřních uzlů explicitně vypouští kořen.
* „Koncový uzel“, někdy také „list“ (anglicky „leaf“ nebo „leaf node“), je takový prvek, který nemá žádného potomka. Má-li strom jen jeden uzel, je tento uzel kořenem i listem zároveň.
[[Soubor:Podstrom.jpg|thumb|Podstrom S]]
==== Maximální počet potomků ====
Konkrétní typy stromů většinou mají definován maximální počet potomků ve svých vnitřních uzlech. Například:
* pro [[binární strom]] je to 2
* pro [[2-3 strom]] je to 3
* pro [[B-strom]] je to definovaná hodnota ''n''
* pro případ extrémně nevyrovnaného stromu (který se blíží lineárnímu seznamu) je to 1
Do uzlu s již maximálním počtem poduzlů nelze další uzel přidat a místo toho je potřeba jej nějakým způsobem přeuspořádat.
„Podstrom“ (anglicky „subtree“) je část stromové datové struktury tvořené jedním uzlem („kořenem podstromu“) a všemi jeho potomky. Může být chápán jako kompletní strom sám o sobě. Každý uzel ve stromu může tvořit kořen podstromu.<br />
| |||