[Powered by Google Translate] [Binary Search] [Patrick Schmid - Harvard University] [To je CS50. - CS50.TV] 

Če sem ti dal seznam imen Disney znakov v abecednem vrstnem redu in vas prosili, da bi našli Miki Miška, Kako bi šel o tem? Eden od očitnih načinov bi bil za skeniranje seznam od začetka in preverite vsako ime, da vidim, če je Mickey. Ampak kot ste prebrali Aladdin, Alice, Ariel, in tako naprej, boste hitro ugotovili, da se začne na sprednji strani seznama ni bila dobra ideja. Ok, morda bi morali začeti delati nazaj od konca seznama. Zdaj ste prebrali Tarzan, Stitch, Sneguljčica, in tako naprej. Kljub temu pa to ne zdi najboljši način, da gredo o tem. 

No, še en način, da bi lahko šel o tem je, da poskusite zožiti seznam imen, ki jih boste morali pogledati. Ker veš, da so v abecednem vrstnem redu, si lahko samo pogled na imena v sredini seznama in preverite, če Mickey Mouse je pred ali po tem imenom. Če pogledamo zadnje ime v drugem stolpcu boš zavedaš, da je M za Mickey prihaja po J za Jasmine, Tako bi preprosto prezreti prvo polovico seznama. Potem bi verjetno pogled na vrhu zadnjega stolpca in glej, da se začne z Rapunzel. Mickey je pred Rapunzel, izgleda, lahko odmislimo zadnji stolpec, kot dobro. Nadaljevanje strategija iskanja, boste hitro videli, da Mickey je v prvi polovici preostalega seznama imen in na koncu je bil Mickey skriva med Merlin in Minnie. 

Kaj si naredil, je bilo v bistvu binarno iskanje. Ker je to že samo ime pove, da opravlja svojo strategijo iskanjem v binarni zadeve. Kaj to pomeni? No, glede na seznam razvrščenih postavk, binarno iskanje algoritem naredi binarno odločitev - levo ali desno, je večja ali manjša od pred ali po abecedi - na vsaki točki. Zdaj, ko imamo ime, ki gre skupaj s to iskalni algoritem, Oglejmo si še en primer, tokrat s seznamom razvrščenih številk. Povejte iščemo številko 144 v tem seznamu razvrščena številk. Tako kot prej, smo našli številko, ki je na sredini - , ki je v tem primeru 13 - in videli, če je večja od 144 ali manj kot 13 let. Ker je očitno večji od 13, lahko odmislimo vse, kar je 13 ali manj in osredotočiti samo na preostalo polovico. Ker imamo zdaj celo število kosov levo, smo preprosto izberete številko, ki je blizu sredini. V tem primeru bomo izbrali 55. Lahko bi prav tako lahko izbrali 89. Ok. Again, 144 je več kot 55, tako da gremo na desno. K sreči za nas, naslednji srednji številka 144, tisti, ki ga iščemo. Torej, da bi našli 144 z binarno iskanje, bomo lahko našli v samo 3 korakih. Če bi smo uporabili linearno iskanje tukaj, bi nas sprejela 12 ukrepov. Kot Dejstvo je, saj je to način iskanja prepolovi število postavk ima pogled na na vsakem koraku, bo našel predmet, se išče v približno dnevnik števila elementov na seznamu. Zdaj, ko smo videli 2 primere, pa si oglejte nekateri psevdokod za rekurzivna funkcija, ki izvaja binarno iskanje. Začnite na vrhu, smo videli, da smo morali najti funkcijo, ki traja 4 argumente: ključ, matrika, min in max. Ključno je število, ki ga iščemo, tako 144 v prejšnjem primeru. Array je seznam številk, ki jih iščejo. Min in max so indeksi najnižje in najvišje položaje da smo trenutno iščejo. Torej, ko smo začeli, bo najmanj enaka nič in max bo največji indeks matrike. Kot smo zožite iskanje navzdol, bomo posodobiti min in max da je samo območje, ki se še vedno išče noter 

Naj preskočite na zanimiv del prve. Prva stvar, ki mi je najti srednjo vrednost, indeks, ki se nahaja na pol poti med min in max polja, ki se še vedno razmišlja. Potem pogledamo vrednosti matrike na tej lokaciji središčem in videli, če je število, ki ga iščemo, je manjša od te tipke. Če je število na tem položaju je manj, potem to pomeni, da je ključ večji od vseh številk levo od tega položaja. Torej lahko rečemo, binarno iskalno funkcijo ponovno vendar tokrat posodabljanje min in max parametre, da se glasi le polovico , ki je večja od ali enaka vrednosti sva pogledala. Po drugi strani pa, če je ključ manjše od števila v sedanji sredini matrike, želimo iti v levo in ignorirati vse številke, ki so večje. Spet pravimo binarno iskanje vendar tokrat z razponom min in max Popravljeno vključiti samo spodnjo polovico. Če je vrednost v trenutni sredini v polju ni niti večja kot niti manjši od ključa, potem mora biti enak ključ. Tako lahko enostavno vrne trenutno kazalo srednjo vrednost, in smo končali. Končno, to preverjanje tu za primer, da se je število dejansko ni v niz številk iščemo. Če se najvišji indeks območju, ki ga iščemo je vedno manj od minimuma, kar pomeni, da smo šli predaleč. Ker se število ni v vnosno polje, vrnemo -1 , ki označuje, da nič ni bilo videti. 

Morda ste opazili, da se za ta algoritem za delo, seznam številk, je treba razvrstiti. Z drugimi besedami, smo lahko našli le 144 dvojiškem iskanje če so vse številke naročil od najnižje do najvišje. Če ne bi bilo tako, ne bi mogli izključiti polovico števil na vsakem koraku. Torej imamo 2 možnosti. Ali lahko vzamemo neurejen seznam in ga rešiti pred dvojiškem iskanje ali pa bomo poskrbeli, da se seznam številk, razvrščenih kot smo Dodajanje številk na njej. Torej, namesto razvrščanja šele takrat, ko bomo morali iskati, zakaj ne hranijo seznam razporejen po vseh časov? 

Eden od načinov, da seznam številk, razvrščenih hkrati pa omogoča 1 dodati ali premakniti številke s tega seznama je z uporabo nekaj, kar ti binarno iskalno drevo. Dvojiško iskalno drevo je podatkovna struktura, ki ima 3 lastnosti. Prvič, levo poddrevo vsakega vozlišča vsebuje samo vrednosti, ki so manjše od ali enaka vrednosti vozlišča. Drugič, desno poddrevo za vozlišče vsebuje le vrednosti, ki so večje od ali enaka vrednosti vozlišča. In končno, tako levi in ​​desni subtrees vseh vozlišč tudi dvojiška iskalna drevesa. Oglejmo si primer z enakimi številkami smo uporabili prej. Za tiste, ki še nikoli niso videli računalništvo drevo pred Naj začnem z vam pove, da računalništvo drevo raste navzdol. Ja, za razliko od dreves ste vajeni, koren drevesa računalništva na vrhu, in listi so na dnu. Vsak malo polje se imenuje vozlišče in vozlišča so med seboj povezani z robovi. Torej je koren tega drevesa je vozlišče vrednost z vrednostjo 13, ki ima 2 otroka vozlišč z vrednostmi 5 in 34. Poddrevo je drevo, ki je nastala samo jih je videti na pododdelku celotnega drevesa. 

Na primer, levo poddrevo od vozlišča 3 je drevo, ki ga ustvarjajo vozlišča 0, 1, 2 in. Torej, če se vrnemo na lastnosti drevo binarno iskanje, vidimo, da je vsako vozlišče v drevesu, skladna z vsemi lastnostmi, in sicer 3, levo poddrevo vsebuje samo vrednosti, ki so manjše ali enake vrednosti vozlišča; pravica poddrevo vseh vozlišč vsebuje samo vrednosti, ki so večje ali enake vrednosti vozlišča in tako levi in ​​desni subtrees vseh vozlišč so tudi iskalna drevesa binarni. Čeprav je to drevo je drugačno, je to veljavno binarno iskalno drevo Za enak nabor številk. Kot Dejstvo je, da obstaja več možnih načinov, ki jih lahko ustvarite veljavno binarno iskalno drevo iz teh številk. No, gremo nazaj na prvi tisti, ki smo jo ustvarili. Torej, kaj lahko naredimo s temi drevesi? No, bomo lahko zelo enostavno najti minimalne in maksimalne vrednosti. Najnižje vrednosti, je na voljo vedno dogaja na levi dokler ni več vozlišč za obisk. Po drugi strani pa, da bi našli največjo 1 preprosto samo pade na desno na vsakem trenutku. 

Iskanje katero koli drugo vrsto, ki ni najnižja ali najvišja je prav tako enostavno. Povejte iščemo številko 89. Mi enostavno preveri vrednost vsakega vozlišča in pojdite na levo ali desno, glede na to, ali je v vozlišču je vrednost manjša ali večja od tisti, ki ga iščemo. Torej, z začetkom ob korenu 13, vidimo, da je 89 več, in tako gremo v desno. Potem bomo videli vozlišča za 34, in spet gremo na desno. 89 je še vedno več kot 55 let, zato smo nadaljevali bomo na desni strani. Nato smo prišli do vozlišča z vrednostjo 144 in pojdite na levo. Glej, glej, 89 je tam. 

Druga stvar, kar lahko naredimo, je izpisal vse številke z izvedbo mora biti zato, prečkanje. Mora biti zato, prečkanje pomeni, da natisnete vse, kar je v levo poddrevo sledi tiskanje vozlišča se in potem sledi tiskanje, vse v pravi poddrevo. Na primer, vzemimo naše najljubše drevo binarno iskanje in tiskanje številk v vrstnem redu razvrščeni. Začnemo pri korenu 13, vendar pred tiskanjem 13 moramo natisniti vse v levo poddrevo. Torej gremo v 5. Še vedno moramo iti globlje navzdol na drevesu, dokler ne najdemo na levi najbolj vozlišče, ki je enaka nič. Po tiskanju nič, gremo nazaj do 1 in natisniti to. Potem gremo v desno poddrevo, kar je 2 in natisniti to. Zdaj, ko smo opravili s tem poddrevo, bomo lahko vrnili do 3 in jo natisnite. Nadaljevanje nazaj, smo natisnili 5 in nato 8. Zdaj, ko smo zaključili celotno levo poddrevo, lahko natisnete 13 in začeli delati na desno poddrevo. Mi hop do 34, vendar pred tiskanjem 34 moramo natisniti svojo levo poddrevo. Tako smo natisniti 21, nato pa pridemo do natisniti 34 in obiščite njegovo desno poddrevo. Od 55 nima levo poddrevo, jo natisnite in nadaljujemo z njegovo desno poddrevo. 144 ima levo poddrevo, zato smo izpisal 89, čemur sledi 144, in na koncu desno najbolj vozlišče 233. Tam ga imate, vse številke so natisnjene v vrstnem redu od najnižje do najvišje. 

Dodajanje nekaj drevesa je relativno neboleč, kot dobro. Vse kar moramo storiti je, da poskrbite, da sledimo 3 dvojiške lastnosti drevesnih iskanja in nato vstavite vrednosti, kjer je prostor. Recimo, želite vstaviti vrednost 7. Ker je 7 manj kot 13, gremo v levo. Ampak to je več kot 5, tako da prečkajo desno. Ker je manj kot 8 in 8 je vozlišče list, dodamo 7 do 8 levi otroka. Voila! Dodali smo nekaj za naše drevo binarno iskanje. 

Če bomo dodali stvari, bolje boste mogli izbrisati stvari, kot dobro. Na žalost za nas, brisanje je malce bolj zapleteno - Ni veliko, ampak samo malo. Obstajajo 3 različne scenarije, ki jih moramo upoštevati Pri brisanju elementov iz binarnih dreves iskanja. Prvič, najlažji primer je, da je element listov vozlišča. V tem primeru smo preprosto izbrisati in iti naprej s naše poslovanje. Povejte nam želite izbrisati 7, ki smo jo pravkar dodali. No, mi preprosto zdi, da ga odstranite, in to je to. Naslednji primer je, če je vozlišče ima samo 1 otroka. Tu lahko izbrišete vozlišče, vendar moramo najprej zagotoviti, povezati poddrevo, ki je zdaj ostalo parentless na matično vozlišča sva se črta. Povejte nam želite izbrisati 3 od našega drevesa. Mi lahko otrok element tega vozla in jo pritrdite na matično vozlišča. V tem primeru smo zdaj pritrditev 1 do 5. Ta deluje brez problema, saj vemo, v skladu z binarno iskalno drevo premoženja, da je vse v levo poddrevo od 3 manj kot 5. Zdaj, ko se je poddrevo 3 poskrbljeno, lahko izbrišete. Tretji in zadnji primer je najbolj zapleten. To je v primeru, ko je vozlišče želimo izbrisati ima 2 otroka. Da bi to storili, moramo najprej najti vozlišče, ki ima naslednjo največjo vrednost, swap 2, in nato izbrišite vozlišče vprašanje. Obvestilo vozlišče, ki ima naslednjo največjo vrednost, ne more imeti 2 otroka sama saj bi njena leva otrok je bolje kandidat za naslednjo, večjo. Zato brisanje vozlišče z 2 otrokoma znaša menjava za 2 vozlišč, , nato pa se črta ravna 1 od 2 zgoraj navedenimi pravili. Na primer, recimo, da želimo izbrisati root vozlišča, 13. Prva stvar, ki mi je, da smo našli naslednje največjo vrednost v drevesu , ki v tem primeru je 21. Nato smo preklopili 2 vozlišč, kar 13 listov in 21 centralna skupina vozlišča. Sedaj lahko preprosto izbrisati 13. 

Kot namiguje že prej, obstaja več možnih načinov, da bi veljavno binarno drevo iskanje. Na žalost za nas, nekateri so slabši od drugih. Na primer, kaj se zgodi, ko gradimo binarno iskalno drevo izločen iz seznama številk? Vse številke so pravkar dodali na desno na vsakem koraku. Ko smo želeli poiskati nekaj, nimamo druge izbire, ampak le, da pogled na desno na vsakem koraku. To ni bolje kot linearni iskanje na vse. Čeprav ne bomo jih pokrijemo tu obstajajo druge, bolj zapletene, podatkovne strukture, da se prepričajte, da se to ne zgodi. Vendar pa je ena preprosta stvar, ki jo lahko storimo, da bi se temu izognili, je na samo naključno shuffle vhodnih vrednosti. To je zelo malo verjetno, da jih Naključje je razvrščen premešan seznam številk. Če bi bilo to res, igralnice, ne bi ostala v poslu dolgo. 

Tam ga imate. Zdaj vem binarno iskanje in iskalna drevesa binarnih. Jaz sem Patrick Schmid, in to je CS50. [CS50.TV] Eden od očiten način bi bil, da skeniranje seznam od ... [beep] ... Število točk ... ja [Smeh] Objavite ... vozlišča 234 ... augh. >> Bravo! To je bilo -