Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme


Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
ARBORI TRIE


ARBORI TRIE




ARBORI TRIE

12.1 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)

1a1a2 . . . an an+1

l r1

b)

0

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 ai 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 :

1 14 n n+1

l a0 a13 a25 a26

1A .. M .. Z blankkey

}

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 ‑> 1A..E..S..key

1..C..T.. 1A..Y.. 0SCENE

0ACTOR 0ATOM 0EAR 0EYE

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 ‑> 1A..E..S..key

parent

1..C..T.. 1A..Y.. 0SCENE

0ACTOR 0ATOM 0EAR 0EYE




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 ‑> 1A..E..S..key

1..C..T.. 1A..Y.. 0SCENE

parent

1. 0ATOM 0EAR 0EYE

| |

salv1 salv2

| |

--- ---

0ACTOR 0ACT

La sfirsitul acestui pas in while i = 3

rad ‑> 1A..E..S..key

1..C..T.. 1A..Y.. 0SCENE



1..T.. 0ATOM 0EAR 0EYE

1. < parent

| |

salv1 salv2

---- ---

0ACTOR 0ACT

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 ‑> 1A..E..S..key

1..C..T.. 1A..Y.. 0SCENE

1..T.. 0ATOM 0EAR 0EYE

1..O.. <- parent

0ACTOR 0ACT







Politica de confidentialitate


Copyright © 2019 - Toate drepturile rezervate

Informatica


Access
Adobe photoshop
Autocad
Baze de date
C
Calculatoare
Corel draw
Excel
Foxpro
Html
Internet
Java
Linux
Mathcad
Matlab
Outlook
Pascal
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word


Atestat informatica - Plante si animale pe cale de disparitie
Sisteme informatice
Gestiunea Mouse-lui
CALCUL TABELAR
Aplicatie informatica in managementul energetic
MODELAREA UNUI SISTEM SOFTWARE
MASURI DE SECURITATE INFORMATICA
UTILIZAREA TEHNOLOGIEI INFORMATIEI IN VIATA DE ZI CU ZI
Fundamentele programarii - probleme
Coeficientul de corelatie a rangurilor (Spearman)