Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice




Acasa » referate » informatica
Arbori binari – Similaritate si echivalenta

Arbori binari – Similaritate si echivalenta




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 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 u1 si u2 apartinand lui T le corespund nodurile u1 si u2' apartinand lui T’, atunci daca u2 apartine lui stg (u1) vom avea si u2' apartine lui stg (u1'), iar daca daca u2 apartine lui dr (u1) vom avea si u2' apartine lui dr (u1'). 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 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 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 = u1 u2 un un arbore binar dat prin lista nodurilor sale la parcurgerea in preordine (RSD). Fiecarui nod ui ii vom asocia trei valori : info (ui) reprezentand informatia din nodul ui si l(ui) , r(ui) valorile functiilor l si r in nodul ui.

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= u1 u2 un 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).

i

n

info

info (ui)

l

l (ui)

r

r (ui)

Ex :(a) Ex :(b)

info

A

B

C

D

l



Text Box: Fig.2.3.2. Valorile vectorilor info, l si r pentru arborii (a) si (b) din Fig.2.3.1.r

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= u1 u2 … un un arbore binar parcurs in preordine.

Atunci urmatoarele relatii sunt adevarate :

(i) f(u1)+ …+ f(uk) pentru orice kI[1,n)

(ii) f(u1)+ … + f(un)= -1

(iii) Daca f(u1)=1 atunci exista min= nl+ 1, unde nl 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= u1 deci l(u1)= r(u1)= 0, deci f(u1)= -1 (din cele trei relatii in acest caz nu ramane decat relatia (ii) care se reduce la f(u1)=-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=u1 u2 … un un arbore binar parcurs in preordine cu n noduri. Avem doar doua valori posibile pentru f(u1), f(u1)I ( caci daca f(u1)= -1 atunci rezulta n=1 , ceea ce contrazice ipoteza n>1)

Sa analizam pe rand cele doua cazuri :

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

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

fie (a2) : stg(T) si dr(T)= ceea ce este echivalent cu l(u1)=1 si r(u1)=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)= u2 u3 … un 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(u2) + …+ f(uk) , pentru orice kI[2, n)

(ii)       f(u2)+ … + f(un)=-1

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

relatiile (i) pentru T :

f(u1)=0

f(u1)+ f(u2)+…+ f(uk)=f(u2)+…+ f(uk) pentru orice kI[2, n)

relatia (ii) pentru T :

f(u1)+ f(u2)+ …+ f(un)= f(u2)+ …+ f(un)=-1 .

si am incheiat demonstratia in cazul (a) .

(b) f(u1)=1. Rezulta ca T are ambii fii nevizi. Daca nl este numarul de noduri din fiul stang al lui T , atunci nodurile de la u2 la un+1 sunt nodurile lui stg(T) parcurs in preordine, iar de la un+2 la un 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)=u2…un+1 si dr(T)= un+2…un .

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(u1)= 1> 0

kI[2,nl] f(u1)+ f(u2)+ …+ f(uk)= 1+ f(u2)+ …+ f(uk)> 0

pentru ca f(u2)+ …+ f(uk) din relatia (i) pentru stg(T)



k= nl+1 f(u1)+ f(u2)+ … f(un+1) = 1+ f(u2)+ … f(un+1)= 1- 1= 0

pentru ca f(u2)+ … f(un+1)=-1 din relatia (ii) pentru stg(T) .

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

kI[nl+2,n-1]

f(u1)+ f(u2)+ …+ f(un+1)+ f(un+2)+ …+ f(uk)= f(un+2)+ …+ f(uk)

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

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

k=n f(u1)+f(u2)+…+f(un+1)+f(un+2)+…+f(un)= f(un+2)+…+f(un)=-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= u1 u2 … un si T’=u’12 … u’ doi arbori binari dati in parcurgerile lor in preordine. Urmatoarele afirmatii sunt adevarate :

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

n=n’

(S) l(ui)=l(u’i) pentru orice i apartinand intervalului [1, n]

r(ui)=r(u’i) pentru orice i apartinand intervalului [1, n]

(b)   T si sunt echivalenti (T T’) daca si numai daca avem relatiile

n=n’

(E) l(ui)=l(u’i) pentru orice i apartinand intervalului [1, n]

r(ui)=r(u’i) pentru orice i apartinand intervalului [1, n]

info(ui)= 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 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 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 similari, T cu n noduri n>0. Aceasta inseamna ca T deci si si in plus avem:

(b1) stg(T)≈stg(T’)

(b2) dr(T)≈dr(T’)

Fie nl si nr numarul de noduri din stg(T) respectiv dr(T), si, analog l si r numarul de noduri din stg(T’) respectiv dr(T’). Avem:

n=1+ nl +nr 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 :

nl= n’l

l(ui)= l(u’i) pentru orice i apartinand intervalului [2, nl+ 1]

r(ui)= r(u’i) pentru orice i apartinand intervalului [2, nl+ 1]

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

nr= n’r

l(ur)= l(u’r) pentru orice i apartinand intervalului [nl+ 2, n]

r(ur)= r(u’r) pentru orice i apartinand intervalului [nl+ 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 u1 .

Sa demonstram ca l(u1)= l(u’1). Daca l(u1)=0, atunci nl=0, deci l=0, deci l(u’1)= 0, si avem egalitatea dorita. Daca l(u1)= 1 atunci nl0, dar l= nl , deci l 0, deci l(u’1)= 1, si din nou avem egalitatea dorita. Analog se demonstreaza ca r(u1)= r(u’1), 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 sunt similari, unde T are m noduri, iar m<n.

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

Este suficient sa demonstram ca avem nl= n’l .Intr-adevar daca aceasta relatie e adevarata, atunci rezulta usor din n=n’ ca nr= n’r .

Apoi, egalitatile functiilor marcaj se impart in doua grupe: pentru indicii i[2,nl+ 1], impreuna cu nl=n’l , conduc, conform ipotezei de inductie la stg(T)≈stg(T’); egalitatile pentru indicii i[nl+ 2, n], impreuna cu nr=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 nl= n’l. Avem trei cazuri :

(1) l(u1)=0. Atunci si l(u’1)=0, iar nl= 0 si l= 0, de unde rezulta nl= n’l;

(2) l(u1)=1 si r(u1)=0. Dar atunci si r(u’1)=0, deci nr= 0 si r=0, de unde nr= n’r , deci nl= n’l .

(3) l(u1)=1 si r(u1)=1. Deci f(u1)=1. Conform relatiei (iii) din Lema exista min= nl+1.

Pe de alta parte pentru 1 avem l(u’1)=1 si r(u’1)=1, deci f(u’1)=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 vom avea si f(ui)=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 nl+1= n’l+1, de unde nl= 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.







Politica de confidentialitate


.com Copyright © 2020 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 SCHITA DE PROIECT DIDACTIC GEOGRAFIE CLASA: a IX-a - Unitatile majore ale reliefului terestru
 PROIECT DIDACTIC 5-7 ani Educatia limbajului - Cate cuvinte am spus?
 Proiect atestat Tehnician Electronist - AMPLIFICATOARE ELECTRONICE
 Proiect - masurarea si controlul marimilor geometrice

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

Lucrari licenta

vezi toate lucrarile de licenta
 LUCRARE DE LICENTA CONTABILITATE - ANALIZA EFICIENTEI ECONOMICE – CAI DE CRESTERE LA S.C. CONSTRUCTIA S.A TG-JIU
 Lucrare de licenta sport - Jocul de volei
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 PROIECT ATESTAT MATEMATICA-INFORMATICA - CALUTUL INTELIGENT
 Proiect atestat Tehnician Electronist - AMPLIFICATOARE ELECTRONICE
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM




Tranformare de coordonate
Organizarea datelor
Instruirea asistata de calculator. E-Learning si cursuri On-Line
CALCULUL CLIENT/SERVER
ATESTAT LA INFORMATICA - Baza de date relationala aplicata intr-o biblioteca scolara
Utilizarea grilelor în tipografie
Sumatoare paralele pe principiul anticiparii transportului
Instructiunile limbajului Visual Basic




Termeni si conditii
Contact
Creeaza si tu