Stromová struktura je jedním ze způsobů znázornění hierarchické struktury grafickým způsobem.
Říká se tomu stromová struktura , protože graf vypadá jako převrácený strom . Ze stejného důvodu říkají, že kořenový uzel (kořen) je úplně nahoře a listy jsou dole.
V teorii grafů je strom souvislý acyklický graf (pro neorientované grafy) nebo souvislý acyklický graf, ve kterém nejvýše jeden uzel nemá žádné vstupní hrany a zbývající uzly mají právě jeden vstupní uzel (pro orientované grafy).
Acyklický orientovaný graf bez přísné podmínky propojení se nazývá síť, nesouvislý graf několika stromů se nazývá les .
Heterogenní sémantické sítě se skládají ze sady stromových struktur .
Každý listový strom obsahuje prvek, který nemá žádného rodiče . Tento prvek se nazývá „kořen“ nebo „kořenový uzel“ . Lze jej považovat za první (neboli počáteční) uzel.
Opak obecně neplatí: nekonečné stromové struktury mohou nebo nemusí mít kořenové uzly.
Čáry spojující prvky se nazývají „větve“ a samotné prvky se nazývají uzly . Uzly bez potomků se nazývají „listové uzly“ nebo „listy“.
Názvy vazeb mezi uzly jsou pojmenovány podle principu rodinných vztahů.
Na Západě se v oblasti informatiky používají převážně pouze jména mužských členů rodiny, v ruštině se pro označení uzlu, který přímo souvisí s nadřazeným uzlem a je v hierarchii níže, často nazývá „dítě“. ".
V lingvistice (například v angličtině) se naopak používají jména ženských rodinných příslušníků. To naznačuje návrat ke společné konvenci pojmenování, kterou sponzorují studenti slavného amerického lingvisty Noama Chomského . Navzdory tomu se v informatice neutrální jména „rodič“ a „dítě“ často nahrazují slovy „otec“ a „syn“, navíc se výraz „strýc“ neméně aktivně používá k označení dalších uzlů, které jsou na stejné úrovni jako rodiče.
Ve výše uvedeném příkladu je „encyklopedie“ rodičem „vědy“ a „kultury“, což jsou její „děti“. „Umění“ a „řemeslo“ jsou bratři ve vztahu k sobě navzájem a děti ve vztahu ke „kultuře“.
Stromové struktury slouží k zobrazení všech druhů informací z oblasti taxonomie , jako je rodokmen , fylogenetický strom , gramatická struktura jazyka (například v angličtině je dobrým příkladem schéma S → NP VP, což znamená, že věta (věta) je jmenná fráze (podstatná jmenná fráze) a skupina sloves (slovesná fráze), způsob, jak logicky uspořádat webové stránky na webu a tak dále.
Ve stromové struktuře může existovat jedna a pouze jedna cesta z jednoho bodu do druhého.
Stromové struktury jsou široce používány v informatice (viz Strom (datová struktura) a Komunikace (inženýrství) ).
Mezi uzly stromové struktury mohou existovat různé sémantické vztahy .
Ve skutečných encyklopediích ( Wikipedia ) existují všechny takové DS v antagonismu, pokud systém jejich prezentace není promyšlen samostatně a jako celek.
Ve struktuře tematicky homogenních skupin článků Wikipedie se používají různé typy odkazů . Zpočátku se identifikují sekce, které se liší dobou výskytu objektů článků (Neživá příroda, Divoká zvěř, Lidstvo, Technosféra), poté se použijí vazby mezi strukturálními úrovněmi v rámci sekcí, vazby mezi homogenními články (rod-druh), poslední v hierarchii se používá počet článků ve skupině.
Existuje mnoho způsobů, jak graficky znázornit stromové struktury. V naprosté většině případů se jedná o různé variace nebo kombinace několika základních stylů:
Popis některých základních metod naleznete v:
| 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 |
|