ARBORI TRIE

ARBORI TRIE

Notiuni introductive :

Arborii de regasire sunt structuri de date speciale care sunt utilizate mai ales pentru reprezentarea multimilor de caractere. De asemenea cu ajutorul lor pot fi reprezentate tipuri de date care sunt siruri de obiecte de orice tip (chiar si sirurile de numere).

De exemplu se doreste gasirea numarului de telefon al domnului SMITH. Se poate presupune ca exista o agenda in care numele sunt in ordine lexicografica. Deci se poate concepe o cautare executata ca-racter cu caracter. Adica se ajunge la litera S care este un index presupus, dar in loc sa se examineze fiecare nume pentru a vedea daca se potriveste cu numele cautat se va cerceta pana se gaseste caracterul M. Daca acest caracter este gasit se cerceteaza mai departe pana se gaseste caracterul I care apare deci pe nivelul 3 al unei structuri care da numele s.a.m.d. Daca s-a intilnit un ca-racter mai mare decat M inseamna ca in agenda nu exista numele dat. Rezulta ca daca in agenda exista inregistrarea data lungimea cauta-rii este aproximativ egala cu lungimea cheii si este independenta de numarul de inregistrari din agenda.

In cazul extrem in care cautarea este fara succes lungimea opera-tiei nu este mai mare decat in cazul cautarii cu succes, mai mult testul de comparare este executat caracter cu caracter si este in-dependent de lungimea cheii inregistrarii (deci nu se impun res-trictii asupra lungimii cheii). Daca cheia este un sir de caractere se poate considera alfabetul care incepe cu litera A, iar daca este numerica se considera alfabetul dat de multimea .

In continuare se considera un alfabet A care are n caractere. In acest alfabet se scrie fiecare cheie pentru inregistrari. Un arbore

de regasire este privit ca o structura arborescenta care are unele particularitati. Astfel : nodurile interne contin indecsi, iar no-

durile terminale (frunza) contin pointeri catre inregistrarile me-morate (catre informatii). De fapt nodurile frunza arata completa-rea cheii.

Ex. : Se considera doua chei : SMYTHON si SMITH si rezulta urmatoarea structura :

S

M

I Y

SMITH SMITHON

Deci cu numai 5 accese si 4 comparatii se ajunge la inregistrarea tinta (informatia cautata). Se noteaza ca a patra comparatie este necesara deoarece exista posibilitatea ca unul din sirurile SMI sau SMY sa fie prefix pentru cheia inregistrarii cautate.

Lungimea cautarii in termenii acceselor este cu 2 unitati mai mare decat lungimea caii care duce catre inregistrare (aceasta este de-finita ca lungimea cea mai mare a prefixului comun al cheii tinta cu alte chei ale inregistrarilor existente).

OBS. Se presupune ca se dau 2 siruri nenule X si Y in acelasi alfa-bet 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).

Ex. Din observatia de mai sus sirurile : S, SM, SMI, SMIT sunt prefixe pentru nume dat (SMITH).

OBS. Cheile care sunt prefixe pentru alte chei pot pune unele pro-bleme.

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 comple-ta cheia la dreapta cu un caracter special (caracterul nu apartine alfabetului dat A). In mod uzual acest caracter este blank-ul. In aceste circumstante insertia inregistrarii cu cheia SM nu va fi di-ferita de insertia altor inregistrari. Arborele pentru acest nou caz este urmatorul :

S

M

I Y

SM

SMITH SMITHON

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

l

a)   

a1 a2 an an+1

l r1

b)

k informatie

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

Implementarea intr-un limbaj de programare o realizam pe o struc-tura asemanatoare, comuna atat nodurilor interne cat si nodurilor frunza :

14 n n+1

l a0 a13 a25 a26

A M Z blank key

OBS.Tabloul 'a' pe care il folosim este format din cele 26 caracte-re ale alfabetului englez + o locatie pentru blank.

Exemplu

Pentru a vedea cum lucreaza procedura de inserare vom porni de

la o structura cu citeva cuvinte si vom incerca sa surprindem

fiecare caz din procedura de inserare.

Structura de la care vom porni va fi :

rad ‑> A E S key

C T A Y SCENE

ACTOR ATOM EAR EYE

OBS. Initializarea variabilei i in ciclul while difera in functie de implementarea in diferite limbaje.Astfel pentru limbajul Pascal intializarea se face pornind de la 1, iar in cazul implementarii in C initializarea se va face de la 0, deoarece valoarea initiala a lui i reprezinta primul caracter din sir (in C indexul porneste de la 0, iar in Pascal de la 1).   

‑introducerea cuvintului 'ACT'   

i=0;

while((index‑>l==1)&&(index‑>a[new_key[i]‑'a']!=NULL))

Iesirea din ciclul WHILE se realizeaza datorita faptului ca index->l=0

si vom avea pentru i valoarea de i = 2

rad ‑> A E S key

parent

C T A Y SCENE

ACTOR ATOM EAR EYE

salv1=parent‑>a[new_key[i‑1]‑'a'];

salv2=NewFrunza(new_key);

j va fi determinat de urmatoarea secventa de program :

j=strlen(new_key);

if(strlen(data‑>key)<j)

j=strlen(data‑>key);

In acest caz j = 3.

Pentru a determmina locul de insertie al noului cuvint eventual crearea de noi noduri interne se foloseste urmatorea secventa de program :

while((i<=j)&&(data‑>key[i‑1]==new_key[i‑1]))

OBS. In ambele secvente de program j=3, deoarece reprezinta lungi-mea unui sir de caractere, care este aceeasi indiferent de limbaj.

OBS. Datorita initializarii diferite a variabilei i, in functie de implementare, in ciclul WHILE din secventa de program de mai sus se va compara i-1 cu j in cazul limbajului Pascal, iar in C se va com-para i cu j.

rad ‑> A E S key

C T A Y SCENE

parent

ATOM EAR EYE

| |

salv1 salv2

| |

ACTOR ACT

La sfirsitul acestui pas in while i = 3   

rad ‑> A E S key

C T A Y SCENE

T ATOM EAR EYE

< parent   

| |

salv1 salv2

ACTOR ACT

Dupa acest pas in WHILE : i = 4

dar datorita decrementarii variabilei i : i = 3

Crearea legaturilor in arbore se realizeaza in acest caz de secventa :

-pentru C : parent‑>a[26]=salv2;

parent‑>a[new_key[j]‑'a']=salv1;   

rad ‑> A E S key

C T A Y SCENE

T ATOM EAR EYE

O <- parent

ACTOR ACT