O structură arborescentă este o modalitate de a reprezenta o structură ierarhică într-un mod grafic.
Se numește structură arborescentă datorită faptului că graficul arată ca un arbore inversat . Din același motiv, ei spun că nodul rădăcină (rădăcină) este în partea de sus, iar frunzele sunt în partea de jos.
În teoria grafurilor, un arbore este un graf aciclic conectat (pentru grafurile nedirecționate) sau un graf aciclic conectat în care cel mult un nod nu are muchii de intrare, iar nodurile rămase au exact un nod de intrare (pentru grafurile direcționate).
Un graf direcționat aciclic fără o condiție strictă de legătură se numește rețea, un graf neconectat al mai multor copaci se numește pădure ..
Rețelele semantice eterogene constau dintr-un set de structuri arborescente .
Fiecare arbore de frunze conține un element care nu are părinte . Acest element se numește „rădăcină” sau „nod rădăcină” . Poate fi considerat primul (sau pornire) nod.
Reversul nu este adevărat în general: structurile de arbore infinite pot avea sau nu noduri rădăcină.
Liniile care leagă elementele sunt numite „ramuri”, iar elementele în sine sunt numite noduri . Nodurile fără copii sunt numite „noduri de frunze” sau „frunze”.
Numele legăturilor dintre noduri sunt denumite conform principiului relațiilor de familie.
În Occident, în domeniul informaticii, sunt folosite în principal doar numele membrilor masculini ai familiei; în rusă, pentru a desemna un nod care este direct legat de nodul părinte și este mai jos în ierarhie, este adesea numit „copil ".
În lingvistică (engleză, de exemplu), dimpotrivă, sunt folosite numele femeilor membrilor familiei. Acest lucru indică o revenire la convenția comună de denumire, sponsorizată de studenții faimosului lingvist american Noam Chomsky . În ciuda acestui fapt, în informatică, denumirile neutre „părinte” și „copil” sunt adesea înlocuite cu cuvintele „tată” și „fiu”, în plus, termenul „unchi” este folosit nu mai puțin activ pentru a se referi la alte noduri care sunt la același nivel cu părintele...
În exemplul de mai sus, „enciclopedia” este părintele „științei” și „culturii”, care sunt, respectiv, „copiii” acesteia. „Arta” și „meșteșugul” sunt frați în raport cu celălalt și copii în raport cu „cultură”.
Structurile arborescente sunt folosite pentru a afișa tot felul de informații din domeniul taxonomiei , cum ar fi arborele genealogic , arborele filogenetic , structura gramaticală a limbii (de exemplu, în engleză, un bun exemplu este schema S → NP VP, adică propoziția (propoziția) este o frază nominală (expresie nominală) și un grup de verbe (expresie verbală), o modalitate de a aranja logic paginile web pe un site și așa mai departe.
Într-o structură arborescentă, poate exista o singură cale de la un punct la altul.
Structurile arborescente sunt utilizate pe scară largă în informatică (vezi Arborele (structura de date) și Comunicarea (inginerie) ).
Pot exista diverse relații semantice între nodurile unei structuri arborescente .
În enciclopediile reale ( Wikipedia ), toate astfel de DS există în antagonism, dacă sistemul de prezentare a acestora nu este gândit separat și în ansamblu.
În structura grupurilor tematice omogene de articole Wikipedia sunt folosite diferite tipuri de legături . Inițial se identifică secțiuni care diferă în momentul apariției obiectelor articolelor (Natura neînsuflețită, Wildlife, Humanity, Technosphere), apoi se folosesc legături între niveluri structurale în cadrul secțiunilor, legături între articole omogene (gen-specie), ultimele în ierarhie se utilizează numărul de articole din grup.
Există multe moduri de a reprezenta grafic structurile arborescente. În marea majoritate a cazurilor, acestea se rezumă la diferite variații sau combinații ale mai multor stiluri de bază:
Descrierile unor metode de bază pot fi găsite în:
| Arborele (structura de date) | |
|---|---|
| Arbori binari | |
| Arbori binari cu auto-echilibrare |
|
| B-copaci |
|
| arbori de prefix |
|
| Partiționarea binară a spațiului | |
| Arbori non-binari |
|
| Despărțirea spațiului |
|
| Alți copaci |
|
| Algoritmi | |