Arborele de căutare binar (BST) cu exemplu

Ce este un arbore binar de căutare?

Arborele de căutare binar este un algoritm avansat utilizat pentru analiza nodului, a ramurilor lui stânga și dreaptă, care sunt modelate într-o structură arborescentă și returnează valoarea. BST este conceput pe arhitectura unui algoritm de căutare binar de bază; prin urmare, permite căutări, inserări și eliminări mai rapide de noduri. Acest lucru face ca programul să fie foarte rapid și precis.

Atributele 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 subarbori pe partea stângă și dreaptă.
Fiecare sub-arbore, cunoscut și ca arbore binar de căutare, are sub-ramuri la dreapta și la stânga lor.
Toate nodurile sunt legate prin perechi cheie-valoare.
Cheile nodurilor prezente pe subarborele din stânga sunt mai mici decât cheile nodului lor părinte
În mod similar, cheile nodurilor din subarborele din stânga au valori mai mici decât cheile nodului lor părinte.

Există nodul principal sau nivelul părinte 11. Sub acesta, există noduri/ramuri din stânga și din dreapta cu propriile valori cheie
Sub-arborele din dreapta are valori cheie mai mari decât nodul părinte
Sub-arborele din stânga are valori decât nodul părinte

De ce avem nevoie de un arbore binar de căutare?

Cei doi factori majori care fac din arborele de căutare binar o soluție optimă pentru orice problemă din lumea reală sunt viteza și acuratețea.
Datorită faptului că căutarea binară este într-un format asemănător unei ramuri cu relații părinte-copil, algoritmul știe în ce locație a arborelui trebuie căutate elementele. Acest lucru 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ă să fie căutat mai mare sau mai puțin 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 întotdeauna valori 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ă eficient operațiuni precum căutarea, inserarea și ștergerea.

Tipuri de arbori binari

Trei tipuri de arbori binari sunt:

Arborele binar complet: Toate nivelurile din arbori sunt pline de posibilele excepții ale ultimului nivel. În mod similar, toate nodurile sunt pline, îndreptând extrema stângă.
Arborele binar complet: Toate nodurile au 2 noduri copil, cu excepția frunzei.
Arborele binar echilibrat sau perfect: În arbore, toate nodurile au doi copii. În plus, există același nivel pentru fiecare subnod.

Aflați mai multe despre Arborele binar în structura datelor dacă sunteți interesat.

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 comparând valorile cu rădăcina și cu nodurile sale secundare ulterioare din sub-arborele din stânga sau din dreapta în consecință.

Depinde de elementul care trebuie inserat, căutat sau șters, după comparație, algoritmul poate arunca 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
Inserare: adaugă un element la arborele binar
Delete: ștergeți elementul dintr-un arbore binar

Fiecare operatie are propria sa structura si metoda de executie/analiza, insa cea mai complexa dintre toate este operatia Delete.

Căutare OperaTION

Inițiați întotdeauna analiza arborelui la nodul rădăcină și apoi deplasați-vă mai departe la subarborele din dreapta sau din stânga al nodului rădăcină, în funcție de faptul că elementul care trebuie localizat este fie mai mic, fie mai mare decât rădăcină.

Elementul care trebuie căutat este 10
Comparați elementul cu nodul rădăcină 12, 10 < 12, deci vă deplasați în subarborele din stânga. Nu este nevoie să analizați subarborele din dreapta
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 copilul din subarborele din dreapta
10 se potrivește cu valoarea din nod, 10 = 10, returnează valoarea utilizatorului.

Pseudocod pentru căutare în BST

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

Insera OperaTION

Aceasta este o operațiune foarte simplă. Mai întâi se inserează nodul rădăcină, apoi se compară următoarea valoare cu nodul rădăcină. Dacă valoarea este mai mare decât rădăcină, 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ă de 6 elemente care trebuie introduse într-un BST în ordine de la stânga la dreapta
Introduceți 12 ca nod rădăcină și comparați următoarele valori 7 și 9 pentru a le insera corespunzător în subarborele din dreapta și din stânga
Comparați valorile rămase 19, 5 și 10 cu nodul rădăcină 12 și plasați-le în consecință. 19 > 12 plasați-l ca copil drept al lui 12, 5 < 12 & 5 < 7, deci plasați-l ca copil stâng al lui 7. Acum comparați 10, 10 este < 12 și 10 este > 7 și 10 este > 9, locul 10 ca subarborele drept al lui 9.

Pseudocod pentru inserarea unui nod în BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Șterge Operații

Pentru ștergerea unui nod dintr-un BST, există unele cazuri, adică ștergerea unei rădăcini sau ștergerea unui nod frunză. De asemenea, după ștergerea unei rădăcini, trebuie să ne gândim la nodul rădăcină.

Să presupunem că vrem să ștergem un nod frunză, îl putem șterge doar, dar dacă vrem să ștergem o rădăcină, trebuie să înlocuim valoarea rădăcinii cu un alt nod. Să luăm următorul exemplu:

Cazul 1- Nodul cu zero copii: aceasta este cea mai ușoară situație, trebuie doar să ștergeți nodul care nu mai are copii la dreapta sau la stânga.
Cazul 2 – Nod cu un singur copil: odată ce ștergeți nodul, conectați pur și simplu nodul său copil cu nodul părinte al valorii șterse.
Cazul 3 Nodul cu doi copii: aceasta este cea mai dificilă situație și funcționează pe următoarele două reguli
3a – Predecesor în ordine: trebuie să ștergeți nodul cu doi copii și să îl înlocuiți cu cea mai mare valoare din subarborele din stânga nodului șters
3b – În ordinea succesorului: trebuie să ștergeți nodul cu doi copii și să îl înlocuiți cu cea mai mare valoare din subarborele 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 legătura din nod.
Vizualizaț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, după 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 predecesoare în ordine, ceea ce înseamnă că cel mai mare element din subarborele din stânga de 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 In Order Successor, ceea ce înseamnă că cel mai mare element din subarborele din dreapta din 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

Pseudocod pentru ștergerea unui nod

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Termeni importanți

Inserare: Inserează un element într-un arbore/creează un arbore.
Căutare: caută un element dintr-un arbore.
Precomandă Traversal: traversează un copac într-o manieră de precomandă.
Traversare în ordine: traversează un copac într-o manieră în ordine.
Traversare după comandă: traversează un copac într-o manieră după comandă.

Rezumat

BST este un algoritm de nivel avansat care efectuează diverse operații bazate pe compararea valorilor nodurilor cu nodul rădăcină.
Oricare dintre punctele dintr-o ierarhie părinte-copil reprezintă nodul. Cel puțin un nod părinte sau rădăcină rămâne prezent tot timpul.
Există un subarboresc din stânga și un subarbore din dreapta. Subarborele din stânga conține valori care sunt mai mici decât nodul rădăcină. Cu toate acestea, subarborele din dreapta conține o valoare care este mai mare decât nodul rădăcină.
Fiecare nod poate avea fie zero, unul sau doi copii.
Un arbore de căutare binar facilitează operațiunile primare precum căutarea, inserarea și ștergerea.
Ștergerea fiind cea mai complexă, are mai multe cazuri, de exemplu, un nod fără copil, un nod cu un copil și un nod cu doi copii.
Algoritmul este utilizat în soluții reale, cum ar fi jocuri, date de completare automată și grafică.