Arbori binari

ARBORI BINARI

DEFINITII

Un arbore este un graf neorientat, finit, conex si fara cicluri.

Un graf conex si fara cicluri se numeste arbore. In urmatorul desen vom avea un arbore cu 10 varfuri.

Fig. II.1

Se observa ca oricare ar fi muchia arborelui pe care am suprima-o se obtine un graf neconex care are doua componente conexe. De asemenea oricare ar fi perechea de varfuri neadiacente ale unui arbore pe care le-am uni printr-o muchie se creaza un ciclu unic. De exemplu, daca adaugam muchia i3, 4s apare ciclul i2, 3, 4, 2s , daca adaugam muchia i5, 7s apare ciclul i5, 1, 10, 7, 5s etc .

Aceste proprietati au loc pentru orice arbore astfel incat urmatoarele afirmatii sunt echivalente pentru un graf G :

G este un arbore.

G este un graf conex minimal, adica G este conex si daca ii suprimam o muchie oarecare ix, ys. Graful obtinut devine neconex.

G este un graf fara cicluri, maximal, adica G nu contine cicluri si daca x si y sunt doua varfuri neadiacente ale lui G atunci graful obtinut din G prin adaugarea muchiei ix, ys contine un ciclu.

Un graf G contine un arbore partial daca si numai daca G este conex .

Orice arbore cu n >= 2 varfuri contine cel putin 2 varfuri terminale (de gradul 1).

Orice arbore cu n varfuri are n - 1 muchii.

Pentru a verifica daca un graf cu n varfuri este arbore, se verifica daca este conex si are n-1 muchii.

Un arbore binar se poate defini ca un arbore care are un varf numit radacina, al carui grad este 0, unu sau doi. Daca gradul radacinii este 0, arborele binar este format numai din radacina. -1]" v:shapes="_x0000_i1028">

Tot din aceasta organizare mai putem deduce ca tatal unui nod k > 1 este nodul ik/2s, iar fiii nodului k sunt nodurile 2k si 2k+1. Daca 2k = N, atunci nodul 2k+1 nu exista, iar nodul k are un singur fiu; daca 2k > N, atunci nodul k este frunza si nu are nici un fiu. Exemple: tatal nodului 5 este nodul 2, iar fiii sai sunt nodurile 10 si 11. Tatal nodului 6 este nodul 3, iar unicul sau fiu este nodul 12. Tatal nodului 9 este nodul 4, iar fii nu are, fiind frunza in heap.

Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de aflarea a maximului, este aceea ca valoarea oricarui nod este mai mare sau egala cu valoarea oricarui fiu al sau. Dupa cum se vede mai sus, nodul 2 are valoarea 10, iar fiii sai - nodurile 4 si 5 - au valorile 10 si respectiv 7. ^ k} times frac}) = O(N) " v:shapes="_x0000_i1038">. Demonstrarea egalitatii se poate face facand substitutia N=2^h si continuand calculele. Se va obtine tocmai complexitatea O(2^h). Lasam aceasta verificare ca tema cititorului.

Daca eliminam un element din heap, trebuie numai sa refacem structura de heap. {n locul nodului eliminat s-a creat un gol, pe care trebuie sa il umplem cu un alt nod. Care ar putea fi acela? {ntrucat trebuie ca toate nivelele sa fie complet ocupate, cu exceptia ultimului, care poate fi gol numai in partea sa dreapta, rezulta ca singurul nod pe care il putem pune in locul celui eliminat este ultimul din heap. Odata ce l-am pus in gaura facuta, trebuie sa ne asiguram ca acest nod 'de umplutura' nu strica proprietatea de heap. Deci vom verifica: daca nodul pus in loc este mai mare ca tatal sau, vom apela procedura percolate. Altfel vom apela procedura sift, in eventualitate ca nodul este mai mic decat unul din fiii sai. Iata exemplul de mai jos:

Fig. II.13

Sa presupunem ca vrem sa eliminam nodul de valoare 9, aducand in locul lui nodul de valoare X. {nsa X poate fi orice numar mai mic sau egal cu 18. Spre exemplu, X poate fi 16, caz in care va trebui urcat deasupra nodului de valoare 10, sau poate fi 1, caz in care va trebui cernut pana la nivelul frunzelor. Deoarece caderea si urcarea se pot face pe cel mult (log N) nivele, rezulta o complexitate a procedeului de O(log N).

void cut (Heap H, int& N, int K) {

HiKs = HiNs;

--N;

if ((K > 1) && (HiKs > Hifather(K)s)) {

percolate(H, N, K); S

else { sift(H, N, K); S

Inserarea unui element

Daca vrem sa inseram un nou element in heap, lucrurile sunt mult mai simple. Nu avem decat sa-l asezam pe a N+1-a pozitie in vector si apoi sa-l 'promovam' pana la locul potrivit. Din nou, urcarea se poate face pe maxim (log N) nivele, de unde complexitatea logaritmica.

void insert (Heap H, int N, int key) {

Hi++Ns = key;

percolate(H, N, N);

S

Acum, ca am stabilit toate aceste lucruri, ideea algoritmului de sortare vine de la sine. {ncepem prin a construi un heap. Apoi extragem maximul (adica varful heap-ului) si refacem heap-ul. Cele doua operatii luate la un loc dureaza O(1)+O(log N) = O(log N). Apoi extragem din nou maximul, (care va fi al doilea element ca marime din vector) si refacem din nou heap-ul. Din nou, complexitatea operatiei compuse este O(log N). Daca facem acest lucru de N ori, vom obtine vectorul sortat intr-o complexitate de O(N log N).

Partea cea mai frumoasa a acestui algoritm, la prima vedere destul de mare consumator de memorie, este ca el nu foloseste deloc memorie suplimentara. Iata explicatia: cand heap-ul are N elemente, vom extrage maximul si il vom tine minte undeva in memorie. Pe de alta parte, in locul maximului (adica in radacina arborelui) trebuie adus ultimul element al vectorului, adica HiNs. Dupa aceasta operatie, heap-ul va avea N-1 noduri, al N-lea ramanind liber. Ce alt loc mai inspirat decat acest al N-lea nod ne-am putea dori pentru a stoca maximul? Practic, am interschimbat radacina, adica pe H¹ cu HiNs. Acelasi lucru se face la fiecare pas, tinand cont de micsorarea permanenta a heap-ului.

void heap_sort(Heap H, int N) {

build_heap(H, N); // Sorteaza vectorul.

for (int i = N; i >= 2; --i) {

swap(Hi1s, Hiis);

sift(H, i, 1); S

2.3 PARCURGEREA UNUI ARBORE BINAR FARA MEMORIE SUPLIMENTARA

Exista mai multe posibilitati de parcurgere a arborilor binari. Cele mai utilizate sunt cele cunoscute prin denumirile de parcurgere in inordine, preordine si postordine.

Pentru parcurgerea arborilor binari exista trei tehnici de baza. Daca pentru fiecare varf din arbore vizitam prima data varful respectiv, apoi varfurile din subarborele stang si, in final, subarborele drept, inseamna ca parcurgem arborele in preordine. Daca vizitam subarborele stang, varful respectiv si apoi subarborele drept, atunci parcurgem arborele in inordine, iar daca vizitam prima data subarborele stang, apoi cel drept, apoi varful respectiv, parcurgerea este in postordine. Toate aceste tehnici parcurg arborele de la stanga spre dreapta. Putem parcurge insa arborele si de la dreapta spre stanga, obtinand astfel inca trei moduri de parcurgere.

Fig. II.14

Pentru exemplul considerat in figura, parcurgerea in preordine furnizeaza varfurile in ordinea 1, 2, 3, 4, 5, 6, 7, 8

Parcurgerea in inordine furnizeaza varfurile in ordinea 4, 3, 6, 5, 7, 2, 1, 8

Parcurgerea in postordine conduce la 4, 6, 7, 5, 3, 2, 8, 1

Arborele de sortare poate fi definit ca un arbore binar cu urmatoarele proprietati:

INF(i) INF(j) pentru orice varf j din subarborele stang al varfului i

INF(i) INF(j) pentru orice varf j din subarborele drept al varfului i.

Un exemplu de arbore de sortare este cel din figura de mai jos.

Fig. II.15

Se observa ca parcurgerea in inordine a varfurilor corespunde ordinei crescatoare a informatiilor atasate varfurilor. Deci problema sortarii se poate reduce la alcatuirea unui arbore de sortare pentru care informatiile atasate varfului sunt elementele vectorului ce trebuie sortat. Fiecarei expresii aritmetice in care apar numai operatori binari i se poate atasa in mod natural un arbore binar. Astfel expresiei a/(b+c)-d*e i se ataseaza arborele din figura de mai sus.

Pentru a determina valoarea expresiei aritmetice trebuie sa parcurgem arborele in postordine, vizitarea unui varf neterminal insemnand efectuarea operatiei asociate lui. Pentru a putea efectua operatia indicata de un varf neterminal trebuie sa cunoastem valoarea operanzilor, deci trebuie sa fi parcurs deja subarborii varfului respectiv. Ideea generala a parcurgerii in inordine este continuta in algoritmul general INORDO, prezentat mai jos.

1 procedure INORDO

2 i RAD

3 do

while ST(i) 0 : // mergi spre stanga cat timp se poate

i ST(i)

repeat

call VIZIT(i)

while DR(i) = 0 : // urca pana la primul varf cu descendent drept

do

j i: i itata(i)s

if i=0 then return

end if

until j = idescendentul stang a lui is

call VIZIT(i)

15 repeat

16 i DR(i)

17 repeat

18 end

Vom folosi in afara de variabila i desemnand varful current inca o variabila j care memoreaza in permanenta tatal lui i. Aceasta permite ca legatura varfului j spre descendentul sau i sa poata fi folosita in alt scop. Astfel daca din j am ajuns la i mergand in jos pre stanga, vom memora in ST(j) nu pe i, ci tatal lui j; similar, daca I este descendentul drept a lui j, vom memora in DR(j) tatal lui j. {n acest mod avem in permanenta posibilitatea de a determina cu ajutorul legaturilor drumul ce uneste varful curent i de radacina. Astfel pentru arborele din figura II.4 in momentul in care i=6, vom avea, j=5 si situatia din figura 2.12 a legaturilor ST si DR (vom figura legaturile spre dreapta punctat):

Fig. II.16

Pentru a realiza acest lucru modificam algoritmul INORDO astfel:

Daca mergem in jos spre stanga (linia 5) punem

(j, i, ST(i)) (i, ST(i), j)

Daca mergem in jos spre dreapta (linia 16) punem

(j, i, DR(i)) (i, DR(i), j)

Daca mergem in sus venind din stanga punem

(j, i, ST(j)) (ST(j), j, i)

Daca mergem in sus venind din dreapta punem

(j, i, DR(j)) (DR(j), j, i)

Se observa ca atunci cand mergem in sus, refacem legaturile modificate la mersul in jos. Pentru aceasta trebuie sa stim daca am urcat venind din stanga sau din dreapta, deci trebuie sa rezolvam a doua problema.

O modalitate de rezolvare este aceea de a prevedea pentru fiecare varf i un bit BIT(i) astfel incat daca ajungem in i urcand, sa avem BIT(i) = 0 cand se vine din stanga si BIT(i) = 1 cand se vine din dreapta.

Pentru aceasta initializam BIT(i) 0 si apoi punem BIT(i) 1 atunci cand am ajuns la varful i si coboram spre dreapta. Obtinem     algoritmul INORD2.

procedure INORD2 ( ST, DR, N, RAD)

integer ST(N), DR(N)

for i = 1, N :

BIT(i)

repeat

I RAD ; j RAD

Do

while ST(i)

(j, I, ST(i)) (I, ST(i), j)

repeat

call VIZIT(i)

while DR(i) = 0

Do

case i=RAD: return

BIT(j) = 0: (j, I, ST(j)) (ST(j), j, i); exit

Else : (j, i, DR(j)) (DR(j), j, i)

end case

repeat

call VIZIT(i)

repeat

(j, I, DR(i)) (I, DR(i), j); BIT(j)

repeat

end

Pastrand modalitatea din acest algoritm de rezolvare a primei probleme putem rezolva a doua problema si intr-un alt mod, care ne va conduce la un algorim de parcurgere in INORDINE a unui arbore folosind memoria suplimentara constanta ( de ordinul o(1)).

Pentru aceasta sa observam intai ca pentru anumite varfuri i, j cu semificatia de mai sus este clar daca i este descendent stang sau drept al lui j. {ntr-adevar, daca ST(j) = 0 atunci i este sigur descendentul drept al lui j, iar daca DR(j) = 0, atunci este descendentul stang a lui j. Deci problema ramane deschisa doar pentru varfurile j cu ST(j) 0 si DR (j) Pentru acestea am putea forma o stiva cu varfurile de acest tip pentru care s-a folosit deja legatura lor dreapta (adica s-a coborat un pas spre dreapta), varfuri pe care le vom numi varfuri SD. Dar stiva ar ocupa memorie suplimentara variabila !

Se observa ca varfurile SD sunt intercalate in inordine cu varfurile terminale. {ntr-adevar primul varf in inordine este un varf terminal. Pentru a trece de la un varf terminal la urmatorul trebuie sa urcam, sa coboram un pas spre dreapta si apoi sa urcam tot timpul spre stanga. ; s-a parcurs intre timp un singur varf SD si anume cel din care s-a mers in jos spre dreapta. Deci in permanenta numarul varfurilor SD este mai mic sau egal cu numarul varfurilor terminale deja vizitate.

Aceasta observatie permite sa folosim pentru stiva varfurile terminale deja vizitate. {ntr-adevar, putem folosi legatura lor stanga pentru memorarea elementelor din stiva, iar legatura lor dreapta pentru inlantuirea elementelor din stiva (este vorba deci de o stiva cu alocare inlantuita).

Daca ajungem la o pereche de varfuri (i, j) cu ST(j) 0 si DR(j) 0, atunci i va fi descendentul drept al lui j daca si numai daca j apare in varful stivei. Pentru a usura aceasta comparare, ultimul varf de tip SD intalnit nu va fi introdus in stiva, ci va fi memorat intr-o variabila cu numele SD.

Se va folosi variabila VT pentru a memora ultimul varf terminal parcurs. Variabila TOP va memora varful stivei. Se vor reface legaturile varfurilor terminale folosite de stiva, dar ulterior eliberate.

Atunci cand urcam in arbore, trebuie verificat intai daca ST(j) = 0 sau DR(j) = 0. Cum j este viitoarea valoare a lui i, ciclul while cu conditia DR(i) = 0 devine inutil. Se obtine astfel algoritmul INORD3.

procedure INORD 3 (n, ST, DR, RAD)

integer ST(n), DR(n)

i RAD; TOP 0 ; j RAD; SD

do

while ST(i)

(j, I, ST(i)) (I, ST(i), j)

Repeat

Call VIZIT(i)

If DR (i)=0 then

ST i/ *varfurile terminale vor fi folosite pentru stiva */

do

case i=RAD: return / * din radacina nu mai putem urca*/

ST(j)=0: (j, i, DR(j))← (DR(j), j, i)

DR(j)=0: (j, i, ST(j)) ← (ST(j), j, i);call VIZIT(i)

j=SD: (j, i, DR(j)) ← (DR(j), j, i) /* merg in sus venind din dreapta*/

k←TOP; SD ← ST(k); TOP ← DR(k) /*scoate elementul din varful stivei */

ST(k) ←0; DR(k) ←0 /* refa legaturile */

else: (j, i, ST(j))→(ST(j),j i) /*mergi in sus venind din stanga */

ST(VT)←SD; DR(VT) ←TOP; TOP←VT /*introdu i in stiva */

SD←i; exit /*s-a ajuns la un varf i cu DR(i)≠0 */

endcase

repeat

endif

call VIZIT(i)

(j, i, DR(i) ←(i, DR(i),j) /*mergi in jos spre dreapta */

Avantajul acestui algoritm este ca necesita memorie suplimentara constanta. Timpul total este tot de ordinul o(n); algoritmul insa este mai lent decat algoritmul INORD1 din cauza numarului mare de modificari de legaturi.