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.

[editovat] Uzly ve stromu

Uzel stromu (anglicky „node“) může:

• obsahovat hodnotu
• obsahovat podmínku
• reprezentovat strukturu oddělených dat
• obsahovat vlastní strom

Uzly jsou navzájem spojeny „hranami“. 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 potomků nějakého uzlu se nazývá „stupeň uzlu“.
Vztahy mezi uzly naleznete na

Podrobnější informace naleznete v článku Strom (graf)#Vztahy mezi uzly..

Strom v informatice

[editovat] Základní prvky stromu

[editovat] 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í právě jeden kořen

[editovat] Vnitřní uzly

• Uzel, který není ani kořen ani koncovým uzlem se nazývá „vnitřní uzel“ (anglicky „internal node“ nebo „inner node“).

[editovat] Koncové uzly

• „Koncový uzel“, někdy také „listy“ (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

[editovat] 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.

[editovat] 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ýšku 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 kromě poslední má tato struktura plný počet uzlů.

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.

[editovat] Stromové uspořádání

Uspořádaný binární strom

Stromy se dělí na dva základní typy stromů:

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

[editovat] Metody procházení stromu

[editovat] 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.

[editovat] 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 žádnem 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 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 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

[editovat] 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

[editovat] 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 hromadě 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

[editovat] Strom jako graf

V teorii grafů odpovídá hierarchická struktura stromu acyklickému grafu s jedním kořenem, někdy nazývaný „přímý acyklický graf“, 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ů.

[editovat] Reprezentace stromu v SQL

Pro reprezentaci struktury v SQL 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

[editovat] 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

[editovat] Stromy

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

[editovat] Související články

• Fronta (datová struktura)
• Zásobník (datová struktura)
• Souvislý graf
• Cyklický graf

[editovat] Reference

• Algoritmy I Jiří Dvorský, pracovní script, Verze ze dne 28. února 2007
• Trees- anglicky
• Datové a informační systémy Michal Krátký, 2006-2007