Stromy jsou velmi důležitou třídou grafů. Mají velmi jednoduchou strukturu a proto se v nich řada věcí spočítá velmi jednoduše — téměř triviálně. Díky následujícím vlastnostem je používáme i při návrhu složitějších algoritmů.

Následující Lemma shrnuje základní vlastnosti stromu, které lze brát i jako ekvivalentní definice stromu.

Lemma: Následující tvrzení jsou ekvivalentní:

  • $T$ je strom
  • $T$ je souvislý graf s $n-1$ hranami.
  • (minimální souvislý podgraf) Přidáním libovolné hrany k $T$ vznikne kružnice.
  • (jednoznačnost cesty) Mezi libovolnými dvěmi vrcholy $T$ vede jednoznačně určená cesta.


Jednoznačnou cestu z vrcholu $x$ do vrcholu $y$ ve stromě $T$ budeme značit $xTy$. Vrcholy stromu stupně $1$ se nazývají listy.

Každý strom můžeme zkonstruovat z jednoho vrcholu postupným přilepováním listů. Tato rekurzivní konstrukce se velmi hodí jak v důkazech, tak v algoritmech. Nahlédnout to můžeme analýzou pozpátku. Natočíme si film o tom, jak postupně odtrháváme listy (najít list a odtrhnout je jednoduché). Když si film pustíme pozpátku, uvidíme jak strom vzniká z jednoho vrcholu postupným přilepováním listů.

Zakořeněné stromy

V algoritmech se častěji setkáme se stromy, které mají jeden význačný vrchol — kořen. Když pracujeme se stromem, tak většinou v jednom vrcholu začneme a z něj postupujeme do dalších vrcholů. Příkladem takového stromu je strom rekurzivních volání (vrcholy jsou instance funkcí1; $2$ instance funkce jsou spojeny hranou, pokud jedna zavolala druhou). Začneme v hlavní funkci a odtamtud voláme všechny ostatní funkce.

Při popisu algoritmů se bez zakořeněných stromů neobejdeme. Často je používáme, aniž bychom rozuměli všem pojmům, a proto si je pojďme ujasnit.

Zakořeněný strom $T$ je strom s jedním význačným vrcholem, který nazýváme kořen. Místo slova vrchol, se někdy používá termín uzel, oba termíny mají stejný význam. Představme si, že jsme hrany stromu zorientovali směrem od kořene (z hran se staly šipky). Vrcholy, ze kterých nevychází žádná šipka, se nazývají listy. Ostatní vrcholy jsou vnitřní vrcholy stromu.

Vrchol $w$ je syn (přímý následník) vrcholu $v$, pokud z $v$ vede šipka do $w$. Naopak $v$ je otec (přímý předchůdce) vrcholu $w$.2 Každý vrchol kromě kořene má právě jednoho otce, ale obráceně jeden vrchol může mít libovolný počet synů. Vrchol $u$ je následník (potomek) vrcholu $v$, pokud $v$ leží na cestě z kořene do $u$. Naopak $v$ je předchůdce $u$.

Podstrom určený vrcholem $x$ je podgraf $T$ indukovaný všemi následníky vrcholu $x$. Tento podstrom je opět zakořeněným stromem s kořenem $x$. Podstrom určený $x$ je ten kus grafu, který odpadne od zakořeněné části, když přeřízneme hranu vedoucí mezi $x$ a jeho otcem $y$. Proto někdy podstromu určenému $x$ říkáme větev $y$.

  • Stupeň vrcholu $x$ v zakořeněném stromě $T$ je počet jeho synů.
  • Hloubka vrcholu $x$ v $T$ je délka cesty z kořene do $x$. Kořen je tedy v hloubce nula.
  • Hloubka stromu $T$ je největší hloubka v $T$, tedy délka nejdelší cesty od kořene k listu.
  • $k$-tá hladina stromu $T$ je množina všech vrcholů stromu $T$ ležících v hloubce $k$. Hladiny začínáme počítat od nulté.
  • Šířka stromu $T$ je velikost největší hladiny ve stromě $T$.
  • Výška stromu $T$ je počet hladin, což je hloubka stromu $T$ plus jedna.

Do obrázku orientaci hran často nekreslíme. Hrany jsou orientovány z vrcholu ležícího výše do vrcholu ležícího níže. Proto kreslíme syny vrcholu $x$ pod vrchol $x$, navíc často rovnáme zleva doprava. Můžete si to představit tak, že graf uvázaný z kuliček a provázků chytneme za kořen, který zvedneme. Když tento model připlácneme a otiskneme na tabuli, dostaneme správné nakreslení.

Příklad: Na obrázku vpravo je zakořeněný strom $T$ o $7$ vrcholech s kořenem $A$. Vrchol $B$ je otec vrcholů $D$, $E$. Naopak $D$, $E$ jsou synové vrcholu $B$. Vrcholy $A$, $C$ jsou předchůdci vrcholu $F$ a $G$ je jeho jediný následník/potomek. Podstrom určený vrcholem $B$ je indukován vrcholy $B$, $D$, $E$. Podstrom určený vrcholem $C$ je indukován vrcholy $C$, $F$, $G$.

Šířka stromu $T$ je $3$, hloubka stromu $T$ je také $3$ a výška stromu $T$ je $4$. V nulté hladině je pouze vrchol $A$. Vrcholy ve $2.$ hladině jsou $\{ D, E, F \}$

Často pracujeme se speciálními stromy. Binární strom je strom, ve kterém má každý je vrchol nejvýše dva syny. Ty potom často označujeme jako levého a pravého syna. Obecně, $k$-ární strom je strom, ve kterém má každý vrchol nejvýše $k$ synů.

Stromová datová struktura je reprezentace stromu v počítači. V každém vrcholu stromu $v$ si budeme pamatovat hodnotu $x(v)$, které se říká klíč (key).

Při reprezentaci stromu v počítači je důležité, abychom se z každého vrcholu uměli dostat k jeho synům a z každého vrcholu, kromě kořene, k jeho rodiči. Je jedno, jestli si strom reprezentujeme dynamicky pomocí ukazatelů (pointrů) a nebo staticky v poli.

V reprezentaci stromu si často nepamatujeme pamatovat odkazy na otce. A to proto, že je můžeme zjistit jinak. Téměř vždy procházíme strom od kořene až se dostaneme do vrcholu $v$. Během průchodu si můžeme vrcholy na cestě od kořene k $v$ ukládat na zásobník. Tím získáme dokonce všechny předchůdce vrcholu $v$.