Strom (datová struktura)

Jednoduchý příklad neuspořádaného stromu

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

Vztahy mezi uzly naleznete na

Související informace naleznete také v článku Strom (graf)#Vztahy mezi uzly.

.

Strom v informatice

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

Podstrom S

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

Strom má výšku 4. Uzel X leží na 3. úrovni a má hloubku 2.

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

Uspořádaný binární strom

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

Příklad

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

Reprezentace stromu

Binární strom jako pole – vztahy uzlu na potomky jsou určeny funkcemi 2i+1 a 2i+2

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.

Reprezentace stromu jako hnízděné množiny

Reprezentace stromu hraničním zobrazením

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

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

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

Typy stromů

• Strom (graf) – pojem z teorie grafů
• B-strom
• Binární strom (anglicky Binary tree)
• Halda (datová struktura) (anglicky Heap)

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
• Cyklický graf

Externí odkazy

• Obrázky, zvuky či videa k tématu strom na Wikimedia Commons

Reference

• Algoritmy I^{[nedostupný zdroj]}, 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 – anglicky