Pe scurt
Arborii sunt structuri de date neliniare, formate din noduri legate ierarhic, cu un nod special numit rădăcină. Arborii binari de căutare (BST) permit căutări eficiente O(log n) în arbori echilibrați, iar heap-ul binar este utilizat pentru heap sort și cozi de prioritate. Pentru Bac, trebuie cunoscute implementarea statică a arborilor binari cu vectori, parcurgerile recursive, proprietățile BST și operațiile heap.
Definiții și proprietăți fundamentale
Arbori – structură de bază
- Arbore: structură de date neliniară, formată din noduri legate ierarhic
- Rădăcină: nodul special de la care pornește arborele
- Fiecare nod poate avea zero sau mai multe noduri subordonate (copii)
Arbore binar
- Fiecare nod are cel mult doi copii, denumiți stânga și dreapta
- Reprezentare statică: se poate implementa cu vectori (2*i = copil stâng, 2*i+1 = copil drept)
Arbore binar de căutare (BST)
- Toate valorile din subarborele stâng sunt mai mici decât valoarea nodului
- Toate valorile din subarborele drept sunt mai mari decât valoarea nodului
- Permite căutări eficiente O(log n) în arbori echilibrați
- Operații: căutare, inserare, ștergere – toate O(log n) (dacă arborele este echilibrat)
Heap binar
- Arbore binar complet: toate nivelurile, exceptând ultimul, sunt pline; ultimul nivel se completează de la stânga la dreapta
- Proprietăți:
-
Max-heap: fiecare nod ≥ copiii săi
- Min-heap: fiecare nod ≤ copiii săi
- Implementat frecvent cu vector (2*i = copil stâng, 2*i+1 = copil drept)
- Utilizări: heap sort și cozi de prioritate
- Operații:
-
Inserare: percolare în sus – O(log n)
- Extragere maxim/minim: percolare în jos – O(log n)
- Heapify: transformă un vector arbitrar în heap în O(n)
Parcurgeri ale arborilor
Tipuri de parcurgeri
- Inordine (stânga – rădăcină – dreapta): pentru BST produce valori sortate
- Preordine (rădăcină – stânga – dreapta): utilizată pentru copierea arborelui
- Postordine (stânga – dreapta – rădăcină): utilizată pentru ștergerea arborelui
- Nivel (BFS): parcurgere pe niveluri
Exemple practice
Exemplul 1: Arbore binar complet cu 7 noduri
- Rădăcina: nodul 1 (valoarea 10)
- Copiii rădăcinii: nodul 2 (5) – stânga, nodul 3 (15) – dreapta
- Copiii nodului 2: nodul 4 (3) – stânga, nodul 5 (7) – dreapta
- Copiii nodului 3: nodul 6 (12) – stânga, nodul 7 (18) – dreapta
- Parcurgerea inordine: 3, 5, 7, 10, 12, 15, 18
Exemplul 2: Max-heap
- Elemente: [50, 30, 20, 15, 10, 8, 16]
- Reprezentare ca arbore: rădăcina 50, copii 30 și 20; 30 are copii 15 și 10; 20 are copii 8 și 16
- Proprietatea: fiecare părinte ≥ copii
- Extragerea maximului (50):
- Se mută ultimul element (16) în rădăcină
- Se aplică heapify (down-heap) pentru a reface proprietatea
- Rezultat: [30, 16, 20, 15, 10, 8]
Exemplul 3: Arbore binar de căutare (BST)
- Inserarea secvențială: 50, 30, 70, 20, 40, 60, 80
- Structura arborelui: rădăcina 50, stânga 30 (cu copii 20 și 40), dreapta 70 (cu copii 60 și 80)
- Căutarea valorii 40: compară cu 50 → mergi stânga la 30 → compară cu 30 → mergi dreapta → găsit 40 (complexitate O(log n))
- Ștergerea nodului 30: se înlocuiește cu succesorul inordine (40) sau predecesorul (20), apoi se reatașează copiii
Verifică-te!
- Care este diferența principală între un arbore binar oarecare și un arbore binar de căutare (BST)?
- Ce proprietate trebuie să îndeplinească un heap binar pentru a fi considerat max-heap?
- Ce parcurgere a unui BST produce valorile în ordine crescătoare?