Strom

Algoritmy a programovanie

---

Dátový typ

>Zásobník
>Zoznam
>Fronta
>Množina
>Strom
>Hromada

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Strom je dátová štruktúra ktorá modeluje vzťah rodič-potomok, resp. rodič-potomkovia. Existuje viacero druhov stromov:

• Binárny strom
• 2-3 stromy
• 2-3-4 stromy
• AA strom
• B-strom
• Náhodný binárny strom

Podrobnejšie informácie o dátovej štruktúre binárny strom sú v kapitole o binárnych stromoch

Definícia stromu

• Koreňový zuol strmu je uzol, ktorý nemá žiadneho rodiča. V strome je takýto uzol práve jeden
• Uzol - list nemá žiadnych potomkov
• Hĺbka uzla n je dĺžka cesty z koreňa k tomuto uzlu. Množina všetkých uzlov s rovnakou hĺbkou sú nazývaná ako úroveň stromu.Koreň má úroveň 0.
• Výška stromu je dĺžka cesty od koreňa k najhlbšiemu uzlu v strome plus 1. Strom s jediným uzlom má výšku 1. Strom, ktorý nemá žiaden uzol má výšku 0.
• Súrodenci sú také uzly, ktoré majú spoločný rodičovský uzol.
• Uzol p je predok uzla q, ak existuje cesta z q ku koreňu stromu. Uzol q je potom označovaný ako potomok uzla p.
• Vstupný stupeň uzla (In-degree) je počet hrán prichádzajúcich do uzla.
• Výstupný stupeň uzla (Out-degree) je počet hrán odchádzajúcich z uzla.
• Koreň stromu je jediný uzol v strome, ktorý má vstupnú stupeň uzla = 0.
• Listy stromu majú výstupný stupeň uzla=0