Strom (datová struktura) - Tree (data structure)

Obecný, a tak nebinární, netříděný, některé štítky duplikovány, libovolný diagram stromu. V tomto diagramu má uzel označený 7 tři potomky označené 2, 10 a 6 a jednoho rodiče označeného 2. Kořenový uzel v horní části nemá žádného rodiče.

v počítačová věda, a strom je široce používán abstraktní datový typ který simuluje hierarchické stromová struktura, s kořenovou hodnotou a podstromy dětí s a nadřazený uzel, představovaný jako sada propojených uzly.

Lze definovat stromovou datovou strukturu rekurzivně jako kolekce uzlů (počínaje kořenovým uzlem), kde každý uzel je datová struktura skládající se z hodnoty, společně se seznamem odkazů na uzly („podřízené“), s omezeními, že žádný odkaz není duplikován, a nikdo neukazuje na kořen.

Alternativně lze strom definovat abstraktně jako celek (globálně) jako objednaný strom, s hodnotou přiřazenou každému uzlu. Obě tyto perspektivy jsou užitečné: zatímco strom lze analyzovat matematicky jako celek, je-li ve skutečnosti reprezentován jako datová struktura, je obvykle reprezentován a pracuje se s ním samostatně podle uzlu (spíše než jako sada uzlů a seznam sousedství hran mezi uzly, protože jeden může představovat a digraf, například). Například při pohledu na strom jako celek lze hovořit o „nadřazeném uzlu“ daného uzlu, ale obecně jako datovou strukturu obsahuje daný uzel pouze seznam jeho podřízených prvků, ale neobsahuje odkaz na jeho rodič (pokud existuje).

Běžné použití

• Zastupování hierarchický údaje jako:
  • Abstraktní syntaxové stromy pro počítačové jazyky
  • Analyzovat stromy pro lidské jazyky
  • Modely objektů dokumentu z XML a HTML dokumenty
  • JSON a YAML zpracovávané dokumenty
• Prohledejte stromy ukládat data efektivním způsobem vyhledávací algoritmus možné prostřednictvím traversal strom
  • A binární vyhledávací strom je typ binární strom
• Zastupování seřazené seznamy dat
• Jako pracovní postup pro skládání digitální obrázky pro vizuální efekty^{[Citace je zapotřebí ]}
• Skladování Barnes-Hut stromy používané k simulaci galaxií

Terminologie

A uzel je struktura, která může obsahovat hodnotu nebo podmínku, nebo představuje samostatnou datovou strukturu (což může být vlastní strom). Každý uzel ve stromu má nulu nebo více podřízené uzly, které jsou pod stromem (podle konvence jsou stromy nakresleny rostoucí dolů). Uzel, který má dítě, se nazývá dítě nadřazený uzel (nebo nadřízený ). Uzel má maximálně jednoho rodiče, ale možná mnoho uzly předků, například rodič rodiče. Podřízené uzly se stejným rodičem jsou sourozenecké uzly.

An vnitřní uzel (také známý jako vnitřní uzel, inode zkrátka nebo uzel větve) je libovolný uzel stromu, který má podřízené uzly. Podobně an externí uzel (také známý jako vnější uzel, listový uzelnebo koncový uzel) je libovolný uzel, který nemá podřízené uzly.

Nejvyšší uzel ve stromu se nazývá kořenový uzel. V závislosti na definici může být vyžadováno, aby strom měl kořenový uzel (v takovém případě jsou všechny stromy neprázdné), nebo může být povoleno, aby byl prázdný, v takovém případě nemusí nutně mít kořenový uzel. Jako nejvyšší uzel nebude mít kořenový uzel rodiče. Je to uzel, ve kterém začínají algoritmy na stromě, protože jako datovou strukturu lze předávat pouze od rodičů k dětem. Všimněte si, že některé algoritmy (jako je hledání po objednávce do hloubky první) začínají v kořenovém adresáři, ale první návštěva uzlů listu (přístup k hodnotě listových uzlů), návštěva kořene pouze jako poslední (tj. První přístup k dětem kořene , ale pouze přístup k hodnotě root naposledy). Všechny ostatní uzly lze z něj získat pomocí následujícího postupu hrany nebo Odkazy. (Ve formální definici je každá taková cesta také jedinečná.) V diagramech je kořenový uzel konvenčně nakreslen nahoře. Na některých stromech, jako např hromady, kořenový uzel má speciální vlastnosti. Každý uzel ve stromu lze považovat za kořenový uzel podstromu zakořeněného v tomto uzlu.

The výška uzlu je délka nejdelší sestupné cesty k listu z tohoto uzlu. Výška kořene je výška stromu. The hloubka uzlu je délka cesty k jeho kořenu (tj. jeho kořenová cesta). To je běžně nutné při manipulaci s různými samovyvažovacími stromy, Stromy AVL zejména. Kořenový uzel má nulovou hloubku, listové uzly mají nulovou výšku a strom pouze s jedním uzlem (tedy kořen i list) má hloubku a výšku nula. Prázdný strom (strom bez uzlů, pokud jsou povoleny) má obvykle výšku -1.

A podstrom stromu T je strom skládající se z uzlu v T a všichni jeho potomci v T.^[A][1] Uzly tedy odpovídají podstromům (každý uzel odpovídá podstromu sebe sama a všem jeho potomkům) - podstrom odpovídající kořenovému uzlu je celý strom a každý uzel je kořenem uzlu podstromu, který určuje; podstrom odpovídající kterémukoli jinému uzlu se nazývá a řádný podstrom (analogicky k a správná podmnožina ).

Další termíny používané se stromy:

Soused

Rodič nebo dítě.

Předek

Uzel dosažitelný opakovaným postupem od dítěte k rodiči.

Potomek

Uzel dosažitelný opakovaným postupem od rodiče k dítěti. Také známý jako vnuk.

Uzel větve

Interní uzel

Uzel s alespoň jedním dítětem.

Stupeň

Pro daný uzel jeho počet dětí. List je nutně stupeň nula. Stupeň stromu je stupeň jeho kořene.

Stupeň stromu

Stupeň kořene.

Vzdálenost

Počet hran podél nejkratší cesty mezi dvěma uzly.

Úroveň

1 + počet hran mezi uzlem a kořenem, tj. (hloubka + 1)^{[pochybný – diskutovat]}

Šířka

Počet uzlů na úrovni.

Šířka

Počet listů.

Les

Sada n ≥ 0 nesouvislých stromů.

Objednaný strom

Kořenový strom, ve kterém je pro děti každého vrcholu určeno pořadí.

Velikost stromu

Počet uzlů ve stromu.

Předběžná definice

Není to strom: dva non-připojeno díly, A → B a C → D → E. Existuje více než jeden kořen.

Není to strom: nepřímý cyklus 1-2-4-3. 4 má více než jednoho rodiče (příchozí hrana).

Není to strom: cyklus B → C → E → D → B. B má více než jednoho rodiče (příchozí hrana).

Není to strom: cyklus A → A. A je kořen, ale má také rodiče.

Každý lineární seznam je triviálně strom

Strom je nelineární datová struktura ve srovnání s poli, propojenými seznamy, zásobníky a frontami, které jsou lineárními datovými strukturami. Strom může být prázdný bez uzlů nebo strom je struktura skládající se z jednoho uzlu zvaného root a nulového nebo jednoho nebo více podstromů.

Kreslení stromů

Stromy jsou často kresleny v rovině. Uspořádané stromy mohou být v rovině zastoupeny v podstatě jedinečně, a proto se nazývají platany, takto: pokud jeden zafixuje konvenční pořadí (řekněme proti směru hodinových ručiček) a uspořádá podřízené uzly v tomto pořadí (první příchozí nadřazená hrana, pak první podřízená hrana atd.), získá se vložení stromu do roviny, jedinečné až do okolní izotopy. Naopak takové vložení určuje uspořádání podřízených uzlů.

Pokud někdo umístí kořen nahoře (rodiče nad dětmi, jako v a rodokmen ) a umístí všechny uzly, které jsou v dané vzdálenosti od kořene (z hlediska počtu hran: „úroveň“ stromu) na danou vodorovnou čáru, získá se standardní výkres stromu. Vzhledem k binárnímu stromu je první dítě vlevo („levý uzel“) a druhé dítě vpravo („pravý uzel“).

Běžné operace

• Výčet všech položek
• Výčet části stromu
• Hledání položky
• Přidání nové položky na určité místo ve stromu
• Odstranění položky
• Prořezávání: Odstranění celé části stromu
• Roubování: Přidání celé sekce do stromu
• Nalezení kořene pro jakýkoli uzel
• Nalezení nejnižší společný předek dvou uzlů

Traverz a metody vyhledávání

Krokování mezi položkami stromu pomocí spojení mezi rodiči a dětmi se nazývá chůze po stromu, a akce je Procházka stromu. Často může být provedena operace, když ukazatel dorazí na konkrétní uzel. Procházka, při které se každý nadřazený uzel prochází, než se jeho děti nazývají a předobjednávka Procházka; procházka, při které se děti procházejí dříve, než se projdou jejich rodiče, se nazývá a na objednávku Procházka; procházka, při které se prochází levým podstromem uzlu, poté samotným uzlem a nakonec jeho pravým podstromem, se nazývá v pořádku traverz. (Tento poslední scénář, odkazující na přesně dva podstromy, levý podstrom a pravý podstrom, předpokládá konkrétně binární strom.) A pořadí na úrovni chůze efektivně provádí a vyhledávání na šířku přes celý strom; uzly jsou procházeny úrovní po úrovni, kde je nejprve navštíven kořenový uzel, poté jeho přímé podřízené uzly a jejich sourozence, následované uzly jeho vnouče a jejich sourozenci atd., dokud nebudou překročeny všechny uzly ve stromu.

Zastoupení

Existuje mnoho různých způsobů, jak reprezentovat stromy; společné reprezentace představují uzly jako dynamicky přiděleno záznamy s ukazateli na jejich děti, jejich rodiče nebo obojí, nebo jako položky v pole, přičemž vztahy mezi nimi jsou určeny jejich polohami v poli (např. binární hromada ).

Binární strom lze skutečně implementovat jako seznam seznamů (seznam, kde jsou hodnoty seznamy): vedoucí seznamu (hodnota prvního členu) je levé dítě (podstrom), zatímco ocas (seznam druhého a následujících termínů) je správné dítě (podstrom). To lze upravit tak, aby umožňovalo hodnoty, stejně jako v Lispu S-výrazy, kde hlava (hodnota prvního členu) je hodnota uzlu, hlava ocasu (hodnota druhého členu) je levé dítě a ocas ocasu (seznam třetího a následujících členů) je pravý dítě.

Obecně uzel ve stromu nebude mít ukazatele na své rodiče, ale tyto informace lze zahrnout (rozšíření datové struktury tak, aby zahrnovaly také ukazatel na nadřazeného) nebo uložit samostatně. Alternativně mohou být vzestupné odkazy zahrnuty v datech podřízeného uzlu, jako v a závitový binární strom.

Zobecnění

Digrafy

Pokud jsou hrany (do podřízených uzlů) považovány za odkazy, pak je strom zvláštním případem digrafu a datovou strukturu stromu lze zobecnit tak, aby představovala řízené grafy odstraněním omezení, která může mít uzel maximálně u jednoho rodiče, a že nejsou povoleny žádné cykly. Hrany jsou stále abstraktně považovány za dvojice uzlů, nicméně termíny rodič a dítě jsou obvykle nahrazeny odlišnou terminologií (například zdroj a cílová). Odlišný implementační strategie existují: digraf může být reprezentován stejnou místní datovou strukturou jako strom (uzel s hodnotou a seznamem podřízených), za předpokladu, že „seznam podřízených“ je seznam odkazů, nebo globálně takovými strukturami jako seznamy sousedství.

v teorie grafů, a strom je připojená acyklická skupina graf; pokud není uvedeno jinak, v teorii grafů se stromy a grafy považují za neorientované. Mezi takovými stromy a stromy jako datovou strukturou neexistuje vzájemná korespondence. Můžeme vzít libovolný neorientovaný strom, libovolně vybrat jeden z jeho vrcholy jako vykořenit, aby všechny jeho hrany směřovaly tak, že budou směřovat od kořenového uzlu - vytvoří se stromovost - a přiřadit objednávku všem uzlům. Výsledek odpovídá stromové datové struktuře. Výběr jiného kořene nebo jiné řazení vytvoří jiný.

Vzhledem k tomu, že uzel ve stromu definuje jeho podřízený les (sjednocení podstromů daných všemi podřízenými nebo ekvivalentní převzetí podstromu samotného uzlu a vymazání kořene). Stejně jako podstromy jsou přirozené pro rekurzi (jako při hledání v hloubce), jsou lesy přirozené korekční (jako při vyhledávání na šířku).

Přes vzájemná rekurze, les lze definovat jako seznam stromů (představovaných kořenovými uzly), kde uzel (stromu) sestává z hodnoty a lesa (jeho podřízených):

f: [n [1], ..., n [k]] n: v f

Datový typ versus datová struktura

Existuje rozdíl mezi stromem jako abstraktním datovým typem a jako konkrétní datovou strukturou, analogicky k rozdílu mezi a seznam a a spojový seznam.

Jako datový typ má strom hodnotu a děti a děti jsou samy stromy; hodnota a podřízené prvky stromu jsou interpretovány jako hodnota kořenového uzlu a podstromů podřízených kořenového uzlu. Chcete-li povolit konečné stromy, musíte buď povolit, aby byl seznam dětí prázdný (v takovém případě může být vyžadováno, aby stromy byly neprázdné, místo toho byl „prázdný strom“ reprezentován lesem s nulovými stromy), nebo umožněte stromům být prázdné, v takovém případě může mít seznam dětí pevnou velikost (větvící faktor, zejména 2 nebo „binární“), pokud je to požadováno.

Jako datová struktura je propojený strom skupina uzly, kde každý uzel má hodnotu a seznam Reference do ostatních uzlů (jejích podřízených). Existuje také požadavek, aby žádné dva „sestupné“ odkazy neukazovaly na stejný uzel. V praxi uzly ve stromu běžně zahrnují i ​​další data, například další / předchozí odkazy, odkazy na jejich nadřazené uzly nebo téměř cokoli jiného.

Z důvodu použití Reference stromům v propojené stromové datové struktuře jsou stromy často diskutovány implicitně za předpokladu, že jsou reprezentovány odkazy na kořenový uzel, protože tak se často implementují. Například místo prázdného stromu může mít nulový odkaz: strom je vždy neprázdný, ale odkaz na strom může mít nulovou hodnotu.

Rekurzivní

Rekurzivně je jako datový typ definován strom jako hodnota (nějakého datového typu, případně prázdná), společně se seznamem stromů (případně prázdný seznam), podstromů jejích podřízených; symbolicky:

t: v [t [1], ..., t [k]]

(Strom t se skládá z hodnoty proti a seznam dalších stromů.)

Elegantněji prostřednictvím vzájemná rekurze, jehož jedním z nejzákladnějších příkladů je strom, lze definovat jako les (seznam stromů), kde se strom skládá z hodnoty a lesa (podstromů jeho podřízených):

f: [t [1], ..., t [k]]

t: v f

Všimněte si, že tato definice je z hlediska hodnot a je vhodná v funkční jazyky (předpokládá se referenční průhlednost ); různé stromy nemají žádné spojení, protože jsou to jednoduše seznamy hodnot.

Jako datovou strukturu je strom definován jako uzel (kořen), který sám o sobě sestává z hodnoty (nějakého datového typu, případně prázdné), spolu se seznamem odkazů na jiné uzly (seznam možná prázdný, odkazy případně null ); symbolicky:

n: v [& n [1], ..., & n [k]]

(Uzel n se skládá z hodnoty proti a seznam odkazů na další uzly.)

Tato datová struktura definuje směrovaný graf,^[b] a aby to byl strom, je třeba přidat podmínku jeho globální struktury (jeho topologie), a to, že nanejvýš jeden odkaz může ukazovat na jakýkoli daný uzel (uzel má nanejvýš jednoho nadřazeného) a žádný uzel ve stromu přejděte na kořen. Ve skutečnosti musí mít každý uzel (jiný než root) přesně jednoho rodiče a root nesmí mít žádné rodiče.

Ve skutečnosti, vzhledem k seznamu uzlů a pro každý uzel seznam odkazů na jeho podřízené prvky, nelze určit, zda je tato struktura stromem nebo ne, aniž by analyzoval její globální strukturu a že je ve skutečnosti topologicky stromem, jak je definováno níže.

Teorie typů

Jako abstraktní datový typ, abstraktní typ stromu T s hodnotami nějakého typu E je definován pomocí abstraktního typu lesa F (seznam stromů), podle funkcí:

hodnota: T → E

děti: T → F

nula: () → F

uzel: E × F → T

s axiomy:

hodnota (uzel (E, F)) = E

děti (uzel (E, F)) = F

Ve smyslu teorie typů, strom je indukční typ definované konstruktory nula (prázdný les) a uzel (strom s kořenovým uzlem s danou hodnotou a potomky).

Matematická terminologie

Z celkového pohledu je stromová datová struktura objednaný strom, obvykle s hodnotami připojenými ke každému uzlu. Konkrétně to je (pokud je požadováno, aby nebylo prázdné):

• A zakořeněný strom se směrem „od kořene“ (užší termín je „stromovost "), význam:
  • A řízený graf,
  • jehož podkladové neorientovaný graf je strom (libovolné dva vrcholy jsou spojeny přesně jednou jednoduchou cestou),
  • s rozlišujícím kořenem (jeden vrchol je označen jako kořen),
  • který určuje směr na okrajích (šipky směřují od kořene; vzhledem k hraně se uzel, ze kterého hrana ukazuje, nazývá rodič a uzel, na který hrana ukazuje, se nazývá dítě),

dohromady s:

• uspořádání na podřízených uzlech daného uzlu a
• hodnotu (nějakého datového typu) v každém uzlu.

Stromy mají často pevné (přesněji ohraničené) větvící faktor (překonat ), zejména vždy s dvěma podřízenými uzly (tedy pravděpodobně prázdnými) nejvíce dva neprázdný podřízené uzly), tedy „binární strom“.

Povolení prázdných stromů činí některé definice jednoduššími, některé komplikovanějšími: kořenový strom musí být neprázdný, a proto, pokud jsou prázdné stromy povoleny, výše uvedená definice se místo toho stane „prázdným stromem nebo kořenovým stromem takovým ...“. Na druhou stranu prázdné stromy zjednodušují definování fixního faktoru větvení: s povolenými prázdnými stromy je binární strom strom, takže každý uzel má přesně dvě děti, z nichž každý je strom (případně prázdný). Kompletní sady operací ve stromu musí zahrnovat operaci vidlice.

Matematická definice

Tato sekce může obsahovat nadměrné množství složitých detailů, které mohou zajímat pouze konkrétní publikum. Pomozte prosím odstartovat nebo přemístění veškeré relevantní informace a odstranění nadměrných podrobností, které mohou být proti Zásady začlenění Wikipedie. (Srpna 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Neuspořádaný strom

Matematicky, an neuspořádaný strom^[2] (nebo „algebraický strom“)^[3] lze definovat jako algebraická struktura (X, rodič) kde X je neprázdná sada dopravců uzly a rodič je funkce na X který přiřazuje každý uzel X jeho "nadřazený" uzel, rodič(X). Struktura podléhá podmínce, že každý neprázdný subalgebra musí mít totéž pevný bod. To znamená, že musí existovat jedinečný „kořenový“ uzel r, takový, že rodič(r) = r a pro každý uzel X, nějaká iterativní aplikace rodič (rodič (⋯ rodič (X)⋯)) rovná se r.

Existuje několik ekvivalentních definic.

Jako nejbližší alternativu lze definovat neuspořádané stromy jako částečný algebry (X, rodič) které se získají z celkového počtu algeber popsaných výše lettováním rodič(r) být nedefinováno. To je kořen r je jediný uzel, na kterém rodič funkce není definována a pro každý uzel X, kořen je dosažitelný z X v řízený graf (X, rodič). Tato definice je ve skutečnosti shodná s definicí anti-arborescence. The TAoCP kniha používá termín orientovaný strom.^[4]

Rámeček vpravo popisuje částečnou algebru (X, rodič) jako relační struktura (X, ≺). Pokud je (1) nahrazeno

pak se podmínka (2) stane nadbytečnou.

Pomocí této definice lze poskytnout vyhrazenou terminologii pro zobecnění neuspořádaných stromů, které odpovídají odlišným podmnožinám uvedených podmínek:

• (1,2,3) – řízený pseudostrom,
• (3) – řízený pseud les,
• (3,4) - neuspořádaný les (jehož součástí jsou neuspořádané stromy),
• (4) – směrovaný acyklický graf, předpokládal X je konečný,
• (1 ', 4) - acyklický přístupný špičatý graf (potom podmínka (2) platí implicitně).

Další ekvivalentní definice neuspořádaného stromu je definice a set-teoretický strom která je zakořeněná jednotlivě a jejíž výška je nanejvýš ω (strom „konečný-ish“).^[5] To znamená algebraické struktury (X, rodič) jsou ekvivalentní k dílčí objednávky (X, ≤) které mají horní prvek r a jehož každý ředitel naštvaný (aka hlavní filtr ) je konečný řetěz. Abych byl přesný, měli bychom mluvit o inverzní množinově-teoretický strom, protože množinově-teoretická definice obvykle používá opačné uspořádání.

Korespondence mezi (X, rodič) a (X, ≤) je stanovena reflexivní přechodné uzavření / snížení, přičemž redukce vyústila v „částečnou“ verzi bez kořenového cyklu.

Definice stromy v deskriptivní teorii množin (DST) využívá reprezentaci dílčích objednávek (X, ≥) tak jako předpona objednávky mezi konečnými sekvencemi. Ukázalo se, že až izomorfismus existuje vzájemná korespondence mezi (inverzní) stromy DST a dosud definované stromové struktury.

Můžeme odkázat na čtyři ekvivalentní charakterizace jako strom jako algebra, strom jako částečná algebra, strom jako částečná objednávka, a strom jako pořadí předpon. Existuje také pátá ekvivalentní definice - definice a graficky teoreticky zakořeněný strom což je pouze připojená acyklika zakořeněný graf.

Výraz stromů jako (částečné) algebry (nazývané také funkční grafy ) (X, rodič) přímo sleduje implementaci stromových struktur pomocí nadřazené ukazatele. Obvykle se používá částečná verze, ve které kořenový uzel nemá definovaného rodiče. V některých implementacích nebo modelech však i rodič(r) = r je stanovena oběžnost. Pozoruhodné příklady:

• Linux VFS kde "Kořenová dentry má d_parent, který ukazuje na sebe".^[6].
• Koncept instanční strom^[7][8][9]

z objektově orientované programování. V tomto případě je kořenový uzel horní metaclass - jediný třída to je přímá instance sama o sobě.

Všimněte si, že výše uvedená definice připouští nekonečný stromy. To umožňuje popis nekonečných struktur podporovaných některými implementacemi prostřednictvím líné hodnocení. Pozoruhodným příkladem je nekonečný regres z vlastní třídy z Rubín objektový model.^[10] V tomto modelu byl strom vytvořen prostřednictvím nadtřída vazby mezi nekoncovými objekty jsou nekonečné a mají nekonečnou větev (jedna nekonečná větev objektů „šroubovice“ - viz diagram ).

Sourozenecké soupravy

V každém neuspořádaném stromu (X, rodič) existuje rozlišující rozdělit sady X uzlů do sourozenecké sady. Dva non-root uzly X, y patří do stejné sourozenecké sady, pokud rodič(X) = rodič (y). Kořenový uzel r tvoří jedináček sourozenecká sada {r}.^[C] Říká se, že je strom místně konečné nebo konečně větvení pokud je každá z jejích sourozeneckých sad konečná.

Každá dvojice odlišných sourozenců je nesrovnatelný v ≤. To je důvod, proč slovo neuspořádaný se používá v definici. Taková terminologie může být zavádějící, když jsou všechny sourozenecké množiny singletony, tj. Když množina X všech uzlů je úplně objednané (a tudíž dobře uspořádané ) od ≤ V takovém případě bychom mohli mluvit o a jednotlivě větvící se strom namísto.

Používání sady zahrnutí

Jako u každé částečně seřazené množiny, stromové struktury (X, ≤) může být reprezentován pořadí zařazení - od nastavit systémy ve kterém ≤ je shodný s ⊆, indukované zařazení objednat. Zvažte strukturu (U, ℱ) takhle U je neprázdná množina a ℱ je sada podmnožin U tak, aby byly splněny následující podmínky (do Vnořená sada kolekce definice):

1. ∅ ∉ ℱ. (To znamená, (U, ℱ) je hypergraf.)
2. U ∈ ℱ.
3. Pro každého X, Y z ℱ, X ∩ Y ∈ {∅, X, Y}. (To znamená, ℱ je laminární rodina.)^[11]
4. Pro každého X z ℱ, je jich jen konečně mnoho Y z ℱ takhle X ⊆ Y.

Pak struktura (ℱ, ⊆) je neuspořádaný strom, jehož kořen se rovná U. Naopak, pokud (U, ≤) je neuspořádaný strom a ℱ je sada {↓X | X ∈ U} ze všech hlavní ideály z (U, ≤) pak nastavený systém (U, ℱ) splňuje výše uvedené vlastnosti.

Strom jako laminární systém sad (zkopírováno z Vnořený model sady )

Nastavený systémový pohled na stromové struktury poskytuje výchozí sémantický model - ve většině nejpopulárnějších případů představují stromové datové struktury hierarchie omezení. To také nabízí zdůvodnění směru objednávky s kořenem nahoře: Kořenový uzel je a větší kontejner než kterýkoli jiný uzel. Pozoruhodné příklady:

• Struktura adresářů souborového systému. Adresář obsahuje podadresáře.
• Strom DOM. Části dokumentu odpovídající uzlům DOM jsou v dílčí relaci podle stromového pořadí.
• Jediné dědictví v objektově orientovaném programování. Instance třídy je také instancí nadtřídy.
• Hierarchická taxonomie tak jako Deweyova desetinná klasifikace s úseky rostoucí specificity.
• BSP stromy, čtyřkolky, oktávy, R. stromy a další stromové datové struktury používané pro rekurzivní rozdělení prostoru.

Dobře založené stromy

Neuspořádaný strom (X, ≤) je opodstatněný pokud je přísná částečná objednávka < je opodstatněný vztah. Zejména je každý konečný strom opodstatněný. Za předpokladu, že axiom závislé volby strom je opodstatněný, právě když nemá nekonečnou větev.

Dobře založené stromy mohou být definováno rekurzivně - formováním stromů z nesouvislého spojení menších stromů. Pro přesnou definici předpokládejme, že X je sada uzlů. Za použití reflexivita částečných objednávek můžeme identifikovat jakýkoli strom (Y, ≤) na podmnožinu X v částečném pořadí (≤) - podmnožina X × X. Sada ℛ všech vztahů R které tvoří dobře založený strom (Y, R) na podmnožinu Y z X je definována po etapách ℛ_i, aby ℛ = ⋃ {ℛ_i | i je pořadové číslo}. Pro každého pořadové číslo i, nechť R patří k i-tá fáze ℛ_i kdyby a jen kdyby R je rovný

⋃ℱ ∪ ((dom (⋃ℱ) ∪ {X}) × {X})

kde ℱ je podmnožinou ⋃ {ℛ_k | k < i} takové, že prvky ℱ jsou párově disjunktní a X je uzel, který nepatří do dom (⋃ℱ). (Používáme dom (S) označit doména vztahu S.) Všimněte si, že nejnižší stupeň ℛ₀ sestává z jednouzlových stromů {(X,X)} protože pouze prázdné ℱ je možné. V každé fázi (případně) nové stromy R jsou postaveny lesem ⋃ℱ s komponenty ℱ z nižších stupňů a připojení nového kořene X na vrcholu ⋃ℱ.

Na rozdíl od stromu výška což je maximálně ω, hodnost fundovaných stromů je neomezené,^[12] zobrazit vlastnosti „odvíjející se ".

Použití rekurzivních párů

Ve výpočtech je běžným způsobem, jak definovat fundované stromy, rekurzivní uspořádané páry(F, X): strom je les F společně s „čerstvým“ uzlem X.^[13] A les F zase je možná prázdná sada stromů s párově disjunktními sadami uzlů. Pro přesnou definici postupujte podobně jako při konstrukci jména používá se v množinově-teoretické technice vynucení. Nechat X být množinou uzlů. V nástavba přes X, definovat množiny T, ℱ stromů a lesů a mapa uzly: T → ℘(X) přiřazení každého stromu t základní sadu uzlů tak, aby:

(stromy přes X)		t ∈ T	↔	t je pár (F, X) z ℱ × X takové, že pro všechny s ∈ F, X ∉ uzly (s),
(lesy nad X)		F ∈ ℱ	↔	F je podmnožinou T tak, že pro každého s,t ∈ F, s ≠ t, uzly (s) ∩ uzly (t) = ∅ }},
(uzly stromů)		y ∈ uzly (t)	↔	t = (F, X) ∈ T a buď y = X nebo y ∈ uzly (s) pro některé s ∈ F }}.

Obvody ve výše uvedených podmínkách lze eliminovat stratifikací každého z nich T, ℱ a uzly do fází jako v předchozí podsekci. Následně definujte vztah „podstromu“ ≤ na T jako reflexivní přechodné uzavření vztahu „okamžitý podstrom“ ≺ definováno mezi stromy pomocí

s ≺ t

↔

s ∈ π1(t)

kde π₁(t) je projekce z t na první souřadnici; tj. je to les F takhle t = (F, X) pro některé X ∈ X. To lze pozorovat (T, ≤) je multitree: pro každého t ∈ T, hlavní ideál ↓t objednáno někým ≤ je fundovaný strom jako částečná objednávka. Navíc pro každý strom t ∈ T, jeho struktura "uzlů" (uzly (t), ≤_t) darováno X ≤_t y jen tehdy, jsou-li tam lesy F, G ∈ ℱ takové, že oba (F, X) a (G, y) jsou podstromy t a (F, X) ≤ (G, y).

Pomocí šipek

Další formalizace i zobecnění neuspořádaných stromů lze získat pomocí reifying páry uzlů rodič-dítě. Každý takto uspořádaný pár lze považovat za abstraktní entitu - „šipku“. Výsledkem je a multidigraf (X, A, s, t) kde X je sada uzlů, A je sada šipky, a s a t jsou funkce od A na X přiřazení každé šipky jeho zdroj a cílová, resp. Struktura podléhá následujícím podmínkám:

1. (A, s ○ t^–1) je neuspořádaný strom jako úplná algebra.
2. The t mapa je a bijekce mezi šipkami a uzly.

V (1) má být symbol kompozice ○ interpretován zleva doprava. Podmínka říká, že inverzní posloupnost šipek^[d] je celková mapa od dítěte k rodiči. Nechte tuto nadřazenou mapu mezi šipkami označit p, tj. p = s ○ t⁻¹. Pak také máme s = p ○ t, tedy multidigraf vyhovující (1,2) lze také axiomatizovat jako (X, A, p, t)s nadřazenou mapou p namísto s jako definiční složka. Všimněte si, že kořenová šipka je nutně smyčka, tj. Její zdroj a cíl se shodují.

Důležité zobecnění výše uvedené struktury je zajištěno povolením cílové mapy t být více ku jedné. To znamená, že (2) je oslaben na

(2 ') t mapa je surjektivní - každý uzel je terčem nějaké šipky.

Podmínka (1) tvrdí, že stejný cíl smí mít pouze listové šipky. Toto je omezení z t do rozsah z p je stále injekční.

Multidigrafy vyhovující (1,2 ') lze nazvat "stromy šípů" - jejich vlastnosti stromu jsou uloženy spíše na šipkách než na uzlech. Tyto struktury lze považovat za nejzásadnější abstrakci linuxového VFS, protože odrážejí pevnou strukturu souborových systémů. Uzly jsou volány inody, šipky jsou dentries (nebo pevné odkazy ). Mateřská a cílová mapa p a t jsou příslušně reprezentovány d_parent a d_inode pole ve struktuře dat dentry.^[14] Každému inodu je přiřazen pevný typ souboru, z nichž adresář typ hraje zvláštní roli „navržených rodičů“:

Použití přerušovaného stylu pro první polovinu kořenové smyčky naznačuje, že podobně jako nadřazená mapa existuje částečný verze pro zdrojovou mapu s ve kterém je zdroj kořenové šipky nedefinovaný. Tato varianta se používá pro další zobecnění, viz #Použití cest v multidigrafu.

Použití cest v digrafu

Neuspořádané stromy přirozeně vznikají „rozvinutím“ přístupné špičaté grafy.^[15]

Nechat ℛ = (X, R, r) být špičatá relační struktura, tj. takové, že X je sada uzlů, R je vztah mezi uzly (podmnožina X × X), a r je rozlišující "kořenový" uzel. Předpokládejme dále ℛ je přístupné, což znamená, že X rovná se preimage z {r} pod reflexivním přechodným uzávěrem Ra nazvat takovou strukturu přístupný špičatý graf nebo apg ve zkratce. (⁎) Pak lze odvodit další apg ℛ '= (X', R', r') - odvíjející se z ℛ - jak následuje:

• X' je sada obrácených cesty na r, tj. množina neprázdných konečných sekvencí p uzlů (prvky X) tak, že a) po sobě jdoucí členové p jsou inverzní R- související a (b) první člen p je kořen r,
• R ' je vztah mezi cestami z X' takové cesty p a q jsou R '- související, pokud a jen pokud p = q ⁎ [X] pro nějaký uzel X (tj. q je maximální řád předpona z p„prasklo " p), a
• r ' je sekvence jednoho prvku [r].

Zdá se, že struktura (X', R') je neuspořádaný strom ve verzi "částečné algebry": R ' je částečná mapa, která souvisí s každým jiným než kořenovým prvkem X' na jeho rodiče vyskakováním cesty. Kořenový prvek je samozřejmě r '. Kromě toho jsou splněny následující vlastnosti:

• ℛ je izomorfní vzhledem k jeho vývoji ℛ ' kdyby a jen kdyby ℛ je strom (⁑). (Rozvíjení je zejména idempotentní, až do izomorfismu.)
• Rozvíjení zachovává opodstatněnost: Pokud R je opodstatněná, pak také je R '.
• Rozvíjení zachovává hodnost: Pokud R je potom opodstatněný R a R ' shodovat se.

Poznámky:

(⁎) Vytvořit shodu mezi R a rodič mapa, používá uvedená definice obráceně přístupnost: r je dosažitelný z libovolného uzlu. V původní definici by P. Aczel^[15], každý uzel je dosažitelný z r (tedy místo slova „preimage“ platí slovo „image“).^[E]

(⁑) Implicitně jsme zavedli definici neuspořádaných stromů jako apgs: zavolej apg ℛ = (X, R, r) A strom pokud redukce (X, R) je neuspořádaný strom jako částečná algebra. To lze přeložit jako: Každý uzel je přístupný přesně jednou cestou.

Použití cest v multidigrafu

Jak ukazuje příklad pevné struktury souborových systémů, umožňuje to mnoho datových struktur ve výpočetní technice násobek vazby mezi uzly. Proto, aby se řádně projevil výskyt neuspořádaných stromů mezi datovými strukturami, je nutné zobecnit přístupné špičaté grafy na multidigraf nastavení. Pro zjednodušení terminologie používáme tento výraz toulec což je zavedené synonymum pro „multidigraf“.

Nechť přístupný špičatý toulec nebo apq zkráceně lze definovat jako strukturu

ℳ = (X, A, s, t)

kde

X je sada uzly,

A je sada šipky,

s je částečný funkce od A na X (dále jen zdroj mapa) a

t je celková funkce od A na X (dále jen cílová mapa).

Tím pádem, ℳ je „částečný multidigraf“.

Struktura podléhá následujícím podmínkám:

1. Existuje právě jedna „kořenová“ šipka, A_r, jehož zdroj s(A_r) není definováno.
2. Každý uzel X ∈ X je dosažitelný přes konečnou sekvenci po sobě jdoucích šipek počínaje kořenovou šipkou A_r.

ℳ se říká, že je strom pokud cílová mapa t je bijekce mezi šipkami a uzly odvíjející se z ℳ je tvořen sekvencemi uvedenými v bodě (2) - kterými jsou cesty přístupnosti (srov. Path algebra ). Jako apq lze rozvinutí zapsat jako

ℳ '= (X', A', s', t')

kde

X' je sada přístupových cest,

A' se shoduje s X',

s ' se shoduje s objevováním cesty a

t ' je identita na X'.

Stejně jako u apgs je rozvinutí idempotentní a vždy vede ke stromu.

The základní apg se získá jako struktura

(X, R, t(A_r))

kde

R = {(t(A),s(A)) | A ∈ A {A_r‍}‍}‍.

Výše uvedený diagram ukazuje příklad apq s šipkami 1 + 14. v JavaScript, Krajta nebo Rubín, strukturu lze vytvořit pomocí následujícího (přesně stejného) kódu:

r = {}; r[1] = {}; r[2] = r[1]; r[3] = {}; r[4] = {}; r[1][5]    = {};   r[1][14]    = r[1][5];r[3][7]    = {};   r[3][8]     = r[3][7];  r[3][13] = {};r[4][9]    = r[4]; r[4][10]    = r[4];     r[4][11] = {};r[3][7][6] = r[3]; r[3][7][12] = r[1][5];

Používání jmen

Neuspořádané stromy a jejich zobecnění tvoří podstatu systémy pojmenování Existují dva prominentní příklady pojmenovacích systémů: souborové systémy a (vnořené) asociativní pole. Poskytnuté struktury založené na multidigrafu z předchozích podsekcí anonymní abstrakce pro oba případy. Chcete-li získat možnosti pojmenování, šipky musí být vybaveny jména tak jako identifikátory Název musí být místně jedinečný - v každé sourozenecké sadě šipek^[F] může existovat maximálně jedna šipka označená křestním jménem.

To lze formalizovat jako strukturu

ℰ = (X, Σ, A, s, σ, t)

kde

X je sada uzly,

Σ je sada jména,

A je sada šipky,

s je částečná funkce z A na X,

σ je částečná funkce z A na Σ, a

t je celková funkce od A na X.

Pro šíp A, složky trojitého (s(A), σ(A), t(A)) jsou příslušně Aje zdroj, název a cílová. Struktura podléhá následujícím podmínkám:

1. Redukce (X, A, s, t) je přístupný špičatý toulec (apq), jak je definováno dříve.
2. Funkce názvu σ je nedefinováno pouze pro kořenovou šipku bez zdroje.
3. Funkce názvu σ je injektivní v omezení pro každou sourozeneckou sadu šípů, tj. pro všechny šípy jiných uživatelů než root A, b, pokud s(A) = s(b) a σ(A) = σ(b) pak A = b.

Tuto strukturu lze nazvat a vnořený slovník nebo pojmenované apq. Ve výpočtech jsou takové struktury všudypřítomné. Tabulka výše ukazuje, že šipky lze za sadu považovat za „neregistrované“ A' = {(s(A), σ (A), t(A)) | A ∈ A {A_r}} trojnásobek zdroj-název-cíl. To vede k relační struktuře (X, Σ, A') které lze zobrazit jako relační databáze stůl. Podtrhuje v zdroj a název naznačit primární klíč.

Strukturu lze přeformulovat jako deterministickou označený přechodový systém: X je sada „stavů“, Σ je sada „štítků“, A' je sada „označených přechodů“. (Navíc kořenový uzel r = t(A_r) je „počáteční stav“ a podmínka přístupnosti znamená, že každý stav je dosažitelný z počátečního stavu.)

Diagram vpravo ukazuje vnořený slovník ℰ který má stejný podkladový multidigraf jako příklad v předchozí podsekci. Strukturu lze vytvořit pomocí níže uvedeného kódu. Stejně jako dříve platí pro JavaScript, Python a Ruby přesně stejný kód.

Nejprve, a spodní konstrukce, ℰ₀, je vytvořen jediným přiřazením a doslovný {...} na r. Tato struktura, znázorněná plnými čarami, ješipka strom "(proto se jedná o kostra ). Doslov se zase jeví jako JSON serializace ℰ₀.

Následně jsou zbývající šipky vytvořeny přiřazením již existujících uzlů. Šipky, které způsobují cykly, jsou zobrazeny modře.

r = {"A":{"A":5,„b“:5},"C":{"A":{"w":5},"C":{}},"d":{"w":1.3}}r[„b“]           = r["A"]; r["C"][„b“] = r["C"]["A"]r["C"]["A"][„p“] = r["C"]; r["d"]["E"] = r["d"]["já"] = r["d"]

V systému Linux VFS název funkce σ je reprezentován d_name pole ve struktuře dat dentry.^[14] The ℰ₀ Struktura výše ukazuje korespondenci mezi strukturami reprezentujícími JSON a strukturami pevných odkazů souborových systémů. V obou případech existuje pevná sada předdefinovaných typů „uzlů“, z nichž jeden typ je typ kontejneru, kromě toho, že v JSON existují ve skutečnosti dva takové typy - Objekt a pole. Pokud je ten druhý ignorován (stejně jako rozdíl mezi jednotlivými primitivními datovými typy), pak poskytované abstrakce souborových systémů a dat JSON jsou stejné - oba jsou stromy se šipkami vybavené pojmenováním σ a rozlišení uzlů kontejneru.

Cesty

Funkce pojmenování σ vnořeného slovníku ℰ přirozeně sahá od šipek po cesty šipek. Každá sekvence p = [A₁, ..., A_n] následných šipek je implicitně přiřazeno a cesta (srov. Název cesty ) - sekvence σ(p) = [σ(A₁), ..., σ(A_n)] názvů šipek.^[G]Local uniqueness carries over to arrow paths: different sibling paths have different pathnames. In particular, the root-originating arrow paths are in one-to-one correspondence with their pathnames. This correspondence provides a "symbolic" representation of the unfolding of ℰ via pathnames – the nodes in ℰ are globally identified via a tree of pathnames.

Objednaný strom

The structures introduced in the previous subsection form just the core "hierarchical" part of tree data structures that appear in computing. In most cases, there is also an additional "horizontal" ordering between siblings. v hledat stromy the order is commonly established by the "key" or value associated with each sibling, but in many trees that is not the case. For example, XML documents, lists within JSON files, and many other structures have order that does not depend on the values in the nodes, but is itself data — sorting the paragraphs of a novel alphabetically would lose information.^{[pochybný – diskutovat]}

The correspondent expanze of the previously described tree structures (X, ≤) can be defined by endowing each sibling set with a linear order as follows.^[17][18]

An alternative definition according to Kuboyama^[2] is presented in the next subsection.

An objednaný strom is a structure (X, ≤_PROTI, ≤_S) kde X is a non-empty set of nodes and ≤_PROTI a ≤_S are relations on X volala protiertical (nebo také hierarchický^[2]) order and sibling order, respectively. The structure is subject to the following conditions:

1. (X, ≤_PROTI) is a partial order that is an unordered tree as defined in the previous subsection.
2. (X, ≤_S) is a partial order.
3. Distinct nodes are comparable in <_S if and only if they are siblings:

   (<_S) ∪ (>_S) = ((≺_PROTI) ○ (≻_PROTI)) ∖ id_X.

4. Every node has only finitely many preceding siblings, i.e. every principal ideal of (X, ≤_S) je konečný. (This condition can be omitted in the case of finite trees.)

Conditions (2) and (3) say that (X, ≤_S) is a component-wise linear order, each component being a sibling set. Condition (4) asserts that if a sibling set S is infinite then (S, ≤_S) je izomorfní s (ℕ, ≤), the usual ordering of natural numbers.

Given this, there are three (another) distinguished partial orders which are uniquely given by the following prescriptions:

(<H)	=	(≤PROTI) ○ (<S) ○ (≥PROTI)	(dále jen horizontal order),
(<L⁻)	=	(>PROTI) ∪ (<H)	(dále jen "discordant" linear order),
(<L⁺)	=	(<PROTI) ∪ (<H)	(dále jen "concordant" linear order).

This amounts to a "V-S-H-L^±" system of five partial orders ≤_PROTI, ≤_S, ≤_H, ≤_L⁺, ≤_L⁻ on the same set X of nodes, in which, except for the pair { ≤_S, ≤_H}, any two relations uniquely determine the other three, see the determinacy table.

Notes about notational conventions:

• The relační složení symbol ○ used in this subsection is to be interpreted left-to-right (as ${displaystyle circ _{l}}$).
• Symboly < a ≤ express the přísný a non-strict versions of a partial order.
• Symboly > a ≥ express the converse relations.
• The ≺ symbol is used for the covering relation z ≤ který je bezprostřední version of a partial order.

This yields six versions ≺, <, ≤, ≻, >, ≥ for a single partial order relation. Až na ≺ a ≻, each version uniquely determines the others. Passing from ≺ na <requires that < be transitively reducible. This is always satisfied for all of <_PROTI, <_S a <_H but might not hold for <_L⁺ nebo <_L⁻ -li X je nekonečný.

The partial orders ≤_PROTI a ≤_Hare complementary:

(<_PROTI) ⊎ (>_PROTI) ⊎ (<_H) ⊎ (>_H) = X × X ∖ id_X.

As a consequence, the "concordant" linear order <_L⁺ je lineární prodloužení z <_PROTI. Podobně, <_L⁻ is a linear extension of >_PROTI.

The covering relations ≺_L⁻ a ≺_L⁺ odpovídají předobjednat průchod a post-order traversal, resp. Li x ≺_L⁻ y then, according to whether y has a previous sibling or not, the X node is either the "rightmost" non-strict descendant of the previous sibling of y or, in the latter case, X is the first child of y. Páry ${displaystyle (x, y)}$ of the latter case form the relation (≺_L⁻) ∖ (<_H) which is a partial map that assigns each non-leaf node its první dítě uzel. Podobně, (≻_L⁺) ∖ (>_H) assigns each non-leaf node with finitely many children its poslední child node.

Definition using horizontal order

The Kuboyama's definition of "rooted ordered trees"^[2] makes use of the horizontal order ≤_H as a definitory relation.^[h] (See also Suppes.^[19])

Using the notation and terminology introduced so far, the definition can be expressed as follows.

An objednaný strom is a structure (X, ≤_PROTI, ≤_H) such that conditions (1–5) are satisfied:

1. (X, ≤_PROTI) is a partial order that is an unordered tree. (The protiertical order.)
2. (X, ≤_H) is a partial order. (The horizontal order.)
3. The partial orders ≤_PROTI a ≤_H are complementary: (<_PROTI) ⊎ (>_PROTI) ⊎ (<_H) ⊎ (>_H) = X × X ∖ id_X.

   (That is, pairs of nodes that are nesrovnatelný v (<_PROTI) are comparable in (<_H) and vice versa.)

4. The partial orders ≤_PROTI a ≤_H are "consistent": (<_H) = (≤_PROTI) ○ (<_H) ○ (≥_PROTI).

   (That is, for every nodes X, y takhle X <_H y, all descendants of X must precede all the descendants of y.)

5. Every node has only finitely many preceding siblings. (That is, for every infinite sibling set S, (S, ≤_H) má typ objednávky of the natural numbers.) (Like before, this condition can be omitted in the case of finite trees.)

The sibling order (≤_S) získává (<_S) = (<_H) ∩ ((≺_PROTI) ○ (≻_PROTI)), i.e. two distinct nodes are in sibling order if and only if they are in horizontal order and are siblings.

Determinacy table

The following table shows the determinacy of the "V-S-H-L^±" system. Relational expressions in the table's body are equal to one of <_PROTI, <_S, <_H, <_L⁻nebo <_L⁺ according to the column. It follows that except for the pair { ≤_S, ≤_H}, an ordered tree (X, ...) is uniquely determined by any two of the five relations.

In the last two rows, inf_L⁻(Y) označuje infimum z Y v (X, ≤_L⁻), a sup_L⁺(Y) označuje supremum z Y v (X, ≤_L⁺). In both rows, (≤_S) resp. (≥_S) can be equivalently replaced by the sibling equivalence (≤_S)○(≥_S). In particular, the partition into sibling sets together with either of ≤_L⁻ nebo ≤_L⁺ is also sufficient to determine the ordered tree. The first prescription for ≺_PROTI can be read as: the parent of a non-root node X equals the infimum of the set of all immediate predecessors of siblings of X, where the words "infimum" and "predecessors" are meant with regard to ≤_L⁻. Similarly with the second prescription, just use "supremum", "successors" and ≤_L⁺.

Vztahy ≤_S a ≤_H obviously cannot form a definitory pair. For the simplest example, consider an ordered tree with exactly two nodes – then one cannot tell which of them is the root.

XPath axes

The table on the right shows a correspondence of introduced relations to XPath axes, které se používají v structured document systems to access nodes that bear particular ordering relationships to a starting "context" node. For a context node^[20] X, své osa named by the specifier in the left column is the set of nodes that equals the obraz z {X} under the correspondent relation. Do XPath 2.0, the nodes are "returned" in document order, which is the "discordant" linear order ≤_L⁻. A "concordance" would be achieved, if the vertical order ≤_PROTI was defined oppositely, with the bottom-up direction outwards the root like in set theory in accordance to natural stromy.^[i]

Traversal maps

Below is the list of partial maps that are typically used for ordered tree traversal.^[21] Each map is a distinguished funkční subrelation of ≤_L⁻ or of its opposite.

• ≺_PROTI ... parent-node partial map,
• ≻_S ... previous-sibling partial map,
• ≺_S ... next-sibling partial map,
• (≺_L⁻) ∖ (<_H) ... first-child partial map,
• (≻_L⁺) ∖ (>_H) ... last-child partial map,
• ≻_L⁻ ... previous-node partial map,
• ≺_L⁻ ... next-node partial map.

Generating structure

The traversal maps constitute a partial unary algebra^[22] (X, parent, previousSibling, ..., nextNode) that forms a basis for representing trees as propojené datové struktury. At least conceptually,there are parent links, sibling adjacency links, and first / last child links. This also applies to unordered trees in general, which can be observed on the dentry data structure in the Linux VFS.^[23]

Similarly to the "V-S-H-L^±" system of partial orders, there are pairs of traversal maps that uniquely determine the whole ordered tree structure. Naturally, one such generating structure is (X, _PROTI, _S) which can be transcribed as (X, parent, nextSibling) – the structure of parent and next-sibling links. Another important generating structure is (X, firstChild, nextSibling) známý jako binární strom levého a pravého sourozence. This partial algebra establishes a one-to-one correspondence between binární stromy and ordered trees.

Definition using binary trees

The correspondence to binary trees provides a concise definition of ordered trees as partial algebras.

An objednaný strom is a structure ${displaystyle (X,lc,rs)}$ kde X is a non-empty set of nodes, and lc, rs are partial maps on X volala left-Child a right-sibling, resp. The structure is subject to the following conditions:

1. The partial maps lc a rs are disjoint, i.e. (lc) ∩ (rs) = ∅ .
2. Inverzní z (lc) ∪ (rs) is a partial map p such that the partial algebra (X, p) is an unordered tree.

The partial order structure (X, ≤_PROTI, ≤_S) is obtained as follows:

(≺S)	=	(rs),
(≻PROTI)	=	(lc) ○ (≤S).

Encoding by sequences

Ordered trees can be naturally encoded by finite sequences of natural numbers.^[24][j] Denote ω^⁎ the set of all finite sequences of natural numbers. Then any non-empty subset Ž of ω^⁎ that is closed under taking předpony gives rise to an ordered tree: take the prefix order for ≥_PROTI a lexikografický řád pro ≤_L⁻. Conversely, for an ordered tree T = (X, _PROTI, ≤_L⁻) assign each node X sekvence ${displaystyle w(x)}$ of sibling indices, i.e. the root is assigned the empty sequence and for every non-root node X, nechť w(X) = w(parent(X)) ⁎ [i] kde i is the number of preceding siblings of X a ⁎ je zřetězení operátor. Dát Ž = {w(X) | X ∈ X}. Pak Ž, equipped with the induced orders ≤_PROTI (the inverse of prefix order) and ≤_L⁻ (the lexicographical order), is isomorphic to T.

Per-level ordering

Dashed line indicates the <_B⁻ ordering)

As a possible expansion of the "V-S-H-L^±" system, another distinguished relations between nodes can be defined, based on the tree's level structure. First, let us denote by ∼_E the equivalence relation defined by X ∼_E y kdyby a jen kdyby X a y have the same number of ancestors. This yields a partition of the set of nodes into úrovně L₀, L₁, ... (, L_n) - a coarsement of the partition into sibling sets. Then define relations <_E, <_B⁻ a <_B⁺ podle

${displaystyle { egin{aligned}left(<_{mathrm {E} }ight)&=left(<_{mathrm {H} }ight)cap left(sim _{mathrm {E} }ight)&{ ext{((per) level order),}}left(<_{mathrm {B} ^{-}}ight)&=left(<_{mathrm {E} }ight)cup left(left(sim _{mathrm {E} }ight)circ left(>_{mathrm {V} }ight)ight)&{ ext{(breadth-first order, BFS ordering),}}left(<_{mathrm {B} ^{+}}ight)&=left(<_{mathrm {E} }ight)cup left(left({<}_{mathrm {V} }ight)circ left(sim _{mathrm {E} }ight)ight)&{ ext{(breadth-first post-order).}}end{aligned}}}$

It can be observed that <_E is a strict partial order and <_B⁻ a <_B⁺ are strict total orders. Moreover, there is a similarity between the "V-S-L^±" and "V-E-B^±" systems: <_E is component-wise linear and orthogonal to <_PROTI, <_B⁻ is linear extension of <_E a ze dne >_PROTI, a <_B⁺ is a linear extension of <_E a ze dne <_PROTI.

Viz také

• Stromová struktura
• Strom (teorie grafů)
• Tree (set theory)
• Cardinal tree a Ordinal tree
• Hierarchie (matematika)
• Dialogový strom
• Jediné dědictví
• Generativní gramatika
• Hierarchické shlukování
• Binary space partition tree
• Rekurze
• Fenwick strom

Jiné stromy

• Trie
• Algoritmus Day – Stout – Warren
• Enfilade
• Left child-right sibling binary tree
• Hierarchická časová paměť

Poznámky

Reference

Další čtení

• Donald Knuth. Umění počítačového programování: Fundamental Algorithms, Třetí edice. Addison-Wesley, 1997. ISBN  0-201-89683-4 . Section 2.3: Trees, pp. 308–423.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Úvod do algoritmů, Druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN  0-262-03293-7 . Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253–320.

externí odkazy

• Data Trees as a Means of Presenting Complex Data Analysis by Sally Knipe on August 8, 2013
• Popis z Slovník algoritmů a datových struktur
• CRAN - Package data.tree implementation of a tree data structure in the R programming language
• WormWeb.org: Interactive Visualization of the C. elegans Cell Tree – Visualize the entire cell lineage tree of the nematode C. elegans (javascript)
• Binary Trees by L. Allison