Arbori TRIE

Arbori TRIE

Arborii de regasire a informatiei numit arbori Trie sunt structure de date special care sunt utilizate mai ales pentru cazul de reprezentare a multimilor de caractere. De asemenea , cu ajutorul lor pot fi reprez 121d35b entate tipuiri de date care sunt siruri de obiecte de orice tip(chiar si siruri de numere).

Se considera un alfabet A care are n caractere. In acest alphabet se scrie fiecare cheie pentru inregistrari. Un arbore de regasire de tip Trie este privit ca o structura arborescenta care are unele particularitati. Astfel, nodurile interne contin indecsi, iar nodurile terminale(frunza) contin pointeri catre intregistrarile memorate. De fapt nodurile frunza arata completarea cheii.

Observatie:Se presupune ca se dau doua siruri nenule X si Y in acelasi alfabet A. Atunci se spune ca sirul X este un prefix pentru sirul Y daca si numai daca exista un al treilea sir nevid Z in acelasi alfabet A astfel incat se poate scrie Y=X*Z (semnul '* 'semnifica operatia de concatenare a sirurilor).

Observatie:Cheile care sunt prefixe pentru alte chei pot pune unele probleme. De exemplu daca se insereaza o inregistrare (informatie) care are cheia SM se pune problema cum apare aceasta inregistrare in arborele dat in exemplul anterior. In acest caz se poate completa cheia la dreapta cu un caracter special (caracterul nu apartine alfabetului dat A). In mod uzual acest carcter este blank-ul. In aceste circumstante insertia inregistrarii cu cheia SM nu va fi diferita de insertia altor inregistrari.

In procesul de cautare cand al i-lea caracter dintr-o cheie este intalnit, acesta ar putea fi oricare din cele n+ lcaractere posibile. Deci fiecare nod intern al structurii va contine n+ lpointeri. Daca unul din acesti pointeri este NIL inseamna ca nu exista nici o inregistrare cu acel prefix. Rezulta urmatoarea structura pentru nodurile interne (a) si nodurile terminale (b).

Nodul frunza contine numai 2 campuri pe cand nodul intern contine n+2campuri. Primul camp in ambele tipuri reprezinta indicatorul tipului de nod (l=0nod terminal). Campul 'rl 'este un pointer la blocul care contine informatia a carui cheie sau prefix a fost completata pe nivelele anterioare. Pentru nodurile interne pointerul al i-lea corespunde caracterului aj din alfabetul A, iar pointerul n+1corespunde caracterului blank.

Inserare:

Radà

Arbori echilibrati

Algoritmul de inserare a unui nod intr-un arbore de cautare realizeaza arbori corespunzatori pentru operatiile de cautare, atunci cind datele de intrare sunt aleatoare. Exista insa posibilitatea aparitiei unui arbore degenerat pentru anumite secvente de intrare a datelor (de exemplu cind elementele se introduc chiar in ordinea crescatoare a cheilor).

O solutie interesanta privind mentinerea unui arbore de cautare avantajos a fost descoperita de catre matematicienii G.M. Adelson-Velskii si E.M. Landis, care au conceput o structura arborescenta in care subarborii unei radacini nu difera in inaltime prea mult (arbori AVL). Solutia foloseste un cimp in plus pentru nodurile arborilor, dar limiteaza foarte mult numarul mediu de operatii pentru cautarea unui element in arbore. In plus, metoda lor conduce la o metoda generala, convenabila pentru reprezentarea listelor liniare cu un numar determinat de elemente, imbinind avantajele alocarii secventiale si inlatuite a elementelor.

Definitie:Se numeste inaltime a unui arbore ca fiind lungimea celui mai lung drum de la nodul radacina la unul din nodurile terminale.

Definitie:Un arbor binar se numeste echilibrat daca inaltimea subarborelui din stinga nu difera cu mai mult de o unitate fata de inaltimea celui din dreapta. Se numeste factor de echilibrare diferenta dintre inaltimea subarborelui drept si a celui sting.

Atasind fiecarui nod un cimp care reprezinta factorul de echilibrare al sau, un arbore binar inseamna ca este echilibrat cind toti factorii de echilibru ai nodurilor sint -l, 0 sau +1.

In principal sint doua cazurile cind se pune problema reajustarii nodurilor.

Primul caz: Am notat cu h, h, h+1 inaltimile celor 3 subarbori.

Din diferite variante de reajustare a nodurilor, una foarte simpla presupune lasarea neschimbata a celor trei subarbori si inversarea nodurilor A si B.

Al doilea caz.

Acest caz apare cind inserarea noului nod a dus la cresterea inaltimii subarborelui din stinga nodului B, spre deosebire de primul caz, cind inserarea nodului a dus la cresterea subarborelui din dreapta lui B. Putem reajusta nodurile intr-un mod asemanator, pastrind neschimbati cei patru subarbori si ordinea lor.

In ambele cazuri trebuie modificate un numar mic de legaturi, tot restul arborelui raminind neschimbat. Singurul lucru care trebuie schimbat ii reprezinta coeficientii de echilibrare ai subarborelui unde se insereaza nodul.

INSERARE SI STERGERE..

BELLMAN-FORD

Algorirmul lui BELLMAN-FORD rezolva problema drumurilor cele mai scurte cu o singura sursa in cazul cel mai general in care ponderile muchiilor pot fi si negative.

Se considera un graf dat G V,E) orientat, ponderat si se considera un nod sursa s precum si o functie de pondere W:EàR. Algoritmul BELLMAN-FORD returneaza o valoare booleana care va indica faptul ca exista sau nu exista in graf un ciclu de pondere negative care poate fi atins din nodul sursa. Daca exista un astfel de ciclu, algoritmul arata ca problema data nu are solutie. Daca nu exista un astfel de ciclu, algoritmul furmizeaza drumurile cele mai scurte si ponderile lor.

Algoritmul BELLMAN-FORD utilizeaza tehnica relaxarii pentru a creste in mod progresiv valoarea estimate d(V) a ponderii unui nod aflat pe drumul cel mai scurt de la nodul sursa s la nodul v apartine V pana cand se obtine ponderea celui mai scurt drum, notate cu DEL(s,v). Algoritmul returneaza valoarea TRUE daca si numai daca graful nu contin e cicluri cu pondere negative care sa fie atinse din nodul sursa.

**Procedure B_F(G,W,s)

BEGIN

*INIT_SINGURA_SURSA(G,s)

FOR i=0 TO (IVI-1) DO

FOR *fiecare muchie (u,v)care apartine lui E DO

RELAX (u,v,W)

FOR * fiecare muchie care apartine lui E DO

IF d[v]>d[u W(u,v)

THEN RETURN (FALSE)

RETURN (TRUE)

END

Dupa executarea initializarilor uzuale, algoritmul executa un numar de (IVI-1) treceri prin muchiile grafului. Fiecare trecere este o iteratie a primei bucle FOR si consta in relaxarea fiecarei muchii a grafului exact odata. Dupa cele (IVI-1) treceri, ultima bucla FOR verifica existent ciclului cu pondere negative si returneaza o valoare booleana adecvata.

DIJKSTRA

Algoritmul lui DIJKSTRA rezolva problema drumurilor cele mai scurte cu o singura sursa pentru grafuri oriectate, ponderate in cazul in care ponderile tuturor muchiilor sunt positive. Deci in acest caz se presupune ca W(u,v)>=0 pentru orice muchie (u,v) apartine E.

Algoritmul lui DIJKSTRA utilizeaza o multime S a nodurilor a caror pondere finala pentru cel mai scurt drum de la nodul sursa la ele a fost deja determinat. Adica, pentru orice nod v apartine S avem d(v)=DEL(s,v), algoritmul selectand in mod repetat un nod u apartine (V/S) cu valoarea ponderii estimate minima si insereaza nodul u in multimea S dupa care aplica operatia de relaxare asupra tuturor muchiilor ce pleaca din nodul u.

In algoritmul prezentat in pseudocod mai jos, se considera o coada de prioritate Q ce va contine toate nodurile din multimea (V/S) dupa valorile d ale lor.

In algoritmul prezentat, graful G este considerat dat cu ajutorul listelor de adiacenta.

**Procedure_DIJKSTRA(G,W,s)

BEGIN

INIT_SINGURA_SURSA(G,s)

EMPTY_SET(S)

Q v

WHILE * coada Q nu este vida DO

u EXTRACT_MIN(Q)

S S reunite cu

FOR * fiecare nod v care apartine lui ADJ[u] DO

RELAX(u,v,w)

END

Prima linie a algoritmului executa initializarea obisnuita a grafului G, adica valoarea pentru ponderea estimate 'd' si pentru predecesorul PI. Urmatoarea linie initializeaza multimea S ce devine vida. Cealalta linie initializeaza coada de prioritate continand toate nodurile din multimea (V-S V-multimea vida=V.

La fiecare iteratie a buclei while un nod u este extras din Q=V/S si inserat in multimea S. La prima iteratie avem u=s nodul u are cea mai mica valoare estimate din nodurile ce se afla in multimea (V/S).

Bucla FOR aplica relaxarea fiecarei muchii (u,v) care paraseste nodul u si astfel se actualizeaza valoarea estimate d(v) si campul predecessor PI(v), daca drumul cel mai scurt catre nodul v poate fi imbunatatit trecand prin nodul u.

PRIM

Algoritmul lui PRIM, ca si algoritmul lui KRUSKAL este un caz particular al algoritmului generic de determinare a arborelui de acoperire minima. Algortmul lui PRIM are ca proprietate de baza faptul ca muchiile din multimea A formeaza intotdeauna un singur arbore. Arborele porneste de la un nod arbitrar r considerat radacina si creste in timpul baleerii nodurilor grafului dat. La fiecare pas o muchie usoara care conecteaza un nod din multimea A cu un nod din multimea (V/A) este adaugata la arboreal care se construieste.

Conform corolarului din paragraful anterior, regula de adaugare a unei muchii la arbore ce se construieste furnieaza o muchie sigura pentru multimea A si deci cand algoritmul se va termina, muchiile multimii A formeaza un arbore de acoperire minima.

Desigur ca strategia algoritmului se bazeaza pe metoda de prrogramare GREEDY, deaorece arboreal creste la fiecare pas cu o muchie. Cheia implementarii algoritmului PRIM este aceea a selectarii unei muchii noi pentru a fi adaugata la arboreal format de muchiile din multimea A.

In timpul executarii algoritmului, toate muchiile care nu se gasesc in arbore se afla intr-o coada de prioritate Q. pentru un nod v vom avea KEY(v) care este ponderea minima a unei muchii care conecteaza nodul v la un nod din arboreal care se construieste. Astfel, KEY(v) = infinit daca nu exista nici o astfel de muchie. Se noteaza prin PI(v) parintele nodului v din arboreal care se construieste. In timpul executiei algoritmului, multimea A data in algoritmul GENERIC -ARB -ACOP -MIN este A=-Q))}. Cand algoritmul se termina coada de prioritati Q este goala si multimea A contine arboreal de acoperire minima a grafului G, adica A==))}

Algoritmul PRIM:

**Procedure_PRIM(G,w,r)

BEGIN

Q v

FOR * fiecare u care apartine lui Q DO

key[u] infinit

key[r] 0

PI[r NIL

WHILE Q<>multimea vida DO

u EXTRACT_MIN(Q)

FOR * fiecare v care apartine lui ADJ[u] DO

IF (v apartine lui Q) AND (w(u,v)<key[v])

THEN key[u] w(u,v)

PI[v] u

END