Binarno stablo pretraživanja (BST) s primjerom

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 manji su od ključeva njihovog nadređenog čvora
• Slično, ključevi čvorova lijevog podstabla imaju manje vrijednosti od ključeva njihovih nadređenih čvorova.

1. Postoji glavni čvor ili nadređena razina 11. Ispod njega postoje lijevi i desni čvorovi/grane s vlastitim ključnim vrijednostima
2. Desno podstablo ima ključne vrijednosti veće od nadređenog čvora
3. Lijevo podstablo ima vrijednosti od nadređenog čvora

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

• Dva glavna čimbenika zbog kojih binarno stablo pretraživanja predstavlja optimalno rješenje za sve probleme 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.
• Dodatno, u slučaju da je element koji se traži veći ili manji od nadređenog čvora, čvor zna koju stranu stabla treba tražiti. Razlog je što je lijevo podstablo uvijek manje od nadređenog čvora, a desno podstablo ima vrijednosti uvijek jednake ili veće od nadređenog č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:

• Kompletno binarno stablo: Sve razine u stablima pune su mogućih iznimaka zadnje razine. Slično tome, svi su čvorovi puni, usmjeravajući krajnje lijevo.
• 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 djeteta. Osim toga, postoji ista razina svakog podčvora.

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 treba umetnuti, pretražiti ili izbrisati, nakon usporedbe, algoritam može lako ispustiti lijevo ili desno podstablo korijenskog čvora.

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

• Pretraživanje: pretražuje element iz binarnog stabla
• Umetni: dodaje element u binarno stablo
• Brisanje: brisanje elementa 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 analiziranje stabla na korijenskom čvoru, a zatim se pomaknite dalje na desno ili lijevo podstablo korijenskog čvora, ovisno o tome je li element koji treba locirati 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 prijeđite na desno podstablo
4. Zatim usporedite 10 sa sljedećim čvorom, koji je 9, 10 > 9, pogledajte u desnom podstablu dijete
5. 10 odgovara vrijednosti u čvoru, 10 = 10, vraća vrijednost korisniku.

Pseudo kod 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 umeće korijenski čvor, zatim se sljedeća vrijednost uspoređuje s korijenskim čvorom. Ako je vrijednost veća od korijena, dodaje se u desno podstablo, a ako je manja od korijena, dodaje se u lijevo podstablo.

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 odgovarajuće 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 stavite ga kao desno dijete od 12, 5 < 12 & 5 < 7, stoga ga stavite kao lijevo dijete od 7. Sada usporedite 10, 10 je < 12 & 10 je > 7 & 10 je > 9, mjesto 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 lisnog čvora. Također, nakon brisanja korijena, moramo razmišljati 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 obrisati čvor koji nema više djece s desne ili lijeve strane.
• Slučaj 2 – Čvor s jednim podređenim čvorom: nakon što izbrišete čvor, jednostavno povežite njegov podređeni čvor s nadređenim čvorom obrisane vrijednosti.
• Slučaj 3 Čvor s dvoje djece: ovo je najteža situacija i funkcionira prema sljedeća dva pravila
• 3a – U redoslijedu prethodnika: trebate izbrisati čvor s dva djeteta i zamijeniti ga najvećom vrijednošću na lijevom podstablu izbrisanog čvora
• 3b – U redoslijedu nasljednika: trebate izbrisati čvor s dva djeteta i zamijeniti ga najvećom vrijednošću na desnom podstablu izbrisanog čvora

1. Ovo je prvi slučaj brisanja u kojem brišete čvor koji nema djecu. Kao što vidite na dijagramu, 19, 10 i 5 nemaju djece. 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 da 9 ima jedno dijete.
2. Izbrišite čvor 9 i zamijenite ga njegovim podređenim čvorom 10 i dodajte vezu od 7 do 10
3. Pogledajte novu strukturu BST-a bez 9

1. Ovdje ćete obrisati čvor 12 koji ima dva djeteta
2. Brisanje čvora dogodit će se na temelju pravila redoslijeda prethodnika, što znači da će ga najveći element na lijevom podstablu od 12 zamijeniti.
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. 1 Izbrišite čvor 12 koji ima dva djeteta
2. 2 Brisanje čvora dogodit će se na temelju pravila Nasljednika po redu, što znači da će ga najveći element na desnom podstablu od 12 zamijeniti
3. 3 Izbrišite čvor 12 i zamijenite ga s 19 jer je to najveća vrijednost na desnom podstablu
4. 4 Pogledajte novu strukturu BST-a nakon brisanja 12

Pseudo kod 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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Važni pojmovi

• Umetni: Umeće element u stablo/stvara stablo.
• Pretraživanje: Pretražuje element u stablu.
• Obilaženje prednarudžbe: prelazi stablo na način prednarudžbe.
• Inorder Traversal: obilazi stablo prema redoslijedu.
• Postorder Traversal: obilazi stablo na postorder način.

rezime

• BST je algoritam napredne razine koji izvodi različite operacije na temelju usporedbe vrijednosti čvora s korijenskim čvorom.
• Bilo koja od točaka u hijerarhiji roditelj-dijete predstavlja čvor. Najmanje jedan nadređeni ili korijenski čvor ostaje cijelo vrijeme prisutan.
• Postoji lijevo podstablo i desno podstablo. Lijevo podstablo sadrži vrijednosti koje su manje od korijenskog čvora. Međutim, desno podstablo sadrži vrijednost koja je veća od korijenskog čvora.
• Svaki čvor može imati nula, jedan ili dva djeteta.
• Binarno stablo pretraživanja olakšava primarne operacije poput pretraživanja, umetanja i brisanja.
• Brisanje je najsloženije i ima više slučajeva, na primjer, čvor bez djeteta, čvor s jednim dijetetom i čvor s dva djeteta.
• Algoritam se koristi u rješenjima iz stvarnog svijeta poput igara, podataka za automatsko dovršavanje i grafike.