Ce este un arbore de căutare binară?
Arborele de căutare binar este un algoritm avansat utilizat pentru analiza nodului, a ramurilor sale stânga și dreapta, care sunt modelate într-o structură de copac și returnarea valorii. BST este conceput pe baza arhitecturii unui algoritm de căutare binară de bază; prin urmare, permite căutări, inserții și eliminări mai rapide de noduri. Acest lucru face ca programul să fie foarte rapid și precis.
În acest tutorial privind structura datelor, veți afla:
- Ce este un arbore de căutare binară?
- Atribute ale arborelui de căutare binară
- De ce avem nevoie de un arbore de căutare binară?
- Tipuri de arbori binari
- Cum funcționează arborele de căutare binară?
- Termeni importanți
Atribute ale arborelui de căutare binară
Un BST este format din mai multe noduri și constă din următoarele atribute:
- Nodurile arborelui sunt reprezentate într-o relație părinte-copil
- Fiecare nod părinte poate avea zero noduri copil sau maximum două subnoduri sau subarburi pe laturile stânga și dreapta.
- Fiecare sub-copac, cunoscut și sub numele de copac de căutare binar, are subramuri în dreapta și în stânga lor.
- Toate nodurile sunt legate cu perechi cheie-valoare.
- Cheile nodurilor prezente în subarborele din stânga sunt mai mici decât tastele nodului lor părinte
- În mod similar, cheile nodurilor subarborelui din stânga au valori mai mici decât cheile nodului părinte.
- Există nodul principal sau nivelul părinte 11. Sub acesta, există noduri / ramuri stânga și dreapta cu propriile valori cheie
- Subarborele din dreapta are valori cheie mai mari decât nodul părinte
- Subarborele din stânga are valori decât nodul părinte
De ce avem nevoie de un arbore de căutare binară?
- Cei doi factori majori care fac din arborele de căutare binară o soluție optimă la orice probleme din lumea reală sunt Viteza și Precizia.
- Datorită faptului că căutarea binară este într-un format asemănător ramurii cu relații părinte-copil, algoritmul știe în ce locație a arborelui trebuie să fie căutate elementele. Aceasta scade numărul de comparații cheie-valoare pe care programul trebuie să le facă pentru a localiza elementul dorit.
- În plus, în cazul în care elementul care urmează a fi căutat este mai mare sau mai mic decât nodul părinte, nodul știe ce parte a arborelui să caute. Motivul este că subarborele din stânga este întotdeauna mai mic decât nodul părinte, iar subarborele din dreapta are valori întotdeauna egale sau mai mari decât nodul părinte.
- BST este utilizat în mod obișnuit pentru a implementa căutări complexe, logici de joc robuste, activități de completare automată și grafică.
- Algoritmul acceptă în mod eficient operațiuni precum căutarea, inserarea și ștergerea.
Tipuri de arbori binari
Trei tipuri de copaci binari sunt:
- Arborele binar complet: toate nivelurile din copaci sunt pline de posibilele excepții ale ultimului nivel. În mod similar, toate nodurile sunt pline, direcționând extrema stângă.
- Arborele binar complet: toate nodurile au 2 noduri copil cu excepția frunzei.
- Arborele binar echilibrat sau perfect: în copac, toate nodurile au doi copii. În plus, există același nivel al fiecărui subnod.
Cum funcționează arborele de căutare binară?
Arborele are întotdeauna un nod rădăcină și alte noduri copil, fie în stânga, fie în dreapta. Algoritmul efectuează toate operațiunile prin compararea valorilor cu rădăcina și cu nodurile copilului său din subarborele din stânga sau din dreapta în consecință.
Depinde de elementul care urmează să fie inserat, căutat sau șters, după comparație, algoritmul poate scăpa cu ușurință subarborele din stânga sau din dreapta nodului rădăcină.
BST oferă în principal următoarele trei tipuri de operațiuni pentru utilizarea dvs.:
- Căutare: caută elementul din arborele binar
- Insert: adaugă un element în arborele binar
- Șterge: șterge elementul dintr-un arbore binar
Fiecare operație are propria structură și metodă de execuție / analiză, dar cea mai complexă dintre toate este operația Ștergere.
Operațiunea de căutare
Începeți întotdeauna analizarea arborelui la nodul rădăcină și apoi deplasați-vă mai departe, fie la subarborele drept sau stâng al nodului rădăcină, în funcție de elementul care urmează să fie localizat, fie mai mic, fie mai mare decât rădăcina.
- Elementul de căutat este 10
- Comparați elementul cu nodul rădăcină 12, 10 <12, prin urmare vă deplasați la subarborele din stânga. Nu este nevoie să analizăm subarborele drept
- Acum comparați 10 cu nodul 7, 10> 7, deci treceți la subarborele din dreapta
- Apoi comparați 10 cu următorul nod, care este 9, 10> 9, uitați-vă în subarborele drept al copilului
- 10 potriviri cu valoarea din nod, 10 = 10, returnează valoarea utilizatorului.
Operațiunea de inserare
Aceasta este o operație foarte simplă. Mai întâi, se introduce nodul rădăcină, apoi se compară următoarea valoare cu nodul rădăcină. Dacă valoarea este mai mare decât rădăcina, aceasta se adaugă la subarborele din dreapta, iar dacă este mai mică decât rădăcina, se adaugă la subarborele din stânga.
- Există o listă cu 6 elemente care trebuie inserate într-un BST în ordine de la stânga la dreapta
- Introduceți 12 ca nod rădăcină și comparați valorile următoare 7 și 9 pentru inserarea corespunzătoare în subarborele drept și stâng
- Comparați valorile rămase 19, 5 și 10 cu nodul rădăcină 12 și plasați-le corespunzător. 19> 12 plasați-l ca copilul potrivit de 12, 5 <12 și 5 <7, de aceea plasați-l ca copil stâng de 7.
- Acum comparați 10, 10 este <12 și 10 este> 7 și 10 este> 9, plasați 10 ca subarborele drept din 9.
Ștergeți operațiunile
Ștergerea este cea mai avansată și complexă dintre toate celelalte operații. Există mai multe cazuri gestionate pentru ștergere în BST.
- Cazul 1 - Nod cu zero copii: aceasta este cea mai ușoară situație, trebuie doar să ștergeți nodul care nu mai are copii în dreapta sau în stânga.
- Cazul 2 - Nod cu un singur copil: odată ce ștergeți nodul, pur și simplu conectați nodul său copil cu nodul părinte al valorii șterse.
- Cazul 3 Nod cu doi copii: aceasta este cea mai dificilă situație și funcționează pe baza următoarelor două reguli
- 3a - În Predecesorul comenzii: trebuie să ștergeți nodul cu doi copii și să-l înlocuiți cu cea mai mare valoare din subarborele din stânga al nodului șters
- 3b - În succesorul comenzii: trebuie să ștergeți nodul cu doi copii și să-l înlocuiți cu cea mai mare valoare din sub-arborele din dreapta al nodului șters
- Acesta este primul caz de ștergere în care ștergeți un nod care nu are copii. După cum puteți vedea în diagramă, 19, 10 și 5 nu au copii. Dar vom șterge 19.
- Ștergeți valoarea 19 și eliminați linkul din nod.
- Vedeți noua structură a BST fără 19
- Acesta este al doilea caz de ștergere în care ștergeți un nod care are 1 copil, așa cum puteți vedea în diagramă că 9 are un copil.
- Ștergeți nodul 9 și înlocuiți-l cu copilul său 10 și adăugați un link de la 7 la 10
- Vizualizați noua structură a BST fără 9
- Aici veți șterge nodul 12 care are doi copii
- Ștergerea nodului va avea loc pe baza regulii predecesorului în ordine, ceea ce înseamnă că cel mai mare element din subarborele din stânga al 12 îl va înlocui.
- Ștergeți nodul 12 și înlocuiți-l cu 10 deoarece este cea mai mare valoare din subarborele din stânga
- Vizualizați noua structură a BST după ștergerea 12
- 1 Ștergeți un nod 12 care are doi copii
- 2 Ștergerea nodului va avea loc pe baza regulii succesorului în ordine, ceea ce înseamnă că cel mai mare element din subarborele din dreapta al 12 îl va înlocui
- 3 Ștergeți nodul 12 și înlocuiți-l cu 19 deoarece este cea mai mare valoare din subarborele din dreapta
- 4 Vizualizați noua structură a BST după ștergerea 12
Termeni importanți
- Insert - Inserează un element într-un copac / creează un copac.
- Căutare - Caută un element dintr-un copac.
- Preorder Traversal - Traversează un copac într-un mod precomandat.
- Inorder Traversal - Traversează un copac într-o manieră în ordine.
- Postorders Traversal - Traversează un copac într-un mod post-comandă.
rezumat
- BST este un algoritm de nivel avansat care efectuează diverse operațiuni bazate pe compararea valorilor nodului cu nodul rădăcină.
- Oricare dintre punctele dintr-o ierarhie părinte-copil reprezintă nodul. Cel puțin un părinte sau nod rădăcină rămâne prezent tot timpul.
- Există un subarbore stâng și un subarborescent drept. Subarborele din stânga conține valori mai mici decât nodul rădăcină. Cu toate acestea, subarborele din dreapta conține o valoare mai mare decât nodul rădăcină.
- Fiecare nod poate avea zero, unul sau doi copii.
- Un arbore de căutare binară facilitează operațiunile principale precum căutarea, inserarea și ștergerea.
- Ștergerea fiind cel mai complex are mai multe cazuri, de exemplu, un nod fără copil, nod cu un singur copil și nod cu doi copii.
- Algoritmul este utilizat în soluții din lumea reală, cum ar fi jocurile, completarea automată a datelor și grafica.