Arbori De Regasire. Arborii de regasire sunt structuri de date excelente pentru reprezentarea multimilor de cuvinte (siruri de caractere) - PowerPoint PPT Presentation
22
Calin Jebelean Arbori De Regasire 1 Arbori De Regasire Arborii de regasire sunt structuri de date excelente pentru reprezentarea multimilor de cuvinte (siruri de caractere) Ei pot fi folositi cu succes si pentru reprezentarea multimilor de numere intregi, daca privim respectivele numere ca pe niste siruri de caractere (alcatuite din caractere din intervalul ‘0’ .. ‘9’) De regula, insa, pentru multimi de numere intregi cea mai optima reprezentare o constituie vectorii de biti
Transcript
Calin Jebelean Arbori De Regasire 1
Arbori De RegasireArborii de regasire sunt structuri de date excelente pentru reprezentarea multimilor de cuvinte (siruri de caractere)
Ei pot fi folositi cu succes si pentru reprezentarea multimilor de numere intregi, daca privim respectivele numere ca pe niste siruri de caractere (alcatuite din caractere din intervalul ‘0’ .. ‘9’)
De regula, insa, pentru multimi de numere intregi cea mai optima reprezentare o constituie vectorii de biti
Calin Jebelean Arbori De Regasire 2
Arbori De Regasire
In continuare vom discuta despre arbori de regasire utilizati pentru memorarea de cuvinte alcatuite din litere mari in intervalul ‘A’ .. ‘Z’Alegerea intervalului de litere (vezi mai sus) este cruciala in implementarea unui arbore de regasire, deoarece de acest interval depinde structura nodurilor arborelui de regasireIntervalul trebuie sa fie compact – nu poate fi aleasa o reuniune de intervale [‘0’ .. ‘9’] U [‘A’ .. ‘Z’] U [‘a’ .. ‘z’], ci intr-o astfel de situatie trebuie ales intervalul [‘0’ .. ‘z’] care le cuprinde pe toate trei (vezi codificarea ASCII a caracterelor care intervin), chiar daca in acest interval mare apar si caractere nedorite (acesta este un dezavantaj al arborilor de regasire)
Calin Jebelean Arbori De Regasire 3
Arbori De Regasire
Practic, un arbore de regasire este o structura alcatuita din noduri, fiecare nod avand subarboriFiecare nod are un numar de subarbori egal cu lungimea intervalului de caractere (‘A’ .. ‘Z’ in cazul nostru) plus o unitateDeoarece intre ‘A’ si ‘Z’ sunt 26 de caractere (inclusiv ‘A’ si ‘Z’, folosind alfabetul englez), rezulta ca fiecare nod al arborelui nostru va avea 27 de pointeri spre fii (dispusi, de exemplu, sub forma unui tablou)Alta informatie nu exista intr-un nod
Calin Jebelean Arbori De Regasire 4
Arbori De Regasire
Un nod al arborelui de regasire arata astfel:
Deoarece fiecare nod al arborelui este strans legat de intervalul de caractere ‘A’ .. ‘Z’ si acest lucru nu reiese din figura de mai sus, vom redesena nodul in varianta urmatoare:
…
0 1 2 25 26
…
‘A’ ‘B’ ‘C’ ‘Z’ ‘[’
Calin Jebelean Arbori De Regasire 5
Arbori De Regasire
Fiecare pointer din nod corespunde unui caracter din intervalul ‘A’ .. ‘Z’ cu exceptia ultimului pointerDupa cum am mentionat anterior, fiecare nod contine cu o unitate mai multi pointeri decat caractere in intervalul ‘A’ .. ‘Z’Ultimul pointer din nod corespunde caracterului ‘[’ (dupa cum se vede si pe figura anterioara)Caracterul ‘[’ nu este ales la intamplare, el este caracterul care urmeaza lui ‘Z’ in codificarea ASCIIAstfel, am extins intervalul ‘A’ .. ‘Z’ la dreapta cu un caracter, obtinand intervalul ‘A’ .. ‘[’ (acesta este intervalul efectiv)Acest ultim caracter este foarte important si il vom folosi pe post de caracter terminator (vezi in continuare)
Calin Jebelean Arbori De Regasire 6
Arbori De Regasire
Iata arborele de regasire care contine cuvintele: AR, ARAC, ARAT, PI si PIAN
A B C P… … Z [
A B C R… … Z [ A B C I… … Z [
A B C G… … Z [
A B C T… … Z [
A … Z [ A … Z [
A B C G… … Z [
A B C N… … Z [
A … Z [
Calin Jebelean Arbori De Regasire 7
Arbori De Regasire
Chiar daca, din figura, ar reiesi ca fiecare nod contine un tablou de 27 de caractere (de la ‘A’ pana la ‘[’), nu trebuie sa uitam ca, de fapt, este vorba de un tablou de 27 de pointeri
Caracterele au fost figurate doar pentru a usura intelegerea structurii
Practic, toti pointerii care nu sunt figurati prin sageti se considera ca sunt nuli
Doar pointerii nuli ai radacinii au fost figurati explicit prin sageti pentru a nu incarca prea mult desenul
Calin Jebelean Arbori De Regasire 8
Arbori De Regasire
Pentru a intelege aceasta structura, trebuie sa stabilim criteriul de apartenenta al unui cuvant la multime
De exemplu, pentru a studia apartenenta cuvantului AR, vom considera sirul “AR[” (completam cuvantul dorit cu caracterul special ‘[’)
Pornim de la radacina (vezi figura de pe slide-ul 6): Nodul curent este nodul rosu Pointerul corespunzator caracterului ‘A’ (pointerul rosu) trebuie sa fie nenul Urmam acest pointer si ajungem intr-un nou nod (nodul verde) Pointerul corespunzator caracterului ‘R’ (pointerul verde) trebuie sa fie nenul Urmam acest pointer si ajungem intr-un nou nod (nodul albastru) Pointerul corespunzator caracterului ‘[’ (pointerul albastru) trebuie sa fie
nenul
Calin Jebelean Arbori De Regasire 9
Arbori De Regasire
Cum toti pointerii de care am mentionat pe calea de cautare sunt nenuli, tragem concluzia: cuvantul “AR” apartine multimiiDaca cel putin un pointer pe calea de cautare ar fi fost nul, cuvantul “AR” nu ar fi apartinut multimiiAtentie!!! Cand vorbim de toti pointerii ne referim la cuvantul extins “AR[” (completat cu caracterul terminator)Se observa ca pointerul corespunzator caracterului ‘[’ (atunci cand este nenul) este intotdeauna un pointer in bucla (un pointer chiar la nodul din care face parte pointerul respectiv)Nu conteaza nodul spre care pointeaza acel pointer, ideea este ca pointerul trebuie sa pointeze spre un nod valid (sa nu fie nul)De exemplu, am fi putut la fel de bine sa-l legam la radacina arborelui
Calin Jebelean Arbori De Regasire 10
Arbori De Regasire
A B C P… … Z [
A B C R… … Z [ A B C I… … Z [
A B C G… … Z [
A B C T… … Z [
A … Z [ A … Z [
A B C G… … Z [
A B C N… … Z [
A … Z [
Calin Jebelean Arbori De Regasire 11
Arbori De Regasire
Dupa cum se vede, exista doar 5 cai de cautare in arbore, corespunzatoare celor 5 cuvinte
Secventele de pointeri corespunzatoare celor 5 cuvinte sunt (pornind de la radacina):
Cuvantul “AR”: ROSU – ROSU – ROSU Cuvantul “ARAC”: ROSU – ROSU – VERDE – VERDE – VERDE Cuvantul “ARAT”: ROSU – ROSU – VERDE – ALBASTRU – ALBASTRU Cuvantul “PI”: PORTOCALIU – PORTOCALIU – PORTOCALIU Cuvantul “PIAN”: PORTOCALIU – PORTOCALIU – MOV – MOV – MOV
Pentru insertia sau suprimarea de cuvinte din multime, trebuie create respectiv distruse secventele de pointeri corespunzatoare
Calin Jebelean Arbori De Regasire 12
Arbori De Regasire
Pentru insertia unui cuvant, consideram ca avem un arbore de regasire continand doar cuvintele AR (pointeri rosii) si PI (pointeri portocalii) si dorim insertia cuvantului PIN
A B C P… … Z [
A B C R… … Z [ A B C I… … Z [
A B C G… … Z [ A B C N… … Z [
A … Z [
Calin Jebelean Arbori De Regasire 13
Arbori De Regasire
Practic, pornim de la radacina si parcurgem calea indicata de pointerii corespunzatori caracterelor ‘P’, ‘I’, ‘N’ si ‘[’Daca cuvantul “PIN” nu face parte din multime, inseamna ca cel putin unul dintre cei 4 pointeri amintiti sunt nuliProcesul de insertie trebuie sa creeze nodurile necesare pe calea de cautare incat cei 4 pointeri sa devina toti nenuliSe observa ca pointerii corespunzatori caracterelor ‘P’ si ‘I’ sunt deja nenuli datorita cuvantului “PI”, deci nu trebuie facut nimic deosebit pentru acesti pointeriTrebuie creat un nou nod corespunzator caracterului N (vezi figura) si in acel nou nod, pointerul corespunzator caracterului terminator ‘[’ trebuie sa nu fie nul, deci cream bucla corespunzatoareDin acest moment, cuvantul “PIN” face parte din multime
Calin Jebelean Arbori De Regasire 14
Arbori De Regasire
Suprimarea unui cuvant din multime comporta 2 cazuri majore, dupa cum e nevoie sau nu sa dezalocam memorieDorim sa suprimam cuvantul “PI” din arborele de mai jos: A B C P… … Z [
A B C R… … Z [ A B C I… … Z [
A B C G… … Z [ A B C N… … Z [
A … Z [
Calin Jebelean Arbori De Regasire 15
Arbori De Regasire
Pornind de la radacina, trebuie sa verificam ca multimea contine cuvantul pe care dorim sa-l stergemParcurgem pointerii corespunzatori caracterelor ‘P’, ‘I’ si ‘[’ (adica drumul figurat cu portocaliu) si ajungem la concluzia ca, intr-adevar, cuvantul “PI” apartine multimiiPentru a suprima cuvantul “PI” trebuie sa anulam pointerul corespunzator caracterului ‘[’ (bucla portocalie)Nodul curent este nodul rosuCum nodul curent mai contine pointeri nenuli inseamna ca mai exista cuvinte care incep cu prefixul “PI”, deci ne oprim aiciPractic, tot ce a trebuit sa facem a fost sa parcurgem calea de cautare si sa anulam ultimul pointer
Calin Jebelean Arbori De Regasire 16
Arbori De Regasire
Rezultatul este (modificarile au fost incercuite):
A B C P… … Z [
A B C R… … Z [ A B C I… … Z [
A B C G… … Z [ A B C N… … Z [
A … Z [
Calin Jebelean Arbori De Regasire 17
Arbori De Regasire
Presupunem ca dorim sa suprimam cuvantul “PIAN” din arborele de mai jos:
A B C P… … Z [
A B C R… … Z [ A B C I… … Z [
A B C G… … Z [ A B C G… … Z [
A B C N… … Z [
A … Z [
Calin Jebelean Arbori De Regasire 18
Arbori De Regasire
Urmand pointerii corespunzatori caracterelor ‘P’, ‘I’, ‘A’, ‘N’ si ‘[’ ajungem in nodul albastru si tragem concluzia ca cuvantul “PIAN” apartine multimiiAnulam pointerul corespunzator caracterului ‘[’ din nodul albastruDeoarece nodul curent (nodul albastru) nu mai contine pointeri nenuli (toti sunt nuli), inseamna ca nu mai exista cuvinte care incep cu prefixul “PIAN”, deci nu are rost sa mentinem spatiul ocupat pentru nodul albastruUrcam in nodul parinte (nodul verde) si dezalocam spatiul corespunzator nodului albastru, anuland si pointerul care ducea la nodul albastru (pointerul verde)In acest moment, arborele se prezinta ca in figura de pe slide-ul urmator
Calin Jebelean Arbori De Regasire 19
Arbori De Regasire
Modificarile au fost incercuite:
A B C P… … Z [
A B C R… … Z [ A B C I… … Z [
A B C G… … Z [ A B C G… … Z [
A B C N… … Z [
A … Z [
Calin Jebelean Arbori De Regasire 20
Arbori De Regasire
Problema se prezinta recursiv la nivelul nodului verde
Tocmai am anulat unul din pointerii din nodul verde (pointerul corespunzator caracterului ‘N’)
Deoarece nodul curent (nodul verde) nu mai contine pointeri nenuli (toti sunt nuli), inseamna ca nu mai exista cuvinte care incep cu prefixul “PIA”, deci nu are rost sa mentinem nici spatiul ocupat pentru nodul verde
Acesta va fi dezalocat in aceeasi maniera si procesul continua in nodul parinte
Se va opri abia atunci cand, in urma anularii unui pointer din cadrul unui nod, in acel nod mai raman pointeri nenuli – aceasta situatie “salveaza” nodul respectiv de la a fi dezalocat
Calin Jebelean Arbori De Regasire 21
Arbori De Regasire
In final, rezultatul suprimarii cuvantului PIAN este:
A B C P… … Z [
A B C R… … Z [ A B C I… … Z [
A B C G… … Z [ A B C G… … Z [
A B C N… … Z [
A … Z [
Calin Jebelean Arbori De Regasire 22
Arbori De Regasire
Structura de arbore de regasire este una foarte performanta pentru memorarea multimilor de cuvinteIntr-o multime obisnuita de cuvinte insertia, suprimarea sau cautarea de cuvinte sunt operatii avand performante proportionale cu numarul total de cuvinte din multime (tablou neordonat, lista inlantuita) sau cel mult cu logaritmul numarului total de cuvinte din multime (tablou ordonat, arbore binar ordonat, arbore B)Intr-un arbore de regasire insertia, suprimarea sau cautarea unui cuvant sunt operatii ale caror performante depind doar de lungimea cuvantului – cu alte cuvinte, nu depind deloc de numarul de cuvinte care exista deja in multimeDezavantajul major al arborilor de regasire este acela ca ocupa un spatiu de memorie destul de mare si in mare parte nefolosit, multi pointeri fiind nuliDaca setul de cuvinte memorat in cadrul multimii are o distributie omogena pe lungimea setului de caractere (de exemplu, cuvintele dintr-o limba formeaza un set relativ omogen – numarul de cuvinte care incep cu litera ‘A’ este comparabil cu numarul de cuvinte care incep cu litera ‘B’ sau ‘C’, etc.), atunci dezavantajul memoriei se manifesta mai putin, in sensul ca vor exista mult mai putini pointeri nefolositi in raport cu numarul total de pointeri ai structurii
