Cozi

Coada este o structură FIFO (First In First Out - primul intrat este primul ieşit). Orice element nou adăugat devine ultimul din coadă, în timp ce extragerea de elemente se face din "capul" cozii. Coada se poate implementa ca o listă, în care adăugarea de elemente se face la unul din capete, iar extragerea se face de la capătul opus. Complexitatea operaţiilor depinde de modul de implementare a cozii. Dacă pentru coada care conţine n elemente se foloseşte o listă implementată ca tablou (cum sunt cele din clasele ArrayList sau Vector), pot sa apară urmatoarele situaţii:    a/ capul cozii se gaseşte la indicele 0, iar sfârşitul cozii se găseşte la indicele n-1, unde n este lungimea cozii. În acest caz, complexitatea operaţiei de punere în coadă este O(1), iar complexitatea operaţiei de extragere din coadă este O(n), deoarece după extragere trebuie deplasate toate elementele rămase;    b/ capul cozii se găseşte în poziţia n-1, iar ultimul element din coadă se găseşte în poziţia de indice 0. În acest caz, complexitatea punerii în coadă este O(n), iar cea a extragerii din coadă este O(1). Vom arăta ulterior că pentru coadă este preferabil să se folosească o structură de listă înlănţuită, în care caz atât punerea în coadă cât şi extragerea din coadă au complexitatea O(1). Coada este o structură de date frecvent folosită in informatică. Ea este utilă atunci când anumite servicii trebuie oferite în ordinea în care au fost primite solicitările.

Coada realizată ca listă înlănţuităPentru realizarea unei cozi se poate folosi, de asemenea, o listă înlănţuită, punând condiţia ca punerea unui element în coadă sa se facă la sfarşitul listei, iar scoaterea elementului să se facă numai din capul listei. În cazul listelor din clasa LinkedList se vor folosi metodele addLast si, respectiv, removeFirst. Dacă se doreşte ca utilizatorul să nu poată folosi alte metode ale listei, aceasta poate fi încapsulată într-o clasă acoperitoare, la fel cum s-a procedat în cazul stivei.

Coada de priorităţi (engleză: priority queue) este o structură de date în care fiecărui element i se asociază un număr întreg, numit prioritate. Principalele operaţii sunt punerea şi extragerea unui element. La extragerea unui element din coadă se alege elementul cu cea mai înaltă prioritate. În principiu, coada cu priorităţi poate fi realizată în două moduri: ca listă ordonată în ordinea descrescătoare a priorităţilor, sau ca arbore de selecţie. Dacă este realizată ca listă ordonată, punerea unui element în coada de priorităţi de lungime n are complexitatea O(n), deoarece este necesar fie să se deplaseze toate elementele situate după el în cazul listei implementate ca tablou, fie să se parcurga toate elementele situate inaintea lui, în cazul listei înlănţuite. Extragerea elementului din coada de priorităţi are complexitatea O(1) atât la lista-tablou cât şi la cea înlănţuită.

Arbori

Arborele este o structură de date ierarhizată, în care fiecare nod are un singur nod părinte şi poate avea mai multe noduri fii. Există un singur nod care nu are părinte, numit rădăcină. Nodurile care nu au fii se numesc Frunze. Fiecare nod al arborelui este rădăcina unui subarbore. În consecinţă, arborele este o structură de date recursivă. Chiar şi frunza este rădăcina unui subarbore care conţine un singur nod. Structura de arbore modelează multe structuri ierarhice existente în lumea reală. Iată numai câteva exemple:   - organigrama unei instituţii sau întreprinderi;   - structura unui produs tehnic (produsul este un ansamblu constituit din subansamble, care sunt constituite fiecare din alte subansamble, până se ajunge la piese indivizibile);   - structura unui desen tehnic.

Arbori binariArborele binar este un arbore, în care fiecare nod are cel mult doi fii.

Arborele binar complet este un arbore binar, în care toate nivelurile sunt complete. Într-un astfel de arbore, toate nodurile intermediare au exact doi fii şi toate frunzele sunt situate pe acelaşi nivel.Arborele binar aproape complet este un arbore binar, în care toate nivelurile sunt complete, cu excepţia ultimului nivel, care este aproape complet. Toate nodurile lipsă de pe ultimul nivel sunt situate la sfârşitul acestuia.

Un arbore binar complet sau aproape complet poate fi reprezentat ca tablou, procedând în modul următor: se consideră că rădăcina arborelui este primul element din tablou, t[0]. În continuare, se plasează în tablou nodurile de pe nivelul 1, parcurse de la stânga la dreapta, apoi cele de nivel doi etc. Procedând astfel cu arborele binar din figura 5, se obţine tabloul următor  

A B C D E F G H I J

Se poate usor arăta că indicii celor doi fii ai unui nod oarecare, de indice i,  se determină cu formulele:

is = 2*i+1 id = 2*i+2

unde is este indicele fiului stânga, iar id este indicele fiului dreapta.  Indicele i al părintelui unui nod oarecare de indice k se determină cu formula

i = (k-1)/2unde, evident, se consideră numai partea întreaga a câtului.  Aplicând relaţiile de mai sus, există posibilitatea de a se parcurge arborele în ambele sensuri: atât în sens descendent, cât şi ascendent. Exemplu: Aplicând aceste relaţii arborelui din tabloul de mai sus constatăm că:     - fiii nodului C de indice 2 sunt nodurile de indici 5 şi 6, respectiv F şi G;     - părintele nodurilor H şi I (de indici 7 şi 8) este nodul D (de indice 3).

Arborele de selecţie (engleză: heap) este o coadă de priorităţi realizată ca arbore binar aproape complet. Fiecare nod al arborelui de selecţie are proprietatea că cei doi fii ai lui (dacă ei există) au priorităţi mai mici decât a lui. Un astfel de arbore de selecţie este reprezentat în figura 6, în care s-a considerat că prioritatea maximă este cea corespunzătoare valorii maxime a numărului care o reprezintă (uneori se admite, dimpotrivă, că prioritatea maximă este 0 sau 1 şi scade cu creşterea numărului prin care este reprezentată).  

Traversarea arborelui binar cu parcurgere în adâncimeTraversarea combină parcurgerea cu vizitarea nodurilor. S-a arătat că, la parcurgerea în adâncime, se trece de mai multe ori prin acelaşi nod. Vizitarea nodului trebuie sa se facă, însa, o singură dată. Se pune problema la care din trecerile printr-un nod se face vizitarea lui. În cazul arborilor binari exista, trei posibilităţi numite, respectiv, traversarea în preordine, inordine şi postordine. În cazul traversării în preordine, vizitarea unui nod se face la prima trecere prin acesta, deci înainte de a fi parcurşi cei doi subarbori.Metode recursive de traversare a arborilor binari în adâncimePentru realizarea celor trei tehnici de traversare a arborilor descrise mai sus, este foarte comodă implementarea ca metode recursive. în acest caz nu se mai foloseste în mod explicit o stivă ca structură auxiliară, deoarece metodele recursive folosesc implicit stiva sistemului de calcul (în cazul de faţă cea a maşinii virtuale Java). Traversarea arborilor in lăţime (pe niveluri)La traversarea în lăţime (engleză: breadth-first), numită şi traversare pe niveluri, nodurile arborelui se parcurg şi se vizitează astfel: se începe cu rădăcina, apoi se vizitează de la stânga la dreapta toate nodurile de nivel 1, apoi toate nodurile de nivel 2 şi aşa mai departePentru a parcurge un arbore în lăţime (pe niveluri), se foloseşte ca structură auxiliară o coadă. La început se pune în coada rădăcina. Se consideră că nodul curent este cel din capul cozii. Se pun în coadă toti fiii nodului curent (dacă ei există), după care acesta se scoate din coadă. Se continuă astfel până când coada rămâne vidă.

Implementarea arborilor generaliÎn cazul general, numărul de fii al fiecărui nod al arborelui nu este limitat. Ca şi în cazul arborilor binari, un  arbore general poate fi implementat prin noduri cu legături, sau ca o structură recursivă. În varianta cu noduri şi legături, fiecare Nod al arborelui conţine o legatură către obiectul informaţiei ataşate şi o listă a fiilor, ca în exemplul următor:

public class Arbore {   Nod radacina;   // Constructori si metode ale clasei Arbore   /* CLASE IMBRICATE SI INTERIOARE */   public static class Nod {     private Object info;     private ArrayList fii;     // Constructori si metode ale clasei imbricate Nod   }   // Alte clase imbricate si interioare } } Traversarea arborilor generaliTehnicile de traversare a arborilor generali sunt: în preordine, în postordine şi în lăţime. Aceste tehnici sunt similare celor cu acelaşi nume de la arborii binari. Traversarea în inordine, evident, nu are sens în cazul arborilor generali.

  Metode recursive de traversare a arborilor generali în adâncimePentru traversarea arborelui general în adâncime, pot fi folosite şi metode recursive. Acestea se bazează pe faptul că orice nod al unui arbore este, de asemenea, rădăcina unui subarbore. Însăşi frunza poate fi considerată un arbore format dintr-un singur nod. În consecinţă, traversarea arborelui în preordine se poate face în urmatoarele etape:     - se vizitează radăcina;     - se traversează toţi subarborii-fii. La traversarea în postordine, cele două operaţii se inversează:     - se traversează toţi subarborii-fii;     - se viziteaza rădăcina. 

Implementarea arborilor binariAm arătat în capitolul precedent că arborii binari (aproape) compleţi pot fi implementaţi ca tablouri. În cazul general al arborilor binari, o astfel de implementare nu mai este eficientă. Într-adevar, deşi s-ar putea implementa un arbore binar incomplet sub formă de tablou la fel ca unul complet, dar lăsând libere locurile nodurilor lipsă, o astfel de implementare ar fi, de cele mai multe ori, neraţională din punct de vedere al consumului de memorie. În cazul general, un arbore binar este implementat printr-un set de noduri, între care există legături ierarhice de la tată la cei doi fii, ca în figura 1. Acolo unde fiul nu există, legatura respectivă este nulă. Fiecare nod conţine o anumită informaţie, ataşată nodului respectiv, şi două legături: către fiul din stânga şi fiul din dreapta. Uneori, fiecare nod conţine şi o legatură către nodul-tată.Traversarea arborelui este parcurgerea tuturor nodurilor într-o anumită ordine, însoţită de vizitarea acestora. Vizitarea nodului înseamnă utilizarea şi, eventual, actualizarea informaţiei aferente nodului respectiv. Parcurgerea nodurilor este o tehnică de trecere sistematică de la un nod la altul, astfel încât să se treaca prin toate nodurile arborelui într-o ordine prestabilită. Este posibil să se treacă de mai multe ori prin fiecare nod, dar vizitarea nodului se face numai o dată. Există două tehnici de parcurgere a arborilor: în adâncime şi în lăţime (pe niveluri).

Pentru a aplica tehnici iterative de vizitare a nodurilor unui arbore, în tehnologia Java se folosesc iteratori. Aceştia sunt definiţi, la fel ca în cazul colecţiilor sau mapărilor, prin clase care implementează interfaţa java.util.Iterator. La fiecare invocare a metodei Object next() a unui iterator, acesta intoarce obiectul de informaţie conţinut în urmatorul nod care trebuie vizitat. Această abordare creează o mare flexibilitate în utilizarea iteraţiei, întrucât utilizatorul clasei de arbori este scutit de implementarea tehnicii de parcurgere a nodurilor în vederea vizitării lor, concentrându-şi atentia numai asupra prelucrării informaţiei din noduri.

Metoda HeapSort (sortarea cu arbore de selecţie)Ideea de bază a metodei HeapSort este că, pe măsură ce elementele sunt scoase din tabloul de sortat şi puse în coada de priorităţi, spaţiul rămas liber în tabloul de sortat este ocupat chiar de către tabloul de selecţie,Fie t tabloul care trebuie sortat, de lungime n. Într-o prima etapă, elementele sunt extrase din tabloul t in ordinea t[1], t[2], ... t[n-1] şi puse în tabloul de selecţie. Dacă s-au extras deja k elemente din tablou şi au fost puse în arborele de selectie, atunci zona t[0],...,t[k-1] este folosită pentru tabloul de selecţie, iar zona t[k],...,t[n-1] este ocupată de elementele din t ramase încă pe vechile poziţii. La sfârşitul primei etape, întregul tablou t s-a transformat în arbore de selectie. În a doua etapă a sortării, elementele sunt extrase pe rând din tabloul de selecţie şi repuse în tabloul t. La extragerea elementelor din tabloul de selecţie, acestea sunt scoase în ordinea priorităţii, iar tabloul de selecţie se scurtează. În spaţiul rămas liber, se pun elementele extrase: primul element extras (cel de prioritate maximă) va fi pus pe pozitia t[n-1], al doilea pe pozitia t[n-2] etc. În final, întregul tablou t conţine elementele sortate în ordine crescătoare a priorităţii, iar arborele de selecţie este vid. Având în vedere că punerea sau extragerea unui element din tabloul de selecţie are complexitatea O(log n), iar in total se pun/extrag n elemente, complexitatea sortării prin metoda HeapSort este O(n.log n).

    public static void sort(double[] t) care sortează prin metoda HeapSort tabloul t cu componente de tip double. Algoritmii folosiţi pentru punerea unui element în arborele de selecţie sau pentru extragerea unui element sunt aceiaşi ca cei folosiţi în metodele put şi remove ale clasei ArboreSelectie.

Arbori de căutareFie un arbore binar, în care informaţiile din noduri sunt comparabile, adică pot fi ordonate după un anumit criteriu. Vom spune că nodul A precede nodul B dacă, după criteriul adoptat, informaţia din A o precede pe cea din B. Se numeşte arbore de căutare un arbore binar cu următoarele proprietăţi:     - toate nodurile din subarborele stâng sunt "mai mici" decât rădăcina (deci preced rădăcina);     - toate nodurile din subarborele drept sunt "mai mari" decât rădăcina (succed rădăcinii);     - orice subarbore al arborelui de căutare este el însuşi un arbore de căutare. Ultima proprietate ne indică faptul că arborele de căutare este o structură recursivă.

Căutarea unui nod în arborele de căutarePentru a căuta o anumită valoare V în arbore ne folosim de proprietăţile acestuia:     - dacă valoarea căutată V coincide cu cea din rădacină, înseamnă că V există în arbore;     - altfel, dacă valoarea căutată V este mai mică decât cea din rădacină, căutăm în subarborele din stânga;     - altfel, cautăm în subarborele din dreapta. Căutarea se încheie cu succes în momentul în care s-a găsit valoarea căutată, sau se încheie cu eşec în momentul în care se constată ca nodul curent nu mai are subarbore în partea în care ar trebui continuată căutarea.

Căutarea valorii minime sau maximeNodul arborelui de căutare, care conţine elementul (obiectul de informaţie) de valoare minimă, se găseşte pornind de la rădacină şi urmând numai calea spre fiul stânga, pâna când se ajunge la un nod care nu mai are fiu stânga. În mod similar, pentru nodul de valoare maximă, se porneşte de la rădăcină urmând consecvent calea spre fiul dreapta, pâna se ajunge la un nod care nu mai are fiu dreapta.

Punerea unui nod în arborele de căutarePunerea unui nou nod în arborele de căutare se face astfel:     - se caută locul în care ar trebui să se găsească nodul respectiv, la fel ca în cazul când se caută o valoare existentă;     - dacă există deja un nod care conţine valoarea respectivă, operaţia se incheie fară a adăuga un nou nod;     - dacă nu se găseşte în arbore un astfel de nod, se adaugă noul nod ca fiu (stânga sau dreapta, după caz) al nodului la care s-a încheiat operaţia de căutare.

Eliminarea unui nod din arborele de căutareEliminarea unui nod frunză al arborelui de căutare este foarte simplă: se caută nodul respectiv şi se elimină legatura către acesta din nodul-tată. Dacă însă se doreşte eliminarea unui nod care este rădacină a arborelui sau a unui subarbore, se procedează astfel: se elimină numai informaţia din nodul care trebuie eliminat şi se înlocuieşte cu cea din fiul minim al subarborelui din dreapta sau cu cea din fiul maxim al subarborelui din stânga. Dacă acest nod, din care s-a extras informaţia, este o frunză, nodul se elimină. Dacă însă este tot un nod intermediar (rădăcină a unui subarbore), se repetă operaţia de propagare descrisă mai sus, continuându-se astfel până se ajunge la o frunză.

Complexitatea operaţiilor cu arbori de căutareSe observă că, atât la căutarea unui nod existent, cât şi la punerea unui nod nou, numărul maxim de paşi de căutare este egal cu înalţimea arborelui. În cazul cel mai favorabil, când arborele este (aproape) complet, sau când numărul de noduri lipsă este relativ mic, complexitatea este O(log n). Totusi, în cazul cel mai defavorabil, când toate nodurile arborelui au numai fiu stâng sau numai fiu drept, complexitatea este O(n), deoarece arborele a degenerat practic, în acest caz, într-o listă înlănţuită. O astfel de situaţie poate să apară, dacă punerea nodurilor în arborele de căutare se face în ordinea strict crescătoare (descrescătoare) a valorilor lor.