| CATEGORII DOCUMENTE |
Arbori
Un arbore reprezinta o multime nevida si finita de elemente de acelasi fel, pe care le denumim noduri:
, 
Proprietatile arborelui sunt:
exista un singur nod numit radacina
nodurile diferite de radacina formeaza submultimi disjuncte - denumite subarbori.
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 |
|
O(1)=2 |
|
|
O(2)=3 |
|
|
O(3)=0 |
|
|
O(4)=2 |
|
|
O(5)=0 |
|
|
O(6)=1 |
|
|
O(7)=0 |
|
|
O(8)=0 |
|
|
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:
se stabileste legatura intre fratii de acelasi parinte
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:
crearea arborelui
inserarea unui nod
stergerea unui nod
stergerea arborelui
accesarea unui nod (cautarea)
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) daca pnod2 este adresa unui nod care poate fi accesat sau inserat in stanga nodului adresat de pnod1
B) daca pnod2 este adresa unui nod care poate fi accesat sau inserat in dreapta nodului adresat de pnod1
C) 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:
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
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)
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.
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++)
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
in caz de insucces
tnod * cautare(int val)
if (p->cheie<val)
}
return p; //nu s-a gasit nodul, p este Null
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:
se elibereaza nodul
se stabileste legatura dreapta a parintelui ca fiind nula:
parinte->dr=0
se elibereaza nodul
se stabileste legatura stanga a parintelui ca fiind nula:
parinte->st=0
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
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
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
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
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.
Sa se scrie o functie care numara intr-un arbore binar ordonat cate noduri contin chei cu valori cuprinse in intervalul [a,b].
Scrieti o functie care calculeaza nivelul si factorul de echilibrare pentru oricare nod al unui arbore binar.
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2972
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
