Arbori binari de cautare
1. Introducere
2. Inserarea si cautarea unui nod intr-un arbore binar de cautare
3. Stergerea unui nod dintr-un arbore binar de cautare
4. Arbori binari de cautare AVL echilibrati
1. Introducere
Arborii binari de cautare sint o implementare a tipului de date abstract numit
"dictionar". Elementele unui dictionar pot fi ordonate, criteriul de sortare fiind dat de
"cheia de sortare" (sau cheie de cautare).
Arborii binari de cautare implementeaza eficient urmatoarele operatii:
search(arbore, k) - determina daca un element specificat prin cheia de sortare k,
exista in arbore si-l returneaza daca exista.
insert(arbore, x) - insereaza in arbore elementul x.
delete(arbore, k) - sterge un element specificat, specificat prin cheia k.
Proprietatea care defineste structura unui arbore binar de cautare este urmatoarea:
Valoarea cheii memorate in radacina este mai mare decit toate valorile cheilor continute
in subarborele sting si mai mica decit toate valorile cheilor continute in subarborele drept.
Aceasta proprietate trebuie sa fie indeplinita pentru toti subarborii, de pe orice nivel in
arborele binar de cautare.
2. Inserarea si cautarea unui nod intr-un arbore binar de cautare
a) varianta recursiva :
insert(r,a) // r - pointer la radacina (trasmis prin referinta)
// a - atomul de inserat
{
if r=0 then r = make_nod(a)
else if key(a) < key(data(r)) then
insert(lchild(r),a)
else if key(a) > key(data(r)) then
insert(rchild(r),a)
}
make_nod(a) // creeaza un nod nou in care memoreaza atomul a
{
p = get_sp() // aloca spatiu pentru un nod
data(p) = a
lchild(p) = rchild(p) = 0
return (p)
}
Pentru varianta de mai sus trebuie sa permitem functiei insert sa modifice valoarea
argumentului r, pentru aceasta el va fi un parametru transmis prin referinta. In
implementarea C++ functia insert va avea prototipul:
void insert(Nod*& r, Atom a);
O varianta care nu necesita argument referinta (deci poate fi implementata in C) este data
mai jos.
insert(r,a)
{
if r=0 then return ( make_nod(a) )
else if key(a) < key(data(r)) then
lchild(r) = insert(lchild(r),a)
else if key(a) > key(data(r)) then
rchild(r) = insert(rchild(r),a)
return (r)
}
Apelul acestei variante va avea de fiecare data forma:
rad = insert(rad, a)
Procedura search intoarce pointer la nodul cu cheia de cautare data sau pointerul NULL
daca nu exista nodul respectiv. Laborator de Structuri de Date si Algoritmi – Lucrarea nr. 6
search(r,k)
{
if ( r=0 ) return NULL
else if k < key(data(r)) then
return ( search(lchild(r),k) )
else if k > key(data(r)) then
return ( search(rchild(r),k) )
else return (r)
}
b) varianta nerecursiva
Trebuie observat ca atit operatia search cit si operatia insert parcurg o ramura a arborelui
(un lant de la radacina spre o frunza). Aceasta parcurgere poate fi efectuata iterativ. Este
vorba de a parcurge o inlantuire, deci se impune o analogie cu parcurgerea listei
inlantuite.
Parcurgerea listei inlantuite Parcurgerea unei ramuri in arbore
p=cap; p=rad;
while(p!=0){ while(p!=0){
┌────────────────────┐ ┌───────────────┐
│ Prelucrare element │ │ Prelucrea nod │
└────────────────────┘ └───────────────┘
p = p->link; if(conditie) p=p->stg
else p=p->drt;
} }
Procedura de inserare in arborele binar de cautare, realizata nerecursiv, are urmatoarea
forma (presupunem ca r este parametru transmis prin referinta):
insert(r,a)
{
if ( r=0 ) r = make_nod(a)
else {p = r
while ( p<>0 )
{
p1 = p
if key(a)<key(data(p)) then p=lchild(p)
else if key(a)>key(data(p)) then p=rchild(p)
else return
}
if ( key(a)<key(data(p1)) )
lchild(p1) = make_nod(a)
else rchild(p1) = make_nod(a)
}
}
3. Stergerea unui nod dintr-un arbore binar de cautare
In continuare vom scrie functia C++ pentru stergerea unei valori dintr-un arbore binar
de cautare care contine numere intregi.
Pentru stergerea unei valori din arbore este necesara mai intii identificarea nodului
care contine aceasta valoare. Vom folosi pentru aceasta tehnica prezentata la operatia
search. Pentru simplitate consideram nodurile etichetate cu numere intregi care vor
contitui chiar cheile de cautare (key(data(p) = data(p)).
struct Nod{
int data;
Nod* stg, *drt;
};
void delete(Nod*& rad, int a)
{
if(rad==NULL)
printf("Eroare: Valoarea %d nu este in arbore!", a);
else if( a<rad->data ) delete(rad->stg,a)
else if( a>rad->data ) delete(rad->drt,a)
else deleteRoot(rad);
}
Am redus sarcina initiala la a scrie functia deleteRoot care sterge radacina unui
arbore binar de cautare nevid. Pentru aceasta avem urmatoarele cazuri:
Atunci cind radacina nu are nici un descendent stergerea este o operatie
imediata.
Laborator de Structuri de Date si Algoritmi – Lucrarea nr. 6
Atunci cind radacina are un sigur descendent nodul sters va fi inlocuit cu
subarborele descendent.
Atunci cind radacina are doi descendenti, ea va fi inlocuita cu nodul cu
valoarea cea mai mare din subarborele sting, acest nod avind intotdeuana cel
mult un descendent. Nodul cel mai mare dintr-un arbore (subarbore) binar de
cautare se gaseste pornind din radacina si inaintind cit se poate spre dreapta.
Urmatoarea functie detaseaza dintr-un arbore binar de cautare nevid nodul cu
valoarea cea mai mare si intoarce pointer la acest nod.
Nod* removeGreatest(Nod*& r)
{
Nod* p;
if( r->drt==0 ) {
p = r;
r = r->stg;
return p;
}
else return removeGreatest(r->rchild);
}
Varianta prezentata este recursiva. Se poate scrie usor si o varianta nerecursiva pentru
aceasta procedura.
Tinind cont de cazurile posibile prezentate procedura deleteRoot va trata separat cazurile:
- daca subarborele sting este vid: promoveaza subarborele drept. Cazul in care si
subarborele drept este vid nu trebuie tratat separat, in acest caz se promoveaza
arborele vid (rad devine NULL);
- altfel daca, subarborele drept este vid: promoveaza subarborele sting.
- altfel (ambii subarbori nu sint vizi): inlocuieste radacina cu cel mai mare nod din
subarborele sting.
void deleteRoot(Nod*& rad)
{
Nod* p = rad;
if( rad->stg==0) rad = rad->drt;
else if( rad->drt==0) rad = rad->stg;
else {
rad = removeGreatest (rad->stg);
rad->stg = p->stg;
rad->drt = p->drt;
}
delete p;
}
TEMA 1
1. Se citeste de la intrare un sir de valori numerice intregi, pe o linie, separate de spatii,
sir care se incheie cu o valoare 0.
a) Sa se introduca valorile citite intr-un arbore binar de cautare (exclusiv valoarea 0
care incheie sirul).
b) Sa se afiseze in inordine continutul arborelui.
c) Se citeste o valoare pentru care sa se raspunda daca este sau nu continuta in arbore.
d) Se citeste o valoare care sa fie stearsa din arbore si apoi sa se afiseze arborele in
inordine.
4. Arbori binari de cautare AVL echilibrati
4.1. Introducere
Arbori binari echilibrati
Un arbore binar echilibrat este definit de proprietatea ca, pentru fiecare nod, diferenta
dintre adincimea subarborelui sting si cea a subarborelui drept este cel mult 1.
Se demonstreaza ca adincimea unui arbore echilibrat cu n noduri interne satisface
relatia:
.1 4404 log ( )2 .0 328 h < ∗ 2
n + −
Ca urmare, parcurgerea unei ramuri in arborele binar echilibrat se va face in O(log n)
pasi.
Arbori binari de cautare echilibrati
Operatia de cautare intr-un arbore binar de cautare care are si proprietatea de a fi
echilibrat este o operatie O(log n). Se pune problema construirii operatiilor INSERT
si DELETE astfel incit ele sa conserve proprietatea de arbore binar echilibrat dar, in
acelasi timp, sa fie la rindul lor operatii O(log n). Costul pe care trebuie sa-l platim
pentru a putea realiza acest lucru este marirea spatiului ocupat de un nod al arborelui prin
memorarea in fiecare nod a unui "factor de dezechilibru" semnificind diferenta intre
adincimea subarborelui drept si cel sting.
La inserare, arborele trebuie reorganizat modificindu-i-se structura, numai atunci cind
o inserare dezechilibreaza un nod, care deja este dezechilibrat in acelasi sens. Operatiile
prin care este realizata echilibrarea sint denumite rotatii si sint descrise mai jos.
4.2. Mecanisme de conservare a proprietatii de arbore binar echilibrat:
Rotatii
In urmatoarele desene am reprezentat:
- Un nod al arborelui
- Un subarbore de adincime h
- Un subarbore de adincime h-1
Rotatiile se aplica arborilor (subarborilor) care, in urma inserarii, au nodul
radacina dezechilibrat, dar toti subarborii sint echilibrati. Laborator de Structuri de Date si Algoritmi – Lucrarea nr. 6
La inserarea unui nod X intr-un arbore, sint 4 cazuri posibile care necesita
efectuarea unei rotatii:
Si
4.2.1. Rotatiile simple
Rotatie simpla dreapta:
Starea initiala: Starea finala: Laborator de Structuri de Date si Algoritmi – Lucrarea nr. 6
Subarborii T1, T2 si T3 au initial aceeasi adincime h, iar nodul A are factorul de
dezechilibru -1. Prin inserarea unui nod in subarborele T1 se mareste adincimea acestuia
si nodul A devine dezechilibrat. Prin operatia numita "rotatie simpla dreapta" se obtine
un arbore care respecta inegalitatea valabila pentru starea initiala:
T1 < B < T2 < A < T3
Adica: Toate nodurile din subarborele T1 sint etichetate cu valori mai mici decit B, B
este mai mic decit etichetele tuturor nodurilor din subarborele T2, etc.
Arborele rezultat in urma rotatiei este echilibrat si, trebuie remarcat in mod deosebit,
are aceeasi adincime cu arborele initial (h+2).
Rotatie simpla stinga:
Se obtine din situatia simetrica celei prezentate mai sus:
4.2.2. Rotatiile duble
Situatiile rezolvate de rotatiile duble sint:
Laborator de Structuri de Date si Algoritmi – Lucrarea nr. 6
Pentru a le reprezenta este nevoie sa reprezentam detaliat subarborele T2. Se va vedea
mai tirziu ca acest arbore (T2) are cu siguranta subarborii descendenti de adincimi egale
(h-1).
Rotatiile duble au ca efect echilibrarea arborelui indiferent de subarborele (t2s sau t2d) in
care este inserat nodul X.
Rotatie dubla dreapta:
Stare initiala Starea finala
Numele de rotatie dubla rezulta din faptul ca situatia finala poate fi atinsa aplicind doua
rotatii simple:
A doua rotatie
Stare initiala Prima rotatie (simpla dreapta pt. A)
(simpla stinga pt. B) Starea finala Laborator de Structuri de Date si Algoritmi – Lucrarea nr. 6
Initial subarborii T1 si T3 au adincimea h iar t2s si t2d au adincimea h-1.
Valoarea inserata va mari adincimea unuia din subarborii t2s sau t2d. In ambele
cazuri se aplica mai intii o rotatie simpla spre stinga nodului B si apoi o rotatie simpla
spre dreapta nodului A. Rezulta un arbore echilibrat indiferent in care din subarborii t2s
si t2d s-a facut inserarea. Procedeul este corect si atunci cind nodul inserat este nodul C
si fiecare din subarborii T1, t2s, t2d, si T3 este arbore vid.
Din nou trebuie notat faptul ca adincimea arborelui rezultat este egala cu cea a
arborelui initial.
TEMA 2
Analizati urmatorul applet in care se poate vizualiza comportarea unui arbore binar de
cautare AVL echilibrat :
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
Efectuati operatii de inserare si stergere a unui nod din arbore.
Analizati modul in care se efectueaza aceste operatii atat in cazul arborilor echilibrati cat
si in cazul celor neechilibrati.
