Tipul de date abstracte numit arbore.

Search:

Structuri de date abstracte.

Prezentarea structurii de date abstracte numita arbore.

Cuprins:
1. Ce este un tip de date abstracte arbore?.
1.1. Nodurile unui arbore.
1.2. Nodurile radacina (de baza).
1.3. Nodurile curente ale unui arbore.
1.4 Nodurile interne ale unui arbore.
1.5. Sub-arbori.
1.6. Echilibrarea arborilor.
1.7. Reprezentaea arborilor.
1.8. Arborii de tip graf.
1.9. Traversarea arborilor.
1.10. Operatii utilizate fregvent in cadrul arborilor.
1.11. Utilizari fregvente ale arborilor.

1. Prezentarea tipului de date abstracte numit arbore. >>>

In domeniul calculatoarelor, un arbore este structura de date larg folosita ce este conpusa din mai multe noduri inlantuite.

1.1 Nodurile unui arbore. >>>
Un nod ar puta contine o valoarea sau o conditie pentru a reprezenta o alta structura de date sau un alt arbore.Fiecare nod dintr-un arbore poate sa aiba sau sa nu aiba noduri fii, care sunt pusi unul deasupra celuilalt in cadrul arborelui (prin conventie, arborii se maresc prin adaugare de noduri [adica in jos], nu in sus cum cresc arborii din natura).Un nod care este detine un fiu se numeste nodul parinte (sau nodul stramos, sau superior) al acelui fiu.Un nod are cel mult un singur parinte.

1.2. Nodurile radacina (de baza) >>>
Cel mai din varf nod intr-un arbore se numeste nod radacina.Acesta nu are parinti deoarece este primul nod din arbore si de la el se dezvolta arborele prin adaugarea de noi noduri.El este nodul de la care se incep operatiile in arbore (desii unii algoritmi incep cu nodurile curente parcurgand si celelalte noduir pana ajung in varf la nodul radacina).Toate celelalte noduri pot fi extinse de la nodul radacina urmand marginile sau legaturile dintre noduri.(Intr-o definitie formala, fiecare legatura este unica).In diagrame nodul radacina este reprezentat ca fiind extins in adancime.In unii arbori cum sunt arborii binari echilibrati (completi), nodul radacina are proprietati speciale.Fiecare nod din arbore poate fi vazut ca fiind un nod radacina daca contine un sub-arbore propriu.

1.3. Nodurile curente >>>
nodurile care provin de la cel mai apropriat nivel sunt numite noduri curente.Initial ele reprezinta nivelul curent al arborelui si nu detin alte noduri succesoare (fii).

1.4 Nodurile interne. >>>
Un nod intern sau nod interior este orice nod al arborelui care detine noduri succesoare, insa acestea nu sunt noduri curente.

1.5 Sub-arbori. >>>
Un sub-arbore este o extindere a structurii de date numita arbore si poate fi vazut ca un arbore perfect echilibrat.Orice nod din arborele A, impreuna cu nodurile succesoare compune un subarbore pentru arborele A.Sub-arborele are ca nod radacina nodul de la porneste.sub-arborele corespunzator oricarui alt nod este numit sub-arbore propriu (in analogie cu termenul de subset propriou).

1.6. Echilibrarea arborilor >>>
Aici sunt doua tipuri de baza ale arborilor.Intr-un arbore neechilibrat un arbore este un arbore din numai punct de vedere a structurii -- adica, cedand un nod el va dezechilibra ordinea succesorilor nodului luat.Un arbore care impune echilibrarea -- de exemplu prin asignarea unor numere naturale diferite la fiecare nod-fiu al altui nod este numita echilibrare (ordonare),caci nu afecteaza ordinea structurii arborelui, si structuria de date construita in cadrul acestuia este numita structura de data echilibrata (ordonata).Echilibrarea arborilor este o procedura necesara pentru structurara arborilor.Arbori binari de cautare reprezinta un tip de arbori ordonati.

1.7. Reprezentarea arborilor >>>
Sunt mai multe metode de a reprezenta un arbore, cea mai obisnuita metoda de a reprezenta un arbore este prezentarea nodurilor ca fiind inregistrari alocate in structuri ordonate (nu structuri de date ordonate) cu legaturi (pointeri) intre fii (succesori), parinti,sau intre parinti si fii, sau ca fiind termeni intr-un tablou care sunt dispun de informatii unul de spre altul pentru a li se determina pozitia din cadrul tabloului.

1.8. Arbori de tip graf >>>
In teoria grafurilor, un arbore este conectat cu un graf aciclic.Un arbore-radacina este asemenator cu un graf cu un singur varf evidentiat asa cum este nodul radacina al unui arbore.In acest caz, oricare doua conexiuni verticale conectate la margine mostenesc o legatura cu un parinte-fiu.Un graf aciclic cu componente multiplu conectate sau o grupare de arbori radacina cateodata se numeste (in termeni englezesti) "forest" (padure).

1.9. Metode de traversare >>>
Trecerile prin termenii unui arbore, adica printre conectiunile dintre parinti si fii, se numeste parcurgerea arborelui, si actiunea este o parcurgere prin arbore.Adesea o fi abordata operatia de a crea un pointer la un alt nod.O parcurgere in care fiecare nod-parinte este parcurs inainte de nodurile-fii proprii este denumita traversare in preordine, iar traversarea in care nodurile-fii sunt parcurse inaintea nodurilor-parinte se numeste traversare in postordine.

1.10. Operatii utilizare fregvent in cadrul arborilor. >>>

* Enumerearea tuturor termenilor.
* Cautarea unui termen.
* adaugarea unui nou termen la o locatie fixa in arbore.
* Stergerea unui termen.
* Mutarea unei intregi sectiuni a arborelui.
* Adaugarea in arbore a unei zone cocupata in intregime.
* Gasirea radacinii pentru fiecare nod.

1.11. Utilizari fregvente ale arborilor. >>>

* Abordarea ierarhica a datelor.
* Realizarea de informatii usor de cautat.
* Lucreaza cu liste de date sortate.

Inapoi la pagina principala