Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Structuri arborescente

c



+ Font mai mare | - Font mai mic



Structuri arborescente



Definitia 3.11

O structura de date arborescenta este o structura de date organizata ca un arbore radacina sau ca un arbore binar.

In prima parte a acestui paragraf se prezinta structura arborescenta radacina si in a doua parte se prezinta structura arborescenta binara.

Una din operatiile frecvente asupra unei structuri arborescente radacina consta in a vizita, intr-o anumita ordine, fiecare nod al structurii arborescente radacina pentru efectuarea unor prelucrari a informatiei atasate nodului. Aceasta operatie se numeste parcurgerea sau traversarea structurii arborescente radacina, care se reduce la parcurgerea arborelui radacina al structurii.

Exista mai multe posibilitati de parcurgere a arborelui radacina: parcurgerea in adancime, parcurgerea in latime si parcurgerea arborelui binar echivalent.

Parcurgerea in adancime se poate realiza in doua moduri: parcurgerea in adancime la stanga si parcurgerea in adancime la dreapta.

Deoarece nu exista deosebiri esentiale intre cele doua moduri de parcurgere in adancime se va prezenta numai parcurgerea in adancime la stanga. Acest mod de parcurgere consta in a ocoli imprejurul arborelui radacina mergand intotdeauna cel mai la stanga posibil. Daca nk este numarul succesorilor nodului k, atunci acest nod este vizitat de nk+1 ori in parcurgerea in adancime la stanga. La fiecare din aceste vizitari poate sa-i corespunda o anumita prelucrare a informatiei asociata nodului k. Se noteaza cu pi prelucrarea informatiei cand nodul k este vizitat a i-a oara, i = 1, , nk+1.

Exemplul 3.4

In figura 3.3 se prezinta parcurgerea in adancime la stanga a unui arbore radacina in care s-a specificat nodul k.


Figura 3.3

Parcurgerea in adancime la stanga a arborilor radacina contine cazuri particulare care corespund la urmatoarea ordine:

ordinea r-prefixata sau r-preordine care se obtine cand numai prelucrarea p1 este efectuata;

ordinea r-postfixata sau r-postordine care se obtine cand numai prelucrarea este efectuata.

Fie G'' = (r , G1 , , Gs ) un subarbore al arborelui radacina G = (r, G1 , , Gt ). Reamintim ca in conformitate cu definitia recursiva, subarborele G poate fi chiar G . Cele doua cazuri particulare de parcurgere a arborilor radacina corespund, referitor la subarborele G , respectiv la urmatoarea ordine:

r-preordinea corespunde la ordinea r , G1 , , Gs

r-preordinea corespunde la ordinea G1 , , Gs , r

Exemplul 3.5

Fie arborele radacina din figura 3.4. Parcurgerea in r-preordine furnizeaza nodurile in ordinea: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Parcurgerea in r-postordine furnizeaza nodurile in ordinea: 3, 4, 2, 5, 7, 8, 10, 9, 6, 1.


Figura 3.4

Parcurgerea in latime a arborilor, nu o prezentam deoarece, in general, nu este utilizata in practica.

Parcurgerea arborilor radacina prin parcurgerea arborelui binar echivalent consta in a asocia arborelui radacina, arborele binar corespunzator si al parcurge pe acesta prin una din metodele care vor fi prezentate in acest paragraf.

Arborele binar asociat arborelui radacina se obtine in modul urmator: pentru fiecare nod intern x cu succesorii s1, , sk se fac urmatoarele doua transformari:

(t1) se construieste un arc (fara sageata) la stanga de la x la primul succesor s1;

(t2) se construieste un arc (fara sageata) la dreapta de la s1 la s2, in continuare de la s2 la s3, , de la sk-1 la sk.

Transformarile t1 si t2 sunt prezentate in figura 3.5.


Figura 3.5

Exemplul 3.6

Arborele binar asociat arborelui radacina din figura 3.4 este prezentat in figura 3.6.


Figura 3.6

Dintre reprezentarile in calculator a unei structuri arborescente organizata ca un arbore radacina se prezinta urmatoarele: reprezentarea standard, reprezentarea cu referinta predecesorului si reprezentarea prin structura arborescenta binara echivalenta.

Reprezentarea standard poate fi realizata in doua moduri: alocand memorie sub forma contigua sau alocand memorie sub forma dinamica.

Reprezentarea standard alocand memorie sub forma contigua este utilizata in cazul in care nu exista posibilitatea de alocare dinamica a memoriei si este realizata prin utilizarea tablourilor. Fie n numarul de noduri ale structurii arborescente. Se utilizeaza matricea

S = (si j), i = 1,2,3; j = 1,,n;

unde:     s1j reprezinta informatia atasata nodului j;

s2j     reprezinta primul succesor al nodului j; daca nodul j nu are succesori atunci s2j = 0;

s3j reprezinta urmatorul frate al nodului j; daca nodul j este ultimul frate atunci s3j = 0.

Exemplul 3.7

Fie structura arborescenta reprezentata in figura 3.4.

Matricea S asociata acestei structuri este urmatoarea:

Reprezentarea standard alocand memorie sub forma dinamica este realizata prin utilizarea pointerilor. Fie ns numarul de succesori ai nodului cu cei mai multi succesori. Fiecarui nod k i se aloca o locatie formata din ns+1 campuri de memorie. Unul atasat informatiei nodului si restul pentru pointerii catre succesori.

Exemplul 3.8


Reprezentarea standard alocand memorie sub forma dinamica a structurii arborescente din figura 3.4 este prezentata in figura 3.7. Daca pentru un camp nu exista succesor se trece *.

Figura 3.7

Reprezentarea cu referinta predecesorului este realizata prin utilizarea tablourilor. Fie n numarul de noduri ale structurii arborescente. Se utilizeaza matricea:

P = (pi j), i = 1, 2; j=1,,n;

unde:     p1j reprezinta informatia atasata nodului j;

p2j reprezinta predecesorul nodului j.

Exemplul 3.9

Pentru structura arborescenta reprezentata in figura 3.3 matricea P este urmatoarea:

Reprezentarea prin structura arborescenta binara echivalenta este realizata prin asocierea structurii arborescente radacina, a structurii arborescente binara echivalenta si aceasta poate fi reprezentata cu una din metodele care vor fi prezentate in acest paragraf.

In continuare, se prezinta parcurgerea si reprezentarea structurilor arborescente binare.

Asemanator cu cazul unei structuri arborescente radacina, parcurgerea unei structuri arborescente binare se reduce la parcurgerea arborelui binar asociat structurii.

Parcurgerea arborilor binari poate fi facuta in adancime sau in latime. Parcurgerea in adancime se poate realiza in urmatoarele doua moduri: la stanga sau la dreapta. La fel ca in cazul arborilor radacina se va prezenta numai parcurgerea in adancime la stanga. Pentru a ilustra aceasta parcurgere transformam arborele binar intr-un arbore binar complet prin adaugarea de noduri si arce fictive in modul urmator:

pentru fiecare nod intern care are un singur succesor se adauga al doilea succesor si arcul respectiv;

pentru fiecare nod terminal se adauga cei doi succesori si arcele respective.

Rezulta ca fiecare nod efectiv k al arborelui binar are numarul succesorilor nk = 2. Conform precizarilor facute la parcurgerea in adancime la stanga a arborilor radacina, rezulta ca fiecare nod efectiv k, este vizitat de nk+1 = 2+1 = 3 ori si corespund prelucrarile p1, p2, p3.



Teorema 3.1

Complexitatea metodei de parcurgere in adancime la stanga a unui arbore binar cu n noduri este (n).

Demonstratie

Fie T(n) timpul necesar pentru parcurgerea in adancime la stanga a unui arbore binar cu n noduri. Se presupune ca exista o constanta reala strict pozitiva c1 astfel incat

T(n) ≤ c1 pentru n = 0, 1 (3.1)

Vom arata prin inductie dupa n ca

T(n) ≤ c2n + c1 pentru n = 2, 3, . (3.2)

unde c2 este o constanta reala strict pozitiva.

Pentru n = 0 afirmatia este adevarata conform relatiei (3.1). Presupunem afirmatia adevarata pentru toti arborii binari cu cel mult n-1 noduri si anume :

T(n-1) ≤ c2 (n-1) + c1    (3.3)

Fie G = (r, G1 , G2 ), un arbore binar cu n noduri. Presupunem ca subarborii binari G1 si G2 au n1 si respectiv n2 noduri. Deoarece nodul radacina r este un arbore binar cu un nod, G1 si G2 sunt arbori binari cu n1 ≤ n-1, n2 ≤ n-1 si 1+n1+n2 = n. Conform relatiilor (3.1) si (3.3) se obtine:

T(n) ≤ c1 + c2n1 + c1 + c2n2 + c1

= c1 + c2n1 + c1 + c2(n-n1-1) + c1

= c2n + c1 - (c2 - 2c1)

Considerand c2 astfel incat c2 - 2c1 ≥ 0 se obtine:

T(n) ≤ c2n + c1

Rezulta ca T(n) O(n). Deoarece fiecare nod este vizitat rezulta ca T(n) Ω(n). Deci T(n) (n).

Parcurgerea in adancime la stanga a arborilor binari contine cazuri particulare cu urmatoarele ordine:

Ordinea prefixata sau preordine, care se obtine cand numai prelucrarea p1 este aplicata .

Ordinea infixata sau inordine, care se obtine cand numai prelucrarea p2 este aplicata .

Ordinea postfixata sau postordine, care se obtine cand numai prelucrarea p3 este aplicata.

Fie G = (r , G1 , G2 ) un subarbore al arborelui binar G = (r, G1 , G2 ). Cele trei cazuri particulare de parcurgere a arborilor binari corespund, referitor la subarborele G , urmatoarelor ordine:

preordinea corespunde la ordinea r , G1 , G2

inordinea corespunde la ordinea G1 , r , G2

postordinea corespunde la ordinea G1 , G2 , r

Exemplul 3.10

Fie arborele binar din figura 3.8.


Figura 3.8

Parcurgerea in preordine furnizeaza nodurile in ordinea:

Parcurgerea in inordine furnizeaza nodurile in ordinea:

Parcurgerea in postordine furnizeaza nodurile in ordinea:

Parcurgerea in latime a arborilor binari corespunde ordinei ierarhice perfecte asociata arborelui.

Exemplul 3.11

Parcurgerea in latime a arborelui binar din figura 3.8 furnizeaza nodurile in ordinea:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

Legatura dintre parcurgerile unui arbore radacina este data de urmatoarea teorema.

Teorema 3.2

Parcurgerea in r - preordine a unui arbore radacina este echivalenta cu parcurgerea in preordine a arborelui binar echivalent. Parcurgerea in r - postordine a unui arbore radacina este echivalenta cu parcurgerea in inordine a arborelui binar echivalent.

Exemplul 3.12

Parcurgerea in r - preordine a arborelui radacina din figura 3.4 si parcurgerea in preordine a arborelui binar echivalent din figura 3.6 furnizeaza nodurile in ordinea :

1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Parcurgerea in r - postordine si inordine a arborilor precizati mai sus furnizeaza nodurile in ordinea :

3, 4, 2, 5, 7, 8, 10, 9, 6, 1.

Asemanator cu cazul unei structuri arborescente radacina, reprezentarea unei structuri arborescente binare poate fi realizata prin mai multe modalitati. In acest paragraf prezentam urmatoarele doua modalitati: reprezentarea standard si reprezentarea secventiala.

Reprezentarea standard poate fi realizata in doua moduri: alocand memorie sub forma contigua si alocand memorie sub forma dinamica.

Reprezentarea standard alocand memorie sub forma contigua consta in definirea matricei S = (sij), i = 1, 2, 3; j = 1,,n,

unde:     s1j reprezinta informatia atasata nodului j;

s2j reprezinta succesorul stang al nodului j; daca nodul j nu are succesor stang atunci s2j=0;

s3j reprezinta succesorul drept al nodului j; daca nodul j nu are succesor drept atunci s3j=0.

Exemplul 3.13

Fie structura arborescenta binara reprezentata in figura 3.8.

Matricea S este urmatoarea:

Reprezentarea standard alocand memorie sub forma dinamica este realizata la fel ca in cazul unei structuri arborescente radacina.

Reprezentarea secventiala poate fi realizata in urmatoarele doua moduri: parcurgand structura arborescenta binara in latime si parcurgand structura arborescenta binara in adancime.

Pentru reprezentarea secventiala parcurgand structura arborescenta binara in latime se considera ca arborele binar asociat este perfect si numerotat in ordine ierarhica perfecta. Aceasta numerotare permite sa folosim numai un tablou L unidimensional cu n elemente. Fiecare element reprezinta informatia atasata nodului respectiv. Restul informatiilor referitoare la un nod k se obtin in modul urmator:

predecesorul lui k este numerotat k/2 daca k ≥ 2 si 0 daca k = 1;

succesorul stang al lui k este numerotat 2k daca 2k ≤ n si 0 daca 2k > n;

succesorul drept al lui k este numerotat 2k+1 daca 2k+1 ≤ n si 0 daca 2k+1 > n.

In acest caz, un nod numerotat cu 0 inseamna ca nodul nu exista.

Exemplul 3.14

Reprezentarea secventiala parcurgand structura arborescenta binara in latime pentru structura din figura 3.8 este urmatoarea:

L = (i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12)

Pentru k=5 avem:

predecesorul nodului 5 este nodul

succesorul stang al nodului 5 este nodul 2*5=10;

succesorul drept al nodului 5 este nodul 2*5+1=11.

Daca arborele binar al structurii nu este perfect, atunci el se completeaza la un arbore binar perfect. Rezulta ca reprezentarea secventiala parcurgand structura arborescenta binara in latime este adecvata pentru structuri ale caror arbori binari sunt perfecti sau apropiati de acestia.

Pentru reprezentarea secventiala parcurgand structura arborescenta binara in adancime se considera parcurgea in inordine. In acest caz reprezentarea necesita un tablou A unidimensional cu n elemente. Fiecare element reprezinta informatia atasata nodului respectiv.

Exemplul 3.15

Reprezentarea secventiala parcurgand structura arborescenta binara in adancime in inordine a structurii din figura 3.8 este urmatoarea:

A = (i8, i4, i9, i2, i10, i5, i11, i1, i12, i6, i3, i7)





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 3267
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved