Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Arbori - Proprietati ale arborilor

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Arbori de decizie - Inteligenta artificiala
Mod de abordare al algoritmilor euristici in Inteligenta Artificiala
F# programming - Introducing Functional Programming
Algoritmi definire
Parcurgerea grafurilor in adancime
LATCH-URI SI BISTABILE IMPLEMENTATE IN VERILOG
Coada - Utilitatea unei cozi - Inserarea unui element in coada
Conducerea Proiectelor software - Evaluarea costurilor proiectelor software
Liste inlantuite - Inserarea unui nod intr-o lista simplu inlantuita circulara
Sistem informational Sistem informatic

1. Notiuni introductive



Exista mai multe moduri echivalente de definire a arborilor. Din punctul de vedere al teoriei grafurilor numim arbore un graf neorientat conex si fara cicluri. Daca graful este aciclic, dar nu este conex il vom numi padure.

De exemplu,

Fig. 1.

a. este arbore, b. este padure, nefiind conex, iar c. nu este nici arbore, nici padure, deoarece contine cicluri.

1.1. Proprietati ale arborilor

Teorema 1

Fie G = (V, U) un graf neorientat. Urmatoarele afirmatii sunt echivalente:

1) G este arbore.

2) Oricare doua varfuri din G sunt unite printr-un lant simplu unic.

3) G este conex minimal (daca suprimam o muchie, graful obtinut este neconex).

4) G este conex si are V-1 muchii.

5) G este aciclic si are V-1 muchii.

6) G este aciclic maximal (daca adaugam o muchie, graful obtinut contine cicluri).

Demonstratie:

1 T 2

Daca G este arbore, atunci G este conex, deci oricare ar fi doua varfuri din graf, acestea sunt unite prin cel putin un lant simplu. Presupunem prin reducere la absurd ca exista x si y doua varfuri unite prin doua lanturi simple distincte l1 si l2 .

Fig. 2.

Fie z primul varf de la care cele doua lanturi se despart, iar t primul varf in care cele doua lanturi se intalnesc din nou. Daca notam l'1 portiunea de pe lantul l1 intre z si t, iar cu l'2 portiunea de pe lantul l2 intre z si t, atunci l'1 si l'2 nu au varfuri comune, cu exceptia varfurilor z si t. Concatenand l'1 si l'2, obtinem un ciclu- contradictie cu ipoteza ca G este arbore. Deci, oricare doua varfuri din graf sunt unite printr-un lant simplu unic.

2 T 3

Daca oricare doua varfuri x, yIV sunt unite printr-un lant simplu unic, atunci orice muchie [x, y]IU reprezinta unicul lant dintre x si y. Suprimand muchia [x, y], intre x si y nu va mai exista lant, deci graful obtinut nu va mai fi conex.

3 T 4

Notam cu n numarul de varfuri si cu m numarul de muchii din graf.

Pentru a demonstra ca orice graf conex minimal are n-1 muchii vom demonstra prin inductie completa dupa n ca m n-1. Cum in orice graf conex m n-1, deducem m = n-1.

P(1) Daca n = 1, atunci m = 0 T m = n-1.

P(2) Daca n = 2, atunci m =1 T m = n-1.

P(n) Presupunem ca intr-un graf conex minimal cu cel mult n varfuri numarul de muchii este strict mai mic decat numarul de varfuri.

P(n+1) Demonstram ca intr-un graf conex minimal cu n+1 varfuri, numarul de muchii este cel mult egal cu n.

Fie G conex minimal cu n+1 varfuri si m muchii. Eliminand o muchie oarecare din graf obtinem un graf G' cu m-1 muchii si doua componente conexe C1 si C2 cu n1, respectiv n2 varfuri (n1+n2 = n+1) si m1, respectiv m2 muchii (m1+m2 = m-1). Subgrafurile C1 si C2 sunt conexe minimale, altfel graful G nu ar fi conex minimal. Din ipoteza inductiva rezulta ca m1 n1-1, m2 n2-1; dar m1+m2 = m-1 n1+n2 = n-2 T m n-1. Deci G conex minimal implica G conex cu n-1 muchii.

4 T 5

Fie G un graf conex cu n-1 muchii. Sa demonstram ca G este aciclic.

Presupunem prin reducere la absurd, ca graful G contine un ciclu C format din varfurile v1, v2, , vk.

Sa consideram subgraful partial Gk = (Vk, Uk) constand din ciclul C. Deci Vk = , iar Uk = (Vk=Uk= k). Daca Vk<V, atunci $viIVk si vk+1IV-Vk astfel incat [vi, vk+1]IU, graful G fiind conex.

Construim Gk+1 = (Vk+1, Uk+1) astfel :Vk+1 = Vk ; Uk+1=Uk si Uk+1=Vk+1=k+1.

Cat timp k+1 < n, aplicam acelasi procedeu pana cand obtinem un graf Gn = (V, Un), cu Un= n, Un U; deci U n, contradictie cu ipoteza U= n-1.

5 T 6

Presupunem ca graful G este aciclic cu n-1 muchii, sa demonstram ca G este aciclic maximal.

Fie C1, C2,, Cp cele p componentele conexe ale grafului G, avand respectiv n1, n2,, np varfuri si m1, m2,, mp muchii fiecare. Evident ca n1+n2++np = n si m1+m2++mp = n-1.

Cum graful G este aciclic, deducem ca fiecare componenta conexa este un arbore. Deoarece am demonstrat ca 1 T 5, rezulta ca m i= ni-1, 'iI. Inlocuind in relatia de mai sus, obtinem n-p = n-1 T p = 1, deci G conex. Daca G este conex si aciclic, conform definitiei G este arbore. Dar am demonstrat ca 1 T 2, deci oricare doua varfuri din G sunt unite printr-un lant simplu. Astfel, adaugand orice muchie obtinem un ciclu.

6 T 1

Presupunem ca graful G este aciclic, dar daca am mai adauga o muchie s-ar obtine un ciclu. Sa demonstram ca G este conex.

Fie u si v doua varfuri neadiacente din graf, arbitrar alese. Deoarece adaugand muchia [u, v] se obtine un ciclu, rezulta ca u si v sunt unite printr-un lant ale carui muchii apartin grafului G. Cum u,v au fost alese arbitrar, deducem ca graful G este conex.

Q.E.D.

Teorema 2

Numerele intregi 0 < d1 d2 dn (n 2) sunt gradele varfurilor unui arbore daca si numai daca d1+d2++dn = 2n-2.

Demonstratie:

Necesitatea Conditia este necesara, deoarece orice arbore cu n varfuri are n-1 muchii, iar suma gradelor varfurilor oricarui graf este de doua ori numarul de muchii. Deci d1+d2++dn = 2n-2.

Suficienta Fie 0 < d1 d2 dn astfel incat d1+d2++dn = 2n-2.

Sa demonstram ca exista un arbore cu gradele varfurilor d1, d2,, dn. Vom proceda prin inductie.

P(2) Daca d1+d2 = 2, atunci d1 = d2 = 1 , arborele fiind cel din figura de mai jos :

Fig. 3

P(n) Presupunem acum ca proprietatea este adevarata pentru orice secventa de n numere naturale 0 < d1 d2 dn, astfel incat d1+d2++dn = 2n-2.

P(n+1) Sa demonstram ca pentru orice secventa 0 < d'1 d'2 d'n d'n+1 astfel incat d'1+d'2++d'n+1 = 2n, exista un arbore cu n+1 varfuri cu secventa gradelor d'1, d'2, , d'n+1.

Observam ca exista macar un nod terminal x1 cu gradul d'1=1, altfel daca di 2,'iI T d'1+d'2++d'n+1 2(n+1), ceea ce contrazice ipoteza. In mod analog, observam ca exista macar un nod neterminal xn+1, cu gradul d'n+1 > 1, altfel daca d'i = 1,'iI T d'1+d'2++d'n+1 = n+1 < 2n .

Sa consideram urmatoarea secventa de n numere intregi d'2,, d'n, d'n+1-1 cu proprietatea ca d'2++d'n+d'n+1 = 2n-2. Din ipoteza inductiva exista un arbore An cu n varfuri si secventa gradelor d'2,, d'n, d'n+1-1. Adaugam la arborele An un varf pe care il unim printr-o muchie cu varful avand gradul d'n+1-1. Obtinem un arbore An+1 cu gradele varfurilor d'1, d'2,, d'n+1.

Q.E.D.

Demonstratia acestei teoreme ofera si o solutie constructiva pentru obtinerea unui arbore cu secventa gradelor data.

Vom retine gradele varfurilor intr-un vector d de dimensiune n, ordonat crescator, cu suma componentelor egala cu 2n-2.

Arborele va fi reprezentat prin matricea muchiilor, o matrice a cu doua linii si n-1 coloane, in care pentru fiecare muchie din arbore vom retine extremitatile.

Spre deosebire de ideea din demonstratie, pentru a conserva ordinea in vectorul d, la fiecare pas al algoritmului gradul care va fi decrementat va fi primul grad mai mare ca 1 si nu ultimul.

Procedure Determinare Arbore;*

//vectorul d, matricea a si n, numarul de varfuri, sunt variabile globale

var NrMuchiiSelectate, VfTerminal, VfNeterminal: Integer;

begin

NrMuchiiSelectate := 0;

VfTerminal := 1;

while NrMuchiiSelectate < n-1 do

begin //selectez o muchie in arbore

VfNeterminal := VfTerminal + 1;

//caut un varf cu grad mai mare decat 1

while d[VfNeterminal] = 1 do inc(VfNeterminal);

inc(NrMuchiiSelectate);

//selectez muchia [VfTerminal,VfNeterminal]

a[1,NrMuchiiSelectate] := VfTerminal;

a[2,NrMuchiiSelectate] := VfNeterminal;

dec(d[VfNeterminal]);

inc(VfTerminal);

end;

end;

De exemplu, pentru n =11 si sirul gradelor:

1

2

3

4

5

6

7

8

9

10

11

1

1

1

1

1

1

1

2

3

4

4

obtinem arborele din figura 4.

Fig. 4

Acest procedeu sugereaza o metoda foarte eficienta de reprezentare a arborilor. Daca An este un arbore cu varfurile x1, x2,.., xn, suprimam varful terminal cu cel mai mic indice si muchia incidenta cu acesta si retinem a1, varful adiacent cu varful terminal suprimat. Am obtinut astfel un subgraf cu n-2 muchii conex si aciclic, deci un arbore An-1. Repetam procedeul pentru arborele An-1, determinand un al doilea varf, a2, adiacent cu varful terminal de indice minim ce va fi eliminat din An-1 impreuna cu muchia incidenta cu el s.a.m.d., pana cand se obtine un arbore A2 cu doua varfuri adiacente.

Am obtinut astfel un sistem de n-2 numere 1ain, 'iI asociat arborelui An numit codul Prffer al lui An.

Pentru arborele din figura 4, codul Prffer este a=.

Propozitie

Exista o corespondenta biunivoca intre multimea arborilor A cu n varfuri si multimea sistemelor , aiI, 'iI .

Demonstratie:

Injectivitatea

Fie a=, 1 ai n, 'iI, codul Prffer al unui arbore A. Completam sirul cu an-1 = n, deci a = .

Sa notam b = (b1, b2, , bn-2, bn-1) indicii varfurilor in ordinea in care au fost eliminate. Observam ca :

1. bi bj, 'i j (deoarece un nod nu poate fi eliminat decat o data);

2.     bi ai (pentru ca exista muchia [ai, bi]);

3.     bi aj, 'j > i (bi fiind eliminat la pasul i, nu mai poate fi parintele unui alt varf eliminat ulterior);

4. ' k I, k este un varf terminal al arborelui A-, altfel k ar fi adiacent cu un varf ce va fi suprimat ulterior, deci k = aj, cu j > i- contradictie (un varf care nu a fost eliminat si care nu este parinte pentru un alt varf, este varf terminal).

5. bi, din modul de definire a codului Prffer va fi :

bi = min{ k k} (*)

Deci din codul Prffer am putut determina in mod unic ordinea de eliminare a varfurilor si implicit, muchiile arborelui

A=}

Surjectivitatea

Demonstram ca 'a = , 1 ai n, 'iI, exista un arbore A cu n varfuri astfel incat codul Prffer al lui A sa fie sirul a.

Completam a cu an-1 = n si definim bi conform relatiei (*), 'iI. Construim A, graful cu muchiile U = {[ai, bi], 'iI}. Vom arata ca A este arbore si codul Prffer al lui A este .

Notam Ui = U-, 'iI,

Vi = -.

Evident A = A1, iar An este format numai din varful n, deci An este arbore.

Sa demonstram ca bi este varf terminal in Ai.

bi = min{ k k}

Dar aiIAi, pentru ca din relatia (*) ai bj,'j < i, iar bi nu poate fi adiacent in Ai decat cu ai, deoarece, daca bi ar fi incident cu o alta muchie [bj, aj], j > i din Ai ar insemna ca bi = bj sau aj = bi, cu j > i ceea ce este in contradictie cu definitia lui bi.

Ai-1 se obtine din Ai eliminand varful terminal bi si muchia [bi, ai], incidenta cu aceasta. Procedand inductiv, cum An este arbore, deducem ca Ai, iI sunt arbori, in particular A este arbore.

Tot din definirea lui bi rezulta ca bi este varful terminal de indice minim, deci, conform definitiei, va fi codul Prffer al arborelui Ai. In particular deducem ca este codul Prffer al arborelui A.

Q.E.D.

Sa consideram, de exemplu, n =11 si a = .

Pentru a determina muchiile arborelui cu acest cod Prffer, completam codul cu a10=11. Deci a= si determinam :

b1 = min }=3

b2 = min }=6

b3 = min }=7

b4 = min }=8



b5 = min }=2

b6 = min }=9

b7 = min }=10

b8 = min }=4

b9 = min }=1

b10 = min }=5

Muchiile arborelui sunt : [1,3], [2,6], [2,7], [2,8], [1,2], [4,9], [4,10], [1,4], [5,1], [5,11].

Fig. 5

Folosind acest rezultat, deducem ca numarul arborilor ce se pot construi cu n varfuri date este egal cu nn-2, numarul functiilor bijective definite pe o multime cu n-2 elemente, cu valori intr-o multime cu n elemente. Aceasta formula poarta numele de formula lui Cayley.

Aplicatie*

Generati toti arborii cu n varfuri.

Problema se reduce la generarea tuturor functiilor

a:

si determinarea arborelui corespunzator fiecarei functii.

Vom genera toate codurile Prffer posibile recursiv, apeland procedura generare(1).

procedure generare(i:byte);

//pozitiile 1,2,,i-1 din vectorul global a sunt fixate;

// completam pozitiile i,,n-2.

begin

if i = n-1 then // codul este complet

determina_arbore

else

for j := 1 to n do

begin

a[i] := j;

generare(i + 1);

end;

end;

procedure determina_arbore;

// afiseaza muchiile arborelui;

var k, i: byte;

MB: set of byte;

//multimea varfurilor care au fost deja eliminate din arbore

MA: set of byte;

//multimea varfurilor pentru care trebuie sa determinam nodul

// terminal adiacent

begin

MB := []; MA := [a1, a2, , an-1];

for i := 1 to n - 1 do //determin cele n-1 muchii ale arborelui

begin

//calculez k, varful de indice minim ce MAMB

k := 1;

while k in MA + MB do inc(k);

MB := MB + [k];

// k este nodul terminal de indice minim cautat

MA := MA - [ai];

write(k, ai,); //afisez muchia [k,ai]

end;

end;

1.2. Arbori cu radacina

Pentru problemele in care se impune o ierarhizare a informatiilor ce corespund varfurilor arborelui, astfel incat anumite varfuri sa fie subordonate altora, este utila introducerea unei noi notiuni- arbore cu radacina. Arborii cu radacina sunt o prezenta cotidiana. Fiecare si-a reconstituit la un moment dat arborele genealogic si, dupa cum vom vedea, cea mai mare parte a termenilor folositi in limbajul informatic deriva de aici. Un alt exemplu este modul de organizare a competitiilor sportive sau organigrama unei intreprinderi. In multe alte exemple ii veti intalni pe parcursul acestei carti.

Definitie

Un arbore cu radacina este o multime finita de noduri care fie este vida fie

- exista un nod special numit radacina arborelui;

-toate celelalte noduri sunt partitionate in n 0 clase A1, A2, , An, fiecare clasa fiind un arbore cu radacina. Radacina arborelui este unita prin muchii de radacinile arborilorA1, A2, , An.

Fig.6.

Definitia este recursiva, orice nod al unui arbore fiind radacina unui subarbore.

Sa observam ca alegand intr-un mod arbitrar un varf drept radacina, orice graf neorientat conex si fara cicluri este un arbore cu radacina in sensul definitiei de mai sus. Arborii A1, A2, , An se numesc subarborii radacinii, numarul de subarbori nevizi ai unui nod fiind numit gradul nodului respectiv.

De exemplu,

Fig. 7.

Sa observam ca definitia conduce la o ierarhizare a nodurilor arborelui :

- consideram ca radacina r se situeaza pe nivelul 0.

- daca notam cu r1, r2, , rn respectiv radacinile arborilor A1, A2, , An, nodurile r1, r2, , rn vor constitui nivelul 1 in arbore, s.a.m.d.

Nodurile r1, r2, , rn, se numesc fiii nodului radacina, iar radacina r reprezinta parintele nodurilor r1, r2, , rn, radacina fiind singurul nod din arbore care nu are parinte. Fiecarei muchii din arbore ii putem asocia o orientare de la parinte spre fiu. In plus, fiii nodurilor de pe nivelul i0, vor constitui nivelul i+1.

Nivelul maxim din arbore va constitui inaltimea (adancimea) arborelui respectiv. Sa observam ca orice nod x poate fi atins din radacina pe un drum unic. Orice nod y care se gaseste pe drumul unic de la r la x se numeste ascendent (stramos) al lui x. Daca y este un ascendent al lui x, atunci x se numeste descendent al lui y. Mai exact, toti descendentii unui nod x sunt nodurile din subarborele cu radacina x. Daca un nod nu are descendenti el se numeste nod terminal sau frunza. Doua noduri care au acelasi parinte se numesc frati.

In exemplul de mai sus, 4 este un ascendent al lui 8. Nodurile 5, 6, 3, 8, 9 sunt noduri terminale. Nodurile 8, 9 sunt frati, iar descendentii nodului 4 sunt nodurile 7, 8, 9.

1.3. Arbori binari

O clasa foarte importanta de arbori cu radacina o constituie arborii binari. Un arbore binar este un arbore cu radacina in care gradul oricarui varf este cel mult egal cu doi. Putem defini recursiv arborii binari astfel :

Definitie

Un arbore binar este un arbore care fie este vid, fie consta dintr-un nod radacina si doi arbori binari disjuncti numiti subarborele stang, respectiv subarborele.

Fig. 8.

A1 = subarbore stang; A2 = subarbore drept.

Se face o distinctie clara intre subarborele drept si cel stang. Daca subarborele stang este nevid, radacina lui se numeste fiul stang al radacinii. Analog, daca subarborele drept este nevid, radacina lui se numeste fiul drept al radacinii.

De exemplu,

Fig. 9.

sunt doi arbori binari distincti.

In continuare, terminologia folosita la arbori cu radacina se va aplica si la arbori binari. Vom deosebi intre arborii binari cateva clase speciale:

1. Arbori binari stricti sunt arborii binari in care orice varf are gradul zero (este terminal ) sau doi (are exact doi fii).

De exemplu, arborii din figura 9 nu sunt arbori binari stricti (nodurile 2 si 6 avand un singur fiu), dar

Fig. 10.

este un arbore binar strict.

2. Arbori binari plini sunt arbori binari care au 2k-1 varfuri dispuse pe nivelurile 0, 1, , k-1, astfel incat pe fiecare nivel i se gasesc 2i varfuri.

De exemplu, arborele binar plin cu inaltimea 2 este:

Fig. 11.

3. Arborii binari completi sunt arbori binari care se obtin dintr-un arbore binar plin prin eliminarea din dreapta catre stanga a unor noduri de pe ultimul nivel. Mai exact, pentru a construi un arbore binar complet cu n noduri, determinam k astfel incat

2k n < 2k+1 k = [log2n].

Construim arborele binar plin cu 2k+1-1 noduri si eliminam de pe ultimul nivel nodurile 2k+1-1, 2k+1-2, , n+1.

De exemplu, arborele binar complet cu 5 varfuri se obtine prin eliminarea varfurilor 7 si 6 din arborele binar plin cu inaltimea 2 :

Fig. 12.

4. Arbori binari degenerati- sunt arbori binari cu n varfuri dispuse pe n niveluri.

De exemplu,

Fig. 13.

5. Arbori binari echilibrati - sunt arbori binari in care, pentru orice nod, numarul nodurilor din subarborele drept si numarul nodurilor din subarborele stang difera cu cel mult o unitate.

De exemplu,

Fig. 14.

1.3.1 Proprietati ale arborilor binari

Proprietatea 1.

Numarul maxim de noduri de pe nivelul i al unui arbore binar este 2i.

Demonstratie:

Vom proceda prin inductie dupa numarul nivelului.

P(0) Pe nivelul i = 0 se gaseste un singur nod (radacina).

P(k) Presupunem ca numarul maxim de noduri de pe nivelul k este

2k.

P(k+1) Vom demonstra ca pe nivelul k+1 sunt cel mult 2k+1 noduri.

Pe nivelul k+1 se gasesc fiii nodurilor de pe nivelul k. Din ipoteza inductiva, pe nivelul k se gasesc cel mult 2k noduri, iar fiecare nod poate avea cel mult doi fii, deci pe nivelul k+1 se gasesc cel mult 2*2k = 2k+1 noduri.

Q.E.D.

Proprietatea 2.

Numarul maxim de noduri intr-un arbore cu inaltimea h este 2h+1-1.

Demonstratie:

Numarul maxim de noduri intr-un arbore cu inaltimea h se obtine atunci cand fiecare nivel i este plin, deci, conform propozitiei anterioare, contine 2i noduri. Numarul maxim de noduri intr-un arbore cu inaltimea h va fi:

Q.E.D.

Proprietatea 3.

In orice arbore binar nevid cu n0 noduri terminale exista n0-1 noduri de grad 2.

Demonstratie:

Notam cu n0 numarul de noduri terminale, cu n1 numarul de noduri de grad 1 si cu n2 numarul de noduri de grad 2. Deci, numarul total de noduri n=n0+n1+n2.

Daca numaram muchiile dintr-un arbore binar, observam ca fiecare nod, cu exceptia radacinii, are o singura muchie orientata spre el. Notand m numarul de muchii obtinem n = m+1. Dar orice muchie provine de la un nod de grad 1 sau 2, rezulta ca m = n1+2n2.

Din n0+n1+n2 = n si n1+2n2 = n-1 T n2 = n0-1.

Q.E.D.

Proprietatea 4.

Un arbore cu n varfuri are inaltimea cel putin egala cu [log2n].

Demonstratie:

In cazul cel mai favorabil, nodurile sunt dispuse pe niveluri astfel incat fiecare nivel sa fie plin, cu exceptia, eventuala, a ultimului nivel. Deci arborele binar cu n noduri de inaltime minima este arborele binar complet cu n varfuri, care, din modul de constructie, are inaltimea [log2n].

Q.E.D.

Proprietatea 5.

Definim lungimea drumurilor interne (I) ca fiind suma lungimilor drumurilor de la radacina la noduri neterminale (interne) si lungimea drumurilor externe (E) ca fiind suma lungimilor drumurilor de la radacina la noduri terminale (frunza sau externe). Intr-un arbore binar cu n noduri interne, E = I+2n.

Demonstratie:

Vom proceda prin inductie dupa n, numarul nodurilor interne.

P(0) Intr-un arbore cu 0 noduri interne (vid sau format numai din radacina) E = I = 0.

P(n-1) Presupunem ca intr-un arbore binar An-1, cu n-1 noduri interne, are loc relatia En-1 = In-1+2(n-1).

P(n) Vom demonstra ca intr-un arbore binar An, cu n noduri interne, are loc relatia En = In+2n.

Fie An un arbore binar cu n noduri interne. Exista in An un nod intern x care are drept fii doua noduri terminale. Indepartand din An fiii nodului x, nodul x se transforma in nod terminal, deci obtinem un arbore An-1 cu n-1 noduri interne. Din propozitia inductiva rezulta ca in arborele A n-1, En-1 = In-1+2(n-1). Daca notam cu d, lungimea drumului de la radacina la nodurile eliminate, obtinem relatiile :

En = En-1+2d-(d-1) (in An nodurile eliminate sunt terminale, dar nodul x nu, lungimea drumului de la radacina la x fiind d-1).

In = In-1+(d-1) (in An nodul x este intern).

Deci En = In-1+2(n-1)+d+1 = In-d+1+2n-2+d+1 = In+2n.

Q.E.D.

1.4. Reprezentarea arborilor

 

1.4.1. Reprezentarea cu referinte descendente

Pentru fiecare nod din arbore vom retine informatia asociata nodului si referinte catre fiii sai. Daca presupunem ca gradul oricarui nod este cel mult egal cu n, putem reprezenta referintele spre fii printr-un vector cu n componente.

Structura unui nod va fi :

Informatie

Fiu1

Fiu2

Fiun

Declararea acestei structuri in sectiunea type in limbajul Pascal este :

Arbore = ^NodArbore;

NodArbore = record

Inf: TipInformatie;

Fiu: array[1..NrMaxFii] of Arbore;

end;

Intr-o astfel de reprezentare risipa de memorie este foarte mare, in fiecare nod alocam memorie pentru numarul maxim de referinte catre fii. In plus, numarul maxim de fii este, in general, necunoscut. Acest neajuns ar putea fi eliminat folosind in locul vectorului de referinte (cu numar a priori fixat de componente) o lista simplu inlantuita in care sa retinem toti fiii nodului respectiv.

Declararea acestei structuri in sectiunea type in limbajul Pascal va fi :

ListaFii = ^Fiu;

Fiu = record

F: Arbore;

Urm: ListaFii;

end;

Arbore = ^Nod Arbore;

NodArbore = record

Inf: TipInformatie;

Ref: ListaFii;

end;

De exemplu, arborele din figura de mai jos,

Fig. 15.

va fi reprezentat prin :

Fig.16.

Daca arborele este reprezentat prin referinte descendente, atunci este suficient sa retinem radacina arborelui pentru a avea acces la toate nodurile acestuia.

1.4.2. Reprezentarea cu referinte ascendente

In aceasta reprezentare, pentru fiecare nod din graf retinem pe langa informatia aferenta, o legatura spre nodul parinte.

Arbore = ^NodArbore;

NodArbore = record

Inf: TipInformatie;

Tata: Arbore;

end;

Mai simplu, putem utiliza doi vectori in care pentru fiecare nod retinem informatia, respectiv nodul parinte. Aceasta reprezentare este mai compacta, dar pentru a avea acces la toate nodurile arborelui trebuie sa retinem toate nodurile terminale.

De exemplu, pentru arborele din figura 15 vom obtine reprezentarea :

Inf

a

b

c

d

e

f

g

h

i

j

k

l

m

Tata

a

a

a

b

b

c

d

d

d

e

e

h

O astfel de reprezentare este utila pentru reprezentarea multimilor disjuncte cu ajutorul arborilor si o rezolvare eficienta a problemelor de reuniune a doua multimi si de determinare a multimii careia ii apartine un element dat.

1.4.3. Reprezentarea Fiu-Frate.

Pentru fiecare nod retinem fiul cel mai din stanga si fratele lui din dreapta cel mai apropiat.

Arbore = ^NodArbore;

NodArbore = record

Inf: TipInformatie;

FiuSt, FrateDr: Arbore;

end;

Pentru arborele din figura 15 obtinem:

Fig. 17.

Rotind aceasta reprezentare cu 45 in sensul acelor de ceasornic, obtinem un arbore binar in care pentru fiecare nod, fiul drept este fratele lui din dreapta cel mai apropiat. Intre cele doua grafuri exista o corespondenta biunivoca. Figura de mai jos ilustreaza aceasta transformare.

Fig. 18.

1.5. Reprezentarea arborilor binari

1.5.1. Reprezentarea inlantuita.

In aceasta reprezentare, pentru fiecare nod retinem, pe langa informatia asociata nodului, radacina subarborelui stang, radacina subarborelui drept si daca este necesar, parintele nodului respectiv.

ArboreBinar = ^NodArboreBinar;

NodArboreBinar = record

c: TipInformatie;

st, dr, parinte: ArboreBinar;

end;

Arborele binar va fi referit prin intermediul radacinii.

1.5.2. Reprezentarea secventiala.

Pentru fiecare nod retinem intr-un vector doar informatia asociata nodului, legaturile dintre noduri fiind implicite. Acest tip de reprezentare este convenabil pentru arbori binari completi. Pentru aceasta, vom numerota nodurile astfel :

- radacina este numerotata cu 1.

- cele 2i noduri de pe nivelul i sunt numerotate 2i, 2i+1, , 2i+1-1 de la stanga la dreapta(i > 0).

- pe ultimul nivel nodurile sunt numerotate pana la n, numarul de noduri din arbore.

Aceasta numerotare ne permite sa deducem legaturile existente intre nodurile arborelui.

Propozitie

Urmatoarele relatiii sunt valabile pentru orice nod x din arbore :

1.     fiul stang al lui x este

2.     fiul drept al lui x este

3.     parintele lui x este

Demonstratie:

Vom demonstra relatiile 1. si 2. prin inductie dupa numarul nodului x, relatia 3. fiind o consecinta imediata a relatiiilor 1. si 2.

P(1) Daca x = 1, st(1) = 2 = 2x, daca 2 n

dr(1) = 3 = 2x+1, daca 3 n.

P(x) Presupunem ca relatiile 1. si 2. sunt indeplinite pentru nodul x.

P(x+1) Demonstram relatiile 1. si 2. pentru x+1, adica

si

Fiul stang al nodului x+1 este precedat de fiul drept al nodului x. Din ipoteza inductiva, dr(x) = 2x+1, deci st(x+1) = 2x+1+1 = 2x+2, evident, daca 2x+2 n. Fiul drept al lui x+1 este succesorul lui st(x+1), deci dr(x+1) = 2x+2+1 = 2x+3, daca 2x+3 n.

Q.E.D.

Deci pentru arbori binari completi aceasta reprezentare este ideala, nefiind necesara decat memorarea informatiilor nodurilor. Se poate utiliza reprezentarea secventiala si pentru arbori binari oarecare, completand arborele cu noduri fictive pana la un arbore binar complet, dar in acest caz o mare parte din vectorul ce contine informatiile nodurilor ramane neutilizata. In plus, ca orice reprezentare secventiala, este inadecvata pentru inserari si stergeri de noduri.




1.6. Operatii elementare pe arbori binari*

In cele ce urmeaza, vom utiliza reprezentarea inlantuita a arborilor binari.

1.6.1. Crearea unui arbore binar.

Algoritmul de creare depinde in mod esential de tipul arborelui binar pe care dorim sa-l construim. Vom prezenta o procedura de creare a unui arbore binar echilibrat, alti algoritmi de creare fiind prezentati in capitolele urmatoare. Pentru a crea un arbore binar echilibrat cu n varfuri se stabileste un varf radacina, se construieste un arbore binar echilibrat cu [n/2] varfuri ca subarbore stang si un arbore binar echilibrat cu n-1-[n/2] varfuri ca subarbore drept. Daca n este par numarul nodurilor din subarborele stang va fi cu o unitate mai mare decat numarul nodurilor din subarborele drept, altfel cei doi subarbori au un numar egal de noduri.

function CreareArboreBinarEchilibrat(n: byte): ArboreBinar;

// functia intoarce adresa radacinii unui arbore binar echilibrat cu n //varfuri

var rad: ArboreBinar;

begin

if n = 0 then //arborele este vid

CreareArboreBinarEchilibrat := nil

else

begin

new(rad) //aloc zona de memorie pentru radacina arborelui

readln(rad^.Inf);//citesc informatia radacinii arborelui

// creez subarborele stang, apoi cel drept

rad^. St := CreareArboreBinarEchilibrat(n div 2);

rad^. Dr := CreareArboreBinarEchilibrat(n - n div 2 -1 );

CreareArboreBinarEchilibrat := rad

end

end;

1.6.2. Parcurgerea arborilor binari

Parcurgerile sunt cele mai frecvent utilizate operatii pe arbori. A parcurge un arbore inseamna a vizita fiecare nod al arborelui o singura data, in scopul prelucrarii informatiei asociate nodului.

Exista mai multe posibilitati de parcurgere a arborilor- in adancime (preordine, inordine, postordine) sau pe niveluri, dar in toate cazurile atat arborele, cat si subarborii sunt prelucrati in acelasi mod.

a) Parcurgerile in adancime

In toate cele trei tipuri de parcurgere in adancime se viziteaza mai intai subarborele stang, apoi subarborele drept. Diferenta consta in pozitia radacinii fata de cei doi subarbori. Fie scrise recursiv, fie iterativ, procedurile de parcurgere in adancime necesita o stiva.

Pentru a parcurge un arbore binar in preordine, se viziteaza mai intai radacina, se parcurge in preordine subarborele stang, apoi se parcurge in preordine subarborele drept.

procedure Preordine(rad: ArboreBinar);

begin

if rad nil then

begin

write(rad^.inf); //vizitez radacina

Preordine(rad^.st); //parcurg subarborele stang

Preordine(rad^.dr); //parcurg subarborele drept

end;

end;

Pentru a parcurge in inordine un arbore binar, se parcurge in inordine subarborele stang, se viziteaza radacina, apoi se parcurge in inordine subarborele drept.

procedure Inordine(rad: ArboreBinar);

begin

if rad nil then

begin

Inordine(rad^.st);

write(rad^.inf);

Inordine(rad^.dr);

end;

end;

Pentru a parcurge in postordine un arbore binar, se parcurge in postordine subarborele stang, apoi cel drept, apoi se viziteaza radacina.

procedure Postordine(rad: ArboreBinar);

begin

if rad nil then

begin

Postordine(rad^.st);

Postordine(rad^.dr);

write(rad^.inf);

end;

end;

Pentru a intelege mai bine operatia de parcurgere, vom prezenta si o varianta iterativa de parcurgere in inordine a unui arbore binar.

Pentru a simula recursia vom folosi o stiva S la care vom adauga sau sterge elemente in acelasi mod ca in procedura recursiva.

Stiva = ^NodStiva;

NodStiva = record

Inf: ArboreBinar;

Urm: Stiva;

end;

procedure InordineIterativ (rad: ArboreBinar);

// procedura parcurge iterativ in inordine arborele cu radacina rad

var S, p: Stiva;

NodCurent: ArboreBinar;

begin

S := nil;

NodCurent := rad;

repeat

while NodCurent nil do

begin

//adauga nodul curent in stiva S

new(p)

p^.Inf := NodCurent;

p^.Urm := S;

S := p;

//radacina subarborelui stang devine nod curent

NodCurent := NodCurent^.St

if S nil then //extrage un element din stiva

begin

p := S;

S := S^.Urm;

write(p^.inf)

NodCurent := p^.Inf^.Dr

dispose(p);

//elibereaza zona de memorie a lui p

until (S = nil) and (NodCurent = nil)

end;

Observatie

Fiecare nod din arbore este plasat si sters din stiva o singura data, deci timpul necesar parcurgerii inordine este de O(n). Spatiul suplimentar necesar depinde de inaltimea arborelui, deci in cazul cel mai defavorabil este de O(n).

b) Parcurgerea pe niveluri

Se viziteaza intai radacina, apoi fiul stang al radacinii, apoi cel drept si se continua in acest mod vizitand nodurile de pe fiecare nivel de la stanga la dreapta.

Pentru a realiza acest mod de parcurgere, vom utiliza o coada, pe care o initializam cu radacina arborelui si din care, la fiecare pas, vom extrage un nod, il vizitam si inseram in coada fii sai, daca acestia exista.

Coada = ^NodCoada;

NodCoada = record

Inf: ArboreBinar;

Urm: Coada;

end;

procedure ParcurgerePeNiveluri (rad: ArboreBinar)

//procedura parcurge pe niveluri arborele cu radacina rad

var C, SfC, p: Coada;

begin

if rad nil then //arborele este nevid

begin

new(C) // initializez coada cu radacina arborelui

C^.Inf := rad;

C^.Urm := nil;

SfC := C;

while C nil do // coada nu este vida

begin

p := C;

write(p^.Inf);

if p^.Inf^.St nil then begin

//adaug fiul stang in coada

new(q);

q^.Inf := p^.Inf^.St;

q^.Urm := nil;

SfC^.Urm := q;

SfC := q;

end;

if p^.Inf^.Dr nil then

begin //adaug fiul drept in coada

new(q);

q^.Inf := p^.Inf^.Dr;

q^.Urm := nil;

SfC^.Urm := q;

SfC := q;

end;

C := C^.Urm //extrag din coada nodul p

dispose(p);

end

end

end;

Observatie

Mai intai am inserat in coada fiii nodului ce urmeaza a fi vizitat si apoi am extras efectiv nodul respectiv din coada, pentru a evita inserarea unui nod intro coada vida.

1.6.3. Determinarea inaltimii unui arbore.

Daca arborele este vid, vom considera ca inaltimea sa este 1, astfel putem calcula inaltimea arborelui ca fiind maximul dintre inaltimile subarborilor radacinii plus nivelul pe care se afla radacina.

function Inaltime (rad: ArboreBinar): integer;

// functia intoarce inaltimea arborelui binar cu radacina rad

begin

if rad = nil then // arbore vid

Inaltime := 1

else

Inaltime := max(Inaltime(rad^.st), Inaltime(rad^.dr))+1

end;

Am presupus cunoscuta functia max, care intoarce cel mai mare dintre cele doua argumente ale sale.

1.6.4. Egalitatea a doi arbori binari.

Spunem ca doi arbori binari sint egali daca au aceeasi structura si contin aceleasi informatii in nodurile corespondente.

function Egali (rad1, rad2: ArboreBinar): boolean;

//functia intoarce true daca arborii cu radacinile rad1,

// respectiv rad2 sunt egali, altfel intoarce false

begin

Egali := (rad1 = nil) and (rad2 = nil) //ambii sunt vizi sau

or (rad1 nil) and (rad2 nil) // ambii sunt nevizi si

and (rad1^.c = rad2^.c) //au aceeasi informatie in radacina

and Egali(rad1^.St, rad2^.St) //subarborii stangi egali

and Egali(rad1^.Dr, rad2^.Dr) // subarborii drepti egali

end;

Aplicatie*

Se dau secventele obtinute prin parcurgerile in preordine si in inordine ale unui arbore binar. Construiti arborele binar corespunzator.

De exemplu, fie A,B,C,D,E,F,G,H- parcurgerea in preordine si

C,B,A,E,D,G,F,H- parcurgerea in inordine.

Analizind parcurgerea in preordine, deducem ca nodul A este radacina. De asemeni, analizand parcurgerea in inordine, deducem ca nodurile C, B vor constitui arborele stang, iar D, E, G, F, H subarborele drept. Pentru a determina structura subarborelui stang, respectiv a subarborelui drept, procedam analog: din parcurgerea in preordine deducem ca B este radacina subarborelui stang, iar din parcurgerea in inordine deducem ca C este fiul stang al lui B. In mod similar, pentru subarborele drept deducem din parcurgerea in preordine ca D este radacina, iar din parcurgerea in inordine ca subarborele stang al lui D este format numai din nodul E, iar subarborele drept al lui D din nodurile F, G, H. Procedeul se repeta pina cind obtinem intreg arborele. Succesiunea operatiilor este ilustrata in figura 19:

Fig. 19.

Propozitie

Succesiunile de noduri obtinute prin parcurgerile in inordine si in preordine ale unui arbore binar definesc in mod unic structura arborelui.

Demonstratie:

Vom proceda prin inductie completa dupa numarul de noduri.

P(1) Daca arborele are un singur nod, radacina, afirmatia este evidenta.

P(n) Presupunem ca pentru 'kI afirmatia este adevarata, adica pentru orice pereche de secvente inordinepreordine de lungime k, arborele binar corespunzator este unic.

P(n+1) Sa demonstram ca orice pereche de secvente preordine-inordine de lungime n+1 determina in mod unic un arbore binar.

Sa consideram o pereche de secvente preordine-inordine de lungime n+1. Primul nod din parcurgerea in preordine este in mod necesar radacina arborelui, celelalte n noduri fiind distribuite in subarbori: toate nodurile situate in stanga radacinii in parcurgerea in inordine vor constitui subarborele stang, nodurile situate in dreapta radacinii in parcurgerea inordine vor constitui subarborele drept.

Obtinem doua perechi de secvente preordine-inordine de lungime cel mult n, care din ipoteza inductiva, determina in mod unic subarborele stang, respectiv cel drept si in consecinta, cum radacina este in mod unic determinata, deducem ca perechea de secvente preordine-inordine de lungime n+1 determina in mod unic un arbore binar cu n noduri.

Q.E.D.

Vom descrie o functie recursiva ConstrArb, care determina arborele binar corespunzator unei perechi de secvente preordine-inordine date. Pentru simplificare, vom considera ca nodurile arborelui sunt numerotate in preordine de la 1 la n. Astfel, este suficient sa retinem intr-un vector global i indicii varfurilor in ordinea in care au fost atinse in inordine. Initial, apelam ConstrArb(1,1,n).

function ConstrArb (rad, st, dr): ArboreBinar;

//functia intoarce radacina arborelui unic determinat de parcurgerile //inordine-preordine

//rad este indicele radacinii arborelui

//st si dr sunt limitele intre care se gaseste parcurgerea inordine a //arborelui in vectorul i

var r: ArboreBinar;

IPozRad: byte;

begin

new(r); //aloc memorie pentru radacina arborelui

r^.c := rad; //retinem drept informatie numarul asociat nodului

IPozRad := st;

// determin pozitia radacinii arborelui in parcurgerea inordine

while i[IPozRad] rad do inc(IPozRad);

if IPozRad = st then //subarborele stang este vid

r.st^ := nil

else

// i[ st.. IPozRad-1] contine subarborele stang

r.st^ := ConstrArb(rad+1, st, IPozRad-1);

if IPozRad = dr then //subarborele drept este vid

r.dr^:=nil

else

// i[ IPozRad+1.. dr] contine subarborele drept

r.dr^ := ConstrArb(rad+IPozRad-st+1, IPozRad+1, dr);

// in subarborele stang au fost IPozRad-st+1 varfuri

end;

1.7. Numararea arborilor binari*

Se pune problema determinarii numarului de arbori binari distincti cu n noduri, facand abstractie, bineinteles de numerotarea nodurilor.

Pentru n=0 sau n=1 exista un singur arbore binar.

Daca n=2, exista doi arbori binari distincti.

Fig. 20.

Pentru n=3, exista 5 astfel de arbori.

Fig. 21.

Notam cu bn numarul arborilor binari distincti cu n noduri.

Evident, b0 = 1.

Pentru n > 0 arborii sunt formati din radacina si doi subarbori cu i, respectiv n-i-1 noduri (0 i < n).

Pentru a obtine numarul arborilor binari distincti cu n noduri este suficient sa rezolvam aceasta relatie de recurenta. Sa consideram functia

Din relatia de recurenta, inmultind ambii membri cu xn ,obtinem :

Sumand dupa n 1, obtinem :

Obtinem B(x)-b0 = x*B2(x) xB2(x) - B(x)+1 = 0.

Rezolvand aceasta ecuatie de grad II obtinem :

Dezvoltand binomial (1-4x)1/2 , obtinem:

Notand n-1 cu m, obtinem:

Cum bn este coeficientul lui xn in B(x) obtinem

Numarul arborilor binari distincti cu n varfuri va fi aproximativ

Observatii

1. Am demonstrat ca fiecarui arbore binar ii corespunde o singura pereche de secvente preordine-inordine. Considerand nodurile numerotate in preordine, rezulta ca arborii binari sunt definiti de permutarile inordine distincte (permutarile distincte ce se pot obtine trecand numerele 1,2,,n intr-o stiva si stergandu-le in toate modurile posibile).

Deci numarul permutarilor inordine de n elemente este

2. O problema care are in mod surprinzator legatura cu cele precedente este calculul produsului a n+1 matrici, M0,M1,,Mn. Cum inmultirea matricilor este asociativa, am dori sa stim in cate moduri putem calcula produsul M0M1Mn.

Pentru n = 1 exista o singura posibilitate.

Pentru n = 2 exista doua posibilitati: (M0M1) M2 sau M0(M1M2).

Pentru n = 3 exista cinci posibilitati :

((M0M1) M2) M3;

(M0M1) (M2M3);

(M0(M1M2)) M3;

M0((M1M2) M3 );

M0(M1(M2M3)).

Notam cu P(n) numarul de moduri distincte in care putem calcula produsul M0M1Mn.

Produsul M0M1Mn poate fi impartit intr-un produs de doua produse de matrici : (M0M1Mk)(Mk+1Mn ).

Acestei asocieri i se poate pune in corespondenta un arbore binar:

Fig. 22.

Deci numarul de parantezari posibile pentru produsul a n+1 matrici coincide cu numarul arborilor binari distincti cu n noduri.

1.8. Paduri

Definitie

O padure este un ansamblu de n 0 arbori disjuncti.

De exemplu,

Fig. 23.

Indepartand radacina din orice arbore obtinem o padure formata din subarborii radacinii.

Orice padure poate fi reprezentata ca un arbore binar. Pentru aceasta, transformam arborii din care este constituita padurea in arbori binari, utilizand reprezentarea fiu-frate. Apoi construim arborele binar corespunzator padurii, utilizand campul frate al radacinii fiecarui arbore.

De exemplu, pentru padurea din figura 24 arborele binar asociat este

Fig. 24.

Definitie

Fie A1, A2, , An arborii unei paduri. Atunci arborele binar corespunzator padurii, B(A1, A2, , An) este:

1.vid, daca n = 0;

2.are radacina egala cu radacina lui A1, subarborele stang este arborele corespunzator padurii formata din subarborii lui A1, iar subarborele drept este arborele binar corespunzator padurii formata din arborii A2, , An.

Operatiile de parcurgere a unei paduri se reduc la parcurgerea arborelui corespunzator.

Fig. 25.

1.9. Probleme rezolvate

1.9.1. Arbori binari m-ponderati

-Olimpiada de informatica faza judeteana, Iasi 1995-

Un arbore binar strict se numeste m-ponderat daca fiecare nod i are asociata o pondere p[i], cu valori intre 1 si m-1, astfel incat pentru orice nod terminal t suma ponderilor din nodurile aflate pe drumul de la radacina la nodul t este egala cu m.

Definim Pn,m(T) ponderea unui arbore binar strict cu n noduri terminale m-ponderat ca fiind suma ponderilor atasate nodurilor din T. Sa se scrie un program care pentru n si m dati determina un arbore binar strict m-ponderat cu n noduri terminale T* astfel incat:

Pn,m(T*)=max

Solutie:

Pentru ca problema sa admita solutie trebuie ca pentru orice drum de la radacina la un nod terminal sa putem asocia nodurilor ponderi 1.

Inaltimea minima a unui arbore cu n varfuri terminale este h=[log2n]. Pentru a asocia ponderi este necesar ca m, suma ponderilor varfurilor de pe orice drum de la radacina la un varf terminal, sa fie cel putin egala cu [log2n]+1.

Deci conditia necesara pentru ca problema sa admita solutie este m [log2n]+1.

Observatii

1. Fie T un arbore binar strict cu n varfuri terminale. Construim o m-ponderare po a arborelui T astfel:

-asociem fiecarui nod interior ponderea 1.

-deoarece suma ponderilor de pe orice drum de la radacina la un varf terminal trebuie sa fie egala cu m, asociem fiecarui nod terminal o pondere egala cu m-lungimea drumului de la radacina la nodul terminal respectiv.

Demonstram ca po este o m-ponderare maximala pentru arborele T.

Sa consideram p o m-ponderare oarecare pentru arborele T si x un varf interior astfel incat p[x]>1. Daca exista mai multe astfel de noduri, consideram un varf de pe un nivel de rang minim. Fie y si z cei doi fii ai lui x. Construim o alta m-ponderare p a lui T astfel:

p[x] = 1; p[y] = p[y]+p[x]-1; p[z] = p[z]+p[x]-1.

Atunci P(T) = P(T)-p[x]-p[y]-p[z]+p[x]+p[y]+p[z] T

P(T) = P(T) -p[x]-p[y]-p[z]+1+ p[y]+p[x]-1+ p[z]+p[x]-1 T



P(T) = P(T)+p[x]-1 T P(T) > P(T).

Modificand succesiv ponderile nodurilor interioare de sus in jos, obtinem dupa un numar finit de pasi m-ponderarea po, in care toate varfurile interioare au ponderea 1.

Deci Po(T) P(T), 'p o m-ponderare a arborelui T

2. Observatia 1. ofera o modalitate de m-ponderare optimala a unui arbore binar strict dat. Ramane sa determinam, pentru n si m dati, arborele binar strict cu n varfuri terminale care maximizeaza Pn,m(T). Demonstram ca arborele cautat T* este arborele binar complet. Fie T un arbore binar strict cu n varfuri terminale care nu este complet si fie x si y doua varfuri terminale fii ai aceluiasi nod interior, situate pe nivelul i, iar z un nod terminal situat pe nivelul j, astfel incat i-j > 1.

Fig. 26.

Mutam nodurile x si y de pe nivelul i pe nivelul j+1, ca fii ai nodului z si reponderam nodurile.

P(T) = P(T)-2(m-i+1)-1-(m-j+1)+2(m-j)+m-i+2+1 T

P(T) = P(T)+i-j-1 > P(T).

Aplicam succesiv aceasta transformare pana cand obtinem un arbore binar complet.

Deci P(T*) > P(T), 'T arbore binar strict.

Q.E.D.

Reprezentarea informatiilor

Arborele cautat fiind complet, pentru implementare alegem reprezentarea secventiala.

program arbore_m_ponderat;

uses crt;

const NMaxVfT=20;

NMaxVf=2*NMaxVfT-1;

type Vf=0..NMaxVf;

arbore_ponderat=array[Vf] of word;

var n,i,nivel:Vf;

m:word;

p:arbore_ponderat;

procedure afisare;

const pst=13;

pdr=28;

pp=42;

var i:Vf;

begin

writeln('Nodul Fiu stang Fiu drept Pondere');

for i:=1 to n-1 do

begin

write(i);

gotoxy(pst,wherey);write(2*i);

gotoxy(pdr,wherey);write(2*i+1);

gotoxy(pp,wherey);writeln(1);

end;

for i:=n to 2*n-1 do

begin

write(i);

gotoxy(pp,wherey);writeln(p[i]);

end

end;

begin

clrscr;

write('n=');readln(n);

write('m=');readln(m);

if m<trunc(ln(n)/ln(2))+1

then writeln('Nu exista solutie!')

else

begin

for i:=1 to n-1 do p[i]:=1;

for i:=n to 2*n-1 do

begin

nivel:=trunc(ln(i)/ln(2));

p[i]:=m-nivel;

end;

afisare

end;

readln

end.

1.9.2. Interclasarea optimala a n siruri ordonate

Fie n secvente S1,S2,,Sn de lungimi respectiv L1,L2,,Ln, ordonate nedescrescator. Sa se interclaseze cele n secvente.

Solutie:

1. Notam cu m L1+L2++Ln.

O prima solutie ar fi sa selectam la fiecare pas articolul cu cheia cea mai mica si sa-l plasam in sirul rezultat. Pentru selectarea minimului ar fi necesare n-1 comparatii, deci algoritmul ar fi de O(nm).

2. Vom utiliza un arbore de selectie.

Definitie

Numim arbore de selectie un arbore binar complet in care fiecare nod este cel mai mic dintre fiii sai.

Observatie

Fiecare nod din arbore are asociata ca valoare minimul valorilor nodurilor din subarborele corepunzator.

Vom construi arborele de selectie in mod bottom-up, apoi la fiecare pas selectam minimul, care este radacina arborelui si restructuram arborele.

Constructia arborelui de selectie este de O(n), restructurarea arborelui, care se repeta de m ori, de O(log n). Deci algoritmul va fi de O(m log n).

Reprezentarea informatiilor

Arborele de selectie fiind complet, vom utiliza reprezentarea secventiala.

program interclasare_optimala;

const NMaxSecv=20;

LgMaxSecv=50;

type Ind=1..LgMaxSecv;

Secv=1..NMaxSecv;

Nod=1..2*NMaxSecv;

Arbore=array[Nod] of integer;

var l:array[Secv] of Ind;

n:Secv;

m,k:word;

o:array[1..LgMaxSecv*NMaxSecv] of integer;

s:array[Secv,Ind] of integer;

A:Arbore;

j:array[Secv] of Ind;

procedure citire;

var f:text;

i:Secv;

j:Ind;

begin

assign(f,'int.in'); reset(f);

readln(f,n);

for i:=1 to n do read(f,l[i]);

readln(f);

for i:=1 to n do

begin

m:=m+l[i];

s[i,l[i]+1]:=MaxInt;

for j:=1 to l[i] do read(f,s[i,j]);

readln(f);

end;

close(f);

end;

procedure ConstrArbSel;

var i:Nod;

begin

for i:=n to 2*n-1 do A[i]:=s[i-n+1,1];

for i:=n-1 downto 1 do

if A[2*i]<A[2*i+1] then

A[i]:=A[2*i]

else

A[i]:=A[2*i+1];

for i:=1 to n do j[i]:=1;

end;

procedure restructurare;

var i,tata,frate:Nod;

begin

i:=1;

while i<=n-1 do

if A[i]=A[2*i] then

i:=2*i

else

i:=2*i+1;

inc(j[i-n+1]);

A[i]:=s[i-n+1,j[i-n+1]];

while i>1 do

begin

tata:=i div 2;

if i=2*tata then frate:=2*tata+1

else frate:=2*tata;

if A[i]>A[frate] then A[tata]:=A[frate]

else A[tata]:=A[i];

i:=tata;

end;

end;

procedure afisare;

var i:word;

begin

writeln('Rezultatul interclasarii: ');

for i:=1 to m do

write(o[i],' ');

writeln;

readln

end;

begin

citire;

ConstrArbSel;

for k:=1 to m do

begin

o[k]:=A[1];

restructurare;

end;

afisare;

end.

1.9.3. O reprezentare a arborilor binare stricti

-problema propusa de Horia Georgescu, G.I. nr.10/1993-

Fie urmatorul arbore binar strict

Fig. 27.

Codificam drumurile de la radacina la nodurile terminale marcand cu 0 fiecare deplasare la stanga si cu 1 fiecare deplasare la dreapta. Concatenand codificarile in preordine, obtinem o reprezentare a arborilor binari stricti.

Pentru exemplul din figura 27 codificarea este 00010001010111.

Problema

Data fiind s, reprezentarea unui arbore binar strict obtinuta prin concatenarea in preordine a codificarilor drumurilor de la radacina la nodurile terminale, generati arborele corespunzator.

Solutie:

Fie x, y doua noduri terminale, situate pe nivelul maxim in arbore, fii ai aceluiasi nod t. Daca notam p secventa ce codifica drumul de la radacina la t, atunci sirul s are forma ap0p1b. Determinam p astfel incat s = ap0p1b, p fiind cea mai lunga secventa cu aceasta proprietate. De exemplu, pentru codificarea de mai sus p = 010.

Putem construi astfel un drum de la radacina arborelui la doua noduri terminale frati.

Fig. 28.

Eliminam din s secventa 0p1, ceea ce corespunde eliminarii din arbore a doua noduri terminale fii ai aceluiasi nod. Obtinem, de exemplu, s = 000100111.

Am redus problema la generarea unui arbore cu un nod terminal mai putin, pe care il vom suprapune peste drumul generat anterior.

program Generare_Arbore_Binar_Strict;

uses crt;

type Arbore=^NodArbore;

NodArbore= record

st,dr:Arbore

end;

var s:string;

f:text;

n, poz, NrNod, lg, NrTest: byte;

A, T: Arbore;

procedure procesare(var poz, lg: byte);

var i,j: byte;

begin

lg:=0; poz:=1;

i:=1;

while i<=n-2*lg-1 do

begin

j:=lg+1;

while i+2*j<n do

begin

while (i+2*j<n) and (s[i+j]<>'0') do inc(j);

if i+2*j<n then

if (copy(s,i,j)=copy(s,i+j+1,j)) and (s[i+2*j+1]='1')

then begin

lg:=j;

poz:=i

end;

inc(j);

end;

inc(i)

end;

end;

procedure ConstrDrum;

var q, x: Arbore;

gata: boolean;

i: byte;

begin

q:=A; i:=poz;

gata:=false;

while not gata and (i<poz+lg) do

if s[i]='0' then

if q^.st<>nil then

begin

q:=q^.st;

inc(i)

end

else gata:=true

else

if q^.dr<>nil then

begin

q:=q^.dr;

inc(i)

end

else gata:=true;

while i<poz+lg do

begin

new(x);

x^.st:=nil; x^.dr:=nil;

if s[i]='0' then

q^.st:=x

else

q^.dr:=x;

q:=x;

inc(i)

end;

new(x);

x^.st:=nil; x^.dr:=nil;

if q^.st=nil then q^.st:=x;

new(x);

x^.st:=nil; x^.dr:=nil;

if q^.dr=nil then q^.dr:=x;

end;

procedure scrie(x: Arbore; niv, st, dr: byte);

var poz: byte;

begin

if x<>nil then

begin

poz:=(st+dr)div 2;

gotoxy(poz,niv);

write(NrNod);inc(NrNod);

scrie(x^.st, niv+2, st, poz-1);

scrie(x^.dr, niv+2, poz+1, dr);

end;

end;

procedure afisare;

begin

clrscr;

inc(NrTest);

NrNod:=1;

writeln('Testul nr. ', NrTest,':');

scrie(A,2,1,80);

readln;

end;

begin

assign(f,'a.in');

reset(f);

while not seekeof(f) do

begin

readln(f,s);

new(A);

A^.st:=nil; A^.dr:=nil;

repeat

n:=length(s);

procesare(poz,lg);

ConstrDrum;

delete(s,poz+lg,lg+2);

until n=0;

afisare;

end;

readln

end.

1.10. Exercitii

1.     Demonstrati ca in orice graf G = (V, U) conex, U V-1.

2.     Demonstrati ca in orice arbore exista cel putin doua varfuri terminale.

3. Calculati numarul arborilor cu n varfuri si secventa gradelor varfurilor d1,d2,,dn (di 1, 'iI, d1+d2++dn = 2n-2). Scrieti un program de generare a tuturor arborilor cu secventa gradelor data.

4. Calculati numarul arborilor cu n varfuri, dintre care p terminale.

5. Secventele obtinute prin parcurgerile in postordine si in inordine ale unui arbore binar definesc in mod unic arborele? Daca da, scrieti un algoritm de generare a arborelui binar corespunzator.

Aceeasi problema pentru parcurgerile in preordine si in postordine, respectiv parcurgerea in inordine si parcurgerea pe niveluri.

6. Generati toti arborii binari distincti cu n varfuri.

7. Scrieti o functie de duplicare a unui arbore binar.

8. Scrieti o functie de cautare a unei valori de tipul informatiei asociate nodurilor intr-un arbore binar. Analizati complexitatea functiei.

9. Scrieti o procedura iterativa de parcurgere in preordine a unui arbore binar.

10. Scrieti o procedura iterativa de parcurgere in postordine a unui arbore binar.

11. Scrieti o functie de stergere a unui arbore binar.

12.Scrieti un program care sa parcurga un arbore oarecare in reprezentarea fiu-frate pe niveluri.

13. Definim gradul unui arbore cu radacina ca fiind gradul maxim al nodurilor sale. Fie un arbore cu gradul k si inaltimea h. Care este numarul maxim de noduri din acest arbore ?

Reprezentam fiecare nod al arborelui printr-un articol ce contine informatia asociata nodului si k pointeri spre radacinile subarborilor :

Arbore = ^NodArbore;

NodArbore = record

c: TipInf;

leg: array[1..k] of Arbore;

end;

a). Scrieti o functie de creare a unui arbore echilibrat de grad k.

b). Descrieti algoritmul de parcurgere pe niveluri si in adancime a unui arbore de grad k.

c). Scrieti o functie care sa determine inaltimea unui arbore de grad k.

d). Scrieti o functie care sa testeze egalitatea a doi arbori de grad k.

14. Scrieti o functie care sa determine numarul de noduri terminale ale unui arbore binar.

15. Scrieti un algoritm care, dat fiind un arbore binar, schimba fiul stang cu fiul drept, pentru orice nod din arbore. De exemplu :

Fig. 29.

16. Demonstrati ca orice arbore binar este 2-colorabil.

17. Fie P un poligon convex. O diagonala este un segment ce uneste doua varfuri neadiacente. Numim triangularizare a poligonului convex P o multime de diagonale care impart poligonul in triunghiuri disjuncte.

Calculati numarul triangularizarilor posibile pentru un poligon convex cu n varfuri.

18. Scrieti o functie care sa verifice daca un arbore binar este strict.

19. Calculati numarul arborilor binari de inaltime h.

20. Scrieti un program care sa construiasca arborele binar corespunzator padurii formate din arborii A1, A2, , An si parcurgeti arborele in preordine, inordine, postordine.

21. Fie P o padure, arborii componenti fiind reprezentati prin referinte ascendente. Scrieti un algoritm care sa determine pentru oricare doua varfuri din padure cel mai apropiat ascendent comun, daca acesta exista. Analizati complexitatea algoritmului.

22. 'Problema' telefonistelor

O retea telefonica formata din n centrale numerotate de la 1 la n, are forma unui arbore oarecare. Telefonista de la centrala k, 1 k n, care a intrat in posesia unei informatii importante, arde de nerabdare s-o impartasesca tuturor colegelor ei. Stiind ca fiecare telefonista poate vorbi la un moment dat doar cu una dintre vecinele ei, ca o convorbire dureaza un minut si ca fiecare telefonista, dupa ce a intrat in posesia informatiei se grabeste sa o comunice celorlalte vecine ale ei care n-au aflat-o inca, sa se determine succesiunea propagarii in timp a informatiei si timpul minim necesar ca toate telefonistele sa cunoasca vestea pornita de la centrala k.


Anexa

program Constructie_arbore_cu_secventa_gradelor_data;

const NMaxVf = 20;

type Vf = 1..NMaxVf;

var a, d: array[Vf] of Vf;

n, i, VfT, VfNt: Vf;

s: byte;

fout: text;

procedure citire;

var i: Vf;

fin: text;

begin

assign(fin, 'grade.in'); reset(fin);

readln(fin, n);

for i := 1 to n do read(fin, d[i]);

readln(fin);

close(fin);

end;

procedure afisare;

var i: Vf;

begin

writeln(fout, 'Muchiile arborelui sunt: ');

for i := 1 to n-1 do write (fout, '(', i, ',', a[i], ') ');

writeln(fout);

end;

begin

citire;

assign(fout,'grade.out'); rewrite(fout);

s := 0;

for i := 1 to n do s := s+d[i];

if s <> 2*(n-1)then

writeln(fout,'Secventa eronata! Suma gradelor trebuie sa fie 2(n-1)!')

else

for VfT := 1 to n-1 do

begin

VfNt := VfT+1;

while (VfNt < n) and (d[VfNT] = 1) do inc(VfNt);

a[VfT] := VfNt;

dec(d[VfNT]);

end;

afisare;

close(fout);

end.

De exemplu, pentru fisierul de intrare:

7

1 1 1 2 2 2 3

fisierul de iesire va contine:

Muchiile arborelui sunt:

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

program Generare_Arbori_cu_n_Varfuri;

const NrMaxVf=10;

type Vf = 1..NrMaxVf;

Arbore = array[Vf] of Vf;

var n: Vf;

fout: text;

a: Arbore;

NrArb: longint;

procedure determina_arbore;

var MB, MA: set of Vf;

i, k: Vf;

begin

inc(NrArb);

write(fout, 'Arborele nr. ',NrArb,' :');

MB := []; MA := [];

for i := 1 to n-1 do MA := MA+[a[i]];

for i := 1 to n-1 do

begin

k := 1;

while k in MA+MB do inc(k);

MB := MB+[k];

MA := MA-[a[i]];

write(fout, '(', k, ',', a[i], ') ');

end;

writeln(fout);

end;

procedure generare(i: Vf);

var j: Vf;

begin

if i = n-1 then

determina_arbore

else

for j := 1 to n do

begin

a[i] := j;

generare(i+1);

end;

end;

begin

write('Introduceti numarul de varfuri '); readln(n);

a[n-1] := n;

NrArb := 0;

assign(fout,'arbnvf.out');

rewrite(fout);

generare(1);

close(fout);

end.

De exemplu, pentru n=4, continutul fisierului de iesire va fi:

Arborele nr. 1 :(2,1) (1,1) (3,4)

Arborele nr. 2 :(3,1) (1,2) (2,4)

Arborele nr. 3 :(2,1) (1,3) (3,4)

Arborele nr. 4 :(2,1) (1,4) (3,4)

Arborele nr. 5 :(3,2) (2,1) (1,4)

Arborele nr. 6 :(1,2) (2,2) (3,4)

Arborele nr. 7 :(1,2) (2,3) (3,4)

Arborele nr. 8 :(1,2) (2,4) (3,4)

Arborele nr. 9 :(2,3) (3,1) (1,4)

Arborele nr. 10 :(1,3) (3,2) (2,4)

Arborele nr. 11 :(1,3) (2,3) (3,4)

Arborele nr. 12 :(1,3) (2,4) (3,4)

Arborele nr. 13 :(2,4) (3,1) (1,4)

Arborele nr. 14 :(1,4) (3,2) (2,4)

Arborele nr. 15 :(1,4) (2,3) (3,4)

Arborele nr. 16 :(1,4) (2,4) (3,4)

program Operatii_pe_arbori_binari;

const NrMaxVf = 20;

type Vf = 0..NrMaxVf;

ArboreBinar = ^NodArboreBinar;

NodArboreBinar = record

inf: char;

st, dr: ArboreBinar;

end;

var n: Vf;

fin, fout: text;

A: ArboreBinar;

function CreareArbore(x: Vf): ArboreBinar;

var rad: ArboreBinar;

begin

if x = 0 then

CreareArbore := nil

else

begin

new(rad);

read(fin, rad^.inf);

rad^.st := CreareArbore(x div 2);

rad^.dr := CreareArbore(x-x div 2 -1);

CreareArbore:=rad;

end;

end;

procedure preordine(rad: ArboreBinar);

begin

if rad <> nil then

begin

write(fout, rad^.inf);

preordine(rad^.st);

preordine(rad^.dr);

end

end;

procedure postordine(rad: ArboreBinar);

begin

if rad <> nil then

begin

postordine(rad^.st);

postordine(rad^.dr);

write(fout, rad^.inf);

end

end;

procedure inordine_iterativ(rad: ArboreBinar);

type Stiva = ^NodStiva;

NodStiva = record

inf: ArboreBinar;

urm: Stiva

end;

var S, p: Stiva;

NodCurent: ArboreBinar;

begin

write(fout, 'Parcurgerea inordine: ');

S := nil;

NodCurent := rad;

repeat

while NodCurent <> nil do

begin

new(p); p^.inf := NodCurent; p^.urm := S; S := p;

NodCurent := NodCurent^.st;

end;

if S <> nil then

begin

p := S; S := S^.urm;

write(fout, p^.inf^.inf);

NodCurent := p^.inf^.dr;

dispose(p);

end;

until (S = nil) and (NodCurent = nil);

writeln(fout);

end;

procedure parcurgere_pe_niveluri(rad: ArboreBinar);

type Coada = ^NodCoada;

NodCoada = record

inf: ArboreBinar;

urm: Coada

end;

var IncC, SfC, p, q: Coada;

begin

write(fout, 'Parcurgerea pe niveluri: ');

if rad <> nil then

begin

new(IncC); IncC^.inf := rad; IncC^.urm := nil; SfC := IncC;

while IncC <> nil do

begin

p := IncC;

write(fout, p^.inf^.inf);

if p^.inf^.st <> nil then

begin

new(q); q^.inf := p^.inf^.st; q^.urm := nil;

SfC^.urm := q; SfC := q

end;

if p^.inf^.dr <> nil then

begin

new(q); q^.inf := p^.inf^.dr; q^.urm := nil;

SfC^.urm := q; SfC := q

end;

IncC := IncC^.urm;

dispose(p)

end;

end;

writeln(fout)

end;

function max(a, b: integer): integer;

begin

if a > b then max := a

else max := b

end;

function inaltime(rad: ArboreBinar): integer;

begin

if rad = nil then

inaltime := -1

else

inaltime := max(inaltime(rad^.st), inaltime(rad^.dr))+1;

end;

begin

assign(fin,'opbin.in'); reset(fin);

assign(fout,'opbin.out'); rewrite(fout);

readln(fin,n);

A:=CreareArbore(n);

close(fin);

write(fout,'Parcurgerea preordine: '); preordine(A);

writeln(fout);

write(fout,'Parcurgerea postordine: '); postordine(A);

writeln(fout);

inordine_iterativ(A);

parcurgere_pe_niveluri(A);

writeln(fout, 'Inaltimea arborelui este: ', inaltime(A));

close(fout);

end.

program Constructie_Arbore_Binar;

const NrMaxVf = 20;

type Vf = 0..NrMaxVf;

ArboreBinar = ^NodArboreBinar;

NodArboreBinar = record

inf: Vf;

st, dr: ArboreBinar;

end;

Parcurgere = array[Vf] of Vf;

var A: ArboreBinar;

i: Parcurgere;

n: Vf;

fout: text;

function ConstrArb(rad, st, dr: Vf): ArboreBinar;

var r: ArboreBinar;

IPozRad: Vf;

begin

new(r); r^.inf := rad;

IPozRad := st;

while i[IPozRad] <> rad do inc(IPozRad);

if IPozRad = st then

r^.st := nil

else

r^.st := ConstrArb(rad+1,st,IPozRad-1);

if IPozRad = dr then

r^.dr := nil

else

r^.dr := ConstrArb(rad+IPozRad-st+1,IPozRad+1,dr);

ConstrArb := r;

end;

procedure Citire;

var k: Vf;

fin: text;

begin

assign(fin,'pi.in'); reset(fin);

readln(fin,n);

for k := 1 to n do read(fin, i[k]);

readln(fin);

close(fin);

end;

procedure preordine(rad: ArboreBinar);

begin

write(fout, rad^.inf, '(');

if rad^.st <> nil then preordine(rad^.st);

write(fout, ',');

if rad^.dr <> nil then

preordine(rad^.dr);

write(fout, ')');

end;

procedure AfisareArb;

begin

assign(fout,'pi.out'); rewrite(fout);

if A = nil then

write(fout, 'Arbore vid')

else

preordine(A);

writeln(fout);

close(fout);

end;

begin

Citire;

if n > 0 then

A := ConstrArb(1, 1, n)

else

A := nil;

AfisareArb;

end.

De exemplu, pentru fisierul de intrare:

10

3 4 5 2 6 1 8 7 10 9

fisierul de iesire va fi:

1(2(3(,4(,5(,))),6(,)),7(8(,),9(10(,),)))

program Numar_Arbori_Binari_Distincti;

var NrVf, i: byte;

NrArb: extended;

begin

write('Introduceti numarul de varfuri '); readln(NrVf);

NrArb := 1;

for i := 2 to NrVf do

NrArb := NrArb*(NrVf+i)/i;

writeln('Nr. de arbori binari distincti cu ',NrVf,'varfuri: ');

writeln(NrArb:50:0);

readln

end.





* Programul Constructie-Arbore-cu-Secventa-Gradelor-Data de la sfarsitul capitolului curent genereaza un arbore avand secventa gradelor data.

* Programul Generare-Arbori-cu-n-Varfuri de la sfarsitul capitolului curent genereaza toti arborii cu n varfuri date.

* Programul Operatii-pe-Arbori-Binari implementeaza operatiile pe arbori binari prezentate.

* Programul Constructie-Arbore-Binar-cu-Secventele-Preordine-Inordine-Date genereaza un arbore binar pentru care se cunosc parcurgerile in preordine si inordine.

* Programul Numar-Arbori-Binari-Distincti afiseaza numarul arborilor binari distincti cu n varfuri date.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1640
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site