[Powered by Google Translate] [Binarni Traži] [Patrick Schmid - Sveučilište Harvard] [Ovo je CS50. - CS50.TV] 

Ako sam ti dao popis Disney karaktera imena po abecednom redu i vas traži da pronađete Mickey Mouse, kako će vam ići oko radiš? Jedan očigledan način bi se skenirati popis od početka i provjeriti svaki naziv za vidjeti ako je Mickey. Ali, kao što ste pročitali Aladdin, Alice, Ariel, i tako dalje, brzo ćete shvatiti da s početkom u prednjem dijelu popisa nije bio dobra ideja. Dobro, možda bi trebao početi raditi unatrag od kraja popisa. Sada ste pročitali Tarzan, Stitch, Snjeguljica, i tako dalje. Ipak, to ne čini kao najbolji način da ide o tome. 

Pa, još jedan način da bi mogao ići o događaj ovaj je pokušati suziti popis imena koje morate pogledati. Budući da znate da su abecednim redom, mogli bi samo pogledate imena u sredini popisa i provjerite je li Mickey Mouse je prije ili poslije tog imena. Gledajući prezimena u drugom stupcu želite shvatiti da M za Mickey dolazi nakon J za Jasmine, tako da jednostavno bih ignorirati prvu polovicu popisa. Onda ste vjerojatno bih pogledati na vrhu posljednjeg stupca i vidjeti da je to počinje s Rapunzel. Mickey dolazi prije Rapunzel, izgleda možemo zanemariti posljednji stupac kao dobro. Nastavljajući pretraživanje strategije, brzo ćete vidjeti da je Mickey je u prvoj polovici preostalog popis imena i napokon pronaći Mickey skriva između Merlina i Minnie. 

Što ste upravo učinio je u osnovi binarni pretraživanje. Kao što to i ime kaže, obavlja svoju strategiju u potrazi u binarnom materije. Što to znači? Pa, s obzirom na popis razvrstanih predmeta, algoritam binarno pretraživanje čini binarnu odluku - lijevo ili desno, veći ili manji od, po abecednom redu prije ili poslije - u svakoj točki. Sada kada imamo ime koje ide uz ovaj pretraživanje algoritam, Pogledajmo još jedan primjer, ali ovaj put s popisom sortirani brojeva. Recimo da su u potrazi za brojem 144 u ovom popisu razvrstanih brojeva. Baš kao i prije, naći ćemo broj koji je u sredini - koja je u ovom slučaju je 13 - i vidjeti ako je veća od 144 ili manje od 13 godina. Budući da je očito veći od 13, što možemo ignorirati sve što je 13 ili manje i samo se koncentrirati na preostale polovine. Budući da sada imamo čak i broj predmeta lijevo, mi jednostavno izabrati broj koji je blizu sredine. U tom slučaju ćemo izabrati 55. Mogli smo jednako lako izabrao 89. Ok. Opet, 144 je veći od 55, pa idemo desno. Srećom za nas, sljedeći srednji broj je 144, jedan tražimo. Dakle, kako bi se pronašli 144 pomoću binarnog pretraživanja, mi smo u mogućnosti da ga pronaći u samo tri koraka. Ako bismo imati koristi linearnu potragu ovdje, to bi trebalo da nam 12 koraka. Kao što je zapravo, jer to traži način poluvremena broj predmeta ima da pogledate na svakom koraku, da će se naći stavku je u potrazi za u zapisniku o broja stavki na popisu. Sada kad smo vidjeli dva primjera, neka je pogledati neki pseudocode za rekurzivni funkciju koja implementira binarno pretraživanje. Počevši na vrhu, vidimo da moramo pronaći funkciju koja uzima četiri argumente: ključ, polje, min, a max. Ključ je broj koji smo u potrazi za, tako 144 u prethodnom primjeru. Array je popis brojeva koji smo u potrazi. Min i Max su indeksi minimalne i maksimalne pozicije da smo trenutno gleda. Dakle, kada smo započeli, min će biti nula i max će biti maksimalno indeks niza. Kao što smo suzili pretraživanje dolje, mi ćemo ažurirati min i max biti samo Raspon da smo još uvijek u potrazi u. 

Ajmo preskočiti do zanimljivog dijela prvi. Prva stvar koju smo učiniti je pronaći tačku, indeks koji je na pola puta između min i max u nizu da smo još uvijek razmišlja. Onda mi gledamo na vrijednosti polja u tom srednjem mjestu i vidjeti ako je broj da smo u potrazi za manje od tog ključa. Ako je broj na toj poziciji je manje, onda to znači da je ključ veći od svih brojeva s lijeve toj poziciji. Tako možemo nazvati binarni funkciju pretragu opet, ali ovaj put ažuriranje najmanju i najveću parametre čitati samo polovicu koja je veća od ili jednaka vrijednosti smo samo gledali. S druge strane, ako je ključ je manji od broja na danu sredinu polja, želimo ići lijevo i ignorirati sve brojeve koji su veći. Opet, mi zovemo binarno pretraživanje, ali ovaj put s rasponom min i max Updated uključiti samo donju polovicu. Ako je vrijednost u trenutnom srednjem u polju nije ni veći od niti manji od ključa, onda mora biti jednak za ključ. Dakle, možemo jednostavno vratiti trenutni indeks srednjeg, a mi smo gotovi. Konačno, ovaj potvrdni ovdje za slučaj da je broj nije zapravo u niz brojeva smo u potrazi. Ako je najveći indeks u rasponu da smo u potrazi za je sve manje od minimuma, to znači da smo otišli predaleko. Budući da je broj nije bio u ulaznom polju, vraćamo -1 ukazati da se ništa nije pronađeno. 

Možda ste primijetili da je za ovaj algoritam za rad, popis brojeva mora biti riješeno. Drugim riječima, možemo samo naći 144 pomoću binarnog pretraživanja ako su svi brojevi naručio od najniže do najviše. Ako to nije slučaj, ne bismo bili u mogućnosti da se isključi pola brojeva na svakom koraku. Dakle, imamo dvije opcije. Ili možemo uzeti Unsorted popis i sortirati prije korištenja binarnog pretraživanja, ili možemo biti sigurni da je popis brojeva sortira kao što smo dodali brojeve na njega. Dakle, umjesto sortiranje samo kada moramo tražiti, zašto ne bi popis sortiran u svim vremenima? 

Jedan od načina da bi popis brojeva sortirani istovremeno omogućujući jedan dodati ili premjestiti brojeva s ovog popisa je pomoću nešto što se zove binarno stablo pretraživanja. Stablo binarno pretraživanje struktura podataka koja ima tri svojstva. Prvo, lijevo podstablo bilo čvoru sadrži samo vrijednosti koje su manje od ili jednaka čvora vrijednosti. Drugo, pravo podstablo od čvora sadrži samo vrijednosti koje su veće od ili jednaka čvora vrijednosti. I, konačno, obje lijeve i desne subtrees svih čvorova su također binarna stabla pretraživanja. Pogledajmo primjer s istim brojevima koje smo ranije. Za one od vas koji nikada nisu vidjeli stablo informatika prije, Dopustite mi da vam reći da je stablo informatika raste prema dolje. Da, za razliku od stabala ste navikli, korijen od stabla informatike je na vrhu, a listovi su na dnu. Svaki kutijica se zove čvor, a čvorovi su međusobno povezani po rubovima. Tako je korijen tog stabla je čvor vrijednost s vrijednošću 13, koja ima 2 djece čvorova sa vrijednostima 5 i 34. Podstablo je stablo koje se formiraju samo gleda na pododjeljku cijelog stabla. 

Na primjer, lijevo podstablo od čvora 3 je stablo stvorili čvorovi 0, 1, 2 i. Dakle, ako se vratimo na svojstva drveta binarnog pretraživanja, vidimo da je svaki čvor u stablu odgovara na sva tri svojstva, naime, lijevo podstablo sadrži samo vrijednosti koje su manje od ili jednaka čvora vrijednosti; pravo podstablo svih čvorova sadrži samo vrijednosti koje su veće od ili jednaka čvora vrijednosti, a i lijevi i desni subtrees svih čvorova su također binarna stabla pretraživanja. Iako je to stablo izgleda drugačije, to je valjan binarno pretraživanje stablo za isti skup brojeva. Kao Zapravo, postoji mnogo mogućih načina na koje možete napraviti vrijedi binarno pretraživanje stablo od tih brojeva. Pa, vratimo se na prvom smo stvorili. Dakle, ono što možemo učiniti s tih stabala? Pa, možemo vrlo jednostavno pronaći minimalne i maksimalne vrijednosti. Minimalne vrijednosti mogu se naći uvijek ide na lijevo dok više ne postoje čvorovi za posjetiti. Isto tako, kako bi pronašli najveću jedan jednostavno samo ide dolje s desne strane na svaki put. 

Pronalaženje bilo koji drugi broj koji nije minimalna ili maksimalna je jednako lako. Reci mi smo u potrazi za brojem 89. Mi jednostavno provjeriti vrijednost svakog čvora i ići lijevo ili desno, ovisno o tome je li čvor je vrijednost manja ili veća od jedan tražimo. Dakle, s početkom u korijenu 13, vidimo da 89 je veća, i tako idemo desno. Onda ćemo vidjeti čvor za 34, i opet idemo desno. 89 je još uvijek veći od 55, tako da smo i dalje ide na desno. Mi smo tada dolazi do čvora s vrijednosti 144 i idite na lijevo. Evo i gle, 89 je tamo. 

Još jedna stvar koja mi se može učiniti je ispisati sve brojeve obavljanje inorder obuhvaćanje. Inorder obuhvaćanje znači ispisati sve u lijevo podstablo slijedi ispis čvora sama i onda slijedi tiskanje sve u pravo podstablo. Na primjer, uzmimo naše najdraže stablo binarnog pretraživanja i ispisati brojeve u sortiraju bi. Krećemo u korijenu 13, ali prije ispisa 13 moramo ispisati sve u lijevo podstablo. Tako smo ići na pet. Mi još uvijek moramo ići dublje u drvo dok ne pronađete lijevo-najviše čvor, koja je nula. Nakon ispisa nula, idemo natrag do jednog i ispisati da van. Onda idemo desno podstablo, koji je dvije i ispisati da van. Sada kada smo gotovi s tim podstablo, možemo se vratiti do tri i isprintati. Nastavljajući natrag gore, mi ispisati pet, a zatim osam. Sada kada smo završili cijeli lijevo podstablo, možemo ispisati 13 i početi raditi na pravo podstablo. Mi hop do 34, ali prije ispisa 34 moramo ispisati njegovo lijevo podstablo. Tako smo ispisali 21, tada ćemo doći do isprintati 34 i posjetiti svoje pravo podstablo. Od 55 nema lijevo podstablo, mi smo ga ispisali i dalje na njeno pravo podstablo. 144 ima lijevo podstablo, pa mi isprintati 89, nakon čega slijedi 144, i na kraju desnom tipkom većina čvor 233. Ima ga imate, svi brojevi se ispisuju u redoslijedu od najniže do najviše. 

Dodavanje nešto na stablo je relativno bezbolno, kao dobro. Sve što morate učiniti je napraviti sigurni da ćemo slijediti tri binarna svojstva pretraživanja stablo , a zatim umetnite vrijednost tamo gdje je prostor. Recimo da želite umetnuti vrijednost sedam. Od sedam manje od 13, idemo lijevo. No, to je veća od 5, pa smo prošli na desno. Budući da je manje od 8 i 8 je čvor nultog stupnja, dodali smo 7 na lijevoj dijete osam. Voila! Dodali smo nekoliko našem stablu binarnog pretraživanja. 

Ako možemo dodati stvari, možemo bolje moći izbrisati stvari kao dobro. Nažalost za nas, brisanje je malo kompliciranije - nije puno, ali samo malo. Postoje tri različite scenarije da moramo uzeti u obzir kada brišete elemente iz binarnih stabala pretraživanja. Prvo, najlakše je slučaj da je element čvor nultog stupnja. U ovom slučaju, mi jednostavno ga izbrisati i ići na s našeg poslovanja. Recimo da želimo izbrisati sedam koje smo upravo dodali. Pa, mi jednostavno ga pronaći, uklonite ga, i to je to. Sljedeći slučaj je ako čvor ima samo jednog djeteta. Ovdje možemo izbrisati čvor, ali prvo moramo osigurati povezati podstablo da je sada lijevo roditelja do roditelja čvora smo upravo izbrisao. Recimo da želimo izbrisati 3 od našeg drveta. Mi uzeti dijete element tog čvora te ga priključiti na roditelja čvora. U ovom slučaju, mi smo sada pridaje 1 do 5. To radi bez problema, jer znamo, prema stabla binarnom pretraživanje nekretnina, da je sve u lijevo podstablo od 3 je manje od pet. Sada je tri podstablo se brine, možemo ga izbrisati. Treći i posljednji slučaj je najsloženiji. To je slučaj kada je čvor želimo izbrisati ima dvoje djece. Da bi to učinili, prvo moramo pronaći čvor koji ima sljedeću najveću vrijednost, swap dvije, a zatim izbrisati čvor u pitanju. Obavijest čvor koji ima sljedeća najveća vrijednost ne može imati dva djeci se jer je njegova lijeva dijete će biti bolji kandidat za sljedeći najveći. Stoga, brisanje čvora sa 2 djece iznosi zamjene od dvije čvorova, a zatim brisanje barata jednom od dva navedena pravila. Na primjer, recimo da želimo izbrisati root čvor, 13. Prva stvar koju radimo je da smo pronašli sljedeću najveću vrijednost u stablu koji, u ovom slučaju, je 21. Mi smo tada zamijenili dva čvorova, što 13 listova i 21 središnja skupina čvorova. Sada možemo jednostavno izbrisati 13. 

Kao aludirao na ranije, postoji mnogo mogućih načina da zaradite valjanu stablo binarnog pretraživanja. Nažalost za nas, neki su gori od drugih. Na primjer, ono što se događa kada se izgraditi binarno pretraživanje stablo iz sortirani popis brojeva? Svi brojevi se dodaje samo na desno na svakom koraku. Kada želimo tražiti broj, nemamo izbora, ali samo da pogledate desno na svakom koraku. Ovo nije bolje nego linearno pretraživanje na sve. Iako nećemo pokriti ih ovdje, tu su i drugi, složeniji, strukture podataka da bi bili sigurni da se to ne desi. Međutim, jedna jednostavna stvar koja se može učiniti kako bi se izbjeglo ovo je na samo slučajno dvoličnost ulaznih vrijednosti. To je vrlo vjerojatno da Slučajnost miješaju popis brojeva sortira. Ako je to slučaj, kockarnice neće ostati u poslovanju za dugo. 

Ima li ga imati. Vi sada znate o binarnom traženje i binarnih pretraživanja drveće. Ja sam Patrick Schmid, a ovo je CS50. [CS50.TV] Jedan očigledan način bi se skenirati popis od ... [beep] ... Broj predmeta ... yep [Smijeh] ... Postavljati čvor 234 ... augh. >> Jupi! To je bio -