Informatică Algoritmi
Arbori binari de cautare
Un arbore binar de căutare este o structură de date arborescentă unde fiecare nod are cel mult doi copii, iar pentru orice nod, toate elementele din subarborele stâng sunt mai mici, iar din subarborele drept sunt mai mari. Această proprietate permite căutări, inserări și ștergeri eficiente.
Proprietăți cheie
- Structura nodului Conține o valoare, un pointer la copilul stâng și unul la copilul drept.
- Regula de ordonare Valoarea din stânga < valoarea nodului < valoarea din dreapta pentru toate nodurile.
- Operații eficiente Căutarea, inserarea și ștergerea au complexitate medie O(log n) în arbori echilibrați.
Exemplu de căutare într-un arbore
- 1 Pasul 1 Începe de la rădăcină. Dacă arborele este gol, elementul nu există.
- 2 Pasul 2 Compară valoarea căutată cu valoarea nodului curent.
- 3 Pasul 3 Dacă sunt egale, returnează nodul. Dacă valoarea este mai mică, mergi la copilul stâng; altfel, la copilul drept.
- 4 Pasul 4 Repetă până la găsire sau până când nu mai există copii, indicând absența.
Exemplu numeric
- Arborele Rădăcina 10, stânga 5, dreapta 15. Subarborele lui 5: stânga 3, dreapta 7.
- Căutarea lui 7 Începe la 10, 7 < 10, merge la stânga la 5, 7 > 5, merge la dreapta, găsește 7.
- Complexitate În acest caz, căutarea durează 3 pași, demonstrând eficiența O(log n).
Menține arborele echilibrat pentru a asigura performanță optimă la căutări.