Structuri Avansate Pentru Cautare

66
Structuri de date avansate pentru cautare 2-3 arbori B-arbori arbori bicolori Tabele hash Arbori digitali

description

siruri

Transcript of Structuri Avansate Pentru Cautare

Page 1: Structuri Avansate Pentru Cautare

Structuri de date avansate pentru cautare

2-3 arbori B-arbori arbori bicolori Tabele hash Arbori digitali

Page 2: Structuri Avansate Pentru Cautare

2-3-arbori: definitie

orice nod intern v are 2 copii (este de aritate 2) sau 3 copii (este de aritate 3)

valStg valStg valMij

subarbore

stanga

subarbore

mijlociu

subarbore

dreapta

p->stg p->drpp->mij

Page 3: Structuri Avansate Pentru Cautare

2-3-arbori : definitie

pentru orice nod v de aritate 2, valorile memorate in subarborele stinga < vvalStg < valorile memorate in subarborele mijlociu

valStg

x < valStg valStg < y

Page 4: Structuri Avansate Pentru Cautare

2-3-arbori : definitie

pentru orice nod v de aritate 3, valorile memorate in subarborele stinga < vvalStg < valorile memorate in subarborele mijlociu < vvalMijl < valorile memorate in subarborele dreapta

valStg valMij

x< valStg

valStg<

y <

valMijvalMij<z

Page 5: Structuri Avansate Pentru Cautare

2-3-arbori : definitie

toate nodurile de pe frontiera au acelasi nivel

h

h

Page 6: Structuri Avansate Pentru Cautare

cautare in 2-3-arbore

function poz23Arb(t, a)begin

p twhile (p != NULL) do

switch(cmp(a, p))a < p->stg: p p->stg; break;p->stg < a < p->mij: p p->mij; break; p->drp < a: p p->mij; break;otherwise: return p;

return pend

Page 7: Structuri Avansate Pentru Cautare

inserare in 2-3-arbore

35

10; 20 40; 50 70; 90; 110; 120

30; 60 100;

80;

50; 35; 10; 20 70; 90; 110; 120

30; 60 100;

80;

40

50; 35;

Page 8: Structuri Avansate Pentru Cautare

inserare 2-3-arbore (continuare)

40; 80

10; 20 50; 70; 90; 110; 12035;

100; 60; 30;

60; 30;

10; 20 50; 70; 90; 110; 12035;

100;

80;

40

Page 9: Structuri Avansate Pentru Cautare

inserare 2-3-arbore (continuare)

subprograme necesareradNoua(t, x, q)

• creeaza o noua radacina cu cheia xt: intrare – rad subarb. stg. iesire – noua rad.q rad. subarb. drp

poz23ArbMod(t, x, s)• memoreaza drumul de la radacina la x in stiva s

insInNod(p, x, q)• insereaza x innodul p

parametri sunt similari subprogramului radNoua()imparte(p, x, q)

• sparge un nodparametri sunt similari subprogramului insInNod()

Page 10: Structuri Avansate Pentru Cautare

inserare 2-3-arbore (continuare)

procedure ins23Arb(t, x)begin if (t == NULL) then radNoua(t, x, NULL) else p = poz23ArbMod(t, x, s) if (p == NULL) then throw ”x in t” else q NULL while(true) do if (p->valMij = ) then insInNod(p, x, q); break imparte(p, x, q) if (p = t) then radNoua(t, x, q); break;

else p = top(s); pop(s);end

Page 11: Structuri Avansate Pentru Cautare

stergere 2-3-arbore

daca elementul sters nu se afla intr-un de pe frontiera, atunci se poate interschimba cu un vecin aflat pe frontiera

vecinul cu care face interschimbarea se poate face ca la arborii binari de cautare

asa ca putem considera numai cazul cand elementul care se sterge se afla pe frontiera

Page 12: Structuri Avansate Pentru Cautare

stergere 2-3-arbore

70; 10; 20 50; 90; 110; 12035;

100; 60; 30;

40; 80

50; 6010; 20 90; 110; 12035;

100; 30;

40; 80

Page 13: Structuri Avansate Pentru Cautare

stergere 2-3-arbore: combinare

30; 40

80;

10; 20 35; 50; 60 90; 110; 120

100;

50; 6010; 20 90; 110; 12035;

100; 30;

40; 80

combina

Page 14: Structuri Avansate Pentru Cautare

stergere 2-3-arbore: rotatie

100; ; 30; 40

50; 80

100; 50; 30;

40; 80

60

roteste dreapta

Page 15: Structuri Avansate Pentru Cautare

stergere 2-3-arbore

modifica p atat timp cat p are zero elemente && p nu e radacina

fie r radacina lui pfie q fratele lui p (stg. sau drp. dupa caz)daca q este de aritate 3

atunci roteste

altfel combina

r devine p

Exercitiu: Sa se scrie procedura de stergere

Teorema

Clasa 2-3-arborilor este O(log n)-stabila.

Page 16: Structuri Avansate Pentru Cautare

2-3-4-arbori

sunt generalizari ale 2-3 arborilorun nod intern poate avea 2, 3 sau 4 copiiun nod cu 4 copiii va memora 3 cheise mentin proprietatile de arbore de cautare si aceeasi

inaltime pentru toate nodurile de pe frontiera ca si in cazul celorlalti abori de cautare, exista doua moduri de

implementare:elementele multimii memorate in nodurile interne (si frunze)elementele multimii doar in nodurile frunza (pe frontiera)

inserarea se face tot prin spargerea nodurilorla momentul inserarii si propagarea spre radacinasau in timpul cautarii, fiecare nod plin este spart in doua

Page 17: Structuri Avansate Pentru Cautare

Arbori de cautare pe M-cai

generalizare de la 2-3 si 2-3-4 la M un nod poate avea n copii cu 2 <= n <= M numarul de chei memorate intr-un nod este n-1; cheile k1,..., kn-1

sunt ordonate crescator are proprietatea de arbore de cautare:

elementele memorate in subarborele Ti sunt mai mici decat cheia ki

elementele memorate in subarborele Ti+1 sunt mai mari decat cheia ki

Page 18: Structuri Avansate Pentru Cautare

B-arbori - motivatie

Un index ordonat este un fisier secvential. Pe masura ce dimensiunea acestuia creste, cresc si dificultatile de administrare

un acces la disc este mult mai scump decat executia unei instructiuni ( 200,000 instructiuni)

memoria secundara (discul) este divizata in blocuri egale (512, 1024, 2048 etc)

o operatie I/O transfera un bloc scopul este de a minimiza numarul de accesari ale discului Solutia: indexarea pe mai multe nivele .

un posibil instrument : B arborii (arbori de cautare multicai)

Page 19: Structuri Avansate Pentru Cautare

Organizarea pe nivele a indexului

Page 20: Structuri Avansate Pentru Cautare

B-arbori

sunt arbori de cautare pe M-cai cu proprietatipresupunem ca M = 2f

• f = factorul de minimizare• ordinul arborelui este 2f-1

fiecare nod intern are cel putin un numar de f-1 chei (f fii) si cel mult 2f-1 chei (2f fii)

doar radacina poate avea mai putin de f fiilungimea oricarui drum de la radacina la o frunza trebuie sa

fie aceeasi (generalizeza 2-3 si 2-3-4 arborii)

Page 21: Structuri Avansate Pentru Cautare

B-arbore: structura unui nod

Page 22: Structuri Avansate Pentru Cautare

Optimizarea accesului la disc

Daca fiecare nod necesita accesarea discului atunci B-arborii vor necesita numar minim de astfel de accesari

Factorul de minimizare va fi ales astfel incat dimensiunea unui nod sa corespunda unui multiplu de blocuri ale dispozitivului de memorare

Aceasta alegere optimizeaza accesarea discului

Inaltimea h a unui B-arbore cu n > 0 chei si f > 1 este

h <= logf[(n+1)/2]

Page 23: Structuri Avansate Pentru Cautare

B-arbori: cautarea

cauta in nodul curent daca nu gaseste, cuta in subarborele care corespunde

intervalului la care apartine cheia

function B-Tree-Search(v, k)

i 0; while (i < v->nrChei k > v->cheie[i]) do i i + 1 if (i <= v->nrChei k = v->cheie[i] ) then return (v, i) if (v->tipNod = frunza) then return NULL citesteDisk(v->fiu[i]) return B-Tree-Search(v->fiu[i], k)end

Page 24: Structuri Avansate Pentru Cautare

B-arbori: insertia

Pentru a efectua o insertie intr-un B-arbore trebuie intai gasit nodul in care urmeaza a se face insertia. Pentru aceasta se aplica un algoritm similar cu BTree-

Search. Apoi cheia urmeaza a fi inserata

Daca nodul determinat anterior contine mai putin de 2f-1chei se face inserarea

Daca acest nod contine 2f-1 chei urmeaza spargerea acestuia• Procesul de spargere poate continua pana in radacina • Pentru a evita doua citiri de pe disc ale aceluiasi nod,

algoritmul sparge fiecare nod plin (2f-1 chei) intalnit la parcurgea top-down in procesul de cautare a nodului in care urmeaza a se face inserarea

Timpul de spargere a unui nod este O(f) Rezulta pentru insertie complexitatea timp O(f log n)

Page 25: Structuri Avansate Pentru Cautare

B-arbori: eliminarea

daca nodul gazda a cheii ce urmeaza a fi stearsa nu este frunza, atunci se efectueaza o interschimbare intre acesta si succesorul sau in ordinea naturala a cheilor. Se repeta operatia pana se ajunge intr-o frunza, care devine nod curent;

se sterge intrarea corespunzatoare cheii; daca nodul curent contine cel putin f-1 chei, operatia de stergere

se considera terminata; daca nodul curent contine mai putin decat f-1 chei se considera

fratii vecini; daca unul din fratii vecin are mai mult decat f-1 chei, atunci se

redistribuie una dintre intrarile acestui frate in nodul parinte si una din intrarile din nodul parinte se redistribuie nodului curent (deficitar);

daca ambii fratii au exact f-1 chei, atunci se uneste nodul curent cu unul dintre fratii vecini si cu o intrare din parinte;

daca nodul parinte devine deficitar (contine mai putin decat f-1 chei) acesta devine nod curent si se reiau pasii de mai sus.

Page 26: Structuri Avansate Pentru Cautare

Arbori bicolori

un arbore bicolor este caracterizat de urmatoarele proprietati:sint arbori binari de cautare in care nodurile pendante

(coresp. intervalelor) fac parte din structurafiecare nod este colorat cu negru sau rosutoate nodurile de pe frontiera sint negredaca un nod este rosu atunci ambii fii ai acelui nod sint

negripentru orice nod v, toate drumurile simple care pleaca din

acel nod si se opresc intr-un nod de pe frontiera, au acelasi numar de noduri negre

Page 27: Structuri Avansate Pentru Cautare

Exemplu de arbore bicolor

70

40

20 60

50

100

80

90

110

Page 28: Structuri Avansate Pentru Cautare

arbori bicolori - proprietati

Notatiebh(x) = numarul de noduri negre aflate pe un drum din x pe

frontiera (x nu se considera)bh(x) nu depinde de drum (ultima conditie)

12 )( xbh

Lema

Subarborele cu radacina in x contine cel putin

noduri interne.

TeoremaInaltimea unui arbore bicolor este cel mult 2log(n + 1).

TeoremaArborii bicolori sint echilibrati.

Page 29: Structuri Avansate Pentru Cautare

arbori bicolori - inserare

2

1

14

11

7

8

15

4

5

x

y

unchiul lui x

recolorare

Page 30: Structuri Avansate Pentru Cautare

arbori bicolori - inserare

unchiul lui x

roteste stanga

2

1

14

11

7

8

15

4

5

x

y

Page 31: Structuri Avansate Pentru Cautare

arbori bicolori - inserare

7

1

14

11

2 8 15

4

5

x

y

unchiul lui x

roteste dreapta

Page 32: Structuri Avansate Pentru Cautare

arbori bicolori - inserare

7

1 14

11 2

8

15 4

5

recoloreaza

Page 33: Structuri Avansate Pentru Cautare

arbori bicolori - inserare

7

1 14

11 2

8

15 4

5

Page 34: Structuri Avansate Pentru Cautare

Discrepanta SSr

B D

A

C

unchiul lui C

B D

A

Cx

unchiul lui C

Daca bunicul e radacina, devine negru

Page 35: Structuri Avansate Pentru Cautare

Discrepanta SDr

B D

A

C

unchiul lui C

B D

A

C

unchiul lui C

Daca bunicul e radacina, devine negru

Page 36: Structuri Avansate Pentru Cautare

Discrepanta SSn

B D

A

C

unchiul lui C

B

D

A C

B

D

A C

Page 37: Structuri Avansate Pentru Cautare

Discrepanta SDn

B D

Aunchiul lui C

C

D

A B

C

D

A B

C

Page 38: Structuri Avansate Pentru Cautare

arbori bicolori - inserare

se considera si transformarile simetrice ...

Page 39: Structuri Avansate Pentru Cautare

arbori bicolori - stergere

nodul sters are cel mult un fiu (daca nu se face o interschimbare cu un “vecin” din lista ordonata)

daca nodul sters este rosu, arborele ramane unul bicolor

daca nodul sters este negru si are un fiu rosu, atunci acesta (fiul) se recoloreaza cu negru

in celelalte cazuri avem o discrepanta ce trebuie rezolvata (a se vedea slide-urile urmatoare) Legenda:

D sau S dau pozitia nodului sters (Dreapta sau Stanga)

n sau r dau culoarea nodului frate

0, 1sau 2 da numarul de fii/nepoti rosii ai nodului frate

Page 40: Structuri Avansate Pentru Cautare

arbori bicolori – stergere – discrepanta Dn0

nodul sters este Dreapta, fratele negru care are ambii copii negri

A

B

A

B

copiii lui B

Page 41: Structuri Avansate Pentru Cautare

arbori bicolori – stergere – discrepanta Dn1

nodul sters este Dreapta, fratele negru care are un copil rosu si unul negru

A

B

A

B

copiii lui B

Page 42: Structuri Avansate Pentru Cautare

arbori bicolori – stergere – discrepanta Dn1

nodul sters este Dreapta, fratele negru care are un copil rosu si unul negru

A

B

C

A B

C

copiii lui B

Page 43: Structuri Avansate Pentru Cautare

arbori bicolori – stergere – discrepanta Dn2

nodul sters este Dreapta, fratele negru care are ambii copii rosii

A

B

C

A B

C

copiii lui B

Page 44: Structuri Avansate Pentru Cautare

arbori bicolori – stergere – discrepanta Dr0

nodul sters este Dreapta, fratele rosu care are toti nepotii negri

A

B

A

B

Page 45: Structuri Avansate Pentru Cautare

arbori bicolori – stergere – discrepanta Dr1

nodul sters este Dreapta, fratele rosu care are un nepot rosu

A

B

C

A B

C

nepotii lui B

Page 46: Structuri Avansate Pentru Cautare

arbori bicolori – stergere – discrepanta Dr1

nodul sters este Dreapta, fratele rosu care are un nepot rosu

A

B

C

A B

D

D

C

nepotii lui B

Page 47: Structuri Avansate Pentru Cautare

arbori bicolori – stergere – discrepanta Dr2

nodul sters este Dreapta, fratele rosu care are doi nepoti rosii

A

B

C

A B

D

D

C

nepotii lui B

Page 48: Structuri Avansate Pentru Cautare

Hashing (dispersie) Tipul de data abstract TabelaDeSimboluri

entitati de tip data: o colectie de perechi (nume, atribute) in care numele identifica unic perechea

operatii:• Atribut(TS, nume) – cauta numele in tabela TS

numele nume si intoarce atributele acestuia (daca il gaseste)

• Insereaza(TS, nume, atribut)- insereaza in tabela TS perechea (nume, atribut)

• Elimina(TS,nume) – cauta in tabela TS numele nume si daca-l gaseste il elimina impreuna cu atributele sale.

Page 49: Structuri Avansate Pentru Cautare

Hashing (dispersie)

Implementarea prin tehnica dispersieistructura de date

• o tabela (hash sau de dispersie) T[0..p-1] cu p numar prim de obicei

• o functie hash h: mult. numelor [0..p-1]

0

1

2 curs

3

4

5

6

7

[curgere, mergere, expunere]

(curs, [curgere, mergere, expunere])nume = cursvaloare = [curgere, mergere, expunere]h(curs) = 2

Page 50: Structuri Avansate Pentru Cautare

Hashing (continuare I)

operatii• cautarea

i = h(nume)if (T[i] )then return T[i]->atrib

• inserareai = h(nume)if (T[i] )then throw “ERR: coliziune”else T[i]->atrib atribut

• eliminareai = h(nume)if (T[i] )then T[i]

Page 51: Structuri Avansate Pentru Cautare

Alegerea functiei hash

modul h(x) = x % p

0

1

2 18

3

4

5 35

6

7

h(18) = 18 % 8 = 2h(35) = 35 % 8 = 5h(58) = 58 % 8 = 2 ???

Page 52: Structuri Avansate Pentru Cautare

Alegerea functiei hash

“folding” h(64747488286) = (647+4748+8286) % 8 = 5

0

1

2

3

4

5 64747488286

6

7

Page 53: Structuri Avansate Pentru Cautare

Alegerea functiei hash

“binning” domeniul cheilor: 0..1000 dimensiunea tabelei: 10 h(x) = 0, 0 <= x < 100 h(x) = 1, 100 <= x < 200 …

0

1

2 218

3

4

h(218) = 2

Page 54: Structuri Avansate Pentru Cautare

Alegerea functiei hash

cazul cand cheia x este sir: suma codurilor ASCIIint h(String x, int p) { char ch[]; ch = x.toCharArray(); int xlength = x.length();

int i, sum; for (sum=0, i=0; i < x.length(); i++) sum += ch[i]; return sum % p; }

x = “prelegere”, sum = 955, p = 8, h(x, p) = 3

x = “aaaabbbb”, sum = 780, p = 8, h(x, p) = 4

x = “abababab”, sum = 780, p = 8, h(x, p) = 4

Page 55: Structuri Avansate Pentru Cautare

Alegerea functiei hash

cazul cand cheia x este sir: suma a cate 4 octeti

long sfold(String s, int M) { int intLength = s.length() / 4; long sum = 0; for (int j = 0; j < intLength; j++) { char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray(); long mult = 1; for (int k = 0; k < c.length; k++) {

sum += c[k] * mult; mult *= 256;

} }

Page 56: Structuri Avansate Pentru Cautare

Alegerea functiei hash (cont.)

char c[] = s.substring(intLength * 4).toCharArray(); long mult = 1; for (int k = 0; k < c.length; k++) { sum += c[k] * mult; mult *= 256; }

return(Math.abs(sum) % p); }

x = “prelegere”, sum = 13238595, p = 8, h(x, p) = 3

x = “aaaabbbb”, sum = 12779715, p = 8, h(x, p) = 3

x = “abababab”, sum = 12714189, p = 8, h(x, p) = 4

Page 57: Structuri Avansate Pentru Cautare

Alegerea functiei hash

cazul cand cheia x este sir:

int h(String x, int p) { char ch[]; ch = x.toCharArray(); int xlength = x.length();

int i, sum; for (sum=0, i=0; i < x.length(); i++) sum = (sum << 5) + ch[i]; return sum % p; }

Page 58: Structuri Avansate Pentru Cautare

Distributia cheilor

demo: http://research.cs.vt.edu/AVresearch/hashing/

Page 59: Structuri Avansate Pentru Cautare

Hashing (continuare III)

coliziuneainlantuire (demo)

• numarul mediu de comparatii in cazul cautarilor cu succes = 1 + b/2, unde b = #S/p este factorul de incarcare al tabelei (demonstratia pe tabla)

adresare deschisa liniara (demo)• se cerceteaza pe rind pozitiile

h(x,i), i = 0,1,2, ...

unde h(x,i) =(h1(x)+i) % p• numarul mediu de comparatii in cazul cautarilor FARA

succes = 1/(1-b) • numarul mediu de comparatii in cazul cautarilor CU

succes = ½(1 + 1/(1-b))

Page 60: Structuri Avansate Pentru Cautare

Arbori digitali

se mai numesc si structuri “trie” (de la information retrieval) cautarea depinde de lungimea cheii salveaza spatiu prin memorarea o singura data a prefixelor

comune spatiul de cautare este micsorat dinamic pe masura parcurgerii

cheii utile, de exemplu, la memorarea dictionarelor

Page 61: Structuri Avansate Pentru Cautare

Arbori digitali - I

Cazul cheilor de aceeasi lungimeS = {102, 120, 121, 210, 211, 212}

Page 62: Structuri Avansate Pentru Cautare

Arbori digitali - II

algoritmul de cautare

function poz(a, m, t) i 0 p t while ((p != NUL) && (i<m)) do p succ[a[i]] i i+1 return pend

Page 63: Structuri Avansate Pentru Cautare

Arbori digitali - III

Cazul cheilor de lungime diferita

Page 64: Structuri Avansate Pentru Cautare

Arbori digitali - IV

compactarea lanturilor

Page 65: Structuri Avansate Pentru Cautare

Arbori digitali - V

Inserarea lui 0111 in structura compactata

Page 66: Structuri Avansate Pentru Cautare

Arbori digitali - VI

Eliminarea lui 1011 in structura compactata