Structuri de Date și Algoritmi

Arbori Binari Optimi

Despre arbori binari optimi putem vorbi atunci cand, pentru fiecare dintre cheile unui arbore binar ordonat cunoastem frecventa cu care aceasta cheie va aparea in cadrul operatiilor ulterioare de cautare

Aceasta frecventa poate fi vazuta si ca “probabilitatea” ca o anumita cheie sa fie subiectul (argumentul) unei operatii viitoare de cautare in arborele binar ordonat

Vorbim despre operatii de cautare deoarece, in general, acestea sunt cele care ne intereseaza atunci cand lucram cu arbori binari ordonati

Arbori Binari Optimi

Pentru o cheie oarecare, timpul de cautare va fi, in cel mai rau caz proportional cu inaltimea arborelui

Pentru o cheie care exista in arbore, timpul de cautare este proportional cu adancimea nodului care contine cheia (distanta de la acesta la radacina)

Ideal ar fi ca acele chei care sunt cautate mai des sa fie plasate mai aproape de radacina arborelui iar acele chei care sunt cautate mai rar sa fie plasate mai departe de radacina arborelui

Arbori Binari Optimi

De exemplu, am putea considera, ca o aplicatie, ca toate cuvintele limbii romane sunt chei intr-un arbore binar ordonat, dispuse intr-un anumit fel

Acest arbore binar ordonat va fi folosit de un dictionar pentru a obtine pentru fiecare cuvant, traducerea sa intr-o limba straina

Evident, anumite cuvinte vor fi cautate mai des decat altele

Fiecare cuvant ar putea avea (teoretic) asociata o probabilitate de aparitie

Cuvintele cu probabilitate de aparitie mai mare (mama, tata, etc.) ar fi bine sa fie mai apropiate de radacina arborelui decat cuvintele cu probabilitate de aparitie mai mica (metempsihoza, parapsihologie, etc.), dintre care multe nici nu vor fi cautate vreodata

Astfel apare ideea pe care se bazeaza arborii binari optimi

Arbori Binari Optimi

Fie un arbore binar ordonat continand cheile k1, k2, …, kn

Consideram ca fiecare cheie ki are asociata o “probabilitate de aparitie” pi

Distributia probabilitatilor pi asigura urmatoarele conditii:

0 d pi d 1, unde i = 1 .. n

p1 + p2 + … + pn = 1

Arborele binar ordonat poate fi numit “optim” daca:

DP = p1 · adancime(k1) + … + pn · adancime(kn) = minim

Arbori Binari Optimi

Suma anterioara poarta numele de “drum ponderat”, fiind suma drumurilor de la radacina la fiecare nod, ponderate cu probabilitatile de acces la noduri

Pentru ca drumul ponderat DP sa fie minim, trebuie ca o probabilitate de acces (pi) mare (adica o cheie cautata des) sa fie insotita de o adancime (adancime(ki)) mica (adica o distanta mica pana la radacina arborelui)