A Tipului De Date Abstracte Numit Arbore Binar

Prezentarea tipului de date abstracte numit arbore binar.Arborele AVL. Cuprins: 1. Ce este un arbore binar? 1.1. Definitii. 1.2. Tipuri de arbori binari. 1.3. Metode de stocare ale arborelui binar. 1.4. Metode de parcurgere ale arborelui binar. 1.5. Metode de traversare ale arborelui binar. 1.6. Parcurgerea in adancime. 1.7. Parcurgerea in latime. 1.8. Implementari.Implementarea succinta 1.9. Implementarea unui numar de n arbori in arbori binari. 2. Arborele binar de cautare. 2.1. Operatii. 2.2. Cautarea. 2.3. Inserarea unui nod. 2.4. Suprimarea unui nod. 2.5. Traversarea arborelui binar de cautare. 2.6. Sortarea arborelui binar de cautare. 2.7. Optimizarea arborelui binar de cautare. 3. Tipuri de arbori binari.Arborele AVL. 3.1. Ce este un arbore AVL?. 3.2.Operatii.Insertia unui nod. 3.3. Suprimarea unui nod. 3.4. Vizualizarea unui arbore AVL. Exemplu de arbore binar simplu.Nodul radacina are valoarea 2, latimea arborelui este 9 si inaltimea 3. 1. Arborele binar. >>> In domeniul calculatoarelor, un arbore binar este structura de date abstracte in care fiecare nod are cel mult doi fii.De obicei nodurile sunt denumite stang daca se afla in partea stanga a arborelui (sau a unui sub-arore), si drept daca se afla in partea dreapta a arborelui (sau a vreunui sub-arbore).O denumire mai utilizata pentru arborii binari este arbori binari de cautare. 1.1. Definitii. >>>

* O margine directa se refera la legatura dintre nodul-parinte pana la nodul-fiu (sagetile din imaginea arborelui prezentata mai sus). * Nodul radacina al unui arbore este nodul care nu are nici un parinte, deoarece este cel mai din varf nod din arbore. * Nodul curent este nodul care nu are fii (noduri predecesoare).el se afla in cel mai de jos nivel al arborelui. *Adancimea unui nod n reprezinta lungimea drumului de la nodul radacina pana la nodul n.Toate nodurile cuprinse intr-o lungime a unui drum dat, reprezinta uneori nivelul arborelui. * Inaltimea arborelui este lungimea drumului incepand de la nodul radacina si pana la cel mai de jos nod al arborelui. * Noduri infratite sunt nodurile care pot oferi altor noduri propriul nod parinte. * Daca exista un drum intre nodul p so q, atunci nodul p este un nod succesor pentru nodul q iar nodul q este un predecesor pentru nodul p. * Dimensiunea unui nod este numarul descendentilor inclusi in acel nod. 1.2. Tipuri de arbori binari >>> * Un arbore binar cu radacina este un arbore care porneste de la un nod radacina, iar fiecare nod are cel mult doi descententi. * Unarbore binar plin, sau arbore binar propriu, este un arbore in care fiecare nod are sau nici un fiu sau doi fii. * Un arbore binar perfect (denumit uneori arbore binar complet este un arbore binar plin in care toate nodurile curente ("frunzele") sunt la aceasi adancime. * Un arbore binar complet ar putea fi definit ca un arbore binar plin in care toate nodurile curente au adancimea de n sau n-1 pentru oricare ar fi n.Ordonand un arbore binar, acesta va deveni un arbore binar complet, adica toate nodurile-fii de la ultimul nivel trebuie sa ocupe consecutiv locurile cele mai din stanga, pana cand nu mai ramane nici un loc neocupat.De exemplu, daca doua noduri aflate in cel mai de jos nivel al arborelui ocupa fiecare cate un loc rezultand astfel un alt loc liber intre cele doua noduri, atunci restul nodurilor descendente vor fi strans marginite intre ele fara sa existe nici un loc neocupat.Cu alte cuvinte, un arbore binar complet are nodurile curente ("frunza") fiecare cu cate doi descendenti, neexistand ca printre acestea sa fie un nod curent cu numai un singur descendent rezultant astfel un loc liber intre acestia. * Un arbore binar complet cu radacina poate fi identificat printr-un vector liber. * Unarbore binar aproape complet este un arbore in care fiecare nod al acestuia are un fiu drept si un fiu stang.Detinerea unui nod-fiu stang nu implica necesitatea ca parintele sa aiba neaparat si un nod-fiu drept.Adica, un arbore binar aproape complet este arborele unde pentru un nod-fiu drept exista un descendent stang,insa nodul-fiu stang nu este obligatoriu sa detina un descendent drept propriu. 1.3. Metode pentru stocarea arborilor binari >>> Arborii binari in cele mai multe cazuri pot fi construiti din limbaje de programare primitive.Intr-un limbaj cu inregistrari si referinte,arborii binari sunt construiti tipic printr-o structura bazata pe un nod radacina care contine unele date si referinte despre nodul-fiu stang sau drept.Uneori aceste noduri-fii contin deasemeni o referinta catre

nodul-parinte.Daca un nod are mai putin de doi fii, atunci unele referinte ale nodurilo- fii ar putea avea o valoare nula. Arborii binari poti fi deasemeni stocati intr-un tablou ca un tip de structura de date implicita, si daca arborele este un arbore binar complet aceasta metoda nu lasa locuri ramase neocupate in tablou.In acest aranjament compact, daca un nod are indicele i descendentii lui pot fi gasiti la indicii 2i+1 si 2i+2, atat timp cat nodul-parinte al acestora este gasit la indicele-nivel((i-1)/2)(declarand ca nodul radacina are indicele zero).Aceasta metoda bebeficiaza de o stocare mai compacta a informatiilor in comparatie cu metoda localizarii referintelor, efectuant in particular o traversare in preordine.Oricum, ea este expansiva si nu utilizeaza un spatiu proportional cu 2h-n pentru un arbore cu inaltime h cu un numar de n noduri. Imaginea arata modul de stocare a unui arbore intr-un SDA tablou. In limabejele ce folosesc uniuni etichetate este limbajul ML, nodul unui arbore este adesea o uniune etichetata a doua tipuri de noduri iar una dintre acestia este a reprezinta a treia parte a datelor.Fiul stang si fiul drept si oricare dintre pot fi un nod curent (frunza), care nu contin date si functii, asa cum sunt valorile nule intr-un limbaj cu referinte (pointeri). 1.4. Metode de parcurgere a arborilor binari. >>> Adesea se doreste sa se verifice fiecare nod dintr-un arbore pentru a examina valoarea acestora.Aici sunt prezentate cateva metode prin care nodurile unui arbore pot fi verificati. 1.5. Metode de traversare a arborilor binari. >>> Traversarea in pre-ordine, in ordine si post ordine verifica fiecare nod dintr-un arbore printr-o parcurgfere recursiva a fiecarui nod din sub-arborele stang si drept pana ale nodului radacina.Daca nodul radacina este examinat inaintea sub-arborilor descendenti, aceasta metoda de parcurgere se numeste parcurgere in pre-ordine, iar daca nodul radacina este verificat dupa verificarea sub-arborilor atunci aceasta metoda de parcurgere se numeste parcurgere in post-ordine.Daca parcurgerea se efectueaza intre nodul radacina si nodurile celor doi sub-arbori, atunci aceasta metoda de a parcurge un arbore se numeste parcurgere in ordine.Traversarea in ordine este folositoare in cadrul arborilor binari de cautare, unde aceasta traversare verifica nodurile intr-o ordine crescatoare. 1.6. Parcurgerea in adancime (depth-first order). >>> Parcurgerea in adancime verifica prima data nodul radacina si inainteaza prin examinarea nodurilor pana la cel mai indepartat nod. 1.7. Parcurgerea in latime (breadth-first order). >>> Este metoda de parcurgere contrara parcurgerii in adancime (depth-first order), care intotdeuna va verifica nodul radacina dat si apoi nodurile invecinate lui, si apoi nodurile invecinate ale acestora pana cand se ajunge la alte noduri nevizitate.

Implementari pentru arborele binar. 1.8. Implementari concise (succinte). >>> O structura de date concisa (succinta) este o structura de date menita sa ocupe un spatiu de memorie cat mai mic posibil, adica arborele sa aiba limite cat mai mici.Numarul altor arbori binari cu un numar de n noduri este Cn, adica al -n-lea numar Catalan (asumand ca se vor primvi arbori cu structuta identica ca fiind identici).Pentru un numar n mare, cum ar fi 4n, va trebui sa se dispuna de un numar log24n biti pentru a fi implementat.Un arbore binar concis va terbui sa cupe doi biti pentru fiecare nod. Acum se doreste a aborda o reprezentare simpla in care se intalneste limitarea parcurgerii in pre-ordine a nodurilor unui arbore,prin generarea unui "1" logic pentru un nod intern si "0" logic pentru un nod curent.Daca arborele contine date,atunci se poate simplifica instantaneu inmagazinarea lor in pre-ordine intr-un tablou consecutiv.Iata o implementare in Pascal: function TransformaSuccint(node n, bit structura, tablou date) { if n = nil then append 0 to structura; else append 1 to structura; append n.date to date; TransformaSuccint(n.stanga, structura, date); TransformaSuccint(n.dreapta, structura, date); } In exemplul de mai sus sirul structure are numai 2n+1 biti la sfarsit, unde n este numarul nodurilor (interne).Nu se doreste sa se inmagazineze mai multe informatii decat poate cuprinde sirul structura.Pentru a arata cum este posibil sa nu se piarda nici o informatie, se va transforma datele de iesire inapoi intr-un arbore: function TransformaSuccint(bit structura, tablou date) { sterge primul bit din structura si il muta in b if b = 1 then creaza un nou nod n suprima primul element si il muta in n.date n.stanga = TransformaSuccint(structura, date) n.dreapta = TransformaSuccint(structura, date) return n else return nil }

Cele mai multe reprezentari concise si complexe ale arborilor binari pot indica nu numai spatiul ocupat de acestia ci si operatiile directe ce se pot aplica acestora atata timp cat acesti arbori sunt pastrsati intr-o forma concisa. 1.9. Implemenatarea unui numar de n arbori in arbori binari. >>> Aceasta este o mapare unu-la-unu dintre arborii ordonati general si arborii binari, care in paricular sunt folosit in limbajul Lisp pentrui a reprezenta arbori total ordonati in arbori binari.Fiecare N nod din arborele ordonat corespunde unui nod N' dintr-un arbore binar.Fiul stang al nodului N' este nodul corespunzator primului nod-fiu al nodului N, si fiul drept al nodului N' este nodul corespunzator nodului inlocuitor al lui N', acesta fiind urmatorul nod in ordinea parcurgerii descendentilor cater nodul parinte N. O metoda de a lamuri cele scrise mai sus este aceea ca fiecare nod-fiu se afla intr-o lista inlantuita,si este inlantuit inpreuna cu celelalte noduri din partea dreapta, si nodul are numai o referire catre inceputul listei sau in varful acestei liste, prin intermediul nodurilor din partea stanga. De exemplu, se da in partea stanga un arbore care are la nodul A sase descendenti {B,C,D,E,F,G}.Ei pot fi transformati in arborele binar aflat in partea dreapta. Arborele din stanga este transformat in arborele binar din dreapta. Arborele binar de cautare.Acest arbore are dimensiunea 9, si de adancime 3.Nodul radacina are valoarea 8, iar 1,4,7,23 sunt valorile nodurilor curente. Arborele binar poate fi vazut prin structura arborelui initial prin faptul ca marginile negre reprezinta primul descendent si marginile albastre reprezentand urmatorul inlocuitor.Nodurile curente ale arborelui din stanga poate fi scrise in Lisp astfel: (((M N) H I) C D ((O) (P) F (L)) acestea putind fi implementate in memorie in structura arborelui din partea dreapta. 2. Arbori binari de cautare. >>> In domeniul calculatoarelor un arbore binar de cautare (ABC) este o structura de date numita arbore, si care detine urmatoarele proprietati: * Fiecare nod are o valoare. * Ordinea totala este definita pe aceste valori. * Sub-arborele stang al unui nod oarecare contine numai valorile mai mici decat valoare nodului respectiv. * Sub-arborele drept al unui nod oarecare detine numai valorile mai mari sau egale cu nodul respectiv.

Avantajul major al arborilor binari de cautare consta in relatarea algorimilor de sortare si algoritmilor de cautare care folosesc metoda traversarii arborilor in ordine, poate fi foarte eficienta. Arborii binari de cautare sunt un fundament pentru structura de date folosinta in construirea mai multor structuri de date abstracte, cum sunt de exemplu colectiile de date sau tablourile asociate. 2.1. Operatii. >>> Toate operatile intr-un arbore binar realizeaza mai multe operatii ce se folosesc de un comparator, care este o subrutina care calculeaza ordinea totala a oricaror doua valori.In implementatiilre simple a arborilor binari de cautare, un program de cele ami multe ori trimite un raspuns catre comparator cand acesta creeaza un arbore, sau altfel explicand, in limbajele de programare care suporta tipul polimorfism parin folosirea valorilor ca fiind de tip comparabil. 2.2. Cautarea >>> Cautarea unei valori date intr-un arbore binar de cautare este un proces care poate fi realizat recursiv in ordinea valorilor care sunt stocate.Se incepe prin axaminarea nodului radacina.Daca valoarea care este cautata este egala cu valoare nodului radacina, atunci inseamna ca valoarea exista in arbore.Daca valoarea ce trebuie cautata este mai mica decat valoarea nodului radacina, atunci aceasta trebuie sa fie in sub-arborele stang, astfel printr-o cautare recursiva se va cauta valoarea in structura acestui sub-arbore stang.Asemenator,daca valoarea care trebuie cautata este mai mare decat valoarea detinuta de nodul radacina, atunci aceasta trebuie sa fie in structura sub-arborelui drept.Daca procedura de cautare a ajuns la un nod curent si valoarea cautata nu s-a gasit, atunci valoarea nu se afla in arbore.O compararatie ar putea fi executata cu o cautare binara, care efectueaza o cautarea a valorii printr-o metoda foarte asemanatoare, insa abordeaza un acces aleator in tabloul valorilor prin urmarirea legaturilor. Aici este prezentat un algoritm de cautare implemntata in limbajul Python: defcautare_arbore_binar(nod, termen): if nod is None: return None # termenul nu este gasit if termen < nod.termen: return cautare_arbore_binar(nod.stanga, termen) else if termen > nod.termen: return cautare_arbore_binar(nod.dreapta, termen) else: # termenul are valoarea egala cu valoarea nodului return nod.value # termenul este gasit Aceasta operatie necesita un timp de executie O(log n) in cazul in care cerinta impune o cautare de o complexitate medie, insa daca se comporta ineficient atunci algoritmul se va executa intr-un timp de O(n) - adica arborele este neechilibrat si re-aranzeaza o lista sortata.

2.3. Insertia. >>> Metoda de insertie se efectueaza asemanator ca si metoda de cautare.Se incepe prin verificarea valorii ce trebuie cautata cu valoarea nodului radacina.Daca valoarea ce trebuie cautata nu este egala cu valoarea nodului radacina, atunci procedura de cautare se va continua ori in structura sub-arborelui stang, ori in structura sub-arborelui drepta ca si la procedeul de cautare.Eventual, se poate extinde un nod extern si se va adauga valoarea ce trebuie cautata ca fiind un nod-fiu drept sau stang.Cu alte cuvinte, se poate examina nodul radacina si se ve insera recursiv un nou nod in cadrul structurii sub-arborelui stang daca valoarea ce trebuie cautata este mai mica sau egala cu valoarea nodului radacina, sau in structura sub-arborelui daca valoarea cautata este mai mare ca si valoaera nodului radacina. Aici este prezentat un exeplu de algoritm de insertie implementat in cod C: void InsertieNod(struct nod **nod_ptr, struct nod *nodNou) { struct nod *nod = *nod_ptr; if (nod == NULL) *nod_ptr = nodNou; else if (nodNou->valoare <= nod->valoare) InsertieNod(&nod->stanga, nodNou); else InsertieNod(&nod->dreapta, nodNou); } Procedura "destructiva" de deasupra modifica variabil structura arborelui.Ea utilizeaza numai un spatiu de memorie constant, insa se pier versiunile anterioare realizaet cu ajutorul algorimului.Alternativ, ca in exemplu de mai jos, se poate reconstrui toate nodurile bunici ale nodului inserat.Orice referinta la nodul radacina al arborelui initial ramane valida numai realizand o structura de date persistenta: def insertie_arbore_binar(nod, termen, valoare): if nod is None: return NodArbore(None, termen, valoare, None) if termen == nod.termen: return NodArbore(nod.stanga, termen, valoare, nod.dreapta) if termen < nod.termen: return NodArbore((insertie_arbore_binar(nod.stanga, termen, valoare), nod.termen, nod.valoare, nod.dreapta) else:return NodArbore((nod.stanga, nod.termen, nod.valoare, insertie_arbore_binar(nod.dreapta, termen, valoare)) Partea este reconstruita folosind un spatiu de È(log n) locatii de memorie in cazul in care cerinta este de dificultate medie, iar in cel mai rau caz flolseste uin spatiu de Ù(n).In fiecare versiune, aceasta operatie necesita un timp direct proportional cu inaltimea

arborelui in cazul in care acesta functioneaza ineficient, adica se efectueaza intr-un timp de O(log n) in cazul (valabil pentru toti arbori creati) in care se rezolva o problema de dificultate medie, insa aceasta va avea Ù(n2) in cazul in care se comporta ineficient. O alta cale de a realiza insertia este prin inserarea in ordinea inserarii noii valori in arbore, aceasta valoare este prima data comparata cu valoarea nodului radacina.Daca aceasta valoare este mai mica decat valoarea nodului radacina atunci ea va fi comparata cu valoarea nodului-fiu stang.Daca valoarea este mai mare, atunci ea va fi comparata cu valoarea nodului-fiu drept.Acest pocedeu continua pana cand npoua valoarea inserata este comparata cu un nod curent fiindu-i adaugata ca un nod-fiu (descendent) drept sau stang.Pot fi mai multe metode de a insera o valoare in cadrul structurii arborilor binari de cautare, insa aceasta este singura metoda care ataseaza nodurilor curente ale arborelui in care se face insertia alte noi noduri fara sa fie afectata structura acestuia. 2.4. Suprimarea unui nod. >>> Aici sunt mai multe cazuri care trebuiesc luate in vedere. * Stergerea unui nod curent: Suprimarea (stergerea) unui nod curent care n-are descendenti se face usor. * Stergerea unui nod care are un nod-fiu: Se va sterge nodul si se va inlocui cu nodul-fiu. * Stergerea unui nod cu doua noduri-fii: Se presupunem ca nodul este numit N.Se va inlocui valoarea nodului N cu valoarea unui succesor parcurs in ordine (cel mai din stanga nod-fiu al sub-arborelui drept) sau cu a predecesorului (cel mai din dreapta nod-fiu al sub-arborelui stang). Imaginea arata modalitatea de suprimare a nodurilor curente ale arborelui din mijloc. Astfel se gaseste oricare predecesor sau succesor al arborelui parcurs in ordine, mutarea lui in locul nodului N si stergerea lui.Astfel fiecare dintre aceste noduri trebuie sa aiba mai putin de doua noduri-fii (caci altfel el nu poate fi un succesor sau predecesor in cazul in care arborele in care se face suprimarea este parcurs in ordine), el putand fi sters folosind cele doua cazuri prezentate mai sus.Intr-o buna implementare, in general este recomandat sa se evite folosirea unuia dintre aceste noduri , deoarecea suprimarea lui ar putea dezechilibra arborele. Aici este prezentat un algoritm C++ care foloseste metoda destructiva a suprimarii (se va presupune ca nodul care trebuie suprimat a fost deja gasit printr-o metoda de cautare): void SuprimareNod(struct nod*& nod) { if (nod->stanga == NULL) { struct nod* temp = nod; nod = nod->dreapta;

delete temp; } else if (nod->dreapta == NULL) { struct nod* temp = nod; nod = nod->stanga; delete temp; }else { // Predecesor parcurs in ordine (cel mai din dreapta nod-fiu al sub-arborelui stang) // Nodul are doua noduri-fii - aceasta fiind limita maxima a sub-arborelui stang struct nod*& temp = nod->stanga; while (temp->dreapta!= NULL) { temp = temp->dreapta; } nod->valoare = temp->valoare; SuprimareNod(temp); } } Deoarece aceasta operatie nu efectueaza intodeauna o traversare in adancime (catre nodurile curente), poate fi oricand o posibilitate, deoarece ea cere in cazul in care algoritmul de suprimare se comporta ineficient un timp care-i proportional cu inaltimea arborelui. 2.5. Traversarea arborilor binari de cautare. >>> Dupa ce arborele binar de cautare a fost creat, elementele lui pot fi pastrate in ordine prin travesrsarea recursiva a sub-arborelui stang, verifcarea nodului radacina, apoi treversarea recursiva a sub-arbrelui drept.Arborele ar putea fi traversat in pre-ordine sau in postordine. def traversarea_arborelui_binar(nodarbore): if nodarbore is None: return stanga, valoarenod, dreapta = nodarbore traversarea_arborelui_binar(stanga) visit(valoarenod) traversarea_arborelui_binar(dreapta) Perioada de traversare a algoritmului necesita un timp de Ù(n) atunci cand acesta doreste sa verifice fiecare nod.Algoritmul de traversare se executa intr- un timp determinat de functia O(n) 2.6. Sortarea arborelui binar de cautare. >>> Un arbore binar de cautare poate fi implementat ca un simplu insa ineficient algoritm de sortare.Asemenator cu metoda sortarii prin inserie, cand se doreste a se inseara toate valorile termenilor aceasta inseamna ca aceste valori intr-o noua structura de data

ordonata - in acest caz un arbore binar de cautare, atunci aceasta noua structura de date se va traversa in ordine oferind rezultatele: def construieste_arbore_binar(valori): arbore = None for v in valori: arbore = inasereaza_arborele_binar(arbore, v) return arbore def traverseaza_arbore_binar(nodarbore): if nodarbore is None: return [] else: stanga, valoare, dreapta = nodarbore return (traverseaza_arbore_binar(stanga) + [valoare] + traverseaza_arbore_binar(dreapta)) Perioadade timp in care construieste_arbore_binar se comporta ineficient este Ù(n2) -daca se lucreaza cu o lista cu valori sortate, el se poate adauga intr-o lista inlantuita fara sa aiba fii stangi.De exemplu, structura_arbore_binar([1,2,3,4,5]) arborele devine (Nici unul, 1,(Nici unul, 2,(Nici unul, 3,(Nici unul, 4,(Nici unul, 5, Nici unul))))). Aici este o varietate de scheme pentru a acoperii aceste "Nici unu"-uri cu arbori binari simpli.Cel mai adesea utilizat este arborele binar echilibrat de cautare.Daca aceeasi procedura este executata folosind de exemplu un arbore, atunci comportarea ineficienta pentru toti este O(nlog n) care este o optiune asimptotica pentru o sortare prin comparare.In practica, performanta scazuta in lucrul cu memoria "cache" si spatiul de memorie folosit in cadrul unei sortari dedicate pe lucrul cu arbori (in particular pentru alocarea nodurilor) realizeaza o sortare mult mai inferioara in comparatie cu alte sortari optime asimptotice cum sunt sortarea rapida ("quick sort") si "heapsort" cand acestea lucreaza cu liste statice sortate.Oricum, aceaste este una din cele mai eficiente metode de sortare incrementala, prin fpatul ca se adauga termeni intr-o lista intr-o maniera rapida atat timp cat lista este sortata. 2.7. Optimizarea arborilor binari de cautare. >>> Daca se doreste sa nu se modifice structura unui arbore binar, si daca se cunoaste metoda de accesare a fiecarui termen din arbore, atunci se poate constru un arbore binar de cautare optimizat, care va fi de fapt un arbore de cautare unde costul de vizualizare a unui termen (exceptand costul de timp al metoda de cautare) este minimizat. Sa presupunem ca se cunoaste numarul de elemente din arbore, inclusiv se stie ca pentru fiecare element proportia de timp pentru a fi vizualizat.Astfel se poate utiliza o solutie de a programare dinamica, detaliata in sectiunea 15.5 din cartea Introductiona of algorithms de Thomas H.Cormec, pentru a construi un arbore de cautare care functioneaza dupa o metoda de cautare foarte eficienta.

Chiar daca se doreste a avea o perioada de cautare estimativa intr-o multime de date, asa ca intr-un dictionar, se poate avea o perioada de cautare foarte rapida.De exemplu, daca am un disctionar de cuvinte in limba engleza utilizat pentru a corecta sintaxa textului dintr-un program de editare.Eu pot echilibra arborele bazat pe cuvinte ele mai des utilizate in cadrul textului prin plasarea in aproprierea nodului radacina (adica in varful arborelui) a cuvintelor scurte , de exemplu "the", si a cuvintelor mai lungi in apropierea nodurilor curente (adica la baza arborelui).Un astfel de arbore cu o astfel de structura poate fi comparat cu un arbore "Huffman" , care procedeaza asemenator cu metoda descrisa: el plaseaza termenii fregvent folositi in aproprierea nodului radacina in ordine pentru a avea un grup mare de informatii ordonat.Oricum arborii "Huffmann" stocheaza numai elementele ce trebuiesc ordonate in aproprierea nodurilor curente. Daca nu se cunoaste segventa in care elementele arborelui pot fi accesate timpuriu, atunci se poate folosi un gen de arbore binar numit "splay" care functioneaza dupa metode asimptotice care il determina sa se comporte eficient si sa fie stabil pentru putea sa-l folosim in construirea unor segvente particulare pentru metodele de vizulalizare ale arborilor. 3. Tipuri de arbori binari de cautare.Arborele AVL. >>> Sunt mai multe tipuri de arbori binari de cautare.Arborii AVL si arborii rosii-negrii sun doua forme de arbori binari echilibrati de cautare.Un arbore "splay" este un arbore binar care muta fregvent si automat elementele din apropierea nodului radacina.Intr-un arbore "treap" ("tree heap"), fiecare nod acorda o inalta prioritate nodulor-parinti. 3.1. Ce este arborele AVL? >>> In domeniul calculatoarelor arborele AVL este primul tip de structuri de date iventat din familia arborilor binari echilibrati de cautare.Daca intr-un arbore AVL inaltimile subarborilor care descind din oricare din nodurile arborelui difera una de cealalata, atunci arborele AVL respectiv este numit "echilibrat prin inaltime".Operatiile de vizualizare,insertie,suprimare se executa intr-un timp de O(log n) in functie de comportarea medie si ineficienta a algoritmului de executie.Aceste operatii de aducere a unui nod sau suprimarea lui ar putea cauza necesitatea reechilibrarii arborelui prin una sau mai multe roatii a arborelui. Arborele AVL este numit dupa numele celor doi iventatorilor ai sai, G.M AndelsonVelsky si E.M. Landis, care publicasera in anul 1962 iventia lor in revista pe care acestia o editau in articolul intitulat "Un algoritm pentru organizarea informatiilor". Factorul de echilibrare al unui nod este inaltimea sub-arborelui drept minus inaltimea sub-arborelui stang ai acestuia.Un nod care are factorul de echilibru 1,0, sau -1 este considerat echilibrat.Un nod cu un alt foactor de echlibru diferit de cei prezentati anterior este considerat dezechilibrat, astfel fiind necesar reechilibrarea arborelui.Factorul de echilibru pentru fiecare dintre cei doi sub-arbori este determinat direct la fiecare nod sau calculat prin inaltimea sub-arborilor.

Exemplu de arbore non-avl. Exemplu de arbore AVL. Arborii AVL sunt adeseori comparati cu arborii rosii-negrii deoarece acestia suporta acelasi set de operatii, iar un alt motiv este ca arborii rosii-negrii necesita un timp de O(logn) pentru a efectua oricare din operatiile de baza. Arborii AVL se comporta mai eficient in operatii decat arborii rosi-negrii in cazul in care se abordeaza aplicatii intensiv vizualizate.Deasemeni algoritmul de echilibrare al arborelui AVL este folosit foarte des in stinta calculatoarelor. 3.2. Operatii in cadrul arborelui AVL. 3.2.1. Insertia unui nod. >>> Insertia intr-un arbore AVL se face prin inserarea valorii date in cadrul arborelui (daca acesta este un arbore binar dezechilibrat de cautare), si chiar daca se repeta un pas din parcurgerea legaturilor spre nodul radacina prin operatia de inserare se imbunatateste factorul de echilibru al nodurilor.Repetarea (retragerea) parcurgerii unui drum este anulata atunci cand factorul de echilibru al unui nod devine 0,1, sau -1.Daca factorul de echilibru este 0 atunci inaltimea sub-arborilor unui nod nu a fost modificata in urma inserarii. Daca factorul de echilibru din cauza inserarii la un nod devine 2 sau -2 atunci subarborele acestui nod este dezechilibrat, astfel trebuind sa se efectueze o rotatie a arborelui.Rotatia nu se va aplica daca sub-arborii sunt echilibrati.Oricum rotatia poate fi facuta intr-un timp constant. Ca si in cazul arborilor binari dezechilibrati de cautare, insertia in arborele AVL se face intr-un timp de O(inaltime).Acesta functie O(inaltime) reprezinta timpul necesar de a gasii locul unde trebie insearat nodul plus inca un timp de O(inaltime) pentru a determina numarul de rotatii necesare. Procedeul de echilibrare urca inaltimea arborelui cu cel mult 1.44 lg(n+2).Astfel procedeul inrteg de inserare a unui nod se executa intr-o perioada de timp determinata de functia O(log n). 3.2.2. Suprimarea unui nod. >>> Daca un nod este un nod curent atunci el este cel mai expus procedeului de suprimare.Daca nodul ce se doreste sa fie suprimat este un nod intern (non-curent), atunci acesta se va inlocui cu oricare nod care va contine cea mai mare valoare din cadrul subarborelui stang sau cu nodul care contine cea mai mica valoare din cadrul sub-arborelui drept, si apoi se sterge nodul,insa nodul care trebuie sters trebuie sa aiba cel mult un nodfiu.Dupa suprimarea nodului se reia parcurgerea inaltimii arborelui din punctul din care

aceasta s-a oprit, astfel potrivindu-se factorii de echilibrare daca aceasta va fi necesar.Reluarea parcurgerii poate fi anulata daca factorul de echilibru al nodului in care s-a efectuat suprimnarea este de -1 sau 1, aceasta indicand ca inaltimea sub-arborilor nodului care a fost suprimat a ramas aceeasi.Daca factorul de echilibru a devenit 0 in urma suprimariinunui nod, atunci inaltimea sub-arborilor nodului suprimat a scazut cu un nod rezultand astfel continuarea procedeului de reluare a parcurgerii din punctul in care aceasta s-a oprit.Daca factorul de echilibru a devenit -2 sau 2 atunci sub-arborii nodului suprimat sunt dezechilibrati si trebuiesc rotit pentru ai fixa (reechilibra).Daca operatia se rotire a sub-arborilor se anuleaza cand acestia au factorul de echilibru 0 atunci procedeul de reluare a parcurgerii arborelui de la baza spre nodul radacina trebie sa continuie pana cand inaltimea unuia dintre sub-arborii nodului care a fost suprimat va scadea cu un nod.Operatie de suprimare este in contradictie cu procedura de insertie, unde o rotatie va rezulta in cazul in care factorul de echilibru a unuia dintre sub-arborii nodului suprimat este 0 indicand astfel ca inaltimea acestui sub-arbore a ramas neschimbata. Pentru operatia de suprimare este necesara o perioada denumita O(h) pentru a vizualiza structura arborelui in care se face suprimarea plus O(h) rotatii intr-o parcurgerea a arboreului in adancime, astfel ca operatia de suprimare se executa in totalitate intr-un timp definit O(log n). 3.2.3. Vizualizarea nodurilor arborelui AVL. >>> vizualizarea unui arbore AVL se face intocmai ca si vizualizarea unui arbore binar dezechilibrat de cautare, iar acest procedeu de vizualizare se efectueaza intr-un timp definit dupa functia O(log n) atunci cand arborele este dat ca fiind echilibrat.In vizualizarea unui arbore nu se tine cont de anumite principii stricte, deaorece structura unui arbore nu se modifica daca acesta se afla intr-un proces de vizualizare.Vizualizarea unui arbore AVL este in contrast cu alte procedee de vizulalizare aplicati la alti arbori, cum este de exemplu arborele "splay" unde acest procedeu e vizualizare modifica structura arborelui.