Pe scurt
Un arbore este o structură de date neliniară formată din noduri conectate prin muchii, cu un nod special numit rădăcină. Arborii binari, în care fiecare nod are cel mult doi fii, stau la baza unor structuri eficiente precum heap-urile, iar parcurgerile (preordine, inordine, postordine, pe niveluri) sunt metode esențiale de vizitare a nodurilor. Heap-ul este un arbore binar complet utilizat pentru cozi de priorități, iar operațiile fundamentale includ inserarea, extragerea și heapify.
Definiții și proprietăți de bază
Un arbore este o structură de date neliniară, formată din noduri conectate prin muchii, în care există un nod special numit rădăcină, iar restul nodurilor sunt organizate în subarbori.
Un arbore binar este un arbore în care fiecare nod are cel mult doi fii: stâng și drept. Arborii binari sunt fundamentali în informatică datorită eficienței operațiilor de căutare, inserare și ștergere, mai ales în variante echilibrate precum heap-urile.
Noțiuni importante de cunoscut
- Adâncimea unui nod
- Înălțimea unui arbore
- Frunză – nod fără fii
- Nod intern – nod cu cel puțin un fiu
- Gradul unui arbore
Reprezentarea arborilor se poate face prin referințe sau prin vectori de tați.
Parcurgerile arborilor
Parcurgerile arborilor sunt metode de a vizita toate nodurile într-o ordine specifică. Cele mai comune sunt:
- Parcurgerea în preordine (rădăcină, stânga, dreapta)
- Parcurgerea în inordine (stânga, rădăcină, dreapta) – pentru un arbore binar de căutare produce elementele sortate
- Parcurgerea în postordine (stânga, dreapta, rădăcină) – utilă pentru eliberarea memoriei sau evaluarea expresiilor
- Parcurgerea pe niveluri (BFS) – vizitează nodurile pe rândurile arborelui, de sus în jos, de la stânga la dreapta
Exemplu: Pentru un arbore binar cu rădăcina 10, fiul stâng 5 (cu fiii 2 și 7) și fiul drept 15 (cu fiul stâng 12):
- Preordine: 10, 5, 2, 7, 15, 12
- Inordine: 2, 5, 7, 10, 12, 15
- Postordine: 2, 7, 5, 12, 15, 10
Implementarea parcurgerilor se poate face recursiv și iterativ.
Heap-ul
Heap-ul este un arbore binar special, utilizat frecvent pentru implementarea cozilor de priorități.
Tipuri de heap
- Max-heap – valoarea fiecărui nod este mai mare sau egală cu valorile fiilor săi
- Min-heap – valoarea fiecărui nod este mai mică sau egală cu valorile fiilor săi
Proprietăți
- Heap-ul este complet (toate nivelurile, cu excepția ultimului, sunt complet umplute, iar ultimul nivel se umple de la stânga la dreapta)
Operații fundamentale pe heap
- Inserarea – se adaugă la sfârșit, apoi se „urcă” elementul prin compararea cu părintele
- Extragerea maximului/minimului – se înlocuiește rădăcina cu ultimul element, apoi se „coboară” prin compararea cu fiii
- Construcția unui heap dintr-un vector – algoritmul heapify
Exemplu – Construcția unui max-heap din vectorul [3, 5, 9, 1, 8, 7]:
Se aplică heapify de jos în sus
- Pentru nodul de la index 3 (valoarea 1) nu se face nimic (frunză)
- Pentru index 2 (9) la fel
- Pentru index 1 (5) se compară cu fiii (8 și 1, maximul 8) și se interschimbă 5 cu 8
- Pentru rădăcină (3) se compară cu fiii (8 și 9, maximul 9) și se interschimbă 3 cu 9
Rezultă heap-ul: [9, 8, 7, 1, 5, 3]
Sortarea prin heap (Heapsort)
Heapsort este algoritmul de sortare care folosește un heap.
Exemplu – Heapsort pentru vectorul [4, 10, 3, 5, 1]:
- Se construiește max-heap: [10, 5, 3, 4, 1]
- Se extrage rădăcina (10) și se mută la sfârșit, apoi se reface heap-ul pentru primele 4 elemente: [5, 4, 3, 1, 10]
- Se extrage 5, apoi [4, 1, 3, 5, 10]
- Se extrage 4, apoi [3, 1, 4, 5, 10]
- Se extrage 3, apoi [1, 3, 4, 5, 10]
Rezultat final sortat: [1, 3, 4, 5, 10]
Verifică-te!
- Care sunt cele patru tipuri principale de parcurgere a unui arbore binar și în ce ordine vizitează nodurile?
- Ce proprietate trebuie să îndeplinească un arbore binar pentru a fi considerat max-heap?
- Care sunt pașii algoritmului de inserare într-un heap?