Ce este un arbore binar de căutare?

Un arbore de căutare binar este una dintre diferitele structuri de date care ne ajută să organizăm și să sortăm datele. Este o modalitate eficientă de a stoca datele într-o ierarhie și este foarte flexibilă.

În acest articol, vom arunca o privire mai atentă asupra modului în care funcționează, împreună cu proprietățile și aplicațiile sale.

Ce este un arbore binar de căutare?

Un arbore de căutare binar este o structură de date compusă din noduri, similare listelor legate. Pot exista două tipuri de noduri: un părinte și un copil. Nodul rădăcină este punctul de început al structurii care se ramifică în două noduri copil, numite nodul stâng și nodul drept.

Fiecare nod poate fi referit doar de părintele său și putem traversa nodurile arborelui în funcție de direcție. Arborele de căutare binar are trei proprietăți principale:

1. Nodul stâng este mai mic decât părintele său.
2. Nodul drept este mai mare decât părintele său.
3. Subarborele din stânga și din dreapta trebuie să fie arbori binari de căutare.

Un arbore de căutare binar perfect este obținut atunci când toate nivelurile sunt umplute și fiecare nod are un nod copil stâng și drept.

Legate de: Biblioteci de știință a datelor pentru Python pe care fiecare cercetător de date ar trebui să le folosească

Operații de bază ale unui arbore de căutare binar

Acum aveți o idee mai bună despre ce este un arbore de căutare binar, ne putem uita la operațiunile sale de bază mai jos.

1. Operațiune de căutare

Căutarea ne permite să găsim o anumită valoare prezentă în arbore. Putem folosi două tipuri de căutări: căutarea pe lățimea întâi (BFS) și căutarea în adâncime (DFS). Breadth-first search este un algoritm de căutare care începe de la nodul rădăcină și traversează orizontal, dintr-o parte în alta, până când obiectivul este găsit. Fiecare nod este vizitat o dată în timpul acestei căutări.

Căutarea în profunzime, pe de altă parte, traversează arborele pe verticală, pornind de la nodul rădăcină și lucrând pe o singură ramură. Dacă obiectivul este găsit, operațiunea se încheie. Dar dacă nu, acesta și caută celelalte noduri.

2. Operațiunea de inserare

Operația de inserare utilizează operația de căutare pentru a determina locația în care ar trebui să fie inserat noul nod. Procesul începe de la nodul rădăcină, iar căutarea începe până când se ajunge la destinație. Există trei cazuri de luat în considerare la inserare.

• Cazul 1: Când nu există niciun nod. Nodul de inserat va deveni nodul rădăcină.

• Cazul 2: Nu există copii. În acest caz, nodul va fi comparat cu nodul rădăcină. Dacă este mai mare, va deveni copilul potrivit; altfel, va deveni copilul stâng.

• Cazul 3: Când rădăcina și copiii săi sunt prezenți. Noul nod va fi comparat cu fiecare nod de pe calea sa pentru a determina ce nod îl vizitează în continuare. Dacă nodul este mai mare decât nodul rădăcină, acesta va traversa în jos sub-arborele din dreapta sau, altfel, pe stânga. În mod similar, se fac comparații pe fiecare nivel pentru a determina dacă va merge la dreapta sau la stânga până când ajunge la destinație.

3. Operațiunea de ștergere

Operația de ștergere este utilizată pentru a elimina un anumit nod din arbore. Ștergerea este considerată dificilă, deoarece după eliminarea unui nod, arborele trebuie reorganizat în consecință. Există trei cazuri principale de luat în considerare:

• Cazul 1: Ștergerea unui nod frunză. Un nod frunză este un nod fără copii. Acesta este cel mai ușor de eliminat deoarece nu afectează niciun alt nod; pur și simplu străbatem copacul până ajungem la el și îl ștergem.

• Cazul 2: Ștergerea unui nod cu un copil. Ștergerea unui părinte cu un singur nod va avea ca rezultat copilul să-și ia poziția și toate nodurile ulterioare se vor ridica la un nivel. Nu va exista nicio modificare în structura sub-arborilor.

• Cazul 3: Ștergerea unui nod cu doi copii. Când trebuie să scoatem un nod cu doi copii, trebuie mai întâi să găsim un nod ulterior care să-și poată lua poziția. Două noduri pot înlocui nodul eliminat, succesorul sau predecesorul în ordine. Succesorul în ordine este copilul din stânga al subarborelui din dreapta, iar predecesorul din ordinea este copilul din dreapta al subarborelui din stânga. Copiem conținutul succesorului/predecesorului în nod și ștergem succesorul/predecesorul în ordine.

Legate de: Cum să construiți structuri de date cu clasele JavaScript ES6

Cum să traversezi un arbore de căutare binar

Traversarea este procesul prin care navigăm într-un arbore binar de căutare. Se face pentru a localiza un anumit articol sau pentru a tipări un contur al arborelui. Începem întotdeauna de la nodul rădăcină și trebuie să urmăm marginile pentru a ajunge la celelalte noduri. Fiecare nod ar trebui considerat un sub-arbore, iar procesul se repetă până când toate nodurile sunt vizitate.

• Traversare în comandă: Traversarea în ordine va produce o hartă în ordine crescătoare. Cu această metodă, începem de la subarborele din stânga și continuăm la rădăcină și subarborele din dreapta.

• Precomandă Traversal: În această metodă, nodul rădăcină este vizitat mai întâi, urmat de subarborele din stânga și subarborele din dreapta.

• Traversare după comandă: Această traversare implică vizitarea ultimului nod rădăcină. Începem de la subarborele din stânga, apoi de la subarborele din dreapta și apoi de la nodul rădăcină.

Aplicații din lumea reală

Deci, cum folosim algoritmii de arbore de căutare binari? După cum se poate presupune, ele sunt extrem de eficiente la căutare și sortare. Cea mai mare putere a arborilor binari este structura lor organizată. Permite căutarea să se facă la viteze remarcabile, reducând cantitatea de date pe care trebuie să o analizăm la jumătate pe trecere.

Arborii binari de căutare ne permit să menținem eficient un set de date care se schimbă dinamic într-o formă organizată. Pentru aplicațiile care au date inserate și eliminate frecvent, acestea sunt de mare ajutor. Motoarele de jocuri video folosesc un algoritm bazat pe arbori cunoscuți sub numele de partiție spațială binară pentru a ajuta la redarea ordonată a obiectelor. Microsoft Excel și majoritatea software-ului pentru foi de calcul folosesc arbori binari ca structură de date de bază.

S-ar putea să fii surprins să știi că codul Morse folosește un arbore de căutare binar pentru a codifica datele. Un alt motiv important pentru care Arborii de căutare binari sunt atât de folositori este variațiile lor multiple. Flexibilitatea lor a dus la crearea a numeroase variante pentru a rezolva tot felul de probleme. Când sunt utilizați corespunzător, arborii binari de căutare sunt un bun avantaj.

Arbori de căutare binari: punctul de plecare perfect

Una dintre principalele moduri de a evalua expertiza unui inginer este prin cunoștințele și aplicarea structurilor de date. Structurile de date sunt utile și pot ajuta la crearea unui sistem mai eficient. Arborii binari de căutare sunt o introducere excelentă în structurile de date pentru orice dezvoltator care începe.

15 metode JavaScript Array pe care ar trebui să le stăpâniți astăzi

Doriți să înțelegeți matricele JavaScript, dar nu le puteți înțelege? Consultați exemplele noastre de matrice JavaScript pentru îndrumare.

Citiți în continuare

Despre autor