Structuri arborescente

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 n_k este numarul succesorilor nodului k, atunci acest nod este vizitat de n_k+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 p_i prelucrarea informatiei cand nodul k este vizitat a i-a oara, i = 1, , n_k+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 p₁ este efectuata;

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

Fie G'' = (r , G₁ , , G_s ) un subarbore al arborelui radacina G = (r, G₁ , , G_t ). 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 , G₁ , , G_s

r-preordinea corespunde la ordinea G₁ , , G_s , 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 s₁, , s_k se fac urmatoarele doua transformari:

(t₁) se construieste un arc (fara sageata) la stanga de la x la primul succesor s₁;

(t₂) se construieste un arc (fara sageata) la dreapta de la s₁ la s₂, in continuare de la s₂ la s₃, , de la s_k-1 la s_k.

Transformarile t₁ si t₂ 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 = (s_{i j}), i = 1,2,3; j = 1,,n;

unde:     s_1j reprezinta informatia atasata nodului j;

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

s_3j reprezinta urmatorul frate al nodului j; daca nodul j este ultimul frate atunci s_3j = 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 n_s numarul de succesori ai nodului cu cei mai multi succesori. Fiecarui nod k i se aloca o locatie formata din n_s+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 = (p_{i j}), i = 1, 2; j=1,,n;

unde:     p_1j reprezinta informatia atasata nodului j;

p_2j 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 n_k = 2. Conform precizarilor facute la parcurgerea in adancime la stanga a arborilor radacina, rezulta ca fiecare nod efectiv k, este vizitat de n_k+1 = 2+1 = 3 ori si corespund prelucrarile p₁, p₂, p₃.

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 c₁ astfel incat

T(n) ≤ c₁ pentru n = 0, 1 (3.1)

Vom arata prin inductie dupa n ca

T(n) ≤ c₂n + c₁ pentru n = 2, 3, . (3.2)

unde c₂ 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) ≤ c₂ (n-1) + c₁    (3.3)

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

T(n) ≤ c₁ + c₂n₁ + c₁ + c₂n₂ + c₁

= c₁ + c₂n₁ + c₁ + c₂(n-n₁-1) + c₁

= c₂n + c₁ - (c₂ - 2c₁)

Considerand c₂ astfel incat c₂ - 2c₁ ≥ 0 se obtine:

T(n) ≤ c₂n + c₁

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 p₁ este aplicata .

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

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

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

preordinea corespunde la ordinea r , G₁ , G₂

inordinea corespunde la ordinea G₁ , r , G₂

postordinea corespunde la ordinea G₁ , G₂ , 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 = (s_ij), i = 1, 2, 3; j = 1,,n,

unde:     s_1j reprezinta informatia atasata nodului j;

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

s_3j reprezinta succesorul drept al nodului j; daca nodul j nu are succesor drept atunci s_3j=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 = (i₁, i₂, i₃, i₄, i₅, i₆, i₇, i₈, i₉, i₁₀, i₁₁, i₁₂)

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 = (i₈, i₄, i₉, i₂, i₁₀, i₅, i₁₁, i₁, i₁₂, i₆, i₃, i₇)