Un arbore de căutare este o structură de date utilizată în programarea computerelor pentru a conține și a organiza o listă de date. Fiecare arbore de căutare este compus dintr-un set ordonat de noduri. Aceste noduri pot fi conectate la zero sau mai multe alte noduri. noduri. Nodurile individuale conțin unele date, precum și legături către orice alte noduri. Datele care sunt conținute în nodurile arborelui sunt foarte adesea ordonate într-un fel pentru a permite algoritmilor eficienți să caute, introduceți și îndepărtați nodurile cu ușurință.
Nodurile unui arbore de căutare sunt descrise cu patru termeni importanți. Partea de sus a unui arbore, unde se află primul nod, se numește rădăcină. Dacă un nod conține link-uri către sub -nodes, acel nod este cunoscut ca părinte. Nodurile care sunt sub părinte se numesc copii, iar orice nod care nu are noduri copil se numește frunză. un nod rădăcină este identificat deoarece nu are un părinte, iar nodurile frunză nu vor avea copii.
Un program este capabil să se deplaseze printr-un arbore căutând date pornind de la un anumit nod, efectuând o verificare condiționată și apoi trecând la următorul nod logic dacă datele necesare nu sunt prezente. În funcție de structura de date utilizată , această căutare poate dura o perioadă variabilă de timp. Dacă arborele de căutare este organizat în timpul procesului de adăugare și eliminare a nodurilor, căutarea poate fi foarte rapidă. Când un arbore este asamblat aleatoriu, este nesortat sau permite mai mulți părinți, căutarea poate dura foarte mult timp.
Un factor care afectează utilizarea arborilor de căutare este problema echilibrului. Un arbore echilibrat este acela în care atât copiii din dreapta cât și din stânga nodului rădăcină conțin fie aceeași adâncime de noduri copii, fie se află într-un număr de un singur nod. Adâncimea unui copac este numărul de noduri de la cea mai de jos frunză a unui copac până la rădăcină. Un copac dezechilibrat ar putea avea toate nodurile pe o singură parte sau să aibă toate nodurile dispuse liniar, fără ramuri.Când adâncimea unui arbore crește, viteza algoritmilor de căutare poate scădea dramatic.
Există anumite tipuri de arbori de căutare care sunt descriși ca auto-echilibrați. Acești arbori folosesc operațiuni precum rotația arborilor pentru a ajuta la menținerea echilibrului, păstrând în același timp ordinea datelor din frunze. Rotațiile arborelui pot încetini un program la adăugarea și eliminarea nodurilor, acest lucru fiind contracarat de viteza cu care datele pot fi recuperate.
Deși există multe tipuri de arbori de căutare, cea mai comună structură de date arborescentă este un arbore de căutare binar. Acest tip de date este format din noduri care au fiecare de la zero la două noduri secundare. Există doar un nod rădăcină, și toate frunzele din arbore sunt ordonate de la stânga la dreapta în valori crescătoare în funcție de datele pe care le dețin. Există mulți algoritmi pentru arbori binari de căutare care pot ușurează foarte mult datele de comandă.
Nu există o implementare unică standard pentru nodurile arborelui de căutare. Nodurile pot fi reprezentate printr-o mare varietate de structuri de date. Pot fi utilizate matrice de matrice, precum ar putea multiplica listele legate. Adesea, un arborele de căutare folosește o structură de date personalizată care este concepută pentru a ajuta la finalizarea operațiunilor necesare cerute de program.Unele biblioteci de programare standard includ chiar și propriile implementări interne ale arborilor de căutare.