Arbori de cautare

Arbori de cautare

Definitie: Un arbore ordonat este arborele in care arcele ce pornesc dintr-un nod sunt ordonate, adica b_i < b_j i < j.

Arborele de cautare este un arbore ordonat, in care, pentru i nod neterminal avem :

inf(i)<inf(j)<inf(k); pentru j nod in subarborele de radacina f_s (i);

pentru k nod in subarborele de radacina f_d (i).

Aceasta inseamna ca cheia unui nod radacina ki este mai mare decat toate cheile din subarborele stang si este mai mica decat toate cheile din subarborele drept al sirului.

La o parcurgere in ordine a unui arbore de cautare se obtine o lista de elemente sortata crescator.

Crearea arborilor de cautare

Se pleaca de la secventa elementelor introduse in ordine crescatoare a cheilor. Se pune in radacina elementul de la mijlocul secventei si subarborele stang va contine elemente din prima jumatate, iar cel drept va contine elemente din a doua jumatate.

Cei 2 subarbori se aranjeaza la fel, adica radacina sa contine elemente de la ? primei jumatati, s.a.m.d .

Cum introducerea nodurilor in arbore se face pe nivele (pe orizontala) ne trebuie structura de date de tip coada simpla . Un element din coada trebuie sa contina din stanga si din dreapta subarborelui care se va trata pentru a gasi elementele aflate la jumatatea .

Structura elementului din coada este:

type def struct tqreq

qreq

typedef qreq * p qreq;

Fie L si H extremitatile secventei. Se genereaza un elem ce are cheia M = si subsecventa de extremitati : L₁ = L, M₁=M-1 si L₂ = M+1, H₂ + H . Aceste variabile sunt indici pentru vectorul K unde avem memorate cheile elementelor.

Pointerul p da adresa nodului ascendent, adica adresa unde se vor lega urmatoarele 2 noduri, adresa data de primele 2 elemente scoase din coada . Actiunuile pentru crearea arborelui de cautare pornind de la vectorul cheilor K.

Se ia L = 1, M = H ;

Se determina M, L₁, M₁, L₂, H₂ ;

Se formeaza nodul rad (memorat in P) si L_1, M_1, L_2, H₂ se introduce in coada ca si P .

Cat timp coada nu e vida se executa :

se scoate din coada un element corespunzator unei subliste (H, H, P) ;

se determina elem din mijlocul listei si se genereaza un nod (element) aferent acestuia ;

se leaga nodul la ascendentul i ;

se introduc in coada 2 elemente corespunzatoare sublistei;

Procedura de introducere a unu element in coada:

Pointerii spre capetele cozii, pf si pr

Cautare in arbori de cautare

Datorita particularitatilor arborilor de cautar, operatia de cautare se modifica astfel :

se porneste cu rad ;

daca cheia data < cheia nodului curent , se reia procesul de cautare in subarborele stang;

altfel, se reia procesul de cautare in subarborele drept.

Procedura de cautare ce intoarce adresa nodului cautat, sau NULL cand nu este gasit, arata astfel :

parb cauta (int x, parb cf p)

else if ( a < p key ) inser ( a, p left );

else inser ( a, p right );

}

Stergerea unui nod dintr-un arbore de cautare

Pentru stergere este necesara cheia elementului scos din arbore si apoi cautat in arbore.

Fie t pointer spre nodul de sters . Se poate ca t sa indice radacina arborelui sau t sa fie descendentul unui nod indicat de un pointer p.

Pentru ca dupa stergere arborele rezultat sa fie tot arbore de cautare, se gaseste elementul cel mai din stanga al arborelui drept, se pune in locul celui ce trebuie eliminat si se schimba structura arborelui al carui varf a fost ca in desenul alaturat :

C E D F A

Algoritmul necesita pointerii : t B, p A si q E

indica nodul ce trebuie eliminat ;

indica nodul ce urmeaza sa fie legat la p dupa stergerea lui t ; el indica cel mai din stanga element al subarborelui drept al lui t ;

indica ascendentul direct al lui q .

Arbori echilibrati

O metoda pt a obtine arbori de cautare de inaltime cat mai mica a fost descoperita de matematicienii G. M. Adelson - Velskii si E.M. Landis obtinand asa numitii arbori AVL .

Definitie :