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.

  • 🌳 Chei comandate: Cheile subarborelui stâng sunt mai mici, iar cheile subarborelui drept sunt mai mari decât cheile subarborelui părinte.
  • ⚡ Rapid Operaacțiuni: Ordonarea permite căutarea, inserarea și ștergerea să se execute eficient prin compararea valorilor.
  • 🔍 Căutare: O comparație la fiecare nod elimină jumătate din arbore, deplasându-se la stânga sau la dreapta.
  • ➕ Introduce: O nouă valoare este plasată la stânga sau la dreapta rădăcinii pe baza comparației.
  • ➖ Șterge: Ștergerea gestionează nodurile cu zero, unul sau doi copii folosind un predecesor sau un succesor.

Arborele de căutare binar (BST) cu exemplu

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.

Atributele arborelui de căutare binar

  1. Există nodul principal sau nivelul părinte 11. Sub acesta, există noduri/ramuri stânga și dreapta cu propriile valori cheie.
  2. Subarborele din dreapta are valori cheie mai mari decât nodul părinte.
  3. 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.

Căutare OperaTION

  1. Elementul care trebuie căutat este 10.
  2. 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.
  3. Acum comparați 10 cu nodul 7, 10 > 7, deci treceți la subarborele din dreapta.
  4. Apoi comparați 10 cu următorul nod, care este 9, 10 > 9, căutați în copilul subarborelui din dreapta.
  5. 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.

Insera OperaTION

  1. Există o listă de 6 elemente care trebuie inserate într-un BST în ordine de la stânga la dreapta.
  2. 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.
  3. 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.

Șterge Operații

  1. 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.
  2. Ștergeți valoarea 19 și eliminați legătura din nod.
  3. Vedeți noua structură a BST fără 19.

Șterge Operații

  1. 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.
  2. Ș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.
  3. Vedeți noua structură a BST fără 9.

Șterge Operații

  1. Aici veți șterge nodul 12 care are doi copii.
  2. Ș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.
  3. Ștergeți nodul 12 și înlocuiți-l cu 10, deoarece este cea mai mare valoare din subarborele din stânga.
  4. Vizualizați noua structură a BST după ștergerea a 12.

Șterge Operații

  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 mic element din subarborele din dreapta lui 12 îl va înlocui.
  3. Ștergeți nodul 12 și înlocuiți-l cu 19, deoarece este cea mai mică valoare din subarborele din dreapta.
  4. 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.

Întrebări frecvente

BST-urile și variantele lor echilibrate organizează datele ordonate în spatele funcțiilor de inteligență artificială, cum ar fi completarea automată, arborii de decizie și căutările rapide prin chei sortate. Acestea mențin eficiența căutării, ceea ce ajută sistemele de inteligență artificială să regăsească rapid candidații în timpul inferenței.

Da. Asistenții AI pot genera căutare, inserare și ștergere cod pentru un BST în Python, Java, C++ dintr-o descriere simplă. Verificați cu atenție logica de ștergere, deoarece cazul cu doi copii este ușor de greșit.

Căutarea, inserarea și ștergerea se execută în timp O(log n) pe un BST echilibrat. În cel mai rău caz, un arbore dezechilibrat se degradează într-o listă înlănțuită, făcând operațiile O(n), motiv pentru care se utilizează adesea arborii autoechilibrați.

Un BST simplu poate deveni dezechilibrat și lent. Un BST echilibrat, cum ar fi un arbore AVL sau Red-Black, rotește automat nodurile după inserare sau ștergere pentru a menține înălțimea mică, garantând operații O(log n).

Rezumați această postare cu: