REPREZENTAREA SI PARCURGEREA ARBORILOR OARECARE

REPREZENTAREA SI PARCURGEREA ARBORILOR OARECARE

1 REPREZENTAREA CU AJUTORUL LEGATURILOR FIU SI FRATE

O prima modalitate de reprezentare a unui arbore orientat oarecare este aceea de a memora pentru fiecare varf i urmatoarele doua informatii:

- FIU (i), reprezentand primul dintre descendentii varfului i (se presupune existenta unei ordini intre descendentii aceluiasi varf) ;

- FRATE (i), reprezentand descendentul tatalui lui i, descendent care urmeaza imediat lui i.

Lipsa fiului, respectiv a fratelui, este marcata prin valoarea 0.

{n acest mod fiecarui arbore i se ataseaza un arbore binar, identificand FIU cu ST si FRATE cu DR. Aceasta corespondenta este biunovoca.

Fig. III.1

Corespondenta descrisa mai sus, reduce parcurgerea arborelui oarecare la parcurgerea arborilor binari atasati. Astfel, pentru exemplul considerat, parcurgerile in preordine , inordine, respectiv postordine arborelui binar atasat furnizeaza varfurile in ordine :

1, 2, 5, 3, 6, 7, 4 (preordine)

5, 2, 6, 7, 3, 4, 1 (inordine)

5, 7, 6, 4, 3, 2, 1 (postordine)

Parcurgerea (varfurilor) unui arbore nu este un scop in sine, ci urmareste prelucarea informatiilor atasate varfurilor intr-o ordine convenabila pentru problema ce necesita aceasta parcurgere. Este insa greu de imaginat o problema pentru care cea mai convenabila parcurgere este cea postordine pentru arborele binar atasat.

Vom prezenta si alte modalitati de parcurgere a arborelui. O a doua modalitate de reprezentare a unui arbore oarecare este de a forma pentru fiecare varf o lista a descendentilor sai. Fie N numarul de varfuri ale arborelui. Vom folosi un vector INF cu N componente pentru a memora informatia continuta in varfuri si un vector CAP cu N componente intregi cu semnificatia :

CAP(i) =0 daca i este varf terminal si CAP(i) = c pozitiv, daca lista descendentilor lui i incepe de la adresa c.

Pentru a memora listele descendentilor varfurilor putem folosi de exemplu o matrice M cu 2 linii si N-1 coloane in care memoram aceste liste, folosind pentru ele alocarea inlantuita. Pentru fiecare i I {1, . , N-1S, M(1, i) reprezinta un descendent al varfului pentru care lista atasata contine coloana i din M iar M(2, i) reprezinta numarul coloanei corespunzatoare urmatorului descendent sau 0 (daca nu exista vreun alt descendent). Pentru exemplul considerat mai sus, avem :

CAP = (5, 3, 6, 0, 0, 0, 0) M =

Se observa ca urmatorul descendent al tatalui varfului M (1, i) este M (1, M (2, i)), bineinteles ca M (2, i) este diferit de 0. Prezentam in continuare alte doua metode de parcurgere a unui arbore oarecare. Ele presupun o ordine bine stabilita intre descendentii oricarui varf.

Parcurgerea in A - preordine consta in a vizita radacina, apoi in ordine subarborii care au ca radacini descendentii sai.

Parcurgerea in A - postordine consta in a vizita subarborii avand ca radacini descendentii radacinii arborelui, apoi radacina arborelui.

Pentru exemplul considerat parcurgerile in A preordine si A postordine furnizeaza varfurile in urmatoarea ordine :

1, 2, 5, 3, 6, 7, 4 (A-preordine)

5, 2, 6, 7, 3, 4, 1 (A - postordine)

Un algoritm pentru parcurgerea in A-postordine pentru un arbore pentru care s-a folosit reprezentarea de mai sus este algoritmul APOST.

procedure APOST(FIU, FRATE, N, RAD)

integer FIU(N), FRATE(N); stack §

i←RAD; § <= Ø

do

while FIU(i)≠0

i=>§; i←FIU(i)

repeat

call VIZIT(i)

while FRATE(i)=0

if §= Ø then return

else i<=§; call VISIT(i)

endif

repeat

i←FRATE(i)

repeat

return

end

Un algoritm pentru parcurgerea in A-preordine a unui arbore pentru care se foloseste a doua reprezentare este procedura APRE, in care stiva § va contine perechi (i, j) unde ori j = 0 ori j reprezinta numarul coloanei din M care contine urmatorul descendent al tatalui varfului i ( adica exista k cu M (1, k) = i, M (2, k) = j).

procedure APRE (CAP, M, N, RAD)

integer CAP (N), M (2, N-1), RAD

stack

i←RAD; j←0; §

do

while CAP (i)≠0 /* adica FIU (i) ≠0 */

call VIZIT(i)

(i, j)=> §; j←M(2, CAP(i)); i←M(1, CAP(i))

repeat

call VIZIT(i)

while j=0: /* adica FRATE(i)=0

if §= Ø then return

else(i, j)

endif

repeat

i←M(1, j); j←M(2, j)

repeat

end

2 REPREZENTAREA ARBORELUI OARECARE CU AJUTORUL LEGATURII TATA

O alta modalitate de reprezentare a unui arbore oarecare este aceea de a memora pentru fiecare varf i tatal sau TATA(i). Aceasta modalitate, evident mai economica decat precedentele, are dezavantajul ca nu permite parcugerea arborelui intr-un mod economic. Exista insa unele probleme in care ea se dovedeste cea mai avantajoasa. Prezentam o astfel de problema, cunoscuta sub numele de problema reuniunii si apartenentei.

Fie T o multime totala. Vom lucra cu submultimi disjuncte ale lui T care formeaza o partitie a lui T. Problemele pe care ni le punem sunt urmatoarele :

1) fiind date doua multimi disjuncte A, B T, sa calculam reuniunea lor A B si sa inlocuim pe A si B prin A B.

2) fiind dat un element t I T, sa determinam submultimea lui T careia ii apartine t.

Vom vedea ca aceste probleme nu sunt artificiale. Ele apar de exemplu la determinatrea arborelui de cost minim. Evident ca modul de elaborare de algoritmi pentru rezolvarea acestor probleme depinde in primul rand de modul de reprezentare al submultimilor lui T. O prima posibilitate este descrisa in continuare.

Daca notam T= {t₁..t_NS, atunci o submultime oarecare A se poate reprezenta ca un vector cu N elemente, numit vectorul caracteristic al multimii A, in care componenta i este 1 daca t_i I A si 0 in caz contrat ; deci vectorul caracteristic apartine multimii {0, 1S^N.

{n privinta apartenentei unui element α la multimea A, timpul necesar este constant daca cunoastem indicele i cu t_i=α sau este de ordinul 0(N), daca nu cunoastem acest indice (in acest caz trebuie parcurs tot vectorul T = (t₁t_N) pentru identificarea lui). Dezavantajul principal este acela ca timpul cerut de reuniune este proportional cu N si nu cu numarul de elemente din cele doua multimi.

Fig. III.2

Un alt mod de reprezentare este acela folosind arbori.

Fie A = {a₁a_mS. Alegem un element din A, de exemplu a₁ ; reprezentam multime prin arborele de mai sus, arbore care are m varfuri si pentru reprezentarea caruia este convenabil sa asociem fiecarui varf i tatal sau TATA (i) si eticheta sa ET (i). Mentionam ca daca A = {1,NS putem elimina informatia continuta in ET, subintelegand ca varful i este asociat elementului i. {n plus, pentru a lucra numai cu multimi disjuncte, opertia de reuniune presupune distrugerea ulterioara a termenilor ei.

Algoritmul corespunzator apare in procedura APART.

procedure APART ( TATA,n,i,j)

integer TATA(n)

j←i

while TATA(j)>0

j←TATA(j)

repeat

return

end

Problema reuniunii a doua multimi (disjuncte) poate fi rezolvata simplu schimband tatal radacinii arborelui corespunzator primei multimi din 0 in radacina arborelui corespunzator celei de a doua multimi. Procedura va fi apelata prin call REUN(a, b) unde a si b sunt radacinile arborilor corespunzatori celor doua multimi.

Dezavantajul acestui mod de a efectua reuniunea are la origine faptul ca operatiile de reuniune si apartenenta se pot efectua alternativ.

Astfel secventa de apelari: call REUN (1,2) ; call APART (1,j) ; call REUN (2,3) ; call APART (1,j) ; .call REUN (n-1,n) conduce la arborele liniar din figura de mai jos:

Fig. III.3

Situatia de mai sus reprezinta cazul cel mai defavorabil si se datoreaza faptului ca structura arborelui este liniara. Ea se poate remedia daca folosim urmatoarea strategie la construirea reuniunii multimilor A si B reprezentate prin arborii de radacina a, respectiv b : daca │A│<│B│, atunci tatal lui a devine b, astfel tatal lui b devine a.

Astfel putem scrie procedura REUN1 pentru reuniunea a doua multimi A, B reprezentate de arborii de radacini a, b.

procedure REUN1 (a, b, TATA, N)

integer TATA(n)

k←TATA(a)+TATA(b)

if TATA(a)>TATA(b) then TATA(a)←b; TATA(b) ←k

else TATA(b) a; TATA(a) k

endif

end )

Observam ca timpul cerut de executia acestei proceduri este constant.

Propozitie. Fiind dat un arbore cu n varfuri construit prin apelari ale procedurii REUN1. Atunci toate varfurile arborelui se afla pe nivele cu numar cel mult

ilog₂ ns + 1.

Facem demostratia prin inductie dupa n. Pentru n = 1 propozitia este evident adevarata. Sa presupunem ca ea este adevarata pentru toti arborii cu cel mult n-1 varfuri si sa consideram un arbore A cu n varfuri. El a luat nastere aplicand procedura REUN1 pentru doi arbori A₁ si A₂ avand respectiv n₁ si n₂ varfuri, cu n₁+n₂ = n.Vom presupune ca n₁ ≤ n/2 deci n₁ ≤ n₂. Fie k, k₁, k₂ nivelele maxime pe care apar varfuri in A, A₁, A₂. Daca n₁<n/2 atunci

k = max( k₁+1, k₂) ≤ max (ilog₂n_is + 2, ilog₂n₂s + 1 ≤ max (ilog₂n/2s + 2, ilog₂ns + 1) = ilog₂ns + 1

Daca n₁ = n/2, atunci k = max(k₁, k₂+1) ≤ max (ilog₂n₁s + 1, ilog₂n₂s + 2 =ilog₂n₂s + 2 = ilog₂n/2s + 2 = ilog₂ns + 1

Propozitie.Fie T(m, n) timpul cerut in cazul cel mai defavorabil de un sir oarecare de m≥n operatia de apartenenta si n-1 operatii de reuniune.Atunci exista K₁,K₂>0 astfel incat K₁m α (m,n) ≤T(m,n) ≤K₂ m α (m,n)

Propozitia arata ca T(m,n) are o comportare aproape liniara.

3 CODUL LUI PRÜFER

Fie A = A₁ un arbore dat

Fie b₁ - varful terminal cu b₁ minim; a₁ - varful (unic) adiacent cu b_1.

Vom elimina varful b₁ si muchia (b_1, a₁)

A₂ este arborele astfel obtinut. Fie b₂ varful terminal care are cel mai mic numar din toate varfurile terminale din A₂; a₂- varf adiacent cu el.

A₃ este arborele obtinut din A₂ eliminand varful b₂ si muchia (b₂, a₂). Se continua in acelasi mod pana la arborele A_N care are un singur varf. Se obtin astfel vectorii (b₁ b_N-1) si (a₁, a₂, . .., a_N-1) precum si arborii A₁, . , A_N-1 in care A_i (1 i N-1) se obtine din A₁ eliminand varfurile b₁ . .., b_i-1 si muchiile (b₁, a₁) . . (b_i-1, a_i-1)

A_N este unicul varf numerotat cu N. Rezulta ca a_N-1 = N deci ne putem margini la a memora {a₁, . . , a_N-2S.

Elementele a₁, . . ., a_N-1 identifica in mod univoc arborele.

Fig. III.4

Se aplica algoritmul lui Prüfer si se obtine :

b = {3, 4, 5, 6, 7, 8, 2, 1, 9S

a = {8, 1, 2, 1, 10, 2, 1, 10, 10S

Prüfer a oferit o solutie constructiva a teoremei lui Cayley prin stabilirea unei corespondente de 1 la 1 intre arbori si setul tuturor vectorilor de n-2 intregi intre 1 si n.

Codul lui Prüfer emite observatia ca pentru orice arbore exista intotdeauna cel putin 2 noduri de grad 1. Prin urmare intr-un arbore T, muchia v este unic determinata si v devine primul simbol in vector. Dupa eliminarea acestui capat si nod, avem un arbore cu n-1 muchii. Se repeta aceasta operatie pana ramane un singur nod si avem n-2 procese intre 1 si n inclusive.

Pentru a reconstrui arborele T pornind de la codul lui Prüfer, notam ca o muchie particulara apare in cod exact odata mai putin decat gradul muchiilor in T. Aceasta permite calcularea gradului tuturor muchiilor lui T si identificarea celui mai mic grad in arbore notat cu u.

Exemplu1 : Codul lui Prüfer pentru un arbore cu 3 noduri ; codul este reprezentat de un numar in intervalul arborelui. Rezultatul este 1, 2, sau 3, fiecare fiind o posibila reprezentare a arborelui. Codul 1 reprezinta arborele cu vectorii (1, 2) si (1, 3) ; codul 2 - arborele cu vectorii (2, 1) si (2, 3) ; codul 3 - arborele cu vectorii (3, 1) si (3, 2).

Exemplul 2 : Codul lui Prüfer pentru un arbore cu 4 noduri este reprezentat ca un vector cu 2 intregi in intevalul 1-4. Fiecare posibilitate de cod de 2 digiti este o reprezentare valida a arborelui.

(2 1) (3 1) (4 1)

Consideram (2 4). Gradul nodurilor 1, 2, 3, 4 este respectiv 1, 2, 1, 2. Cel mai mic nod este nodul 1 cu gradul 1.

De cand nodul 2 este primul terminal, nodul 1 este adiacent nodului 1 formand muchia (1, 2). Reducem gradul nodului 1 la zero si gradul nodului 2 la 1 si continuam.

Acum cel mai mic nod marcat la grad 1 este nodul 2 si acesta trebuie sa fie adiacent nodului 4. Arborele rezultat devine :

Fig. III.5

Codul lui Prüfer - Arbore 'stea'

Codul lui Prüfer este bine prezentat prin reprezentarea unui arbore 'stea'. Numarul aparitiei nodului n cod indica gradul nodului pornind de la structura partiala a arborelui.

Codul lui Prüfer pentru arborele 'stea' neregulat din figura de mai jos este : 4, 2, 1, 1, 1

Fig. III.6

Spre exemplu, pentru un arbore 'stea' cu k ramuri, radacina trebuie sa apara in cod de k-1 ori pentru ca gradul radacinii este k. Nodul ramas apare doar odata in cod si ramura k nu apare deloc.

Spre exemplu pentru un arbore 'star' cu 7 noduri codul Prüfer ar trebuie sa fie vectorul 4 2 1 1 1 , unde nodul 1 are gradul 4, nodurile 2 si 4 au gradul 2 si nodurile 5, 3, 6, 7 sunt noduri frunza. Arborele desfasurat corespunzator acestui cod Prüfer este in figura de mai sus.