Strom (datová struktura)

V informatice je strom široce využívanou datovou strukturou, která představuje stromovou strukturu s propojenými uzly.

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“.

Základní prvky stromu

Kořen stromu 
 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í maximálně jeden kořen, takový strom nazýváme „zakořeněný strom“

Vnitřní uzly 
 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é uzly 
 „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ň.

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 
„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.

Hloubka, výška, šířka, úroveň a cesta 

 „Cesta“ k nějakému uzlu je definována jako posloupnost všech uzlů od kořene k uzlu.
 „Délka cesty“ je rovna počtu hran, které cesta obsahuje, tedy počtu uzlů posloupnosti – 1.
 „Hloubka uzlu“ je definována jako délka cesty od kořene k uzlu.
 Prvky se stejnou hloubkou jsou na „téže úrovni“.
 „Výška stromu“ je rovna hodnotě maximální hloubky uzlu, se označuje též za „hloubku stromu“.
 „Šířkou stromu“ je počet uzlů na stejné úrovni.
 Strom má „nejmenší výšku“ právě tehdy, když na všech úrovních (s možnou výjimkou té poslední) má tato struktura plný počet uzlů. Úroveň všech listů je stejná nebo se liší maximálně o 1.

Při sestavování stromové struktury je důležité sestavovat stromy s nejmenší možnou výškou, protože tím se zajistí optimální rychlost práce se strukturou.

„Vyvážený strom“ je takový strom, který má uzly rovnoměrně rozložené, tedy má nejmenší výšku. Ideální situace je taková, kdy má strom v každé hladině, kromě poslední, maximální počet uzlů, a v poslední hladině má uzly co nejvíce vlevo.

Stromové uspořádání 

Stromy se dělí na dva základní typy:
 Uspořádaný (anglicky „ordered tree“)
 Neuspořádaný (anglicky „unordered tree“)

„Uspořádaný“ nebo také „seřazený strom“ je takový strom, ve kterém jsou všichni přímí potomci každého uzlu seřazeni. Tudíž, pokud uzel má n dětí, lze určit prvního přímého potomka, druhého přímého potomka, až n-tého přímého potomka.

U „neuspořádaného stromu“ se jedná o strom v čistě strukturálním smyslu. To znamená, že pro daný uzel nejsou uspořádáni potomci.

Metody procházení stromu

Procházení stromem do šířky 
 Procházením „stromu do šířky“ (anglicky „level-order“) se rozumí procházení stromem po vrstvách úrovní (tzn. po hladinách). Viz prohledávání do šířky.

Procházení stromem do hloubky 
Procházení začíná v kořeni stromu a postupuje se vždy na potomky daného vrcholu. Procházení končí, když v žádné větvi (tj. v žádném podstromu) již není následník. Viz prohledávání do hloubky.

Podle pořadí, ve kterém se prochází uzly uspořádaného stromu, se rozlišují tři základní metody:
 PREORDER
 proveď akci
 projdi levý podstrom
 projdi pravý podstrom
 INORDER
 projdi levý podstrom
 proveď akci
 projdi pravý podstrom
 POSTORDER
 projdi levý podstrom
 projdi pravý podstrom
 proveď akci

Při použití metody INORDER se prochází uzly v uspořádaném stromě podle jejich přirozeného pořadí.

Procházení stromem do hloubky lze řešit pomocí:
 Rekurze – funkce volá sama sebe
 Iterace – provádění stejné operace znovu a znovu

Příklad

Reprezentace stromu 

Je mnoho způsobů jak reprezentovat stromy. Běžné reprezentace reprezentují uzly jako záznamy na haldě s ukazatelem na dítě nebo na rodiče nebo na oba. Případně se reprezentují jako pole prvků se vztahy mezi sebou (pomocí algoritmů), které určují jejich pozici v poli.

Často se setkáváme s reprezentací hierarchickou:
 F
 B
 A
 D
 C
 E
 G
 I
 H

Nahlížet na hierarchii můžeme mnoha způsoby. Jedním z nich je „hnízděná množina“, kterou si lze představit jako vnořené množiny. Další velmi podobný způsob je „hraniční“ reprezentace.

Strom jako graf 
V teorii grafů odpovídá hierarchická struktura stromu acyklickému grafu s jedním kořenem, jež bývá často nazýván jako „orientovaný acyklický graf“ a ve kterém každý vrchol má „vstupní hranu“. Acyklický graf, který není propojen, se někdy nazývá les, protože se skládá z více stromů.

Reprezentace stromu v relační databázi 
Pro reprezentaci struktury v relační databázi se používá zpravidla jedna tabulka, ve které si ukládáme identifikaci rodičovského uzlu a identifikátor uzlu. Je-li potřeba vytvořit strom s více rodiči pro jeden uzel, tabulka se rozdělí na dvě. Jedna tabulka bude obsahovat seznam uzlů a ve druhé budou zaznamenány vazeb mezi uzly (tzv. vztah uzlů M:N). V případě binárního stromu se používá tabulka se třemi sloupci kde je zaznamenána hodnota, levý a pravý ukazatel na dítě.

Operace na stromech 
 Počet všech prvků
 Hledání prvků
 Přidání nového prvku na určitou pozici ve stromu
 Smazání prvku
 Vyjmutí celé části stromu – prořezávání (anglicky „pruning“)
 Přidání celé části do stromu – roubování (anglicky „grafting“)
 Hledání kořene pro každý uzel
 Výška (hloubka) stromu

Využití 
Stromy, a zejména jejich některé konkrétní vyhledávací varianty, nacházejí široké uplatnění v oblastech, kde je třeba řešit ukládání a vyhledávání dat, zejména tam, kde je kritickou omezující podmínkou vyhledání dat s co nejmenší úrovní složitostí a při co nejméně přístupy čtení.

Pravděpodobně nejpoužívanější v praxi jsou aplikace B+ stromů, kde nejčastější použití je u souborových systémů (např. NTFS) a většiny databází.

Související články 
 Fronta (datová struktura)
 Zásobník (datová struktura)
 Souvislý graf
 Kružnice (graf)

Externí odkazy 
 
 Algoritmy I, Jiří Dvorský, pracovní skript, verze ze dne 28. února 2007

 Datové a informační systémy  Michal Krátký, 2006–2007
 Reprezentace stromu v SQL 

Stromy (datové struktury)
Datové struktury