Što je binarno stablo pretraživanja?
Binarno stablo pretraživanja napredni je algoritam koji se koristi za analizu čvora, njegove lijeve i desne grane, koji su modelirani u strukturi stabla i vraćaju vrijednost. BST je osmišljen na arhitekturi osnovnog algoritma binarnog pretraživanja; stoga omogućuje brže pretraživanje, umetanje i uklanjanje čvorova. To čini program doista brzim i preciznim.
U ovom vodiču o strukturi podataka naučit ćete:
- Što je binarno stablo pretraživanja?
- Atributi binarnog stabla pretraživanja
- Zašto nam treba binarno stablo pretraživanja?
- Vrste binarnih stabala
- Kako djeluje binarno stablo pretraživanja?
- Važni pojmovi
Atributi binarnog stabla 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 roditeljski čvor može imati nula podređenih čvorova ili maksimalno dva podugla ili podstabla na lijevoj i desnoj strani.
- Svako podstablo, poznato i kao binarno stablo pretraživanja, ima podgrane s desne i lijeve strane od sebe.
- Svi čvorovi povezani su parovima ključ / vrijednost.
- Tipke čvorova prisutnih na lijevom podstablu manje su od tipki njihovog roditeljskog čvora
- Slično tome, ključevi lijevog podstabla imaju manje vrijednosti od ključeva roditeljskog čvora.
- Postoji glavni čvor ili roditeljska razina 11. Ispod njega nalaze se lijevi i desni čvorovi / grane sa vlastitim ključnim vrijednostima
- Desno podstablo ima vrijednosti ključa veće od nadređenog čvora
- Lijevo podstablo ima vrijednosti od nadređenog čvora
Zašto nam treba binarno stablo pretraživanja?
- Dva glavna čimbenika koja čine binarno stablo pretraživanja optimalnim rješenjem za bilo koji stvarni problem su brzina i preciznost.
- Zbog činjenice da je binarno pretraživanje u formatu nalik grani s odnosima roditelja i djeteta, algoritam zna na kojem mjestu stabla treba tražiti elemente. To smanjuje broj usporedbi ključ / vrijednost koje program mora napraviti da bi pronašao željeni element.
- Uz to, u slučaju da je element koji treba pretraživati veći ili manji od nadređenog čvora, čvor zna koju će stablu tražiti. Razlog je taj š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 igara, automatskog dovršavanja aktivnosti 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 na stablima pune su mogućih izuzetaka posljednje razine. Slično su i svi čvorovi puni, usmjeravaju 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 dvoje djece. Osim toga, postoji ista razina svake podvrste.
Kako djeluje binarno stablo 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.
Ovisno o elementu koji će se umetnuti, pretraživati ili izbrisati, nakon usporedbe algoritam može lako ispustiti lijevo ili desno podstablo korijenskog čvora.
BST prvenstveno nudi sljedeće tri vrste operacija za vašu upotrebu:
- Pretraživanje: pretražuje element s binarnog stabla
- Umetni: dodaje element binarnom stablu
- Delete: brisanje elementa iz binarnog stabla
Svaka operacija ima svoju strukturu i način izvođenja / analize, ali najsloženija od svih je operacija Delete.
Operacija pretraživanja
Uvijek započnite analiziranje stabla na korijenskom čvoru, a zatim se pomaknite dalje u desno ili lijevo podstablo korijenskog čvora, ovisno o tome je li element koji se nalazi manji ili veći od korijena.
- Element koji se traži je 10
- Usporedite element s korijenskim čvorom 12, 10 <12, stoga prelazite na lijevo podstablo. Ne treba analizirati desno podstablo
- Sada usporedite 10 s čvorom 7, 10> 7, pa prijeđite na desno podstablo
- Zatim usporedite 10 sa sljedećim čvorom, a to je 9, 10> 9, pogledajte desno poddrvo djeteta
- 10 podudaranja s vrijednošću u čvoru, 10 = 10, vratite vrijednost korisniku.
Umetni rad
Ovo je vrlo direktna operacija. Prvo se umetne 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.
- Postoji popis od 6 elemenata koje treba umetnuti u BST redom slijeva udesno
- Umetnite 12 kao korijenski čvor i usporedite sljedeće vrijednosti 7 i 9 za umetanje u skladu s tim u desno i lijevo podstablo
- Usporedite preostale vrijednosti 19, 5 i 10 s korijenskim čvorom 12 i postavite ih u skladu s tim. 19> 12 smjestite ga kao desno dijete od 12, 5 <12 i 5 <7, stoga ga stavite kao lijevo dijete od 7 godina.
- Sada usporedite 10, 10 je <12 & 10 je> 7 & 10 je> 9, mjesto 10 postavite kao desno podstablo od 9.
Izbriši operacije
Delete je najnaprednija i najsloženija među svim ostalim operacijama. U BST-u se rješava više slučajeva za brisanje.
- Slučaj 1- Čvor s nula djece: ovo je najlakša situacija, samo trebate izbrisati čvor koji nema daljnje djece 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 djeluje na sljedeća dva pravila
- 3a - U prethodniku naloga: trebate izbrisati čvor s dvoje djece i zamijeniti ga najvećom vrijednošću na lijevom podstablu izbrisanog čvora
- 3b - Redoslijed nasljednika: trebate izbrisati čvor s dvoje djece i zamijeniti ga najvećom vrijednošću na desnom podstablu izbrisanog čvora
- Ovo je prvi slučaj brisanja u kojem brišete čvor koji nema djece. Kao što možete vidjeti na dijagramu da 19, 10 i 5 nemaju djece. Ali izbrisat ćemo 19.
- Izbrišite vrijednost 19 i uklonite vezu s čvora.
- Pogledajte novu strukturu BST-a bez 19
- Ovo je drugi slučaj brisanja u kojem brišete čvor s 1 djetetom, kao što možete vidjeti na dijagramu da 9 ima jedno dijete.
- Izbrišite čvor 9 i zamijenite ga podređenim dijelom 10 i dodajte vezu od 7 do 10
- Pogledajte novu strukturu BST-a bez 9
- Ovdje ćete izbrisati čvor 12 koji ima dvoje djece
- Brisanje čvora dogodit će se na temelju pravila prethodnika po redu, što znači da će ga zamijeniti najveći element u lijevom podstablu od 12.
- Izbrišite čvor 12 i zamijenite ga s 10 jer je to najveća vrijednost na lijevom podstablu
- Pogledajte novu strukturu BST-a nakon brisanja 12
- 1 Izbrišite čvor 12 koji ima dvoje djece
- 2 Brisanje čvora dogodit će se na temelju pravila Redoslijed nasljednika, što znači da će ga zamijeniti najveći element u desnom podstablu od 12
- 3 Izbrišite čvor 12 i zamijenite ga s 19 jer je to najveća vrijednost na desnom podstablu
- 4 Pogledajte novu strukturu BST-a nakon brisanja 12
Važni pojmovi
- Umetni - umeta element u stablo / stvara drvo.
- Pretraživanje - traži element na stablu.
- Preorder Preorder - prelazak stabla na način predbilježbe.
- Unutarnje zaobilaženje - prelazi stablo redom.
- Postorder Prelazak - prelazi stablo na način nakon narudžbe.
Sažetak
- BST je algoritam napredne razine koji izvodi razne operacije na temelju usporedbe vrijednosti čvora s korijenskim čvorom.
- Bilo koja od točaka u hijerarhiji roditelj-dijete predstavlja čvor. Barem jedan roditeljski ili korijenski čvor ostaje prisutan cijelo vrijeme.
- Postoje lijevo 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 ili nula, jedno ili dvoje djece.
- Binarno stablo pretraživanja omogućuje primarne operacije poput pretraživanja, umetanja i brisanja.
- Delete kao najsloženiji ima više slučajeva, na primjer, čvor bez djeteta, čvor s jednim djetetom i čvor s dvoje djece.
- Algoritam se koristi u stvarnim rješenjima poput igara, automatskog dovršavanja podataka i grafike.