Informatică Algoritmi
Structuri de date arbore binar de cautare
Un arbore binar de căutare este o structură de date în care fiecare nod are cel mult doi copii, iar pentru orice nod, toate nodurile din subarborele stâng au valori mai mici, iar cele din dreapta au valori mai mari. Această proprietate permite căutări, inserări și ștergeri eficiente.
Proprietăți cheie
- Ordinea valorilor Pentru un nod cu valoarea v, toate nodurile din subarborele stâng au valori < v, iar cele din dreapta au valori > v. Exemplu: pentru rădăcină 10, stânga poate avea 5, dreapta 15.
- Structură binară Fiecare nod are cel mult doi copii: stâng și drept. Aceasta permite o organizare simplă și parcurgeri standard (preordine, inordine, postordine).
- Eficiența operațiilor În cazul mediu, căutarea, inserarea și ștergerea au complexitate O(log n), unde n este numărul de noduri, dacă arborele este echilibrat.
Operații comune
- 1 Căutarea unei valori Începi de la rădăcină; dacă valoarea căutată este mai mică, mergi la stânga, altfel la dreapta, până o găsești sau ajungi la null.
- 2 Inserarea unui nod Parcurgi arborele ca la căutare; când ajungi la o poziție null, creezi un nou nod cu valoarea dată și îl atașezi ca copil.
- 3 Ștergerea unui nod Dacă nodul are zero copii, îl elimini direct; dacă are un copil, îl înlocuiești cu copilul; dacă are doi, găsești succesorul inordine și îl înlocuiești.
Menține arborele echilibrat pentru a evita degradarea la O(n) în cel mai rău caz.