Arbori binari - Similaritate si echivalenta

Ne ocupam in acest paragraf cu formularea unor definitii precise si cu caracterizarea matematica a unor notiuni intuitive pentru arbori binari, precum notiunea ca doi arbori sa aiba "aceeasi forma" (similaritatea) si notiunea sa aiba "aceeasi forma si acelasi continut" (echivalenta).

Informal, doi arbori binari T si T' se numesc similari daca "au aceeasi forma". Mai precis, putem spune ca exista o bijectie intre nodurile lui T si cele lui T ^' astfel incat daca nodurilor u₁ si u₂ apartinand lui T le corespund nodurile u₁ si u₂' apartinand lui T^', atunci daca u₂ apartine lui stg (u₁) vom avea si u₂' apartine lui stg (u₁'), iar daca daca u₂ apartine lui dr (u₁) vom avea si u₂' apartine lui dr (u₁'). Cu alte cuvinte, relatiile tata-fiu dintre perechi de noduri din T se pastreaza prin bijectie in arborele T^' .

Doi arbori binari sunt echivalenti daca sunt similari si, in plus, nodurile ce se corespund prin bijectie contin aceleasi informatii.

Putem sa dam alte definitii ale relatiilor de similaritate si echivalenta, bazate pe definitia recursiva a arborelui binar, pe care o reamintim:

Definitie T se numeste arbore binar daca:

(a) fie T este vid (T = Ø)

(b) fie T este nevid (T Ø) si deci contine un nod numit radacina, notat root (T), impreuna cu doi arbori binari stg(T) si dr (T), numiti fiul stang, respectiv fiul drept al lui root (T).

Pe baza ei putem defini formal similaritatea si echivalenta dupa cum urmeaza. 

Definitie Doi arbori binari T si T' se numesc similari, si notam aceasta cu TT ^' , daca:

(a)    fie sunt ambii vizi, adica T = Ø si T ' = Ø ;

(b) fie sunt ambii nevizi, adica T Ø si T ' Ø si atunci avem stg (T) stg (T ') (fii stangi ai radacinilor sunt similari) si dr (T) dr (T) fii drepti ai radacinilor sunt similari)

Definitie Doi arbori binari T si T' se numesc echivalenti, si notam aceasta cu T T ^' , daca:

(a) fie sunt ambii vizi, adica T = Ø si T ' = Ø ;

(b) fie sunt ambii nevizi, adica T Ø si T ' Ø si atunci avem info (root (T)=info (root (T ^')) si stg (T) stg (T ^') si dr (T) dr (T ^')

Fie T = u₁ u₂ u_n un arbore binar dat prin lista nodurilor sale la parcurgerea in preordine (RSD). Fiecarui nod u_i ii vom asocia trei valori : info (u_i) reprezentand informatia din nodul u_i si l(u_i) , r(u_i) valorile functiilor l si r in nodul u_i.

Functiile l (de la left) si r (de la right) sunt functii marcaj pentru existenta fiilor stangi, respectivi drepti, definite intr-un nod u dupa cum urmeaza :

l (u) := 1, daca u are fiu stang nevid (adica stg (u) Ø)

0, daca u nu are fiu stang nevid (adica stg (u) = Ø)

Analog, 

r (u) = 1, daca dr (u) Ø

0, daca dr (u) = Ø

Atunci arborele T= u₁ u₂ u_n va fi caracterizat prin valorile celor trei vectori cu n componente, vectorii info , l si r (ultimii doi avand ca valori posibile doar pe 0 si 1).

Sa definim tot pe nodurile unui arbore binar functia f prin

f(u):= l(u)+ r(u)- 1.

Sa observam ca

1, daca l(u)= r(u)= 1 , adica u are doi fii

l(u)= 1 si r(u)= 0

f(u)= 0, daca sau , adica u are un singur fiu

l(u)= 0 si r(u)= 1

-1, daca l(u)= r(u)= 0 , adica u nu are fii

Functia f definita mai sus, asociata cu parcurgerea in preordine a unui arbore binar ne da extrem de multa informatie despre arbore dupa cum vom vedea din rezultatul care urmeaza.

Lema Fie T= u₁ u₂ . u_n un arbore binar parcurs in preordine.

Atunci urmatoarele relatii sunt adevarate :

(i) f(u₁)+ .+ f(u_k) pentru orice kI[1,n)

(ii) f(u₁)+ . + f(u_n)= -1

(iii) Daca f(u₁)=1 atunci exista min= n_l+ 1, unde n_l este numarul de noduri din fiul stang al lui T.

Demonstratie O vom face prin inductie dupa n .

n=1. T are un singur nod T= u₁ deci l(u₁)= r(u₁)= 0, deci f(u₁)= -1 (din cele trei relatii in acest caz nu ramane decat relatia (ii) care se reduce la f(u₁)=-1 pe care tocmai am demonstrat-o adevarata).

Fie n>1. Ipoteza de inductie este ca presupunem lema adevarata pentru orice arbore binar cu m noduri, unde m <n .

Fie acum un n oarecare si T=u₁ u₂ . u_n un arbore binar parcurs in preordine cu n noduri. Avem doar doua valori posibile pentru f(u₁), f(u₁)I ( caci daca f(u₁)= -1 atunci rezulta n=1 , ceea ce contrazice ipoteza n>1)

Sa analizam pe rand cele doua cazuri :

(a) f(u₁)=0 . Rezulta ca u₁ radacina lui T are un singur fiu nevid deci avem

fie (a1) : stg(T)= si dr(T) ceea ce este echivalent cu l(u₁)= 0 si r(u₁)= 1

fie (a2) : stg(T) si dr(T)= ceea ce este echivalent cu l(u₁)=1 si r(u₁)=0

Rationamentul este acelasi pentru oricare din cazurile (a1) sau (a2) .

Presupunem ca suntem in cazul (a1), adica singurul fiu nevid al lui T este cel drept. Atunci dr(T)= u₂ u₃ . u_n reprezinta parcurgerea lui in preordine, dr(T) are n-1 noduri si ii putem aplica ipoteza de inductie obtinand relatiile (i) si (ii) pentru dr(T) :

(i)         f(u₂) + .+ f(u_k) , pentru orice kI[2, n)

(ii)       f(u₂)+ . + f(u_n)=-1

La aceste relatii putem aduna f(u₁) care are valoarea 0 si adaugam si relatia f(u₁)=0 obtinand :

relatiile (i) pentru T :

f(u₁)=0

f(u₁)+ f(u₂)+.+ f(u_k)=f(u₂)+.+ f(u_k) pentru orice kI[2, n)

relatia (ii) pentru T :

f(u₁)+ f(u₂)+ .+ f(u_n)= f(u₂)+ .+ f(u_n)=-1 .

si am incheiat demonstratia in cazul (a) .

(b) f(u₁)=1. Rezulta ca T are ambii fii nevizi. Daca n_l este numarul de noduri din fiul stang al lui T , atunci nodurile de la u₂ la u_n+1 sunt nodurile lui stg(T) parcurs in preordine, iar de la u_n+2 la u_n sunt nodurile lui dr(T) parcurs in preordine. Cu alte cuvinte, din parcurgerea in preordine a lui T obtinem parcurgerile in preordine ale fiilor sai : stg(T)=u₂.u_n+1 si dr(T)= u_n+2.u_n .

Subarborilor stg(T) si dr(T) le putem aplica ipoteza de inductie.

Sa calculam acum sumele partiale din enuntul lemei pentru arborele T si sa le evaluam .

k= 1 f(u₁)= 1> 0

kI[2,n_l] f(u₁)+ f(u₂)+ .+ f(u_k)= 1+ f(u₂)+ .+ f(u_k)> 0

pentru ca f(u₂)+ .+ f(u_k) din relatia (i) pentru stg(T)

k= n_l+1 f(u₁)+ f(u₂)+ . f(u_n+1) = 1+ f(u₂)+ . f(u_n+1)= 1- 1= 0

pentru ca f(u₂)+ . f(u_n+1)=-1 din relatia (ii) pentru stg(T) .

(cu acesta am demonstrat relatia (iii) pentru T) .

kI[n_l+2,n-1]

f(u₁)+ f(u₂)+ .+ f(u_n+1)+ f(u_n+2)+ .+ f(u_k)= f(u_n+2)+ .+ f(u_k)

pentru ca este relatie de tip (i) pentru dr(T)

(cu aceasta am incheiat demonstrarea relatiilor (i) pentru T)

k=n f(u₁)+f(u₂)+.+f(u_n+1)+f(u_n+2)+.+f(u_n)= f(u_n+2)+.+f(u_n)=-1

pentru ca este relatia (ii) pentru dr(T)

(cu acesta am demonstrat si relatia (ii) pentru T).

q.e.d.

Teorema de caracterizare a similaritatii si echivalentei arborilor binari

Teorema Fie T= u₁ u₂ . u_n si T'=u'₁ u'₂ . u'_n' doi arbori binari dati in parcurgerile lor in preordine. Urmatoarele afirmatii sunt adevarate :

(a)   T si T' sunt similari (T ≈T') daca si numai daca avem relatiile

n=n'

(S) l(u_i)=l(u'_i) pentru orice i apartinand intervalului [1, n]

r(u_i)=r(u'_i) pentru orice i apartinand intervalului [1, n]

(b)   T si T' sunt echivalenti (T ^≈T') daca si numai daca avem relatiile

n=n'

(E) l(u_i)=l(u'_i) pentru orice i apartinand intervalului [1, n]

r(u_i)=r(u'_i) pentru orice i apartinand intervalului [1, n]

info(u_i)= info(u'_i) pentru orice i apartinand intervalului [1, n]

Demonstratie Este evident ca e suficient sa demonstram punctul (a), (b) urmand imediat din definitia relatiei de echivalenta.

Vom face demonstratia prin inductie dupa n numarul de noduri ale lui T.

n= 0 Daca T si T' sunt similari, cum T= vom avea si T'= n'= 0, deci n= n' (singura relatie din setul (S) care este de demonstrat in acest caz).

Pentru implicatia in sens contrar, din n=0 si n=n' rezulta n'=0, deci atat T cat si T' sunt vizi, deci similari (primul caz al definitiei).

n>0 Ipoteza de inductie : presupunem, pentru arbori cu m noduri, m<n, ca, daca sunt similari, atunci avem relatiile (S) pentru nodurile lor.

Fie acum T si T' similari, T cu n noduri n>0. Aceasta inseamna ca T deci si T' si in plus avem:

(b1) stg(T)≈stg(T')

(b2) dr(T)≈dr(T')

Fie n_l si n_r numarul de noduri din stg(T) respectiv dr(T), si, analog n'_l si n'_r numarul de noduri din stg(T') respectiv dr(T'). Avem:

n=1+ n_l +n_r si n'=1+n'_l + n'_r .

Din relatia de similaritate (b1), aplicand ipoteza de inductie (caci stg(T) are mai putin de n noduri) obtinem relatiile :

n_l= n'_l

l(u_i)= l(u'_i) pentru orice i apartinand intervalului [2, n_l+ 1]

r(u_i)= r(u'_i) pentru orice i apartinand intervalului [2, n_l+ 1]

Din relatia de similaritate (b2), aplicand ipoteza de inductie obtinem relatiile :

n_r= n'_r

l(u_r)= l(u'_r) pentru orice i apartinand intervalului [n_l+ 2, n]

r(u_r)= r(u'_r) pentru orice i apartinand intervalului [n_l+ 2, n]

Punand cap la cap aceste doua seturi de relatii obtinem pe de o parte n=n', pe de alta parte toate egalitatile dorite intre functiile marcaj, mai putin cele pentru primul nod u₁ .

Sa demonstram ca l(u₁)= l(u'₁). Daca l(u₁)=0, atunci n_l=0, deci n'_l=0, deci l(u'₁)= 0, si avem egalitatea dorita. Daca l(u₁)= 1 atunci n_l0, dar n'_l= n_l , deci n'_l 0, deci l(u'₁)= 1, si din nou avem egalitatea dorita. Analog se demonstreaza ca r(u₁)= r(u'₁), ceea ce incheie demonstratia unei implicatii.

Pentru implicatia in sens invers sa presupunem ca ipoteza de inductie ca, daca relatiile de tip (S) sunt adevarate atunci arborii T si T' sunt similari, unde T are m noduri, iar m<n.

Sa presupunem acum ca avem arborii T si T' ca in enunt, T cu n noduri, si relatiile (S) pentru ei sunt adevarate.

Este suficient sa demonstram ca avem n_l= n'_l .Intr-adevar daca aceasta relatie e adevarata, atunci rezulta usor din n=n' ca n_r= n'_r .

Apoi, egalitatile functiilor marcaj se impart in doua grupe: pentru indicii i[2,n_l+ 1], impreuna cu n_l=n'_l , conduc, conform ipotezei de inductie la stg(T)≈stg(T'); egalitatile pentru indicii i[n_l+ 2, n], impreuna cu n_r=n'_r conduc, tot prin aplicarea ipotezei de inductie la concluzia dr(T)≈dr(T'). De unde, aplicand definitia recursiva a similaritatii rezulta T ≈T'.

Sa demonstram egalitatea n_l= n'_l. Avem trei cazuri :

(1) l(u₁)=0. Atunci si l(u'₁)=0, iar n_l= 0 si n'_l= 0, de unde rezulta n_l= n'_l;

(2) l(u₁)=1 si r(u₁)=0. Dar atunci si r(u'₁)=0, deci n_r= 0 si n'_r=0, de unde n_r= n'_r , deci n_l= n'_l .

(3) l(u₁)=1 si r(u₁)=1. Deci f(u₁)=1. Conform relatiei (iii) din Lema exista min= n_l+1.

Pe de alta parte pentru u'₁ avem l(u'₁)=1 si r(u'₁)=1, deci f(u'₁)=1, deci conform relatiei (iii) din Lema exista min=n'_l+1.

Cum functiile marcaj l si r sunt egale pe nodurile corespunzatoare din T si T' vom avea si f(u_i)=f(u'_i) pentru orice i[1,n], deci sumele partiale pe cei doi arbori coincid, deci va coincide si indicele pe care se anuleaza prima oara, adica vom avea n_l+1= n'_l+1, de unde n_l= n'_l . Q.E.D.

Teorema ne spune ca informatia completa despre structura unui arbore binar este cuprinsa in vectorii info[1..n], l[1..n] si r[1..n] mentionati la inceputul sectiunii. Cu alte cuvinte, din valorile acestor vectori se poate reconstrui arborele. Mai mult, avem chiar o 'metoda de constructie, care se poate transforma usor in algoritm calculam f(u) pentru fiecare nod, apoi sumele partiale pe rand, la prima care se anuleaza am aflat ce noduri contine subarborele stang, etc.

Daca am avea doar sirul campurilor info de la parcurgerea arborelui binar in preordine, informatia nu ar fi suficienta pentru a reconstitui structura arborescenta. Lucrurile se schimba insa daca am avea si lista campurilor info ale parcurgerii in ordine, cu conditia ca arborele sa nu contina chei multiple.

Exercitii

1. Scrieti un program care are ca date de intrare vectorii info, l si r si construieste arborele binar corespunzator.

2. Scrieti un program care are ca date de intrare un arbore binar si construieste vectorii info, l si r.

3. Demonstrati ca din parcurgerile in preordine si inordine ale unui arbore binar se poate reconstitui structura arborescenta.

4. Scrieti un program care are ca date de intrare parcurgerile in preordine si inordine ale unui arbore binar si construieste arborele binar corespunzator.