Arborele de căutare binar (BST) cu exemplu
⚡ Rezumat inteligent
Arborele binar de căutare (BST) este un arbore bazat pe noduri, în care subarborele stâng al fiecărui nod conține chei mai mici, iar subarborele drept conține chei mai mari, permițând căutarea, inserarea și ștergerea rapidă. Acesta acoperă atributele, tipurile, operațiile și pseudocodul BST.
Ce este un arbore binar de căutare?
Arborele binar de căutare este un algoritm avansat utilizat pentru analizarea nodului, a ramurilor sale stânga și dreaptă, care sunt modelate într-o structură arborescentă, și returnarea valorii. Arborele binar de căutare este conceput pe arhitectura unui algoritm de bază de căutare binară; 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.
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 în subarborele din stânga sunt mai mici decât cheile nodului lor părinte.
- În mod similar, cheile nodurilor prezente în subarborele din dreapta sunt mai mari decât cheile nodului lor 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 cheie mai mici decât nodul părinte.
De ce avem nevoie de un arbore binar de căutare?
- Cei doi factori majori care fac dintr-un arbore binar de căutare o soluție optimă pentru orice problemă din lumea reală sunt viteza și precizia.
- 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ă a fi căutat este mai mare sau mai mic decât nodul părinte, nodul știe în 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ă eficient operațiuni precum căutarea, inserarea și ștergerea.
Tipuri de arbori binari
Trei tipuri de arbori binari sunt:
- Arbore binar complet: Toate nivelurile din arbore sunt pline, cu o posibilă excepție la ultimul nivel. În mod similar, toate nodurile sunt pline, direcționând spre extrema stângă.
- Arbore binar complet: Toate nodurile au 2 noduri copil, cu excepția frunzei.
- Arbore binar echilibrat sau perfect: În arbore, toate nodurile au câte 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ță.
În funcție de elementul care trebuie inserat, căutat sau șters, după comparație, algoritmul poate elimina cu ușurință subarborele stâng sau drept al 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.
- Introduce: adaugă un element arborelui binar.
- Șterge: șterge 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
Întotdeauna inițiați analiza arborelui la nodul rădăcină și apoi treceți mai departe la subarborele din dreapta sau din stânga nodului rădăcină, în funcție de dacă elementul care trebuie localizat este mai mic sau mai mare decât rădăcina.
- Elementul care trebuie căutat este 10.
- Comparați elementul cu nodul rădăcină 12, 10 < 12, prin urmare vă mutaț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, căutați în copilul subarborelui din dreapta.
- 10 se potrivește cu valoarea din nod, 10 = 10, returnează valoarea utilizatorului.
Pseudo Code pentru căutarea î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 introduce nodul rădăcină, apoi următoarea valoare se compară cu nodul rădăcină. Dacă valoarea este mai mare decât rădăcina, aceasta este adăugată la subarborele din dreapta, iar dacă este mai mică decât rădăcina, aceasta este adăugată la subarborele din stânga.
- Există o listă de 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 următoarele valori, 7 și 9, pentru inserarea corespunzătoare î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ță. Dacă 19 > 12, plasați-l ca fiu din dreapta lui 12; dacă 5 < 12 și 5 < 7, prin urmare, plasați-l ca fiu din stânga lui 7. Acum comparați 10, 10 este < 12 și 10 este > 7 și 10 este > 9, plasați 10 ca subarborele din dreapta 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ă câteva cazuri, de exemplu, ștergerea unui nod rădăcină sau ștergerea unui nod frunză. De asemenea, după ștergerea unui nod rădăcină, 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 – Nod cu zero copii: Aceasta este cea mai ușoară situație, trebuie doar să ștergeți nodul care nu are alți copii la dreapta sau la stânga.
- Cazul 2 – Nod cu un copil: După ce ștergeți nodul, conectați pur și simplu 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 – 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 al nodului șters.
- 3b – Succesor în ordine: Trebuie să ștergeți nodul cu doi copii și să îl înlocuiți cu cea mai mică valoare din subarborele din dreapta 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 îl vom șterge pe 19.
- Ștergeți valoarea 19 și eliminați legătura 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. După cum puteți vedea în diagramă, 9 are un copil.
- Ștergeți nodul 9 și înlocuiți-l cu fiul său 10 și adăugați o legătură de la 7 la 10.
- Vedeț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, 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 a 12.
- Ștergeți un nod 12 care are doi copii.
- Ștergerea nodului va avea loc pe baza regulii In-Order Successor, ceea ce înseamnă că cel mai mic element din subarborele din dreapta lui 12 îl va înlocui.
- Ștergeți nodul 12 și înlocuiți-l cu 19, deoarece este cea mai mică valoare din subarborele din dreapta.
- Vizualizați noua structură a BST după ștergerea a 12.
Pseudo Code 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, delete the successor
free(newNode)
else
free(y)
Termeni importanți
- Introduce: Inserează un element într-un arbore / creează un arbore.
- Căutare: Caută un element într-un arbore.
- Precomandă Traversal: Parcurge un arbore într-o manieră precomandă.
- Traversare în ordine: Parcurge un arbore într-o manieră ordonată.
- Traversare postordin: Parcurge un arbore într-o manieră post-ordonare.








