Strom je jednou z nejpoužívanějších datových struktur v informatice , emuluje stromovou strukturu jako sadu propojených uzlů. Jde o souvislý graf , který neobsahuje cykly. Většina zdrojů také přidává podmínku, že okraje grafu nesmí směřovat. Kromě těchto tří omezení některé zdroje uvádějí, že okraje grafu nesmí být váženy.
Říká se, že strom je orientován , pokud žádná hrana nevstupuje do kořene.
Uzel je instancí jednoho ze dvou typů prvků grafu, které odpovídají objektu nějaké pevné povahy. Uzel může obsahovat hodnotu, stav nebo reprezentaci individuální informační struktury nebo samotného stromu. Každý uzel stromu má nula nebo více podřízených uzlů , které jsou dále ve stromu (podle konvence stromy „rostou“ dolů, nikoli nahoru, jako to dělají skutečné stromy). Uzel, který má potomka, se nazývá nadřazený uzel svého potomka (nebo uzel předchůdce nebo starší uzel). Každý uzel má nejvýše jednoho rodiče. Výška uzlu je maximální délka sestupné cesty z tohoto uzlu k nejnižšímu uzlu (hranovému uzlu), nazývanému list . Výška kořenového uzlu se rovná výšce celého stromu. Hloubka vnoření uzlu se rovná délce cesty ke kořenovému uzlu.
Uzel bez předků (nahoře) se nazývá kořenový uzel . Toto je uzel, kde začíná většina operací na stromě (ačkoli některé algoritmy začínají na „listech“ a běží, dokud nedosáhnou kořene). Všechny ostatní uzly lze dosáhnout tak, že půjdete od kořenového uzlu podél hran (nebo spojnic) (podle formální definice musí být každá taková cesta jedinečná). V diagramech je obvykle znázorněn úplně nahoře. V některých stromech, jako jsou haldy , má kořenový uzel speciální vlastnosti. Každý uzel stromu lze považovat za kořenový uzel podstromu „vyrůstajícího“ z tohoto uzlu.
Podstrom je součástí stromové datové struktury, kterou lze reprezentovat jako samostatný strom. Jakýkoli uzel stromu T spolu se všemi jeho potomky je podstromem stromu T . Pro jakýkoli uzel v podstromu buď musí existovat cesta ke kořenovému uzlu tohoto podstromu, nebo samotný uzel musí být kořenovým uzlem. To znamená, že podstrom je spojen s kořenovým uzlem celým stromem a vztah podstromu se všemi ostatními uzly je definován konceptem odpovídajícího podstromu (analogicky s termínem "odpovídající podmnožina ").
Existují dva hlavní typy stromů. V rekurzivním stromu nebo neuspořádaném stromě záleží pouze na struktuře samotného stromu, bez ohledu na pořadí potomků pro každý uzel. Strom, ve kterém je dáno pořadí (například každé hraně vedoucí k potomkovi je přiřazeno jiné přirozené číslo ), se nazývá strom s pojmenovanými hranami nebo uspořádaný strom s datovou strukturou danou před pojmenováním, nazývaný uspořádaná stromová datová struktura . .
Mezi stromovými strukturami jsou nejběžnější uspořádané stromy. Binární vyhledávací strom je typem uspořádaného stromu.
Existuje mnoho různých způsobů, jak znázornit stromy. Nejběžnější reprezentace zobrazuje uzly jako záznamy umístěné v dynamicky alokované paměti s ukazateli na jejich potomky, předky (nebo obojí) nebo jako prvky pole , které jsou vzájemně propojeny vztahy definovanými jejich pozicemi v poli (například binární halda ).
V teorii grafů je strom spojený acyklický graf . Kořenový strom je graf s vrcholem vybraným jako kořen. V tomto případě libovolné dva vrcholy spojené hranou zdědí vztah rodič-potomek. Nesouvislý graf sestávající pouze ze stromů se nazývá les .
Postupný výčet prvků stromu podél vazeb mezi uzly předka a uzly potomky se nazývá procházení stromem . Často lze operaci provést přejetím ukazatele přes jednotlivé uzly. Procházení, ve kterém je každý uzel předků vyhledán před jeho potomky, se nazývá předřazené procházení nebo procházení v přímém pořadí (procházka před objednávkou), a když se nejprve podíváme na potomky a poté na předky, pak se procházení nazývá post . -objednaný traverz nebo traverz v obráceném pořadí (poobjednací procházka). Existuje také symetrické procházení , které nejprve navštíví levý podstrom, pak uzel, poté pravý podstrom, a procházení šířky , které navštíví uzly úroveň po úrovni (N-tá úroveň stromu je množina uzlů s výškou N ). Každá úroveň se prochází zleva doprava.
| Strom (datová struktura) | |
|---|---|
| Binární stromy | |
| Samovyrovnávací binární stromy |
|
| B-stromy |
|
| předponové stromy |
|
| Binární dělení prostoru | |
| Nebinární stromy |
|
| Rozbití prostoru |
|
| Jiné stromy |
|
| Algoritmy |
|
| Datové struktury | |
|---|---|
| Seznamy | |
| Stromy | |
| Počítání | |
| jiný | |