Un Binary Search Tree (arbore binar de căutare) este o structură de date arborescentă în care fiecare nod are cel mult doi copii (stânga și dreapta), respectând o proprietate de ordonare:
- Toate valorile din subarborele stâng al unui nod sunt mai mici decât valoarea nodului.
- Toate valorile din subarborele drept sunt mai mari (sau egale, în funcție de convenție).
- Această regulă se aplică recursiv pentru fiecare subarbore.
Datorită acestei ordonări, operațiile de bază devin eficiente:
| Operație | Complexitate medie | Complexitate în cel mai rău caz |
|---|---|---|
| Căutare (search) | O(log n) | O(n) |
| Inserare (insert) | O(log n) | O(n) |
| Ștergere (delete) | O(log n) | O(n) |
Complexitatea "în cel mai rău caz" apare când arborele devine degenerat (practic o listă înlănțuită) — de exemplu dacă inserezi valori deja sortate (1, 2, 3, 4...). Din acest motiv există variante echilibrate (AVL, Red-Black Tree) care garantează O(log n) mereu.
Cele trei parcurgeri clasice, ca în codul pe care l-am scris:
- Inorder (stânga → nod → dreapta) → afișează valorile în ordine crescătoare.
- Preorder (nod → stânga → dreapta) → util pentru a reconstrui arborele.
- Postorder (stânga → dreapta → nod) → util pentru ștergerea completă a arborelui (se șterg copiii înainte de părinte).
Ștergerea are 3 situații:
- Nod frunză (fără copii) — se elimină direct.
- Un singur copil — nodul e înlocuit de copilul respectiv.
- Doi copii — nodul este înlocuit fie cu cel mai mare din subarborele stâng (ca în codul tău, funcția
mostlyRight), fie cu cel mai mic din subarborele drept — ambele metode păstrează proprietatea de BST.