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

c

+ Font mai mare | - Font mai mic



DOCUMENTE SIMILARE

Trimite pe Messenger
Tablouri de pointeri, pointeri pe pointeri
Notiunea de tablou
Modifica informatia nodului cu info=para din lista
Probleme rezolvate in C la informatica
Structura de tip coada
Prezentarea generala a notiunii de limbaj de programare
Verificarea existentei elementelor sortate crescator din lista
RECURSIVITATE – probleme rezolvate
Adaugarea unui element la sfarsitul listei
OPERATORI DE PRELUCRARE LA NIVEL DE BIT

TERMENI importanti pentru acest document

:

Arbori

Un arbore reprezinta o multime nevida si finita de elemente de acelasi fel, pe care le denumim noduri:

 ,

            Proprietatile arborelui sunt:

1.       exista un singur nod numit radacina

2.       nodurile diferite de radacina formeaza submultimi disjuncte – denumite subarbori.

3.       Fiecare subarbore respecta proprietatile 1 si 2.

Arborii sunt structuri de date de natura dinamica si recursiva (ca si listele). Reprezentarea grafica a unui arbore oarecare este ilustrata mai jos:

Nodurile arborelui pot fi:

-          nodul radacina (fiecare arbore are un singur nod de acest tip)

-          noduri interne

-          noduri terminale (frunze)

Nodul radacina se distinge de celelalte noduri prin faptul ca nu acesta nu are succesori (noduri care il preced ).

Nodurile interne sunt precedate de 1 singur nod si pot fi urmate de 1 sau mai multe noduri.

Nodurile terminale sunt precedate de 1 singur nod si sunt urmate de 0 noduri.

Terminologia specifica incorporeaza denumirile de parinte pentru nodul care preced alte noduri, fii, pentru nodurile care urmeaza un nod parinte si frati – pentru nodurile care au acelasi parinte.

Nodurile unui arbore se caracterizeaza prin doua marimi:

- Nivelul nodului: reprezinta o valoarea naturala prin care se identifica numarul de stramosi  pana la nodul radacina.

o        Nodul radacina este considerat pe nivelul 1

o        Fiii nodului radacina sunt pe nivelul 2

o        Fiii fiilor nodului radacina sunt pe nivelul 3

o        etc.

- Ordinul nodului:  este un numar natural si reprezinta numarul de descendenti directi  (fii) pe care ii are nodul respectiv. Nodurile terminale au ordinul 0.

Nivelele nodurilor in arbore

Nodul

Ordinul nodului

1

O(1)=2

2

O(2)=3

3

O(3)=0

4

O(4)=2

5

O(5)=0

6

O(6)=1

7

O(7)=0

8

O(8)=0

9

O(9)=0

Ordinul fiecarui nod din arborele prezentat ca exemplu

Fiecare subarbore al arborelui este caracterizat prin inaltimea sa, marime care reprezinta numarul de nivele pe care le contine subarborele respectiv.

Un nod al arborelui contine:

a.       zona de date

b.       1 sau mai multe legaturi spre fii sai

Daca intre fiii oricarui nod exista o relatie de ordine, spunem ca arborele respectiv este arbore ordonat.

Daca numarul de fii ai fiecarui nod din compunerea unui arbore este 0,1 sau 2, atunci arborele respectiv este numit arbore binar. Structura unui nod al arborelui binare contine:

-          zona de informatii

-          legatura spre fiul stang

-          legatura spre fiul drept

Intr-un arbore binar, exista posibilitatea ca una sau ambele legaturi ale unui parinte spre fiii sai sa fie nule. Nodurile terminale au ambele legaturile nule. Anumite noduri interne pot sa aiba doar un fiu, astfel incat legatura spre celalalt fiu este nula.

Importanta studierii arborilor binari este data de multitudinea de aplicatii practice in care se face uz de aceasta structura de date. In plus, un arbore poate fi transformat si reprezentat prin arbore binar. Transformarea presupune etapele urmatoare:

1.    se stabileste legatura intre fratii de acelasi parinte

2.    se suprima legaturile dinspre parinte, cu exceptia legaturii cu primului fiu

Exemplu:

Fie arborele oarecare din figura urmatoare:

Figura 1 Arbore oarecare

Dupa transformare, arborele devine binar:

Figura 2 Arbore binar

Parcurgerea arborilor

Parcurgerea (traversarea) arborilor presupune obtinerea unei liste a  nodurilor arborelui. In functie de ordinea in care sunt considerate nodurile arborelui, avem mai multe tipuri de traversare a arborilor.

-          Parcurgerea  in adancime (in depth): se viziteaza subarborii descendenti ai nodului radacina, in aceiasi maniera, apoi se viziteaza nodul radacina. Parcurgerea in adancime a arborelui considerat ca si exemplu in figura 1 produce urmatoarea lista a nodurilor: 7 5 6 2 3 4 1.

-          Parcurgerea  in latime (in breadth): se viziteaza nodurile pe nivele, pornindu-se de la nivelele cele mai de sus (nivelul 1 – radacina) spre nivelele mai mari, si pe fiecare nivel se viziteaza nodurile intr-o anumita ordine, spre ex. de la stanga la dreapta. Parcurgerea in latime a arborelui din figura 1 produce lista: 1 2 3 4 5 6 7.

ARBORI BINARI

Structura unui nod al arborelui binar este urmatoarea:

typedef struct nod

Tnod;

unde:

            st – este un pointer, a carei valoare este adresa fiului stang a nodului curent

            dr – este un pointer, a carei valoare este adresa fiului drept a nodului curent

Absenta unui fiu (stang sau drept) se marcheaza prin valoarea Null (0) a pointer-ului corespunzator.

Gestionarea unui arbore binare este posibila prin adresa nodului radacina:

Tnod *rad;

Operatiile specifice arborilor binari sunt:

1.       crearea arborelui

2.       inserarea unui nod

3.       stergerea unui nod

4.       stergerea arborelui

5.       accesarea unui nod (cautarea)

6.       parcurgerea unui arbore

Operatia de creare a arborelui binar necesita initializarea nodului radacina: rad=0 si adaugarea (inserarea) ulterioara a noilor noduri dupa o anumita regula. Operatiile de inserare si accesare a nodurilor dintr-un arbore binar presupun existenta unui criteriu care se desprinde din specificatiile problemei concrete de rezolvat. Aceste criterii fiind variate, rezolvarea problemelor cu arbori binare se poate simplifica prin considerarea unei functii verifica care are doi parametri: pnod1 si pnod2 – adresele a doua noduri si returneaza valoare -1,0 sau 1 cu semnificatia:

A)    -1 daca pnod2 este adresa unui nod care poate fi accesat sau inserat in stanga nodului adresat de pnod1

B)     +1 daca pnod2 este adresa unui nod care poate fi accesat sau inserat in dreapta nodului adresat de pnod1

C)     0  daca pnod2 refera un nod care NU poate fi accesat sau inserat in subarborii stang sau drept ai nodului referit de pnod2.

Prototipul acestei functii ajutatoare este:

int verifica(Tnod *pnod1 , Tnod * pnod2);

Inserarea unui nou nod presupune:

-          determinarea locului in care va fi inserat noul nod

-          alocarea de memorie si incarcarea cu informatii a nodului nou

-          stabilirea legaturilor in arbore

In privinta locatiei  in care poate fi inserat nodul, aceasta este data de criteriul specificat de problema concreta si se disting urmatoarele cazuri:

-          in pozitia radacinii

-          ca nod terminal

-          ca nod intern

Stergerea unui nod oarecare presupune:

-          determinarea locatiei sale

-          refacerea legaturilor in arbore

-          eliberarea memoriei alocate nodului sters

Stergerea intregului arbore necesita stergeri repetate ale nodurilor sale pana cand radacina devine vida.

Parcurgerea unui arbore binare poate fi facuta in trei moduri:

1.       parcurgerea in preordine: pentru fiecare nod curent se va accesa/prelucra informatia continuta, subarborele stang si in final subarborele drept. (fiecare subarbore va fi parcurs in aceiasi maniera).

-          Simplificat, parcurgerea in preordine a unui arbore presupune parcurgerea in ordinea: R (radacina), S (subarbore stang), S (subarbore stang). R S D

2.       parcurgerea in postordine: pentru fiecare nod curent se va parcurge subarborele stang, subarborele drept si in final se va accesa/prelucra informatia continuta in nodul curent (fiecare subarbore va fi parcurs in aceiasi maniera).

-          Simplificat parcurgerea in postordine inseamna traversarea arborelui in ordinea: S (stang) D(drept) R (radacina)

3.       parcurgerea in inordine: pentru fiecare nod curent se va parcurge subarborele stang, nodul curent si in final subarborele drept (fiecare subarbore va fi parcurs in aceiasi maniera).

-          Simplificat: ordinea de traversare a arborelui este S (stanga) R (radacina) D (dreapta).

Exemplu:

La parcurgerea in preordine a arborelui din figura anterioara se vor accesa nodurile in ordinea: J H E A B F I G C D  

La parcurgerea in postordine se vor accesa nodurile in ordinea:  

A B E F H C G D I J

La parcurgerea in inordine se vor accesa nodurile in ordinea:

A E B H F J I C G D

Functiile de parcurgere a unui arbore binar in cele trei variante (preordine, postordine, inordine) sunt date mai jos:

void  preordine(tnod *p)

}

void inordine(tnod *p)

}

void postordine(tnod *p)

}

Cautarea unui nod

Fiind dat un criteriu de cautare, cautarea intr-un arbore binar presupune parcurgerea nodurilor si verificarea criteriului pentru fiecare nod vizitat.  In cazul in care s-a gasit un nod care respecta criteriul, procesul de parcurgere a arborelui se va incheia. Daca nu se gaseste niciun nod care verifica criteriul, acest lucru trebuie semnalat.

In scopul definirii unei functii de cautare in arborele binar, se considera functia auxiliara prin care se verifica indeplinirea sau neindeplinirea criteriului de cautare si continuare cautarii intr-unul din subarborii stang sau drept ai nodului curent. In mod frecvent, criteriul se refera la indeplinirea conditiei de egalitate intre o valoare data si valoarea unui camp din informatia memorata in noduri. Pentru a generaliza, consideram functia verificare descrisa anterior prin care se decide daca un nod cautat pnod2  este gasit in arbore la adresa pnod1, sau se va continua cautarea in subarborele stang sau drept a nodului adresat de pnod1.

O functie de cautare se poate descrie ca mai jos. Functia returneaza adresa nodului gasit sau 0 in cazul in care nu se gaseste un nod care verifica criteriul stabilit.

tnod *rad; //variabila globala

tnod *cautare(tnod *pnod2)

return 0; //nu s-a gasit nodul cautat

}  

Crearea unui arbore binar

Operatia de creare a unui arbore binar presupune operatii repetate de inserare a unui nou nod ca nod terminat. Pentru fiecare nod care urmeaza sa fie inserat este necesara in prealabil determinarea pozitiei in care acesta va fi adaugat, respectiv, parintele de care acesta se va lega. Nodul parinte se va determina printr-o parcurgere partiala a arborelui.  In realizarea acestei operatii ne putem folosi de functia auxiliara verifica sau o alta functie prin care se decide in care din subarbore va fi continuata cautarea posibilului parinte.

ARBORI BINARI DE CAUTARE

Un caz particular de arbori binari sunt arborii binari de cautare. In plus fata de aspectele mentionate la prezentarea arborilor binari, un arbore de cautare prezinta o caracteristica suplimentara: fiecare nod al sau contine o cheie (camp cu valori unice pentru nodurile arborelui) si:

-          toate nodurile din stanga nodului respectiv au valorile cheilor mai mici decat cheia nodului curent

-          toate nodurile din dreapta nodului respectiv au valorile cheilor mai mari decat cheia nodului curent

Exemplu: Figura alaturata ilustreaza reprezentarea grafica a unui arbore binar de cautare (valoarea cheii este precizata in fiecare nod):

Se poate observa o proprietate importanta a arborilor binari de cautare: la parcurgerea in inordine se obtine lista nodurilor ordonate dupa valoarea cheii. In plus, operatia de cautare a unui nod specificat de valoarea cheii este simplificata  (de aici si denumirea arborilor de cautare).

Cautarea unui nod dupa o cheie data nu necesita parcurgerea intregului arbore. Datorita specificului acestor arbori, valoarea cheii este comparata cu cheia continuta in radacina si in functie de rezultatul comparatiei, cautarea se va continua doar intr-unul dintre cei doi subarbori, celalalt subarbore fiind exclus din cautare. Procedeul se va continua in mod similar pentru subarborele curent: se compara valoarea cheii cautate cu cheia radacinii subarborelui si in functie de rezultatul comparatiei se va continua cautarea doar intr-unul dintre subarborii subarborelui curent. Cautarea se va incheia in momentul in care un nod radacina a subarborelui curent contine cheia cautata sau daca nu mai sunt noduri de parcurs si cheia nu a fost gasita.

Cautarea unei informatii intr-o structura de arbore binar de cautare este eficienta, deoarece numarul nodurilor accesate se reduce prin excluderea acelor subarbori a caror parcurgere ar fi inutila.

Operatiile de inserare si stergere executate asupra unui arbore binar de cautare vor produce de asemenea un arbore binar de cautare. Astfel, in definirea unor functii specifice care opereaza asupra arborilor de cautare se va tine cont de criteriul de ordine intre cheile nodurilor ce formeaza arborele.

  1. Creare arbore binar de cautare. Inserarea nodurilor.

Fiind data o multime de informatii ce trebuie organizate sub forma unui arbore binar de cautare, crearea arborelui se realizeaza in urmatoarele etape:

-                        creare arbore vid

-                        creare arbore cu un singur nod (radacina)

-                        inserare noduri cat timp mai exista informatie de organizat

La fiecare pas de inserare unui nod in arborele deja format se va tine cont de criteriul de ordonare si arborele rezultat va fi tot un arbore binar de cautare.

Daca radacina este vida inainte de inserare, nodul de inserat va deveni radacina arborelui:

rad=nou; rad->st=rad->dr=0;

Daca exista cel putin un nod in arbore, se va cauta  un parinte al nodului de inserat. Acest parinte indeplineasca conditiile:

-   daca cheia continuta de parinte este mai mare decat cheia nodului nou, atunci, parintele trebuie sa aiba legatura stanga vida, pentru a reusi legarea nodului nou in stanga sa (prin aceasta ne asiguram ca subarborele construit, al carei radacina este nodul parinte, este ordonat)

-   daca cheia continuta de parinte este mai mica decat cheia nodului nou, atunci, parintele trebuie sa aiba legatura dreapa vida

    

int inserare(tnod *nou)

   p=rad;

   while(1)

  

      else

         if (p->dr!=0)

               p=p->dr;

         else

              

   }

return 0; //nu s-a realizat operatia, cod de eroare

}

Arborele binar de cautare se poate construi printr-o secventa:

printf('ncate noduri introduceti?'); scanf('%d',&n);

tnod *nou;

rad=0; //arbore vid

for (int i=0;i<n-1;i++)

}

2.      Cautarea unui nod de cheie precizata

Cautarea dupa valoarea cheii este operatia specifica in arborele binar de cautare prin care se determina adresa nodului a carei cheie este egala cu o valoare data. Daca nu se gaseste un astfel de nod, operatia se incheie cu insucces.

Construim mai jos o functie care primeste ca parametru valoarea cheii cautate si returneaza:

-          adresa nodului  gasit, sau

-          0,  in caz de insucces

tnod * cautare(int val)

       if (p->cheie<val)

           

    }

return p; //nu s-a gasit nodul, p este Null

}

  1. Stergere nod de cheie precizata

Stergerea unui nod de cheie precizata, precum si celelalte operatii specifice arborilor de cautare, va produce un arbore cu aceleasi caracteristici (cheile nodurilor raman ordonate dupa stergere).

Prima etapa a operatiei de stergere consta in determinarea nodului de cheie precizata (nodul ce se va sterge). In acest scop este utila o functie care cauta cheia in arbore, insa fata de operatia de cautare descrisa anterior, este nevoie determinarea unui element suplimentar:  adresa parintelui nodului ce va fi sters.

In functie de pozitia nodului de sters: p si a parintelui sau in arbore: parinte, intalnim urmatoarele cazuri:

  1. nodul gasit este nod frunza (nod terminal) si este situat in dreapta parintelui sau:

-          se elibereaza nodul

-          se stabileste legatura dreapta a parintelui ca fiind nula:

parinte->dr=0

  1. nodul gasit este nod frunza (nod terminal) si este situat in stanga parintelui sau:

-          se elibereaza nodul

-          se stabileste legatura stanga a parintelui ca fiind nula:

parinte->st=0

  1. nodul cautat nu este nod terminal, dar are doar un subarbore stang

-          leaga parintele de subarborele stang al nodului de sters:

o        daca nodul este legat in stanga parintelui, atunci

parinte->st=p->st – cazul c.1

o        daca nodul este legat in dreapta parintelui, atunci

parinte->dr = p->st – cazul c.2

-          elibereaza nodul

  1. nodul cautat p nu este nod terminal, dar are doar un subarbore drept

-          leaga parintele de subarborele drept al nodului p:

o        daca nodul este legat in stanga parintelui, atunci

parinte->st=p->dr– cazul d.1

o        daca nodul este legat in dreapta parintelui, atunci

parinte->dr = p->dr – cazul d.2

-          elibereaza nodul

  1. nodul cautat p nu este terminal si are ambii subarbori (legaturile stanga si dreapta sunt nenule).

O alta maniera de stabilire a cazurilor de stergere in arborele binar este data de ordinul nodului ce va fi sters:

Daca nodul are ordinul 0 sau 1 (are maxim un subarbore) este util sa grupam cazurile descrise mai sus a,b,c,d intr-o singura tratare: parintele nodului  p va contine adresa subarborelui lui p (stang sau drept), chiar daca acest subarbore este vid (nodul p este terminal).

Daca ordinul nodului p este 2, se va trata cazul e.

Cazul e este cel mai complex caz de stergere a unui nod. Numim predecesor al nodului p, cel mai din dreapta nod din subarborelui stang al lui p. Numim succesor al nodului p, cel mai din stanga nod din subarborelui drept al lui p. Atat predecesorul cat si succesorul unui nod oarecare, sunt noduri terminale in arborele dat.

Exemplu:

Nodurile predecesor si succesor au proprietate ca sunt nodurile de cheie imediat mai mica, respectiv, imediat mai mare decat cheia nodului p, si sunt noduri cu un singur subarbore, fapt pentru care stergerea nodului p se realizeaza prin:

-          copierea informatiei din predecesor/succesor in nodul p

-          stergerea predecesorului/succesorului nodului p- cazul stergerii unui nod cu un subarbore

Practic, stergerea unui nod cu doi subarbori se transforma intr-o cautare a altui nod care are maxim un subarbore, urmata de stergerea acestuia.

Exemplu:

Figura 3 Inainte de stergerea nodului

Figura 4 Dupa stergerea nodului

Observatii: Daca nodul p ce va fi sters este parintele direct al predecesorului sau, atunci predecesorul este in stanga parintelui sau (in stanga nodului p).

Daca nodul p ce va fi sters nu este parintele direct al predecesorului sau, atunci, predecesorul este legat de parintele sau direct prin legatura dreapta.

Exemplu: In figura anterioara, nodul 4 nu este parintele direct al predecesorului (nodul 3), astfel incat, predecesorul este legat in dreapta parintelui sau direct – nodul 2.

Ne imaginam urmatoarea situatie:

In acest caz, pentru nodul de sters se va actualiza legatura stanga. Dupa operatia de stergere, arborele devine:

Functia de mai jos este o varianta de implementare a algoritmului de stergere a unui nod dintr-un arbore de cautare. Se acorda atentie nodului radacina, acesta fiind un nod important prin care se gestioneaza arborele. Daca acest nod trebuie sters, tratarea cazului se face in mod diferit pentru protejarea adresei de acces la arbore.

void stergere()//stergere nod de cheie data

      if (cheie>p->cheie)

      }//caut p si retine parintele sau

if (p==0)

//cazul I________________________nod frunza

if ((p->st==0)&&(p->dr==0))

  if (tatap->dr==p) //cazul b

}

//cazul II________________________nod cu un subarbore

//cazul c, p are doar subarbore stang

if (p->dr==0)

     

      if (tatap->st==p) // cazul c.1

      if (tatap->dr==p)// cazul c.2

      }//sfarsit caz c

//cazul d, p are doar subarbore drept

if (p->st==0)

     

      if (tatap->st==p) // cazul d.1

      if (tatap->dr==p) // cazul d.1

      }//sfarsit caz d

//cazul e________________________nod cu 2 subarbori

//pas 1 caut predecesor si retin parintele predecesorului

tatapredecesor=p;

predecesor=p->st;

while(predecesor->dr!=0)

      //retin parintele predecesorului

if (tatapredecesor==p)

     

if (tatapredecesor!=p)

     

}//sfirsit functie stergere

  1. Stergere arbore binar de cautare

Stergerea completa a arborelui binar consta in stergerea tuturor nodurilor sale. In acest scop se poate defini o functie recursiva prin care se parcurge arborele in post ordine si vizitarea nodului consta in eliberarea sa. Ultimul nod eliberat este nodul radacina.

void stergere_arbore(tnod *p)

}

Apelul functiei este:

stergere_arbore(rad);

ARBORI BINARI ECHILIBRATI (AVL)

Un caz special de arbori binari ordonati (arbori de cautare) sunt arborii AVL (descrisi de Adelson, Velski, Landis). Acestia au in plus proprietatea de echilibru, formulata prin:

Pentru orice nod al arborelui diferenta dintre inaltimea subarborelui stang al nodului si inaltimea subarborelui drept al nodului este maxim 1.

Fiecarui nod intr-un arbore AVL ii este asociata o marime denumita factor de echilibru. Factorul de echilibru se defineste prin diferenta dintre inaltimile subarborelui drept si inaltimea subarborelui stang, si pentru arborii echilibrati poate fi una dintre valorile -1, 0, +1. Daca factorul de echilibru pentru un nod are alta valoare decat cele enumerate, arborele nu este arbore AVL.

Operatiile posibile asupra arborilor AVL sunt aceleasi operatii ca in cazul arborilor binari ordonati simpli: creare, inserare, stergere, parcurgere, cautare. In schimb, in operatiile asupra arborilor AVL trebuie tinut cont de proprietatea de echilibru din moment ce o operatie de inserare a unui nod  nou sau de stergere a unui nod poate conduce la arbori binari dezechilibrati.

Practica este urmatoarea: operatiile definite pentru arborii de cautare se aplica si asupra arborilor AVL, insa, ulterior, este verificata indeplinirea proprietatii de echilibrare. In cazul in care arborele a devenit dezechilibrat, prin operatii suplimentare se va reorganiza arborele pentru obtine un arbore echilibrat.

Probleme propuse spre rezolvare

1.       Se citeste de la tastatura o expresie matematica in forma prefixata, sub forma unui sir de caractere (operatorul este plasat in fata operanzilor). Sa se construiasca arborele corespunzator acestei expresii. Fiecare nod contine un operator sau un operand. Sa se evalueze expresia.

2.       Sa se scrie o functie care numara intr-un arbore binar ordonat cate noduri contin  chei cu valori cuprinse in intervalul [a,b].

3.       Scrieti o functie care calculeaza nivelul si factorul de echilibrare pentru oricare nod al unui arbore binar.


DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 619
Importanta: rank

Comenteaza documentul:

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

Creaza cont nou

Distribuie URL

Adauga cod HTML in site

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