Structuri de date
AxeL
Structuri de date
Structurile de date erau definite in limbajul C drept organizarea
datelor primare.In limbajul C++, acestea reprezinta o colectie de date
impreuna cu operatiile lor (data obiect).
De exemplu, prin multimea N a numerelor naturale se va intelege si
elementele multimii N, dar si operatiile ce se pot efectua cu acestea:
1, 2, 3, ..., +, -, *, /.
Sau prin multimea numerelor complexe: C: {z = a + bi/a si bR, i =
sqrt(-1)}, -, +, *, /, etc.
Algoritmul se defineste ca o metoda de rezolvare a unei probleme
intr-un numar de pasi, metoda efectiva (pas cu pas), finita (are un
numar finit de pasi) si cu o intrare si o iesire (I/O). Un algoritm
poate avea un limbaj natural (o specificatie), un limbaj matematic
(alta specificatie), un limbaj de programare (alta specificatie),
s.a.m.d.
Intre limbajul natural si cel in C++, de exemplu, vom folosi un
pseudolimbaj (de trecere).
Modele de calcul
Masina este un model de calcul care se constituie din Unitate Centrala
(U.C.), Memorie (M), I/O.
Exemple de modele de calcul:
Masina Von Newman - presupune executia pe baza modelului de calcul cu:
Programarea este in acest caz programare imperativa procedurala.
Masina RAM (Random Acces Memory) cu:
model bazat pe algebra booleana;
programarea este imperativa procedurala;
evolutia se face prin set redus de instruciuni;
viteza foarte mare de executie.
Masina TURNING
1. MODELUL functional - bazat pe teoria lambda - calcul.
Limbajele in acest model sunt LISP, ML, MIRANDA, etc. iar programarea
este in acest caz programare functionala.
2. MODELUL logic - bazat pe predicate de ordin I. Un exemplu de limbaj
in acest model este PROLOG. Iar programarea se numeste programare
logica.
In cele ce urmeaza ne vom limita la modelul Von Newman. Asadar limbajul
C++ se constituie din:
variabile;
identificatori;
constante;
operatori numerici obisnuiti;
operatori relationali;
structuri de control a executiei: if/else, while, do/while, for, etc.
Analiza performantelor algoritmului
Analiza performantelor (estimarea algoritmului) se impune inca inainte
de scrierea programelor.
Etapele de realizare a unui produs software (software engineering).
Aceasta stiinta pune in evidenta metodologii clare pentru modele.
Modelul initial: waterfall (cascada):
Etapele de realizare ale unui produs software:
O prima faza:
se pleaca de la cerinte;
se obtin specificatii;
se face analiza specificatiilor;
A doua faza (DESIGN):
proiectare de ansamblu (se sparge modulul in submodule, etc);
proiectarea structurilor de date;
proiectarea algoritmilor;
analiza performantelor;
codarea (scrierea programului);
A treia faza:
testarea;
Ultima faza:
implementarea.
Programul rezultat se compara cu cerintele, si daca nu corespunde, se
reia ciclul ori de cate ori este nevoie. Analiza performantelor
presupune renuntand la acuratete estimarea timpului de lucru si a
spatiului de stocare, nestiind inca limbajul care va fi folosit si
calitatea programului ce se va obtine.
Presupunand ca modelul RAM de masina pe care lucram executa
instructiuni pseudocod, si ca fiecare instructiune pseudocod consuma
acelasi timp de executie,rezulta ca timpul estimat pentru executia unui
algoritm este proportional cu numarul instructiunilor executate de acel
algoritm.
Timpul de executie al algoritmului depinde de:
dimensiunea datelor de intrare
spatiul de memorie suplimentar ocupat
Dimensiunea datelor de intrare este o functie f(n) care calculeaza,
pentru un n dat, numarul de instructiuni al algoritmului respectiv.
Estimarea se face pana la o constanta c.
Spatiul de memorare suplimentar
Curs 2
Structuri de date elementare
O structura de date presupune un mod de organizare a datelor (in
tablouri, structuri, etc), si definirea operatiilor acceptate. Deci, o
structura de date reprezinta o colectie organizata de date si un set de
operatii definite.
Si notiunea de tip de date presupune:
|--- reprezentare
|--- operatii acceptate
De exemplu, pentru tipul int:
|--- reprezentare: pe doi octeti: cod complementar
|---operatii acceptate: +, -, *, /, &, |, etc.
Daca pentru un tip de date nu intereseaza reprezentarea, ci doar
operatiile acceptate,inseamna ca tipul de date este abstract.
Structuri de date
Tablouri
Tabloul este o colectie de date in care fiecare element poate fi
identificat pe baza unui index, colectia asigurand timp de acces
constant pentru fiecare element. Prin reprezentarea tabloului se
intelege plasarea elementelor in locatii succesive de memorie:
Locatiile de memorie pot fi numerotate, putand accesa direct orice
element. Timpul de accesare al elementului numar, de exemplu, fiind
acelasi cu timpul de accesare al elementului n.
Liste
O lista este o multime de obiecte, numite atomi, pentru care este
definita o ordine:
Operatiile principale care se pot se face in cadrul listei:
inserare: introducerea unui nou element intr-o anumita pozitie;
stergere: scoaterea unui element dintr-o anumita pozitie;
consultare: accesul asupra fiecarui element din lista;
parcurgere.
Tipuri speciale de liste
Stive
O stiva este o lista in care operatiile de inserare, stergere si
consultare se efectueaza asupra unui capat al listei. Stiva se poate
asemana cu un recipient in care se pun si se pot scoate diferite
obiecte. Operatia care pune obiectele in stiva se numeste push, iar cea
care scoate obiecte din stiva se numeste pop. Capatul accesibil pentru
stiva se numeste varful stivei:
Asadar:
push insereaza un element in varful stivei;
pop sterge un element din varful stivei;
top consulta (citeste) elementul din varful stivei;
top(S) citeste varful stivei.
Cozi
O coada este o lista in care inserarea se face la un capat (la
sfarsit), iar stergerea se face de la celalalt capat al cozii (de la
inceput). Partea din fata a cozii (a primului element) se numeste
front, iar partea din spate (a ultimului element) se numeste end.
Operatia de inserare in coada add (put)
Operatia de stergere din coada del (get)
Implementari de liste
O lista poate fi realizata ca: lista ordonata sau lista inlantuita
Lista ordonata tine cont de o ordine a pozitiilor elementelor listei,
nu de continutul elementelor.
Inserarea intr-o lista de forma:
se face cu deplasare de o pozitie la stanga din punctul in care dorim
sa inseram (pentru a face acest loc noului element). Deplasarea se face
inspre zona de memorie libera (cea hasurata) presupunem
ca dorim sa inseram pe a in pozitia i):
Presupunand acum hasurat corpul de elemente din lista si nehasurata
zona de memorie libera, inserarea s-ar putea figura astfel:
Stergerea: deplasarea cu o pozitie la stanga din acel punct.
Liste inlantuite
Intr-o lista inlantuita, ordinea din memorie nu mai corespunde cu
ordinea din lista. Fiecare element al listei inlantuite va avea
urmatoarea structura:
(a(i) , succesor(a(i)))
unde a(i) este atomul listei inlantuite, iar informatia succesor(a(i))
ne permite sa identificam un nou element de lista inlantuita. Ordinea
din memorie a elementelor listei nu conteaza. Informatia care indica
primul element al listei se numeste "capul" listei. Informatiei
succesor(a(i)) i se potriveste
notiunea de pointer (identificator), pointer-ul fiind o variabila care
pastreaza o adresa din memorie. El indica pozitia elementului urmator.
Cand informatiile de inlantuire sunt pointeri, putem utiliza urmatoarea
reprezentare:
Capul de lista este un pointer separat care duce la primul element din
lista, iar 0 este pointer-ul nul (NULL) cu valoare zero. La
implementarea listei inlantuite concentrarea se face la fluxul
instructiunilor, nu la declaratiile de variabile.
In programe vom utiliza urmatoarele notatii:
x adresa unui element din lista, deci un pointer;
data(x) atomul memorat in elementul de lista indicat de x;
link(x) informatia de legatura memorata in elementul de lista indicat
de x, adica adresa elementului urmator;
y = get_sp() y (de acelasi tip cu x) primeste adresa unei zone de
memorie in care se poate memora un element din lista (get space sau
alocare de memorie cand este vorba de pointer);
ret_sp(x) elibereza memoria ocupata de elementul de lista indicat de x
(din momentul respectiv acolo se poate memora altceva).
Un element de lista va fi o astfel de structura:
struct Element {
Atom data;
Element* link;
};
Se va scrie:
tipul lui x ---------------- Element* x
data(x) ---------------- x data
link(x) ---------------- x link
y = get_sp() ---------------- y = new Element
ret_sp() ---------------- delete x
Deoarece lucram cu conceptul de lista vom face declaratia : typedef
Element* Lista;
Un pointer la un element de lista considerat aproximeaza lista ce
porneste cu elementul indicat.
Operatii primitive pentru liste inlantuite
1.Inserarea
Inserarea se face: in fata, sau in interior (la mijloc ori la sfarsit)
a) Inserarea in fata
1 - Prima atribuire: link(x) = l
2 - A doua atribuire: l = x
Observatie: daca lista este vida, l are valoarea 0 (capatul listei) iar
atribuirile de mai sus raman valabile:
b) Inserarea la mijloc
Analog pentru inserarea la sfarsit.
1 - Prima atribuire: link(x) = link(y)
2 - A doua atribuire: link(y) = x
2.a)Stergerea (stergerea din fata):
1 - Prima atribuire: p = l
2 - A doua atribuire: l = link(l)
3 - ret_sp(p)
Sau, stergerea din fata s-ar mai putea reprezenta astfel:
Situatia initiala:
Situatia finala:
(1) p = cap;
(2) cap = cap link;
delete p ; // Elibereaza zona de memorie
Elementul care a fost izolat de lista trebuie sa fie procesat in
continuare, cel putin pentru a fi eliberata zona de memorie pe care o
ocupa, de aceea adresa lui trebuie salvata (sa zicem in variabila
pointer p).
2.b)Stergerea de la mijloc sau de la sfarsit
Varibila q va indica elementul din fata celui care va fi sters.
Situatia initiala:
Situatia finala:
(1) p = q->link;
(2) q-> link = p->link; // sau q->link = q->link->link;
delete p;
Observatii:
Atunci cand q indica penultimul element dintr-o lista, atribuirile de
mai sus functioneaza corect si sterg ultimul element din lista. Nu se
poate face stergerea elementului indicat de q fara parcurgerea listei
de la capat.
Curs 3
Operatia de inserare într-o lista înlantuita
Presupune adaugarea unui element într-o pozitie specificata în lista.
Exista
posibilitati diferite de a specifica pozitia în care vrem sa inseram
elementul:
Situatia în care pozitia de inserat este data printr-un numar care sa
indice al
cƒtelea element trebuie sa fie în lista elementul inserat;
Situatia în care pozitia de inserat este data prin valoarea atomului
dupa care
sau înainte de care se face inserarea;
Situatia în care pozitia de inserat poate fi data implicit prin
valoarea
atomului de inserat.
Inserarea în fata unui element specificat
Functia înscrie un element în fata altui element dintr-o lista:
insert (l, a, b)
// l lista (pointer la primul element)
// a valoarea atomului de inserat
// b valoarea atomului în fata caruia se insereaza
{
p=get_sp();
data(p)=a;
if (l==0) or (data(l)==b) then
{
link(p)=l;
l=p;
}
else
{
q=l;
while ((link(q)!=0)and (data(link(q)!=b))
do q=link(q);
link(p)=link(q);
link(q)=p;
}
}
Operatia de stergere dintr-o lista înlantuita
Operatia delete sterge un atom dintr-o lista. Deci vom avea în
pseudocod,
o functie de forma:
delete(l, a)
// l lista
// a valoarea atomului care trebuie sters
{
if l=0 then eroare ("Atomul nu se afla în lista")
else if data(l)=a then |½ p=1
| l=link(l)
|_ ret_sp(p)
else |½ q=l
| while(link(q)!=0)and(data(link(q))!=a) do
| q=link(q)
| if link(q=0) then eroare("S-a ajuns la sfƒrsitul
| listei si atomul nu a fost gasit")
| else
| p=link(q)
| link(q)=link(p)
|_ ret_sp(p)
}
Operatia de parcurgere a listei înlantuite
Operatia de parcurgere a listei înlantuite consta dintr-o secventa de
instructiuni care se foloseste de fiecare data cƒnd dorim sa prelucram
elementele listei într-un anumit scop.
O parcurgere a listei presupune o prelucrare efectuata asupra fiecarui
element
din lista (asadar nu o functie, ci o secventa de instructiuni):
Fie p pointer-ul care indica pe rƒnd fiecare element al listei, si
consideram
ca p începe cu l:
while (p!=0) do |½ prelucrare (data(p)) // ex:afisarea | //atomului
|_ p=link(p) // trece la urmatorul
Stive ordonate
O stiva este o structura de date de tip "container" (depoziteaza
obiecte de un
anumit tip) organizata dupa principiul LIFO (Last In First Out).
Operatiile de acces la stiva (push - adauga un element in stiva si pop
- scoate
un element din stiva) sunt create astfel încƒt pop scoate din stiva
elementul
introdus cel mai recent.
O stiva este un caz particular de lista, si anume este o lista pentru
care
operatiile de acces (inserare, stergere, accesare element) se
efectueaza la un
singur capat al listei.
Daca STACK este de tip stiva si ATOM tipul obiectelor continute în
stiva atunci
operatiile care definesc tipul structura de stiva pentru tipul STACK
sunt:
CREATE() STACK
Operatia CREATE nu primeste parametri, creeaza o stiva care pentru
început
este vida (nu contine nici un obiect).
PUSH(STACK, ATOM) STACK
Operatia PUSH primeste ca parametri o stiva si un obiect si produce
stiva
modificata prin adaugarea obiectului în stiva.
POP(STACK) STACK, ATOM
Operatia POP primeste ca parametri o stiva pe care o modifica scotƒnd
un
obiect. De asemenea produce ca rezultat obiectul scos din stiva.
TOP(STACK) ATOM
Operatia TOP întoarce ca rezultat obiectul din vƒrful stivei pe care
o primeste
ca parametru.
ISEMPTY(STACK) boolean
Operatia ISEMPTY este folosita pentru a testa daca stiva este vida.
Facem notatiile:
S stiva
S.vect vectorul în care se reprezinta elementele stivei S
S.sp indicele vƒrfului stivei
Elementele sunt memorate asadar unul dupa altul în vectori, nefiind
neaparat
în ordine crescatoare. Zona de memorat trebuie sa contina aceste doua
informatii: S.vect si S.sp grupate într-o structura:
struct Stack {
int sp;
Atom vect [DIMMAX]
};
Conditia de stiva vida este: S.sp=0
Se scrie:
push(S,a)
{
if S.sp >=DIMMAX then eroare("Stiva plina")
else |½ S.sp=S.sp+1
|_ S.vect[S.sp]=a //atomul este pus pe prima
//pozitie
}
Functia pop scoate un element din stiva:
pop(S)
{
if S.sp=0 then eroare ("Stiva vida")
else S.sp=S.sp-1
}
Observatie: Se obisnuieste ca pe lƒnga stergerea elementului, functia
pop sa
returneze elementul scos din lista.
top(S)
{
if S.sp=0 then eroare("Stiva vida")
else return(S.vect[S.sp])
}
Functia isEmpty(S) testeaza conditia stiva vida:
isEmpty(S)
{
return(S.sp==0)
}
Stive înlantuite
O stiva poate fi implementata ca o lista înlantuita pentru care
operatiile de acces se fac numai asupra primului element din lista.
Deci, operatia PUSH va însemna inserare în prima pozitie din lista
(în fata) iar POP va însemna stergerea primului element din lista.
Pentru a manevra o stiva vom avea nevoie de un pointer la primul
element din înlantuire, deci, vom echivala tipul Stack cu tipul
"pointer la element de lista", iar functiile care implementeaza
operatiile de acces vor avea aceleasi prototipuri cu cele date mai sus.
struct Element {
Atom data;
Element* link; //legatura
};
typedef Element* Stack;
Fie S pointer-ul la primul element din înlantuire, se echivaleaza
tipul Stack
cu typedef Element* Stack, iar conditia de stiva vida este S=0 :
push(S,a)
{
p=get_sp()
data(p)=a
link(p)=S
S=p
}
pop(S)
{
if S=0 then eroare("Stiva vida")
else |½ p=S;
| S=link(S)
|_ ret_sp(p)
}
top(S)
{
if S=0 then eroare("Stiva vida")
else return(data(S))
}
isEmpty(S)
{
return(S==0)
}
Stivele sunt cele mai simple structuri de date, ele avƒnd si
operatiile
imediate.
Cozi ordonate
O coada este o lista în care operatiile de acces sunt restrictionate
la
inserarea la un capat si stergerea de la celalat capat.
Pricipalele operatii de acces sunt:
PUT(Coada, Atom) Coada
Adauga un element la coada.
GET(Coada) Coada, Atom
Scoate un Atom din coada.
Returneaza atomul scos.
O coada poate fi organizata pe un spatiu de memorare de tip tablou
(vector).
Sunt necesari doi indicatori:
head indica: primul element care urmeaza sa fie scos.
tail indica: locul unde va fi pus urmatorul element adaugat la coada.
Conditia "coada vida" este echivalenta cu: head = tail. Initial
indicatorii vor
fi initializati astfel încƒt sa indice ambii primul element din
vector.
Operatia PUT înseamna:
- V[tail] primeste Atomul adaugat;
- incrementeaza tail.
Operatia GET înseamna:
- întoarce V[head];
- incrementeaza head
Se observa ca adaugari si stergeri repetate în coada deplaseaza
continutul
cozii la dreapta, fata de începutul vectorului. Pentru a evita acest
lucru ar
trebui ca operatia GET sa deplaseze la stƒnga continutul cozii cu o
pozitie.
Primul element care urmeaza sa fie scos va fi întotdeauna în prima
pozitie,
indicatorul head pierzƒndu-si utilitatea. Dezavantajul acestei solutii
consta
în faptul ca operatia GET necesita o parcurgere a continutului cozii.
Facem notatiile:
C coada
C.vect vectorul în care sunt memorate elementele cozii
C.head indicele elementului ce va fi scos din coada la urmatoarea
operatie get
C.tail indicele (pozitia) în care va fi memorat urmatorul element
adaugat la coada.
Conditia coada vida este
C.head=C.tail.
Functia put pune în coada C un atom a:
put(C,a)
{
if C.tail>DIMMAX then eroare("Coada plina")
else |½ C.vect [C.tail]=a
|_ C.tail=C.tail+1
}
Functia get scoate un element din coada si-l returneaza:
get(C)
{
if C.head=C.tail then eroare("Coada vida")
else |½ C.head=C.head+1
| return C.vect [C.head-1];
}
isEmpty(C)
{
return(C.head==C.tail)
}
Cozi ordonate circulare
Pentru a obtine o coada circulara vom porni de la o coada liniara
simpla
(cu doi indicatori) si vom face în asa fel încƒt la incrementarea
indicatorilor
head si tail, cƒnd acestia ating ultima pozitie din vector sa se
continue cu
prima pozitie din vector.
Functia urmatoare poate realiza aceasta cerinta:
int nextPoz(int index)
{
if (index<DIMVECTOR-1) return index+1;
else return 0;
}
unde DIMVECTOR este dimensiunea vectorului în care se memoreaza
elementele
cozii.
Continutul cozii va arata asa:
sau asa:
Conditia "coada vida" ramƒne echivalenta cu: head = tail
Coada va fi plina daca: head=1 si tail=DIMVECTOR
sau daca: tail+1 = head
Ambele situatii sunt continute în conditia:
nextPoz(tail) = head // conditia "coada plina"
Coada circulara ordonata asigura reutilizarea spatiului eliberat de get
la urmatoarele inserari în coada.
Observatie:
In coada circulara de dimensiune DIMMAX pot fi memorate DIMMAX
elemente.
"Coada plina" se realizeaza în 2 situatii:
a) C.head=1 si C.tail=DIMMAX
b) C.tail+1=C.head
Iar, conditia C.head=inc(C.tail) le contine pe amƒndoua.
In cazul cozilor circulare se modifica doar operatiile put si get:
put(C,a)
{
if C.head=inc(C.tail) then eroare("Coada plina")
else |½ C.vect[C.tail]=a
|_ C.tail=inc(C.tail)
}
get(C)
{
if C.head=C.tail then eroare("Coada vida")
else |½ a=C.vect [C.head]
| C.head= inc (C.head)
|_ return(a)
}
Curs 4
Cozi inlantuite
O coada poate fi implementata printr-o lista inlantuita la care
operatiile de
acces sunt restrictionate corespunzator.
Este nevoie de doi indicatori (pointeri):
head indica primul element din coada (primul care va fi scos);
tail indica ultimul element din coada (ultimul introdus).
O coada vida va avea: head=tail=nil
In mod obisnuit, adaugarea unui element in coada modifica numai tail
iar
stergerea unui element numai head. ×ntr-un mod special trebuie sa fie
tratate cazurile:
adaugare intr-o coada vida:
Initial: head=tail=nil
Final: Coada cu un element:
stergere dintr-o coada cu un element:
Initial: Coada cu un element
Final: head=tail=nil
In aceste cazuri se modifica atƒt head cƒt si tail.
Facem notatiile :
C.head pointer la primul element din coada;
C.tail pointer la ultimul element din coada;
C coada.
Conditia de coada vida este head=0.
Operatiile cozii inlantuite
Functia put insereaza un element in coada, in pozitia fata:
put(C,a)
{
p= get_sp();
data(p); link(p)= 0;
if C.head=0 then |½ C.head= p
|_ C.tail= p
else |½ link(C.tail)= p
|_ C.tail= p
}
Functia get scoate un element din pozitia fata:
get(C,a)
{
if C.head= 0 then eroare("Coada plina")
else |½ a= data(C.head)
| p= C.head
| C.head= link(C.head)
| ret_sp(p)
|_ return(a)
}
Functia front returneaza elementul din fata cozii, fara a-l scoate din
coada.
front(C)
{
if C.head=0 then eroare("Coada vida")
else return data(C.head)
}
isEmpty(C)
{
return(C.head=0)
}
Exista aici un element de redundanta: ar fi convenabil sa nu mai avem
spatiu
suplimentar de memorare, ci, sa avem un singur pointer ca sa putem
manevra
coada. De aceea apar utile cozile inlantuite circulare.
Cozi inlantuite circulare
Daca reprezentam coada printr-o structura inlantuita circulara va fi
nevoie
de un singur pointer prin intermediul caruia se pot face ambele
operatii de
adaugare si stergere din coada:
Fie:
C pointer la ultimul element din coada
link(C) pointer la primul element din coada
Operatiile de plasare si de scoatere din coada, sunt:
put(C,a)
{
p= get_sp()
data(p)=a
if C=0 then |½ C= p
| link(C)= p
else |½ link(p)= link(C)
| link(C)= p
|_ C= p
}
get(C)
{
if C= 0 then eroare("Coada vida")
else if C=link(C) then |½ a= data(C)
| ret_sp(C)
| C= 0
|_ return(a)
else |½ {p= link(C)
| link(C)= link(p)
| a= data(p)
| ret_sp(p)
|_ return(a)
}
front(C) returneaza data(link(C))
isEmpty(C) retuneaza conditia C=0.
Complexitatea algoritmilor
La evaluarea (estimarea) algoritmilor se pune in evidenta necesarul de
timp si
de spatiu de memorare al lui.
Studierea complexitatii presupune analiza completa in cadrul
algoritmului a
urmatoarelor 3 puncte de vedere:
1.configuratia de date cea mai defavorabila (cazurile degenerate);
2.configuratia de date cea mai favorabila;
3.comportarea medie.
Punctul 3 presupune probabilitatea de aparitie a diferitelor
configuratii de
date la intrare.
Punctul 1 este cel mai studiat si este folosit, de obicei, pentru
compararea
algoritmului. Si in ceea ce priveste timpul, se studiaza configuratia
cea mai
defavorabila a algoritmului.
Complexitatea unui algoritm se noteaza cu: O(f(n)).
Definitie
Fie f : N N si g : N N doua functii.
Spunem ca f O(g) si notam f = O(g) daca si numai daca o constanta c R
si
un numar n0 N astfel incƒt pentru n n0 f(n) cg(n)
Observatie:
f : N N este o functie f(n) cu n dimensiunea datelor de intrare.
f(n) reprezinta timpul de lucru al algoritmului exprimat in "pasi".
Lema 1
Daca f este o functie polinomiala de grad k, de forma:
f(n) = ak nk + ak-1nk-1 + ... + a1 n + a0, atunci f = O(nk).
Facƒndu-se majorari in membrul drept, obtinem rezultatul de mai sus:
f(n) = ak nk + ak-1 nk-1 + ... +a1 n +a0 < nkú (ak + ak-1 + a0) < nk c
pentru n > 1 f(n) < c nk, cu n0 = 1.
Concluzie: f = O(nk), si ordinul O exprima viteza de variatie a
functiei, functie de argument.
Exemplu: Calcularea maximului unui sir
maxsir(A,n)
{
max = A[1]
for i= 2 to n do
if A[i] > max then
max = A[i]
return (max)
}
Exprimam:
T(n) timpul de executie in pasi al acestui algoritm;
T(n)= 1 + 2(n-1) = numarul de atribuiri si comparatii
Cazul cel mai defavorabil: situatia in care vectorul este ordonat
crescator
(pentru ca de fiecare data se face si comparatie si atribuire).
Putem spune ca T(n) = O(n), este o functie polinomiala de gradul I.
Conteaza
doar Ordinul polinomului, nu coeficientul termenului de grad maxim. Iar
la
numararea pasilor ne concentram asupra numarului buclelor, nu asupra
pasilor
din interiorul buclei.
Exemplu: Insertion Sort (algoritmul de sortare prin inserare)
Algoritmul INSERTION SORT considera ca in pasul k, elementele A[1ök-1]
sunt
sortate, iar elementul k va fi inserat, astfel incƒt, dupa aceasta
inserare,
primele elemente A[ ök] sa fie sortate.
Pentru a realiza inserarea elementului k in secventa A[1ök-1], aceasta
presupune:
memorarea elementului intr-o varibila temporara;
deplasarea tuturor elementelor din vectorul A[1ök-1] care sunt mai
mari decƒt
A[k], cu o poziie la stƒnga (aceasta presupune o parcurgere de la
dreapta la
stƒnga);
plasarea lui A[k] in locul ultimului element deplasat.
Complexitate: O(n)
insertion_sort(A,n)
{
for k= 2 to n do
|½temp = A[k]
|i=k-1;
|while (i>=1) and (A[i] > temp) do |½ A[i+1] = A[i]
|_ i=i-1
|_ A[i+1] = temp
}
Cazul cel mai dafavorabil: situatia in care deplasarea (la dreapta cu o
pozitie in vederea inserarii) se face pƒna la inceputul vectorului,
adica
sirul este ordonat descrescator.
Exprimarea timpului de lucru:
T(n) = 3ú(n - 1) + (1 + 2 + 3+ ... + n - 1) = 3(n-1) + 3n (n - 1)/2
Rezulta complexitatea: T(n) = O(n2) functie polinomiala de gradul II.
Observatie: Cƒnd avem mai multe bucle imbricate, termenii buclei celei
mai
interioare dau gradul polinomului egal cu gradul algoritmului.
Bucla cea mai interioara ne da complexitatea algoritmului.
Exemplu: Inmultirea a doua matrici
prod_mat(A,B,C,n)
{
for i = 1 to n do
for j = 1 to n do
| C[i,j] = 0
|for k = 1 to n do
| C[i,j] = C[i,j] + A[i,k] * B[k,j]
}
Rezulta complexitatea O(n3).
Exemplu: Cautarea binara(Binary Search)
Fie A, de ordin n, un vector ordonat crescator. Se cere sa se determine
daca o
valoare b se afla printre elementele vectorului. Limita inferioara se
numeste
low, limita superioara se numeste high, iar mijlocul virtual al
vectorului, mid
(de la middle).
Binary_search(A,n,b)
{
low = 1;
high = n;
while low >= high do
|½ mid = [(low + high)/2] //partea intreaga
| if A[mid]=b then return (mid)
| else if A[mid]>b then high=mid-1 //restrƒng
| //cautarea la partea
| //stƒnga
|else low = mid+1 //restrƒng cautarea
//la dreapta
return(0)
}
Calculul complexitatii algoritmului consta in determinarea numarului de
ori
pentru care se executa bucla while.
Se observa ca, la fiecare trecere, dimensiunea zonei cautate se
injumatateste.
Cazul cel mai defavorabil este ca elementul cautat sa nu se gaseasca in
vector.
Pentru simplitate se considera n = 2k unde k este numarul de
injumatatiri.
Rezulta k = log2 n si facƒnd o majorare, T(n) log2 n + 1 n, a.i. 2k
n < 2k+1.
Rezulta complexitatea acestui algoritm: este O(log2n). Dar, baza
logaritmului
se poate ignora, deoarece: logax = logbx logab si logab este o
constanta, deci
ramƒne O(log n), adica o functie logaritmica.
Proprietati:
1) Fie f, g : N N.
Daca f = O(g) | k f = O(g)
| f = O(k g) , k R constant.
2) Fie f, g, h : N N.
si: f = O(g) |
g = O(h) | f = O(h)
3) Fie f1, f2, g1, g2 : N N.
si: f1 = O(g1) | | f1 + f2 = O(g1 + g2)
f2= O(g2) | | f1 f2 = O(g1g2)
Aceasta proprietate permite ca, atunci cƒnd avem doua bucle imbricate
(de
complexitati diferite), complexitatea totala sa se obtina inmultindu-se
cele
doua complexitati. Cele doua complexitati se aduna, daca buclele sunt
succesive.
Teorema:
Oricare ar fi doua constante c > 0, a > 1, si f : N N, o functie
monoton
strict crescatoare, atunci:
(f(n))c= O(af(n))
Intre clasa functiilor logaritmice, si cea a functiilor polinomiale
exista
relatia: O(nc) O(an).
Au loc urmatoarele incluziuni:
O(1) O(log n) O(n) O(nlog n) O(n2) O(nklog n) O(nk+1) O(2n)
Pentru calculul complexitatii se va incerca incadrarea in clasa cea mai
mica
de complexitate din acest sir:
O(1) clasa algoritmilor constanti;
O(log n) clasa algoritmilor logaritmici;
O(n) clasa algoritmilor liniari;
O(nlog n) clasa algoritmilor polilogaritmici;
O(n2) clasa algoritmilor patratici;
O(nklog n) clasa algoritmilor polilogaritmici;
O(nk+1) clasa algoritmilor polinomiali;
O(2n) clasa algoritmilor exponentiali.
Curs 5
Am vazut ca:
Algoritmul recursiv si relatii de recurenta
Exemplu:Problema turnurilor din Hanoi
Se dau n discuri: a1, a2, ... , an de dimensiuni diferite, cu
d1 < d2 < ... < dn , di - fiind diametrul discului. Discurile
respective
sunt stivuite pe o tija:
Se cere sa se deplaseze aceasta stiva pe o alta tija, folosind ca
manevra o
tija auxiliara, respectandu-se conditia << Un disc nu poate fi plasat
decat
peste un disc mai mare >>.
Problema P(n) a deplasarii a n discuri, se rezolva prin deplasari
succesive
ale discurilor de pe o tija pe alta. Deplasarea de pe o tija pe alta
este echivalenta cu deplasarea a n-1 discuri de pe tija intiala
(ti) pe tija de manevra, apoi plasarea celui mai lung disc pe tija
finala,
pentru ca la sfarsit sa se aduca de pe tija de manevra (tm), pe tija
finala
(tf), cele n-1 discuri deplasate.
Primele miscari s-ar figura astfel:
Procedura Hanoi:
Hanoi(n, ti, tf, tm)
{
if(n=1) then muta (ti, tf) //deplaseaza discul superior // de pe ti pe
tf
else | Hanoi(n-1, ti, tm, tf)
| muta(ti, tf)
|_ Hanoi(n-1, tm, tf, ti)
}
Pentru o problema P(1) , timpul T(1) = 1 , pentru o mutare.
Pentru P(n) , timpul:
(1)
Dorim sa aflam ordinul de complexitate a lui T(n).
Asociem relatiei (1) ecuatia caracteristica:
Facand identificarea:
Ordinul este O(2n), adica o complexitate exponentiala.
Relatii de recurenta. Clasele relatiilor de recurenta
1.f(n) = aùf(n - 1) + b
x0 = aùx0 + b
Prin scaderea celor doua relatii, rezulta un algoritm exponential cu
baza a:
f(n) - x0 = a (f(n-1) - x0)
2.f(n)=aùf(n-1)+bùf(n-2)
f(n) = tü => tü = aùt(la n-1) + bùt(la n-2)
Facand n = 2, tý = aùt + b , cu urmatoarele cazuri:
a) t1 , t2 apartin R => solutia ecuatiei este de forma:
f(n)=alfaùt1ü+betaùt2ü iar alfa si beta se calculeaza din
conditiile initiale:
cu x1 si x2 constante.
Astfel, este rezolvata ecuatia recursiva.
b) t1 = t2 = t Solutia este de forma:
c) t1, t2 C Solutia este de forma:
In care si C, = (conjugat) solutia trigonometrica:
3.Clasa de relatii de recurenta pentru algoritmi de tip "divide et
impera"
Exemplu: Algoritmul Merge Sort (sortare prin interclasare)
Pentru a sorta o secventa de n elemente ale unui vector A, se imparte
vectorul
in 2 segmente de lungime n/2 pe care le sorteaza separat recursiv, dupa
care
urmeaza interclasarea.
Pseudocod:
Procedura MERGE_SORT primeste ca argumente A - vectorul de sortat, si
doi
indici care delimiteaza o portiune din acest vector. Apelul initial va
fi
MERGE_SORT(A, 1, n).
MERGE_SORT(A, low, high)
{
if(low high) return
else | |½ low + high ½|
| mid=| ---------------- | //partea intreaga
| |_ 2 _|
| MERGE_SORT(A, low, mid) //sortare separata
| MERGE_SORT(A, mid+1, high) //sortare separata
|_MERGE(A, low, mid, high) //interclasare
}
Procedura MERGE interclaseaza secventele sortate A[lowömid] si
A[mid+1öhigh].
Pentru aceasta este nevoie de un vector auxiliar B, de aceeasi
dimensiune cu A.
MERGE(A, low, mid, high)
{
i=low; j=mid+1; k=low;
while i mid and j high do
|½ if A[i] <A [j] then B[k]=A[i]; i=i+1
| else B[k] = A[j]; j=j+1
|_ k = k+1
while i mid do
|½ B[k] = A[i]; i=i+1
|_ k = k+1
whilej high do
|½ B[k] = A[j]; j=j+1
|_ k = k+1
for k=low to high do
A[k] = B[k];
}
Aratam complexitatea procedurii MERGE_SORT: O(nlog n)
Aceasta functie cere pentru o secventa cn operatii.
Timpul de executie al algoritmului este:
Consideram: n = 2k;
T(n) = 2T(n/2) + n = 2(2T(n/4) + n/2) + n = ... = 22úT(n/22) + 2n=
22 (2úT(n/23) + n/22) + 2n =
= 23T(n/23) + 3n = ... = 2kT(n/2k) + kn T(n) = kn = nlog2n ,
pentru ca n = 2k , si, deci, k = log2n.
Asadar complexitatea algoritmului este O(nlog n).
Pentru a rezolva problema de dimensiune n, se rezolva pentru a
probleme de dimensiune n/b, iar combinarea rezultatelor celor a
prbleme, duce
la lg(n) operatii.
Se demonstreaza, analog, si relatia de recurenta:
Solutia acestei ecuatii de recurenta este:
Utilizand aceste retete putem calcula complexitatile pentru:
algoritmul Merge_Sort: a = 2 , b = 2 , k = 1 , bk = a complexitatea
O(nklog n)
algoritmul Binary_Search: a = 1 , b = 2 , k = 0 complexitatea
O(n0log n) = O(log n), (situatia ak= b).
4.Relatii de recurenta cu istorie completa
Exemplu:
Exemplu: Algoritmul Quick_Sort
Quik_Sort(A, low, high)
{
if(high low) then
|½ k= Partition(A, low, high) // procedura de |
// partitionare |
| Quick_Sort (A, low, k-1)
|_ Quick_Sort(A, k+1, high)
}
Pseudocodul pentru functia partition:
Partition(A, low, high)
{
l= low; h= high;
x= A[l];
while (l <h) do
I |½ while (A[l] x) and (l _high)
| do l= l+1
II | while (A[l] >x) and (h low)
| do h= h-1
|_ if (l <h) then interchange (A[l], A[h])
interchange (A[h], A[low])
return(h);
}
Algoritmul considera pivotul ca fiind: A[low]. Indicele l parcurge
vectorul
de la stanga la dreapta, iar indicele h parcurge vectorul de la dreapta
la
stanga. Ei se apropie pana se intalnesc (l = h). Deci, l lasa in urma
numai
elemente A[i] pivot, iar h lasa in urma numai elemente A[i] pivot.
Ciclul I while inseamna ca inainteaza l cat timp A[l] pivot. Acest
ciclu se opreste pe conditia
A[h] pivot, fixandu-se aici.
Ciclul II while insemna ca inainteaza h cat timp A[h] pivot. Acest
ciclu se
opreste pe conditia
A[h] pivot, fixandu-se aici.
Cele doua pozitii se schimba, astfel incat sa se permita inaintarea
indicilor
mai departe.
Pentru aflarea complexitatii, cercetam cazul cel mai defavorabil. Fie
cazul
in care vectorul este ordonat descrescator. Pivotul gasit, la primul
pas,
este elementul maxim din vector, rezulta ca trebuie plasat in ultima
pozitie.
Pivotul va fi maximul dintre elementele secventei, deci, va fi plasat
in ultima
pozitie din secventa.
Problema se imparte in 2 subprobleme: P(n) P(n-1) , P(0).
Numarul de comparatii pentru functia Partition este (n-1). Vectorul se
parcurge
in doua directii, dar o singura data.
Rezulta ca timpul de functionare al algoritmului Quick_Sort este:
Rezolvand aceasta ecuatie, avem:
unde: T(1) este 0 (nu se partitioneaza). Rezulta:
Aceasta suma este de complexitate O(n2). Rezulta ca este un algoritm
ineficient
Studiul complexitatii algoritmului Quick_Sort in caz mediu
Pentru complexitatea medie trebuie considerata probabilitatea tuturor
aparitiilor datelor de intrare. Consideram ca orice configuratie de
date la
intrare este egal probabila. Probabilitatea ca pivotul sa fie plasat in
pozitia
k este egala pentru . Asadar, pivotul va fi plasat in pozitia k prin
partitionare, cu o probabilitate egala cu 1/n, pentru .
Suma tuturor probabilitatilor este 1. Evenimentul este plasarea
pivotului in
pozitia k. Consideram Ti(n) timpul de executie al algoritmului
Quick_Sort
atunci cand pivotul este plasat in pozitia i:
Rezulta:
Timpul mediu va fi o medie aritmetica:
Dezvoltand,
(Facand schimbarea de variabila j = n - i + 1)
Rezulta relatia de recurenta cu istorie completa:
Aceasta se rezolva astfel: inmultind relatia cu n rezulta:
Scriem acum relatia inlocuind pe n cu n+1:
Si scazandu-le acum membru cu membru rezulta:
care se inmulteste cu: ,
Notam:
Facand o majorare:
(un element nu se ordoneaza).
Rezulta: si este aria zonei de sub graficul
functiei .
unde O(nln n) este complexitatea acestei functii.
Curs 6
Analiza spatiului de memorie consumat intr-un algoritm
Algoritmi recursivi
Algoritmii recursivi consuma memorie suplimentara pentru simularea
recursivitatii.
Fie urmatoarea procedura recursiva:
parcurgere(l) // l - lista inlantuita (pointer la primul element)
{
if(l 0)
|½ parcurgere(link(l))
|_ prelucrare(data(l)) // exemplu: afisare
}
Functia afiseaza o lista invers, de la coada la cap.
Apelul functiei se face astfel:
se creeaza in stiva programului o "inregistrare de activare" in care
sunt
memorate:
- parametrii de apel;
- adresa instructiunii de retur (cu care va continua programul dupa
terminarea executiei functiei);
se rezerva spatiu pentru variabile locale.
se executa instructiunile functiei care folosesc pentru parametri si
variabile locale din "inregistrarea de activare";
se scoate din stiva "inregistrarea de activare" (decrementarea
virfului stivei), stiva fiind ordonata;
se continua cu instructiunea data de adresa de retur memorata in
"inregistrarea de activare".
Asadar, variabilele globale (statice) sunt memorate intr-o zona de
memorie
fixa, mai exact in segmentele de date. Variabilele automate (locale) se
memoreaza in stiva, iar variabilele dinamice in "heap"-uri (cu malloc
in C,
si cu new in C++).
Consumul de memorie al algoritmului recursiv este proportional cu
numarul de
apeluri recursive ce se fac. Variabilele recursive consuma mai multa
memorie
decit cele iterative. La prelucrarea unei liste, daca primul element nu
este
vid, se prelucreaza acesta, urmind apoi ca restul listei sa fie
considerata
ca o noua lista mai mica, etc.
De exemplu, algoritmul Quick_Sort:
Quick_Sort(A, low, high)
{
if(low < high)
|½ k = Partition(A, low, high)
| Quick_Sort(A, low, k-1)
|_Quick_Sort(A, k+1, high)
}
Avem in acest algoritm doua apeluri recursive.
Cazul cel mai defavorabil:
Consideram consumul de memorie in stiva : M(n) = c + M (n - 1) M(n) =
O(n)
un ordin de complexitate mare.
Pentru reducerea consumului de memorie, se concepe un alt algoritm la
Quick_Sort, astfel incit un apel sa fie rezolvat recursiv, iar celalalt
apel
iterativ.
Quick_Sort(A, low, high)
{
while (low < high)
|½ k = Partition(A, low, high)
| if( k-low > high-k)
| |½ Quick_Sort(A, k+1, high)
| |_high = k-1
| else
| |½ Quick_Sort(A, low, k-1)
| _|_low = k-1
}
Necesarul de memorie pentru aceasta este M(n) c + M(n/2), insemnind ca
oricare ar fi secventa mai mica, ea este decit jumatatea M(n) = O(log
n)
am redus ordinul de complexitate.
Liste generalizate
Definitie:
Data o multime de elemente (atomi), se numeste lista generalizata o
secventa
finita (1, 2, ... , n), in care i sunt atomi.
Exemplu: A = (a, b, c)
B = (x, A, (a, c), ( ))
| | | \
atom lista lista lista vida
Observatie: Listele generalizate pot sa aiba elemente comune. Se
permite
definirea de liste recursive.
Reprezentarea listelor generalizate
Presupunem o lista de forma: (tag, data, link) in care tag este o
eticheta
{0,1}.
Daca tag = 0 nodul va corespunde unui element atomic cimpul data va
contine
atomul respectiv.
Daca tag = 1 nodul va corespunde unei subliste cimpul data va semnifica
legatura la primul element al sublistei; link este legatura pentru
urmatorul
nod din lista.
Fie urmatoarele primitive de selectie pentru un nod de adresa p:
p adresa unui nod;
link(p) cimpul "link" din nodul indicat de p;
Notam: tag(p) cimpul "tag" din nodul indicat de p
data(p) cimpul "data" din nodul indicat de p
Fie urmatoarele liste:
D = ( )
A = (a, (b, c))
B = (A, A, ( ))
C = (a, C)
cu urmatoarele reprezentari:
D : o lista vida inseamna un pointer nul
Ne propunem sa dam nume unei subliste, deci daca tag = 1, adica tag(p)
= 1
data(p) va fi adresa unei structuri ce contine:
Asadar, obtinem urmatoarea reprezentare:
Operatii la liste generalizate:
functia insert, este asemanatoare cu cea de la liste inlantuite.
Elementul
ce se insereaza poate fi un atom sau o sublista;
functia del ( ) trebuie sa tina seama de existenta unor liste comune.
Deci,
este necesara pastrarea in elementul ce contine numele listei A si a
unui
indicator care sa contorizeze numarul de referinte ale lui.
Exemplu:
Numai daca acest indicator este 0, se face stergerea efectiva a listei.
Traversarea listelor generalizate
Traversarea listelor generalizate presupune prelucrarea elementelor
listei,
si a elementelor sublistelor componente.
Exemplu: O functie de copiere si o functie de test de egalitate a doua
liste
generalizate, realizate recursiv si iterativ. Functia returneaza o
copie a
listei. Copie mai intai primul element, si apoi recursiv restul listei:
Varianta recursiva:
Copy (l) // l - lista inlantuita
{
if (l = 0) then return (0)
else |½ p = get_sp()
| data(p) = data(l)
| link(p) = Copy(link(l))
|_ return(p)
}
Copy (l) // l - lista generalizata
{
if (l = 0) then return (0)
else |½ p = get_sp()
| if (tag(l) = 0) then data(p) = data(l)
| else data(p) = Copy(data(l))
| link(p) = Copy(link(l))
|_ return(p)
}
Functia pentru testarea egalitatii este:
isEqual (l1,l2) // procedura tratata iterativ
{
p1 = l1; p2 = l2
while(p1 0 and p2 0)
|½ if (data(p1) data(p2)) then return (FALSE)
| p1 = link(p1)
|_ p2 = link(p2)
return(p1 = p2)
}
isEqual (l1,l2) // procedura tratata recursiv
{
p1 = l1; p2 = l2
while(p1 0 and p2 0)
|½ if (tag(p1) tag(p2)) then return (FALSE)
| if (tag(p1) = 0 and data(p1) data(p2)) then return (FALSE)
| if (tag(p1) = 1 and not isEqual(data(p1),data(p2)) then
return (FALSE)
| p1 = link(p1)
|_ p2 = link(p2)
return (p1 == p2)
}
Curs 8
Arborele binar de cautare (BST)
Arborele binar de cautare reprezinta o solutie eficienta de
implementare a
structurii de date numite "dictionar". Vom considera o multime "atomi".
Pentru fiecare element din aceasta multime avem: a atomi, este definita
o functie numita cheie de cautare: key(a)a partine lui k cu
proprietatea ca
doi atomi distincti au chei diferite de cautare: a1!=a2=>
key(a1)!=key(a2).
Exemplu: (abreviere, definitie) ("BST","Binary Search Tree")
("LIFO","Last In First Out") key(a) = a.abreviere
Un dictionar este o colectie S de atomi pentru care se definesc
operatiile:
insert(S,a) insereaza atomul a in S daca nu exista deja;
delete(S,k) sterge atomul cu cheia k din S daca exista;
search(S,k) cauta atomul cu cheia k in S si-l returneaza sau determina
daca
nu este.
O solutie imediata ar fi retinerea elementelor din S intr-o lista
inlantuita,
iar operatiile vor avea complexitatea O(n).
Tabelele Hashing
Acestea sunt o alta solutie pentru a retine elementele din S.
Complexitatea
pentru arborele binar de cautare in cazurile:
cel mai defavorabil: O(n);
mediu: O(log n).
Un arbore binar de cautare este un arbore T ale carui noduri sunt
etichetate
cu atomii continuti la un moment dat in dictionar.
T = (V, E) , ˆVˆ = n. (n atomi in dictionar)
Considerand r V (radacina arborelui), Ts subarborele stang al radacinii
si
Td subarborele drept al radacinii, atunci structura acestui arbore este
definita de urmatoarele proprietati:
1) un 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.
Observatii:
1) Consideram ca pe multimea k este definita o relatie de ordine (de
exemplu
lexico-grafica);
2) Pentru oricare nod din BST toate nodurile din subarborele stang sunt
mai
mici decat radacina si toate nodurile din subarborele drept sunt mai
mari decat
radacina.
Exemple: 15 15
/ \ / \
7 25 10 25
/ \ / \ / \ /
2 13 17 40 2 17 13
/ / \
9 27 99
este BST nu este BST.
3) Inordine: viziteaza nodurile in ordine crescatoare a cheilor:
2 7 9 13 15 17 25 27 40 99
Functii:
1)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
}
2)Insert:
Se va crea un nod in arbore care va fi plasat la un nou nod terminal.
Pozitia in care trebuie plasat acesta este unic determinata in functie
de
valoarea cheii de cautare.
Exemplu: vom insera 19 in arborele nostru:
15
/ \
7 25
/ \ / \
2 13 17 40
/ \ / \
9 19 27 99
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)
}
Functia 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)
}
Observatie:
1)La inserarea unui atom deja existent in arbore, functia insert nu
modifica
structura arborelui. Exista probleme in care este utila contorizarea
numarului
de inserari a unui atom in arbore.
2)Functia insert poate returna pointer la radacina facand apeluri de
forma
p= insert(p,a).
3)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 // in 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.:
1) 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
}
15
/ \
7 25
/ \ / \
2 13 17 40
/ /
9 27
/ \
26 33
Detasarea din structura arborelui BST a celui mai mare nod
(remove_greatest):
Pentru a gasi cel mai mare nod dintr-un arbore binar de cautare, se
inainteaza
in adancime pe ramura dreapta pana 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 SAS subarborele stang (SAS).
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)))
}
Observatie:
Functia remove_greatest modifica arborele indicat de parametru, in
sensul
eliminarii nodului cel mai mare, si intoarce pointer la nodul eliminat.
Demonstratia eficientei (complexitate)
Complexitatea tuturor functiilor scrise depinde de adancimea arborelui.
In cazul cel mai defavorabil, fiecare functie parcurge lantul cel mai
lung
din arbore. Functia de cautare are, in acest caz, complexitatea O(n).
Structura arborelui BST este determinata de ordinea inserarii.
De exemplu, ordinea 15 13 12 11 este alta decat 15 12 11 13 .
Studiem un caz de complexitate medie:
Crearea unui BST pornind de la secventa de atomi (a1 a2 ... an)
gen_BST (va fi in programul principal)
| rad= 0
| for i= 1 to n
| insert (rad, ai)
Calculam complexitatea medie a generarii BST:
Complexitatea in cazul cel mai defavorabil este:
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, in urma primei operatii de
inserare pe care o facem, rezulta:
a1
/ \
a1 ai
(ai<a1) (ai>a1)
Nu vom considera numararea operatiilor in ordinea in care apar ele, ci
consideram numarul de operatii globale. Dupa ce am inserat a1, pentru
inserarea fiecarui element in SAS sau SAD a lui a1, se face o
comparatie cu a1.
Deci:
T(n)= (n - 1) + val.med.SAS + val.med.SAD
val.med.SAS = valoarea medie a numarului de comparatii necesar pentru a
construi subarborele stang SAS
val.med.SAD = valoarea medie a numarului de comparatii necesar pentru a
construi subarborele drept SAD
Notam:
Ti(n) = numarul mediu de comparatii necesar pentru construirea unui BST
cu n
noduri atunci cand prima valoare inserata (a1) este mai mare decat i-1
dintre
cele n valori de inserat. Putem scrie:
Deci:
Deci:
Complexitatea acestei functii este: O(nln n) (vezi curs 5 complexitatea
medie
a algoritmului Quick-Sort)
Arbori binari de cautare dinamic echilibrati (AVL)
Definitie
Un arbore binar este echilibrat daca si numai daca, pentru fiecare nod
din arbore, diferenta dintre adancimile SAS si SAD in modul este 1.
Exemple:
a a
/ \ / \
b c b c
/ \ / \ / \ \
d e f g d e f
/ \
g h
arbore binar arbore binar
complet echilibrat echilibrat
Adancimea 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, in 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.
Caz 1: Fie arborele echilibrat
A
/ \
B T3 h = depth(T1) = depth(T2) = depth(T3)
/ \
T1 T2
Consideram arborii T1, T2, T3 echilibrati. Inserand un nod prin rotatie
simpla,
rezulta structurile rotit simplu la dreapta si rotit simplu la stanga
imaginea
oglinda a rotatiei dreapta:
A A
/ \ / \
B T3 T3 B
/ \ / \
T1 T2 T2 T1
Caz 2: Inserarea se face prin rotatii duble:
A A
/ \ / \
B T3 T3 B
/ \ / \
T1 T2 T2 T1
rotatie dubla rotatie dubla
la dreapta la stanga
Fie primul caz:
A
/ \
B T3
/ \
T1 T2 este BST: T1 < B < T2 < A < T3
Toti arborii care respecta in continuare aceasta conditie vor fi BST.
Ridicand pe B in sus, si notand cu // legaturile neschimbate, rezulta:
B
// \
// A
T1 / \\
____________T2___T3_________ pe aceeasi linie
care este un BST , deci este arbore echilibrat, si are aceeasi adancime
(!!!)
cu arborele initial (de dinainte de inserare). Nodurile superioare nu
sunt
afectate. Rationament analog pentru imaginea oglinda.
Fie cazul 2: Pentru rotatia dubla se detaliaza structura arborelui T2.
Nu se poate sparge arborele initial ca in cazul 1.
A
/ \\
B \\
// \ T3
// C
// / \
T1 T2S T2D
depth(T1) = depth(T3) = h
depth(T2S) = depth(T2D) = h - 1
In urma inserarii, unul dintre arborii T2S si T2D isi mareste
adancimea.
Aplicam aceiasi tehnica:
T1 < B < T2S < C < T2D < A < T3
Incepem cu C:
C
/ \
B A
// \ / \\
// T2S T2D \\
______T1___________________ T3_____________________
la acelasi nivel
Rezulta un BST echilibrat, de aceeaai adancime cu arborele initial.
Rotatiile
sunt duble, in sensul ca
s-a facut o rotatie simpla B la stanga cu o rotatie simpla A la
dreapta.
Operatiile care trebuiesc facute in cazul 1 (rotatie simpla la
dreapta):
r- pointer la nodul radacina (A)
a- pointer la radacina
p = lchild(r) b = lchild(a)
lchild(r) = rchild(p) lchild(a) = rchild(b)
rchild(p) = r rchild(b) = a
r = p a = b
Operatiile care trebuiesc facute in cazul 2 (rotatie dubla)
b = lchild(a)
c = rchild(b)
lchild(a) = rchild(c)
rchild(b) = lchild(c)
rchild(c) = a
lchild(c) = b
a = c // se schimba radacina arborelui.
Curs 9
Asadar, in inserarea prin rotatie se obtine un arbore echilibrat cu
adancimea
egala cu adancimea arborelui de dinainte de inserare. La inserarea unui
nod
terminal intr-un arbore AVL este necesara aplicarea a cel mult o
rotatie asupra
unui nod. Trebuie, deci sa gasim nodul asupra caruia trebuie aplicata
rotatia.
Reprezentam ramura parcursa de la radacina la nodul inserat:
x bf = 1
/
y bf = 0
\
z bf = - 1 (bf = -2 dupa inserare)
\
w bf = 0 (bf = 1 dupa inserare)
/
v bf = 0 (bf = -1 dupa inserare)
\
nodul
inserat
S-a notat pentru fiecare nod bf balance factor (factor de
dezechilibrare):
bf(nod) = depth (lchild (nod)) depth (rchild (nod))
adica este diferenta dintre adancimea subarborelui stang si adancimea
subarborelui drept.
Calculam factorii de balansare dupa inserare.
Observatie: Pentru nodul terminal s-a schimbat adancimea si factorul de
balansare; bf = -2 dupa inserare devine nod dezechilibrat. Trebuie
aplicata,
deci, echilibrarea.
Definitie:
Se numeste nod critic primul nod cu bf 0 intalnit la o parcurgere de
jos
in sus a ramurii care leaga nodul inserat de radacina.
Observatie: 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.In acest caz nu
este
nevoie de rotatie (el completeaza un gol in arbore).
2.Factorul de balansare devine bf = 2 sau bf = -2 atunci cand nodul
inserat
mareste dezechilibrul arborelui (s-a inserat nodul in subarborele cel
mai mare)
In acest caz, se aplica o rotatie in urma careia se schimba strucutra
subarborelui, astfel incat noua radacina capata bf = 0, conservandu-se
adancimea.
Concluzie: Problema conservarii proprietatii de echilibrare a arborelui
se
rezolva aplicand o rotatie asupra nodului critic numai atunci cand
inserarea
dezechilibreaza acest nod.
Costul suplimentar care trebuie suportat se materializeaza prin
necesitatea
ca in fiecare nod sa se memoreze factorul de dezechilibrare bf. Acesti
factori
de dezechilibrare vor fi actualizati in urma operatiilor de rotatie si
inserare
Operatia de stergere intr-un AVL implica mai multe rotatii, ea nu se
studiaza
in acest curs.
Exemplu: Se da arborele cu urmatoarea structura:
55
/ \
20 80
/ \ \
10 35 90
/ /
5 30
Sa se insereze nodurile 15, apoi 7 si sa se echilibreze arborele.
Inseram prima valoare 15. Comparam mai intai cu 55 : e in stanga lui,
s.a.m.d. pana cand gasim locul ei in pozitia de mai jos. Pentru a doua
valoare
de inserat, 7, nodul critic este 55. El este dezechilibrat stanga.
Deci, va fi
echilibrat la valoarea 2. Este necesara aplicarea unei rotatii asupra
radacinii
55
/ \
20 80
/ \ \
10 35 90
/ \ /
5 15 30
\
7
Facem o identificare cu unul din desenele de echilibrare prezentate in
cursul
anterior. Se asociaza nodurile:
55->A
20->B etc. =>
20 ----------> noduri implicate
/ \ in
10 55 ------> rotatie
/ \ / \
5 15 35 80
\ / \
7 30 90
In urma unei rotatii simple, factorii de dezechilibru implicati in
rotatie
devin zero.
Fie o a treia valoare de inserat 3, apoi a patra 9:
Nodul critic pentru 3 este 5, iar pentru 9 este este 10. Dupa rotatia
aplicata
(T2D, T2S vizi), rezulta arborele:
20
/ \
7 55
/ \ / \
5 10 35 80
/ / \ / \
3 9 15 30 90
La rotatia dubla, daca nodul 9 a fost inserat in subarborele T2S,
B are bf = 0 |
A are bf = -1 | exceptie facand nodul C nodul de inserat
La rotatia dubla, daca nodul 9 a fost inserat in subarborele T2D,
B are bf = 1 |
A are bf = 0 | exceptie facand nodul C nodul de inserat
Reprezentarea implicita a arborilor binari
In acest mod de reprezentare se reprezinta arborele printr-un tablou.
Fie un
arbore binar complet:
a
/ \
b c
/ \ / \
d e f g
/ \ / \ / \ / \
h i j k l m n o
care are 4 nivele, deci 24 - 1 = 15 noduri.
Asociem acestui arbore un vector V:
structurat astfel: radacina, nivelul 1 de la stanga la dreapta,
nodurile
nivelului 2 de la stanga la dreapta, etc, despartite de linii duble.
Lema
Daca in vectorul V un nod x este reprezentat prin elementul de vector
V(i), atunci:
1. left_child(x) este reprezentat in elementul de vector V [2úi];
2. right_child(x) este reprezentat in elementul de vector V [2úi + 1];
3. parent(x) este reprezentat in elementul de vector V [[i/2]]
cu observatia ca paranteza patrata interioara este partea intrega.
Demonstratie:
Se face inductie dupa i:
Pentru i = 1 => V[1] radacina
=> V[2] left_child(rad)
=> V[3] right_child(rad)
Presupunem adevarata lema pentru elementul V[i]=>V[2i] left_child
V[2i + 1] right_child
Elementul V[i + 1] este nodul urmator (de pe acelsi nivel sau de pe
nivelul urmator) intr-o parcurgere binara.
V[i + 1] => left_child in V[2i + 2] = V[2(i + 1)]
right_child in V[2i + 3] = V[2(i + 1) + 1]
Daca avem un arbore binar care nu este complet, reprezentarea lui
implicita se
obtine completandu-se structura arborelui cu noduri fictive pana la
obtinerea
unui arbore binar complet.
Arbori heap (heap gramada)
Definitie:
Se numeste arbore heap un arbore binar T = (V, E) cu urmatoarele
proprietati:
1) functia key : V R care asociaza fiecarui nod o cheie.
2) un nod v V cu degree(v) > 0 (nu este nod terminal), atunci:
key(v) > key(left_child(v)), daca left_child(v)
key(v) > key(right_child(v)), daca right_child(v)
(Pentru fiecare nod din arbore, cheia nodului este mai mare decat
cheile
descendentilor).
Exemplu:
99
/ \
50 30
/ \ / \
45 20 25 23
Observatie: De obicei functia cheie reprezinta selectia unui subcamp
din campul
de date memorate in nod.
Aplicatii ale arborilor heap
Coada cu prioritate;
Algoritmul Heap_Sort
Arborii heap nu se studiaza complet in acest curs.