Binarno stablo pretraživanja (BST) s primjerom

Što je stablo binarnog pretraživanja?

Binarno stablo pretraživanja je napredni algoritam koji se koristi za analizu čvora, njegove lijeve i desne grane, koje su modelirane u strukturi stabla, i vraćanje vrijednosti. BST je osmišljen na arhitekturi osnovnog binarnog algoritma pretraživanja; stoga omogućuje brže pretraživanje, umetanje i uklanjanje čvorova. To čini program vrlo brzim i točnim.

Atributi stabla binarnog pretraživanja

BST se sastoji od više čvorova i sastoji se od sljedećih atributa:

• Čvorovi stabla predstavljeni su u odnosu roditelj-dijete.
• Svaki nadređeni čvor može imati nula podređenih čvorova ili najviše dva podčvora ili podstabla na lijevoj i desnoj strani.
• Svako pod-stablo, također poznato kao binarno stablo pretraživanja, ima pod-grane desno i lijevo od sebe.
• Svi su čvorovi povezani parovima ključ-vrijednost.
• Ključevi čvorova prisutnih na lijevom podstablu su manji od ključeva njihovog roditeljskog čvora.
• Slično tome, ključevi čvorova prisutnih na desnom podstablu veći su od ključeva njihovog roditeljskog čvora.

1. Tu je glavni čvor ili roditeljska razina 11. Ispod njega nalaze se lijevi i desni čvorovi/grane sa svojim vlastitim ključnim vrijednostima.
2. Desno podstablo ima ključne vrijednosti veće od roditeljskog čvora.
3. Lijevo podstablo ima manje ključnih vrijednosti od roditeljskog čvora.

Zašto nam je potrebno stablo binarnog pretraživanja?

• Dva glavna faktora koja čine binarno stablo pretraživanja optimalnim rješenjem za bilo koji problem iz stvarnog svijeta su brzina i točnost.
• Zbog činjenice da je binarno pretraživanje u formatu sličnom grani s relacijama roditelj-dijete, algoritam zna na kojoj lokaciji stabla elemente treba pretražiti. Time se smanjuje broj usporedbi ključa i vrijednosti koje program mora napraviti da bi locirao željeni element.
• Osim toga, u slučaju da je element koji se traži veći ili manji od roditeljskog čvora, čvor zna koju stranu stabla treba pretraživati. Razlog je taj što je lijevo podstablo uvijek manje od roditeljskog čvora, a desno podstablo uvijek ima vrijednosti jednake ili veće od roditeljskog čvora.
• BST se obično koristi za implementaciju složenih pretraživanja, robusne logike igre, aktivnosti automatskog dovršavanja i grafike.
• Algoritam učinkovito podržava operacije poput pretraživanja, umetanja i brisanja.

Vrste binarnih stabala

Tri su vrste binarnih stabala:

• Potpuno binarno stablo: Sve razine u stablu su pune, s mogućom iznimkom na posljednjoj razini. Slično tome, svi čvorovi su puni, u smjeru krajnje lijeve strane.
• Potpuno binarno stablo: Svi čvorovi imaju 2 podređena čvora osim lista.
• Uravnoteženo ili savršeno binarno stablo: U stablu svi čvorovi imaju dva podređena čvora. Osim toga, postoji ista razina za svaki podčvor.

Saznajte više o Binarno stablo u strukturi podataka ako si zainteresiran.

Kako funkcionira stablo binarnog pretraživanja?

Stablo uvijek ima korijenski čvor i daljnje podređene čvorove, bilo s lijeve ili desne strane. Algoritam izvodi sve operacije uspoređujući vrijednosti s korijenom i njegovim daljnjim podređenim čvorovima u lijevom ili desnom podstablu prema tome.

Ovisno o elementu koji se umeće, pretražuje ili briše, nakon usporedbe, algoritam može lako ukloniti lijevo ili desno podstablo korijenskog čvora.

BST primarno nudi sljedeće tri vrste operacija za vašu upotrebu:

• Traži: pretražuje element iz binarnog stabla.
• Umetnuti: dodaje element binarnom stablu.
• Izbrisati: briše element iz binarnog stabla.

Svaka operacija ima svoju strukturu i metodu izvođenja/analize, ali najsloženija od svih je operacija Brisanje.

Traži OperaANJE

Uvijek započnite analizu stabla u korijenskom čvoru, a zatim se pomaknite dalje prema desnom ili lijevom podstablu korijenskog čvora, ovisno o tome je li element koji se želi pronaći manji ili veći od korijena.

1. Element koji se traži je 10.
2. Usporedite element s korijenskim čvorom 12, 10 < 12, stoga se pomičete na lijevo podstablo. Nema potrebe za analizom desnog podstabla.
3. Sada usporedite 10 s čvorom 7, 10 > 7, pa se pomaknite na desno podstablo.
4. Zatim usporedite 10 sa sljedećim čvorom, koji je 9, 10 > 9, pogledajte u desnom podstablu.
5. 10 odgovara vrijednosti u čvoru, 10 = 10, vraća vrijednost korisniku.

Nadimak Code za pretraživanje u BST-u

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)

umetak OperaANJE

Ovo je vrlo jednostavna operacija. Prvo se ubacuje korijenski čvor, a zatim se sljedeća vrijednost uspoređuje s korijenskim čvorom. Ako je vrijednost veća od korijena, dodaje se desnom podstablu, a ako je manja od korijena, dodaje se lijevom podstablu.

1. Postoji popis od 6 elemenata koje je potrebno umetnuti u BST redom s lijeva na desno.
2. Umetnite 12 kao korijenski čvor i usporedite sljedeće vrijednosti 7 i 9 za umetanje u desno i lijevo podstablo.
3. Usporedite preostale vrijednosti 19, 5 i 10 s korijenskim čvorom 12 i postavite ih u skladu s tim. 19 > 12, postavite ga kao desno dijete od 12; 5 < 12 i 5 < 7, stoga ga postavite kao lijevo dijete od 7. Sada usporedite 10, 10 je < 12 i 10 je > 7 i 10 je > 9, postavite 10 kao desno podstablo od 9.

Pseudokod za umetanje čvora u 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

Izbrisati Operama

Za brisanje čvora iz BST-a postoje neki slučajevi, npr. brisanje korijena ili brisanje listnog čvora. Također, nakon brisanja korijena, moramo razmisliti o korijenskom čvoru.

Recimo da želimo obrisati listni čvor, možemo ga jednostavno obrisati, ali ako želimo obrisati korijen, moramo zamijeniti korijensku vrijednost drugim čvorom. Uzmimo sljedeći primjer:

• Slučaj 1 – Čvor s nula djece: Ovo je najlakša situacija, samo trebate izbrisati čvor koji nema daljnje potomke s desne ili lijeve strane.
• Slučaj 2 – Čvor s jednim djetetom: Nakon što izbrišete čvor, jednostavno povežite njegov podređeni čvor s roditeljskim čvorom izbrisane vrijednosti.
• Slučaj 3 – Čvor s dvoje djece: Ovo je najteža situacija i funkcionira prema sljedeća dva pravila:
  • 3a – Prethodnik po redu: Potrebno je izbrisati čvor s dva potomka i zamijeniti ga najvećom vrijednošću na lijevom podstablu izbrisanog čvora.
  • 3b – Nasljednik po redu: Potrebno je izbrisati čvor s dva potomka i zamijeniti ga najmanjom vrijednošću na desnom podstablu izbrisanog čvora.

1. Ovo je prvi slučaj brisanja, u kojem brišete čvor koji nema djecu. Kao što možete vidjeti na dijagramu, 19, 10 i 5 nemaju djecu. Ali mi ćemo izbrisati 19.
2. Izbrišite vrijednost 19 i uklonite vezu iz čvora.
3. Pogledajte novu strukturu BST-a bez 19.

1. Ovo je drugi slučaj brisanja, u kojem brišete čvor koji ima 1 dijete. Kao što možete vidjeti na dijagramu, 9 ima jedno dijete.
2. Izbrišite čvor 9 i zamijenite ga njegovim podređenim čvorom 10, te dodajte vezu od 7 do 10.
3. Pogledajte novu strukturu BST-a bez 9.

1. Ovdje ćete izbrisati čvor 12 koji ima dva potomka.
2. Brisanje čvora će se dogoditi na temelju pravila prethodnika po redoslijedu, što znači da će ga zamijeniti najveći element na lijevom podstablu od 12.
3. Izbrišite čvor 12 i zamijenite ga s 10, jer je to najveća vrijednost na lijevom podstablu.
4. Pogledajte novu strukturu BST-a nakon brisanja 12.

1. Izbriši čvor 12 koji ima dva potomka.
2. Brisanje čvora će se dogoditi na temelju pravila nasljednika po redoslijedu, što znači da će ga zamijeniti najmanji element na desnom podstablu od 12.
3. Izbrišite čvor 12 i zamijenite ga s 19, jer je to najmanja vrijednost na desnom podstablu.
4. Pogledajte novu strukturu BST-a nakon brisanja 12.

Nadimak Code za brisanje čvora

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)

Važni pojmovi

• Umetnuti: Umeće element u stablo / stvara stablo.
• Traži: Traži element u stablu.
• Prolazak prednarudžbe: Obilazi stablo na način unaprijed određenog reda.
• Prolazak unutar reda: Obilazi stablo po određenom redu.
• Prolazak nakon narudžbe: Obilazi stablo na način nakon redoslijeda.

Pitanja i odgovori