Stromy

Súvislý graf, ktorý neobsahuje cykly voláme strom. Dá sa ukázať, že v strome medzi každou dvojicou vrcholov existuje práve jedna cesta. Tiež sa dá ukázať, že graf s $N$ vrcholmi je strom vtedy a len vtedy, keď je súvislý a má N−1 hrán.

Zakorenené stromy

V strome si často zvolíme jeden vrchol $r$ a ten nazveme koreň. Všetky hrany orientujeme smerom ku koreňu. Ak $v \neq r$ je vrchol, tak (jediný) jeho sused bližšie ku koreňu je jeho otec, susedia ďalej od koreňa sú jeho synovia (rodovo korektne ich tiež voláme rodič a deti $v$). Vrcholy, ktoré nemajú žiadnych synov voláme listy stromu. Takýto strom voláme zakorenený. Zakorenené stromy kreslíme väčšinou nasledovne: úplne na vrchu je koreň, pod ním sú jeho synovia, pod nimi sú ich synovia atď...

Potomkami vrcholu $v$ voláme všetky vrcholy, ktoré sú synovia $v$, synovia synov $v$ atď... Pokiaľ uvažujeme len časť stromu obsahujúcu vrchol $v$ a jeho potomkov, tak hovoríme o podstrome stromu s koreňom $v$.

Hĺbka vrchola $v$ v zakorenenom strome je jeho vzdialenosť od koreňa.

Ak má každý vrchol, ktorý nie je list, presne dvoch synov, hovoríme o binárnom strome. Keď binárny strom nakreslíme, každý vrchol (okrem listov) bude mať dvoch synov, z ktorých jeden bude viac naľavo a druhý viac napravo. Podľa toho ich niekedy voláme ľavý syn a pravý syn.

Hoci zakorenené binárne stromy vyzerajú ako veľmi špecifický druh grafov, sú veľmi užitočné: veľa dátových štruktúr má tvar binárneho stromu. Ako príklad spomeňme napríklad haldu, väčšinu vyvažovaných vyhľadávacích stromov a intervalové stromy.