Strom (datová struktura)

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

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

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

• 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ň.

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.

(c) Plej na projektu Wikipedie v jazyce čeština, CC BY-SA 3.0

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

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.

• 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í 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
  1. proveď akci
  2. projdi levý podstrom
  3. projdi pravý podstrom
• INORDER
  1. projdi levý podstrom
  2. proveď akci
  3. projdi pravý podstrom
• POSTORDER
  1. projdi levý podstrom
  2. projdi pravý podstrom
  3. 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

Výsledky způsobů procházení v binárním vyhledávacím stromu, N = navštívený uzel, L = levý, R = pravý Preorder (NLR): F, B, A, D, C, E, G, I, H Inorder (LNR): A, B, C, D, E, F, G, H, I Postorder (LRN): A, C, E, D, B, H, I, G, F Procházení do šířky (po vrstvách) Level-order: F, B, G, A, D, I, C, E, H

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.

(c) Plej na projektu Wikipedie v jazyce čeština, CC BY-SA 3.0

(c) Plej at cs.wikipedia, CC BY-SA 3.0

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

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

Id_uzlu Id_rodiče A B B F C D D B E D F – G F H I I G

• 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

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

• Fronta (datová struktura)
• Zásobník (datová struktura)
• Souvislý graf
• Kružnice (graf)

• Obrázky, zvuky či videa k tématu strom na Wikimedia Commons
• Algoritmy I^{[nedostupný zdroj]}, Jiří Dvorský, pracovní skript, verze ze dne 28. února 2007
• Datové a informační systémy Archivováno 9. 8. 2017 na Wayback Machine. Michal Krátký, 2006–2007
• Reprezentace stromu v SQL (anglicky)