Seminar 5
Acest seminar prezinta urmatoarele concepte Arbori de intervale, Coduri Huffman .
Arbori de intervale
arbore binar echilibrat, in care:
- fiecare nod interior este asociat unui interval
- fiecare frunza este asociata unei pozitii din vector
TO DO: IMAGINE
Cand folosesc? Am un sir de numere si queryuri pe intervale (suma, maxim, minim), intercalate cu queryuri de update pe element.
Implementare: La fel ca la heap. Se construieste ca un vector in care:
- parinte(i) -> pozitia i/2
- left(i) -> pozitia 2*i
- right(i) -> pozitita 2*i+1
Numar maxim de noduri: 4*n
Vizualizare operatii: aici
Constructie
build(int nod, int l, int r, x)
- in nodurile interioare: apelam recursiv pe fiii nodului si reunim valorile in nodul curent
- in frunze: updatam valoarea
build(nod, l, r){
daca r - l == 1 //sunt in frunza
suma[nod] = a[l];
return ;
}
mid = (l+r)/2;
build(2 * nod, l, mid);
build(2 * nod + 1, mid, r);
suma[nod] = suma[nod * 2] + suma[nod * 2 + 1];
}
Update
- modificam valoarea de pe pozitia pos cu x
- la fel ca la constructie, dar updatam un singur element, iar restul sumelor care il contine cresc cu diferenta fata de valoarea initiala
update(pos, x, nod, l, r){
suma[nod] += x - a[pos];
if(r - l == 1){ // sunt in frunza pos
a[pos] = x;
return ;
}
mid = (l + r)/2;
if(pos < mid)
modify(pos, x, 2 * nod, l, mid);
else
modify(pos, x, 2 * nod + 1, mid, r);
}
Query
- interogam suma/min/max pe un interval
- daca intervalul din nod e inclus in intervalul dorit intoarcem valoarea din nod
- daca intervalul e disjunct cu intervalul din query intoarcem 0
- daca e inclus in fiul stang apelam recursiv pe stanga => val1
- daca e inlus in fiul drept apelam recursiv pe stanga => val2
- intoarcem val1 + val2
query(st_q, dr_q, int nod, l, r){
if(st_q >= r or l >= dr_q) return 0
if(st_q <= l && r <= dr_q) return suma[nod]
mid = (l+r)/2;
val1 = query(st_q, dr_q, nod * 2, l, mid)
val2 = query(st_q, dr_q, nod * 2 + 1, mid, r)
return val1 + val2
}
Arbori indexati binar (AIB)
Motivatie: Aceasi ca in cazul arborilor de intervale
De ce? Mai rapid si mai usor de implementat. :)
Explicatie suma
QUERY:
- se foloseste un vector v[i] - suma pe (i - 2^k, i]. (pozitiile divizibile cu 2^k stochează suma ultimelor 2^k elemente)
- cu ajutorul lui calculam sumele partiale [1..y]
- descompunem pe y ca suma de patrate iar suma se obtine ca suma de v[k] k se obtine din y eliminand succesiv cate un bit de 1
void Add(int x, int quantity)
{
int i;
for (i = x; i <= N; i += zeros(i))
AIB[i] += quantity;
}
UPDATE:
int Compute(int x)
{
int i, ret = 0;
for (i = x; i > 0; i -= zeros(i))
ret += AIB[i];
return ret;
}
Coduri Huffman
Exista codificari:
- cu lungime fixa: mai putin eficient din punct de vedere al lungimii
- cu lungime variabila
De ce Huffman? Ne dorim un arbore optim (minimizeaza suma w * lg_pana_la_frunza)
Algoritm Arbore Huffman: Arbore binar avand ca frunze datele de intrare insotite de ponderi, iar muchiile sunt codificate astfel:
- muchia stanga: 0
- muchia dreapta: 1
TO DO: IMAGINE
La fiecare pas vom impreuna nodurile cu cele mai mici ponderi=> un nod interior cu ponderea suma fiilor sai.
Observatii
- Arborele nu este unic din cauza cazurilor de egalitate intre ponderi
- Decodificarea unui mesaj este unica (are proprietatea prefix: codul niciunei litere nu este prefix al altei litere)
- e optim