Stromová struktura

V matematice , přesněji v teorii grafů  : strom je strom obsahující určitý vrchol , nazývaný kořen stromu, ze kterého existuje jediná cesta ke všem ostatním vrcholům.

Ve vědě o počítačích tento pojem často označuje pojem stromu teorie grafů. Stromová struktura pak obecně označuje organizaci dat v paměti , v logické a hierarchicky, pomocí algoritmické stromové struktury . Tato organizace zefektivňuje konzultace a zpracování uložených dat. Nejběžnější použití jsou:

Obecná logika stromové struktury se shoduje s relačním modelem SQL: 1 až N a recipročně 1 až 1. Uzel může mít N listů, ale každý list je vlastněn pouze jedním uzlem.

V informatice také označuje komponentu grafického rozhraní, která představuje hierarchický pohled na informace. Každý prvek (často označovaný jako větev nebo uzel) může mít řadu dílčích prvků. Toto je často představováno jako odsazený seznam .

Prvek lze rozložit a odhalit dílčí položky, pokud existují, a sbalit, aby se dílčí položky skryly.

Stromové zobrazení se často objevuje v aplikacích pro správu souborů , kde umožňuje uživateli procházet adresáře v systému souborů . Používá se také k prezentaci hierarchických dat, například dokumentu XML .

Použijte pro správu disků

Na základně stromu je adresář s názvem root. Tento adresář může obsahovat soubory a adresáře, které samy mohou obsahovat totéž.

Pokud jsou soubory a adresáře umístěny konzistentně, je vyhledávání souborů relativně snadné a rychlé.

Linearizace

Protože stromová struktura je často reprezentována ve formě grafického stromu a protože klasické systémy psaní jsou lineární, používají se a koexistují různé typy reprezentace, v závislosti na použité metodě procházení a oblasti použití.

Arities

Jednoduše řečeno, arita označuje počet argumentů nebo dětí užitečných nebo nezbytných pro funkci nebo rodiče. V 10 + 20 tedy doplněk (+) potřebuje člen nalevo (10), potom další napravo (20), jeho arrita je tedy 2. V abs (mavar) potřebuje absolutní hodnota pouze jeden argument (mavar ), jeho arity je 1. V Prologu klauze pere (alain, bernard). má arity 2, protože vztah „otce“ vyžaduje rodiče a nevyhnutelně dítě.

Arity lze opravit, protože může být variabilní. Takže operátor * má ve většině počítačových jazyků pevnou arititu na 2, pro vyjádření výpočtu napíšeme 2 * 3. Na druhou stranu v Lispu můžeme psát (* 2 3 4), abychom vyjádřili 2 * 3 * 4 nebo jinak (* 2 3 4 5), což je variabilní arity.

Druhy tras

Předpona

V tomto mechanismu je nejprve kladen rodič, poté následují jeho děti. Objednávka / objednávka je vpředu, další prvky pak. Viz také jazykový příklad VSO . Příklad: + 2 3

Tato notace je pro člověka snadno pochopitelná a snadno se programuje.

Infix

V tomto mechanismu je rodič vložen mezi své děti, jako je tomu například v matematice: 2 + 3.

Velkým problémem infixu je nejednoznačnost a často se musíme uchýlit k závorkám. Mělo by se tedy 10 + 20 * 30 analyzovat jako (10 + 20) * 30 nebo jako 10+ (20 * 30)? K překonání některých obtíží existuje priorita operátora v dobrém počtu jazyků.

Přípona

Rodič je umístěn za svými dětmi. Tato logika se často používá ve výpočtech ( zásobník , Forth , virtuální stroj Java , Postscript a další): 2 3+

Jazyk neslyšících má syntaxi docela blízkou tomuto typu notace: nastavuje scénu dříve, umisťuje herce a poté označuje akci jako poslední.

Circumfix

Rodič stojí před a za svými dětmi. Může to být stejné slovo (přidat ... přidat), dvě zcela odlišná slova (pro ... další / začátek ... konec) nebo dvě slova, z nichž jedno je zfalšováno na základě druhého (zatímco ... wend / while ... endfully / for ... rof). Nejběžnější symboly obvodových obrysů jsou: (...), [...], {...}, <...>, „...“ a „...“

Hodnocení

Opravená arityVariabilní arity

Poznámky a odkazy

Podívejte se také

Související články