Algoritmi de cautare

Arbori binari de cautare.

In capitolul precedent, am folosit algoritmul de cautare binara pentru a sorta elementele unei liste. Asa cum am vazut, dupa fiecare iteratie algoritmul reduce numarul de elemente in care se face cautarea la jumatate. Algoritmul este eficient dar structura de date folosita este o lista liniara, in care inserarile si stergerile nu sunt eficiente ( mai exact sunt de ordin n). In continuare prezentam arborii binari de cautare in care operatiile de baza sunt proportionale cu inaltimea arborelui, care pt un arbore binar complet cu n noduri este log n.

Definitie: Un arbore binar de cautare este un arbore binar in care, daca se presupune ca fiecarui nod ii asociem un element al colectiei de obiecte ce dorim sa o sortam, toate nodurile ce se afla in subarborele stang al oricarui nod dat au o valoare mai mica decat valoarea nodului dat, iar toate nodurile ce se afla in subarborele drept au o valoare mai mare decat valoarea nodului.

Exemple:

Arbore care este arbore binar de cautare

Arbore care nu este arbore binar de cautare

1 Cautare in arbori binari de cautare

Pentru a cauta o valoare data intr-un arbore binar de cautare incepem comparand valoarea data cu radacina arborelui si mergem apoi in jos la stanga sau la dreapta, depinde cum este valoarea cautata fata de valoarea radacinii. De exemplu, in exemplul 1 de mai sus, pentru a cauta valoarea 9, comparam 9 cu 10 valoarea radacinii, si cum 9 < 10 comparam valoarea cautata cu radacina subarborelui stang adica vom compara 9 si 4 si cum 9>4 se merge si mai jos un nivel si se compara valoarea cautata cu valoarea radacinii subarborelui drept, si observam ca am gasit valoarea cautata. Fiecare comparatie reduce numarul de elemente comparate la jumatate si deci algoritmul este similar cautarii binare intr-o lista liniara. Dar acest lucru se intampla numai cand arborele este echilibrat. De exemplu, pentru un arbore ca cel din figura de mai jos timpul de cautare este proportional cu numarul de elemente ale intregii colectii.

2 Inserare si stergere arbori binari de cautare

Operatiile de inserare si stergere trebuie efectuate astfel incat proprietatea de arbore binar de cautare sa se mentina.

Algoritm de inserare (varianta recursiva): Se dau arbore binar de cautare T = pointer la radacina arborelui si v noua valoare ce trebuie inserata in arbore.

Insert (T, v)

if T = NULL then Aloca memorie pentru un nod nou. Returneaza p, un

pointer la noul nod.

p -> info = v

p ->stang = NULL

p -> drept = NULL

T = p

else if v > T -> info then call Insert (T->drept, v)

else if v < T -> info then call Insert (T-> stang, v)

else write 'valoare deja in arbore'

stop

endif

endif

endif

Algoritm de stergere: Se dau arbore binar de cautare T = pointer la radacina arborelui si nodul N ce trebuie eliminat din arbore. In acest caz exista trei cazuri:

N este nod terminal atunci daca se noteaza cu P un pointer la tatal

nodului N atunci nodul N este inlocuit cu NULL, adica P->stang = NULL daca N este fiu stang or P->drept = NULL daca N este fiu drept.

N are un singur fiu si fie X un pointer la fiul lui N atunci fiul lui N

devine fiul tatalui lui N, adica daca se noteaza cu P un pointer la tatal nodului N atunci P->stang = X daca N este fiu stang or P->drept = X daca N este fiu drept.

N are 2 fii: algoritmul este:

Gaseste R cel mai din dreapta nod al subarborelui stang al lui N

Inlocuieste informatia nodului N cu informatia din nodul R

Sterge nodul R.

Scrieti un program care cauta un element dat intr-un arbore binar de cautare.

Scrieti un program care insereaza un element dat intr-un arbore binar de cautare.

Scrieti un program care sterge un element dat intr-un arbore binar de cautare.