Arbori binari de cautare BST, dinamic echilibrat AVL, Structuri elementare si abstracte
Arbori binari de căutare (BST).
Tabelele Hashing - o alta solutie pentru a retine elementele
din S. Complexitatea pentru arborele binar de cautare in cazurile: cel mai
favorabil O(n), mediu O(logn). arbore binar de cautare - arbore T ale carui
noduri sunt etichetate cu atomii continuti la un moment dat în dictionar. r ∈ V
(radacina arborelui), Ts - subarborele stâng al radacinii si Td - subarborele
drept al radacinii, atunci structura acestui arbore este definita de
urmatoarele proprietati: 1) ∀ nod x ∈ Ts
atunci key(data(x)) < key(data(r));
2) ∀ x ∈ Td
atunci key(data(x)) > key(data(r)); 3)
Ts si Td sunt BST.
Funcții:
Search
search(rad,k) // rad - pointer la radacina arborelui
{ // k - cheia de cautare a arborelui cautat
if (rad = 0) then
return NULL
else
if key (data (rad))
> k then
return search (lchild
(rad))
else
if key (data (rad))
< k then
return search (rchild
(rad))
else return rad }
Insert
Se va crea un nod în
arbore care va fi plasat la un nou nod terminal. Pozitia în care trebuie plasat
acesta este unic determinata în functie de valoarea cheii de cautare
vom insera 19 în arborele nostru:
insert(rad,a) // rad referinta la pointerul la radacina
// arborelui
{
if (rad= 0) then rad= make_nod(a)
else if key (data (rad)) > key(a) then
insert(lchild(rad),a)
else if key
(data(rad)) < key(a)then
insert (rchild
(rad),a)
}
make_nod
creaza un nou nod:
make_nod(a)
{
p= get_sp() // alocare
de memorie pentru un nod nou
data(p)= a
lchild(p)= 0
rchild(p)= 0
return(p)
}
La inserarea unui atom
deja existent în arbore, functia insert nu modifica structura arborelui. Exista
probleme în care este utila contorizarea numarului de inserari a unui atom în
arbore.
Functia insert poate
returna pointer la radacina facând apeluri de forma p= insert(p,a).
Delete
delete(rad,k) // rad - referinta la pointer la radacina
{ // k - cheia de cautare a atomului care
trebuie sters de noi
if rad = 0 then
return // nodul cu cheia k nu se afla în arbore
else if key(data(rad))
> k then delete(lchild(rad),k)
else if key(data(rad))
< k then delete(rchild(rad),k)
else delete_root(rad)
}
Stergerea radacinii unui BST:
rad ⇒ arbore vid
2) a)
rad sau b) rad
⇒ a) SAS
sau b) SAD
/ \
SAS SAD
delete_root(rad) // rad - referinta la pointer la radacina
{
if lchild(rad)=0 then
p= rchild(rad)
ret_sp(rad)
rad= p
else if rchild(rad)= 0
then
p= lchild(rad)
ret_sp(rad)
rad= p
else p= remove_greatest(lchild(rad))
lchild(p)= lchild(rad)
rchild(p)= rchild(rad)
ret_sp(rad)
rad= p
}
Detașarea celui mai mic (mai mare nod) din
arborele BST.
Pentru a gasi cel mai
mare nod dintr-un arbore binar de cautare, se înainteaza în adâncime pe ramura
dreapta pâna se gaseste primul nod care nu are descendent dreapta. Acesta va fi
cel mai mare. Vom trata aceasta procedura recursiv:
Caz1: rad ⇒ se returneaza pointer la radacina si arborele
rezultat va fi vid.
Caz2: rad ⇒ se returneaza pointer la radacina si arborele
rezultat va fi format doar din subarborele stâng.
Caz3: rad ⇒ functia returneaza pointer la cel mai mare nod
din SAD, iar rezultatul va fi SAS - arborele care este fomat din radacina, SAS
si SAD - cel mai mare nod.
remove_greatest(rad) //rad -referinta la pointer la
//radacina: un pointer
la radacina de poate fi modificat de catre functie
{
if rchild (rad)= 0
then
p= rad
rad= lchild (rad)
return(p)
else return
(remove_greatest (rchild(rad)))
}
Functia
remove_greatest modifica arborele indicat de parametru, în sensul eliminarii
nodului cel mai mare, si întoarce pointer la nodul eliminat.
Complexitatea tuturor
functiilor scrise depinde de adâncimea arborelui. În cazul cel mai defavorabil,
fiecare functie parcurge lantul cel mai lung din arbore. Functia de cautare
are, în acest caz, complexitatea O(n). Structura arborelui BST este determinata
de ordinea inserarii. De exemplu, ordinea 15 13 12 11 este alta decât 15 12 11
13 .
Crearea unui BST pornind de la secvența de
atomi.
Studiem un caz de
complexitate medie:
gen_BST (va fi în programul principal)
rad= 0
for i= 1 to n
insert (rad, ai)
Calculam complexitatea
medie a generarii BST: ∑ (i)=O(n*n), i=[1,n]
Notam cu T(k) -
numarul de comparatii mediu pentru crearea unui BST pornind de la o secventa de
k elemente la intrare. Ordinea celor k elemente se considera aleatoare. Pentru
problema T(n) avem de creat secventa (a1
a2 ... an) cu observatia ca a1 este radacina
arborelui. Ca
rezultat, în urma primei operatii de inserare pe care o facem, rezulta:
a1 –a1 (ai
-ai (ai>a1)
Consideram numarul de
operatii globale. Dupa ce am inserat a1, pentru inserarea fiecarui element în
SAS sau SAD a lui a1, se face o comparatie cu a1.
T(n)=(n-1) +
val.med.SAS + val.med.SAD
val.med.SAS = valoarea
medie a numarului de comparatii necesar pentru a construe subarborele stâng SAS
val.med.SAD = valoarea
medie a numarului de comparatii necesar pentru a construi subarborele drept SAD
T(n)=(n-1)+1/n*∑T(i-1)+1/n*∑T(n-1)
i=[1,n]; i=[i+1,n].
Ti(n) = numarul mediu
de comparatii necesar pentru construirea unui BST cu n noduri atunci când prima
valoare inserata (a1) este mai mare decât i-1 dintre cele n valori de inserat.
Putem scrie:
Ti(n)=(n-1)+T(i-1)+T(n-i)
T(n)+1/n*∑Ti(n)
Deci
T(n)=2/n*∑T(i);
i=[0,n-1]
Complexitatea acestei
functii este: O(n⋅ln n)
Arbori binari de căutare dinamică echilibrata (AVL).
Un arbore binar este
echilibrat daca si numai daca, pentru fiecare nod din arbore, diferenta dintre
adâncimile SAS si SAD în modul este ≤ 1. Adâncimea unui arbore echilibrat cu n
noduri este O(ln n). Se completeaza operatiile insert si delete cu niste
prelucrari care sa pastreze proprietatile de arbore binar echilibrat pentru
arborele binar de cautare. Arborele binar echilibrat este un BST echilibrat,
proprietatea de echilibrare fiind conservata de insert si
delete. Efortul, în plus, pentru completarea operatiilor insert
si delete nu schimba complexitatea arborelui binar echilibrat.
Transformarea structurii arborelui dupa inserare pentru a conserva proprietatea
de arbore binar
Echilibrat.
Modificarile care se vor face se vor numi rotatii. în inserarea prin rotatie se
obtine un arbore echilibrat cu adâncimea egala cu adâncimea arborelui de
dinainte de inserare. La inserarea unui nod terminal într-un arbore AVL este
necesara aplicarea a cel mult o rotatie asupra unui nod. Trebuie, deci sa gasim
nodul asupra caruia trebuie aplicata rotatia. S-a notat pentru fiecare nod bf -
balance factor (factor de dezechilibrare):
bf(nod) = depth
(lchild (nod)) - depth (rchild (nod))
Calculam factorii de
balansare dupa inserare.
Pentru nodul terminal
s-a schimbat adâncimea si factorul de balansare; bf = -2 dupa inserare
devine nod
dezechilibrat. Trebuie aplicata, deci, echilibrarea. Se numeste nod critic
primul nod cu bf ≠ 0 întâlnit la o parcurgere de jos în sus a ramurii care
leaga nodul
inserat de radacina.
Toate nodurile din ramura care sunt pe nivele inferioare nodului critic vor
capata bf = 1 sau bf = -1. La nodul
critic exista doua situatii: 1. Nodul critic va fi perfect balansat (bf = 0),
daca dezechilibrul creat de nodul inserat anuleaza dezechilibrul initial al
nodului. În acest caz nu este nevoie de rotatie (el completeaza un gol în
arbore). 2. Factorul de balansare devine bf = 2 sau bf = -2 atunci când nodul
inserat mareste dezechilibrul arborelui
(s-a inserat nodul în
subarborele cel mai mare). În acest caz, se aplica o rotatie în urma careia se
schimba strucutra subarborelui, astfel încât noua radacina capata bf = 0,
conservându-se adâncimea. Problema conservarii proprietatii de echilibrare a
arborelui se rezolva aplicând o rotatie asupra nodului critic numai atunci când
inserarea dezechilibreaza acest nod. Costul suplimentar care trebuie suportat
se materializeaza prin necesitatea ca în fiecare nod sa se
memoreze factorul de
dezechilibrare bf. Acesti factori de dezechilibrare vor fi actualizati în urma
operatiilor de rotatie si inserare. Operatia de stergere într-un AVL implica
mai multe rotatii.
Structuri de date elementare şi abstracte.
Un vector este o
colectie de date de acelasi tip, în care elementele colectiei sunt identificate
prin indici ce reprezintă pozitia relativă a fiecărui element în vector. La
început se puteau declara si utiliza numai vectori cu dimensiuni fixe, stabilite
la scrierea programului si care nu mai puteau fi modificate la executie. Introducerea
tipurilor pointer si alocării dinamice de memorie în limbajele Pascal si C a
permis utilizarea de vectori cu dimensiuni stabilite si/sau modificate în
cursul executiei programelor. Gruparea mai multor date, de tipuri diferite,
într-o singură entitate, numită “structură” în C a permis definirea unor noi
tipuri de date de către programatori si utilizarea unor date dispersate în
memorie, dar legate prin pointeri: liste înlăntuite, arbori si altele. Astfel
de colectii se pot extinde dinamic pe măsura necesitătilor si permit un timp
mai scurt pentru anumite operatii, cum ar fi operatia de căutare într-o
colectie. Limbajul C asigură structurile de date fundamentale (vectori, pointeri,
structuri) si posibilitatea combinării acestora în noi tipuri de date, care pot
primi si nume sugestive prin declaratia typedef. Dintr-o perspectivă
independentă de limbajele de programare se pot considera ca structuri de date fundamentale
vectorii, listele înlăntuite si arborii, fiecare cu diferite variante de
implementare. Alte structuri de date se pot reprezenta prin combinatii de
vectori, liste înlăntuite si arbori. De exemplu, un tabel de dispersie (“Hash
table”) este realizat de obicei ca un vector de pointeri la liste înlăntuite
(liste de elemente sinonime). Un graf se reprezintă deseori printr-un vector de
pointeri la liste înlăntuite (liste de adiacente), sau printr-o matrice (un
vector de vectori în C).
Clasificarea
structurilor de date:
Un criteriu de
clasificare foloseste relatiile dintre elementele colectiei:
Colectii liniare (secvente,
liste), în care
fiecare element are
un singur succesor
si un singur predecesor;
Colectii arborescente (ierarhice), în care un element poate avea mai
multi succesori (fii), dar un singur predecesor (părinte);
Colectii neliniare generale, în care relatiile dintre elemente au forma
unui graf general (un element
poate avea mai multi succesori si mai multi
predecesori).
Un alt criteriu poate
fi modul de reprezentare a relatiilor dintre elementele colectiei:
Implicit, prin dispunerea lor în memorie (vectori de valori, vectori de
biti, heap);
Explicit, prin adrese de legătură (pointeri).
Un alt criteriu grupează diferitele colectii după rolul pe care îl au în
aplicatii si după operatiile
asociate colectiei,
indiferent de reprezentarea în memorie, folosind notiunea de tip abstract de
date. Astfel putem deosebi:
Structuri de căutare (multimi si dictionare abstracte);
Structuri de păstrare temporară a datelor (containere, liste, stive,
cozi s.a.)
Un tip abstract de date este definit numai prin operatiile asociate
(prin modul de utilizare), fără referire la modul concret de implementare.
Pentru programele
nebanale este utilă o abordare în (cel putin) două etape:
o etapă de conceptie (de proiectare), care include alegerea tipurilor
abstracte de date si algoritmilor necesari;
o etapă de implementare (de codificare), care include alegerea
structurilor concrete de date, scrierea de cod si folosirea unor functii de
biblioteca.
Problema alegerii unei
structuri de date eficiente pentru un tip abstract nu are o solutie unică, desi
există anumite recomandări generale în acest sens. Sunt mai multi factori care
pot influenta această alegere si care depind de aplicatia concretă.
Exemplul cel mai bun
este al structurilor de date folosite atunci când sunt necesare căutări frecvente
într-o colectie de date după continut (după chei de căutare); căutarea într-un
vector sau într-o listă înlăntuită este ineficientă pentru un volum mare de
date si astfel au apărut tabele de dispersie (“hash table”), arbori de căutare
echilibrati, arbori B si alte structuri de date optimizate pentru operatii de
căutare.
Alt exemplu este cel
al algoritmilor folositi pentru determinarea unui arbore de acoperire de cost
minim al unui graf cu
costuri (Prim, Kruskal), care au o complexitate ce depinde de structurile de
date folosite.
Eficienta unei anumite
structuri este determinată de doi factori: memoria ocupată si timpul necesar pentru
operatiile frecvente. Mai des se foloseste termenul de “complexitate”, cu variantele “complexitate temporală” si
“complexitate spatială”.
