[Powered by Google Translate] [Binary Search] [Patrick Schmid - Harvardin yliopisto] [Tämä on CS50. - CS50.TV] 

Jos antaisin luettelon Disney aakkosjärjestyksessä ja pyysi sinua löytämään Mikki Hiiri, miten mennä noin tehdä tästä? Yksi ilmeinen tapa olisi skannata luettelon alusta ja tarkista jokaista nimeä, onko se Mikki. Mutta kun luet Aladdin, Alice, Ariel, ja niin edelleen, voit nopeasti, että alkaen edessä luettelon ei ollut hyvä idea. Okei, ehkä sinun pitäisi aloittaa työskentely taaksepäin luettelon loppuun. Nyt voit lukea Tarzan, Stitch, Lumikki, ja niin edelleen. Silti tämä ei tunnu paras tapa edetä asiassa. 

No, toinen tapa että voisit mennä noin tehdä tämä on yrittää kaventaa nimiluettelo, että sinun täytyy katsoa. Koska tiedät, että ne ovat aakkosjärjestyksessä, voisit katsokaa nimet keskellä luettelon ja tarkista, Mikki Hiiri on ennen tai jälkeen tämän nimen. Tarkasteltaessa sukunimi toisessa sarakkeessa sinun ymmärtää, että M Mickey jälkeen tulee J Jasmine, niin olisit yksinkertaisesti sivuuttaa alkupuoliskolla luettelon. Sitten sinun todennäköisesti näyttää yläreunassa viimeisen sarakkeen ja nähdä, että se alkaa Rapunzel. Mikki tulee ennen Tähkäpää, näyttää voimme jättää viimeinen sarake samoin. Jatkuvat hakustrategia, voit nopeasti nähdä, että Mikki on alkupuoliskolla jäljellä nimiluettelon ja lopulta löytää Mickey piilossa välillä Merlin ja Minnie. 

Mitä teit oli pohjimmiltaan binäärihakupuu. Koska tämä nimi kertoo, se suorittaa haun strategiaa binary asiassa. Mitä tämä tarkoittaa? No, annetaan luettelo lajiteltuja, binäärihakupuu algoritmi tekee binäärisen päätöksen - vasemmalle tai oikealle, suurempi tai pienempi kuin, aakkosellisesti ennen tai jälkeen - kussakin pisteessä. Nyt meillä on nimi, joka menee yhdessä tämän hakualgoritmi, Katsotaanpa toinen esimerkki, mutta tällä kertaa listan lajiteltu numeroita. Sano etsimme numero 144 tässä luettelossa lajiteltu numeroita. Aivan kuten ennen, huomaamme numero, joka on keskellä - joka tässä tapauksessa on 13 - ja nähdä, jos 144 on suurempi tai pienempi kuin 13. Koska se on selvästi suurempi kuin 13, voimme sivuuttaa kaikki, mikä on 13 tai vähemmän ja vain keskittyä jäljellä puoli. Koska meillä on parillinen määrä kohteita jäljellä, me yksinkertaisesti valita numeron, joka on lähellä keskellä. Tässä tapauksessa me valitsemme 55. Olisimme voineet yhtä hyvin valittu 89. Okei. Jälleen 144 on suurempi kuin 55, joten menemme oikealle. Onneksi meille seuraavaksi keskimmäinen numero on 144, yksi etsimme. Joten jotta löydettäisiin 144 käyttäen binäärihakupuu, pystymme löytämään sen vain 3 vaihetta. Jos olisimme käyttäneet lineaarista hakua täällä, se olisi vienyt meidät 12 askelta. Koska itse asiassa, koska tämä hakumenetelmä puolittaa kappalemäärä se on tutkittava kussakin vaiheessa, se löytää kohteen se hakee noin loki kohteiden määrä luettelossa. Nyt kun olemme nähneet 2 esimerkkejä, katsotaanpa katsomaan Joissakin pseudokoodi rekursiivinen funktio, joka toteuttaa binäärihakupuu. Aloita ylhäältä, näemme, että meidän on löydettävä funktio, joka kestää 4 argumentit: avain, array, min ja max. Tärkeintä on numero että etsimme, niin 144 edellisessä esimerkissä. Array on luettelo numeroista että etsimme. Min ja Max ovat indeksit minimi ja maksimi kantoja että olemme parhaillaan osoitteessa. Joten kun aloitamme, min on nolla, ja max on suurin indeksi jono. Kuten rajata hakua alas, päivitämme min ja max olla vain välillä, että etsimme edelleen sisään 

Katsotaanpa siirtyä mielenkiintoinen osa ensin. Ensimmäinen asia mitä teemme on löytää midpoint, indeksi on välissä min ja max array että olemme vielä harkitsevat. Sitten katsomme arvo array siinä keskipisteessä paikassa ja katso jos numero etsimme on pienempi avain. Jos numero tuossa asemassa on vähemmän, sitten se tarkoittaa, että avain on suurempi kuin kaikki numerot vasemmalla puolella, että kanta. Joten voimme kutsua binary hakutoiminto uudestaan, mutta tällä kertaa päivittää min ja max parametrit lukea vain puoli , joka on suurempi tai yhtä suuri kuin arvo me vain tarkasteltiin. Toisaalta, jos avain on pienempi kuin numero nykyisellä keskikohdassa array, haluamme mennä vasemmalle ja sivuuttaa kaikki luvut, jotka ovat suurempia. Jälleen kutsumme binäärihakupuu mutta tällä kertaa valikoima min ja max päivitettyjä sisällyttää vain alempi puoli. Jos arvo on nykyisen keskikohdassa pakassa ei ole suurempi kuin eikä pienempi kuin näppäintä, niin se on yhtä suuri kuin avaimen. Näin voimme yksinkertaisesti palata nykyinen keskipiste indeksi, ja olemme tehneet. Lopuksi, tämä tarkastus tässä, on siinä tapauksessa, että numero ei oikeastaan ​​joukko numeroita etsimme. Jos suurin indeksi alue että etsimme on aina pienempi kuin minimi, se tarkoittaa, että olemme menneet liian pitkälle. Koska määrä ei ollut tulo array, palaamme -1 osoittaa, että mitään ei löytynyt. 

Olet ehkä huomannut, että tämä algoritmi toimii, luettelo numeroista on lajiteltu. Toisin sanoen, voimme vain löytää 144 käyttäen binäärihakupuu jos kaikki numerot tilataan alimmasta ylimpään. Jos näin ei olisi, emme voi sulkea pois puolet numerot jokaisessa vaiheessa. Eli meillä on 2 vaihtoehtoa. Joko voimme lajittelemattomana luetteloa ja lajitella se ennen binäärihakupuu, tai voimme varmistaa, että luettelo numeroista on järjestetty niin lisäämme numeroita sitä. Niinpä sen sijaan, lajittelu juuri kun meidän täytyy etsiä, miksi ei pidä luetteloa lajitellaan aina? 

Yksi tapa pitää luetteloa numeroiden järjestetty samalla mahdollistaa yksi lisätä tai siirtää numeroita listalta on käyttää jotain kutsutaan binäärihakupuu. Binäärihakupuu on tietorakenne, joka on 3 ominaisuudet. Ensinnäkin vasemman alipuun tahansa solmu sisältää vain arvot, jotka ovat vähemmän kuin tai yhtä suuri kuin solmun arvo. Toiseksi, oikea alipuun solmun sisältää vain arvot, jotka ovat suurempia kuin tai yhtä suuri kuin solmun arvo. Ja lopuksi, sekä vasen ja oikea alipuut kaikkien solmujen Myös binäärihakupuu puita. Katsotaanpa esimerkiksi samat numerot käytimme aikaisemmin. Niille teistä, jotka eivät ole koskaan nähneet tietojenkäsittelytieteen puu ennen, haluaisin aloittaa kertomalla, että tietojenkäsittelytieteen puu kasvaa alaspäin. Kyllä, toisin kuin puut olet tottunut, juuri tietojenkäsittelytieteen puu on ylhäällä, ja lehdet ovat alareunassa. Jokainen pieni laatikko kutsutaan solmu, ja solmut on yhdistetty toisiinsa reunoista. Niinpä juuri tämä puu on solmu arvo arvo 13, joka on 2 lasta solmujen arvojen 5 ja 34. Alipuu on puu, joka on muodostettu vain katsomalla momentti koko puun. 

Esimerkiksi vasemman alipuun solmun 3 on puun luoman solmut 0, 1, ja 2. Joten, jos menemme takaisin ominaisuuksien binäärihakupuu, näemme, että jokainen solmu puussa täyttää kaikki 3 ominaisuuksia, nimittäin, vasemman alipuun sisältää vain arvot, jotka ovat pienempiä tai yhtä suuri kuin solmun arvo; oikea alipuu kaikkien solmujen sisältää vain arvoja, jotka ovat suurempi tai yhtä suuri kuin solmun arvo; ja sekä vasen alipuut kaikkien solmujen ovat myös binäärihakupuu puita. Vaikka tämä puu näyttää erilaiselta, tämä on voimassa binäärihakupuu sillä samoja numeroita. Koska itse asiassa, on olemassa monia mahdollisia tapoja, joilla voit luoda voimassa binäärihakupuu näistä numeroita. No, mennään takaisin ensimmäinen loimme. Mitä voimme tehdä näitä puita? No, voimme hyvin yksinkertaisesti löytää minimi-ja maksimiarvot. Minimiarvoja löytyy aina menossa vasemmalle kunnes ei enää ole solmuja käydä. Kääntäen, löytää enintään yksi yksinkertaisesti vain menee alas oikealle kullakin hetkellä. 

Löytää jokin muu numero, joka ei ole pienin tai suurin on aivan yhtä helppoa. Sano etsimme numero 89. Me yksinkertaisesti tarkistaa arvo kunkin solmun ja siirry vasemmalle tai oikealle, riippuen siitä, onko solmun arvo on pienempi kuin tai suurempi kuin yksi etsimme. Joten, alkaa juureen 13, huomaamme, että 89 on suurempi, joten menemme oikealle. Sitten näemme solmu 34, ja jälleen menemme oikealle. 89 on edelleen suurempi kuin 55, joten jatkamme menossa oikealle. Sitten keksiä solmu arvo 144 ja mene vasemmalle. Kas kummaa, 89 on oikeassa. 

Toinen asia, että voimme tehdä, on tulostaa kaikki numerot suorittamalla monena läpikäyminen. Monena traversal tarkoittaa tulostaa kaiken ulos vasemman alipuun seuraa painaminen solmu itse ja sitten seuraa painaminen kaiken ulos oikealla alipuu. Esimerkiksi sallikaa meidän suosikki binäärihakupuu ja tulostaa numerot lajiteltu järjestyksessä. Aloitamme juureen 13, mutta ennen tulostusta 13 meidän täytyy tulostaa kaikki vasemman alipuun. Joten menemme 5. Meillä on vielä mennä syvemmälle puuhun kunnes löydämme äärimmäisenä vasemmalla solmu, joka on nolla. Tulostuksen jälkeen nolla, menemme takaisin ylös 1 ja tulostaa se ulos. Sitten menemme oikeaan alipuun, joka on 2, ja tulosta se ulos. Nyt olemme tehneet, että alipuu, voimme mennä takaisin ylös 3 ja tulostaa sen. Jatkuvat takaisin ylös, me painamme 5 ja sitten 8. Nyt olemme saattaneet koko vasen alipuu, Voimme tulostaa 13 ja alkaa työstää oikealla alipuu. Meidän hop alas 34, mutta ennen tulostusta 34 joudumme tulostaa sen vasemman alipuun. Joten me tulostaa 21, sitten pääsemme tulostaa 34 ja käydä oikeutta alipuu. Koska 55 ei vasemman alipuun, me tulostaa sen ja jatka sen oikealla alipuu. 144 on vasen alipuu, ja niin me tulostaa 89, jota seuraa 144, ja lopuksi äärimmäisenä oikealla solmun 233. Siellä on se, kaikki numerot tulostetaan järjestyksessä pienimmästä suurimpaan. 

Lisäämällä jotain puu on suhteellisen kivuttomasti samoin. Meidän täytyy vain varmistaa, että me noudatamme 3 binäärihakupuu ominaisuudet ja aseta arvo, jossa on tilaa. Sanotaan haluamme lisätä arvoa 7. Koska 7 on alle 13, menemme vasemmalle. Mutta se on suurempi kuin 5, joten etene oikealle. Koska se on pienempi kuin 8 ja 8 on lehtisolmu, lisäämme 7 vasemmalla puolella lapsi 8. Voila! Olemme lisänneet useita meidän binäärihakupuu. 

Jos voimme lisätä asioita, voimme paremmin pystyä poistamaan asioita. Valitettavasti meille, poistaminen on vähän monimutkaisempi - ei paljon, mutta vain vähän. On 3 eri skenaarioita, jotka meidän on harkittava kun poistat elementtejä binäärihakupuu puista. Ensinnäkin Helpoin tapaus on, että elementti on lehtisolmu. Tässä tapauksessa me yksinkertaisesti poistaa se ja mennä meidän liiketoimintaan. Sano haluamme poistaa 7 että lisäsimme vain. No, me yksinkertaisesti löydä sitä, poista se, ja se on siinä. Seuraava tapaus on, jos solmulla on vain 1 lapsi. Täällä voimme poistaa solmun, mutta meidän on ensin varmistettava yhdistää alipuun joka on nyt jätetty parentless sen vanhemman solmun me juuri poistettu. Sano haluamme poistaa 3 meidän puusta. Otamme lapsi osa tätä solmu ja kiinnitä se vanhempi solmun. Tässä tapauksessa olemme nyt liittää 1 5. Tämä toimii ilman ongelmia, koska tiedämme, mukaan binäärihakupuu omaisuutta, että kaikki vasemman alipuun 3 oli alle 5. Nyt 3: n alipuu on hoidettu, voimme poistaa sen. Kolmas ja viimeinen asia on kaikkein monimutkainen. Näin on silloin, kun solmu halutaan poistaa on 2 lasta. Voidakseen tehdä tämän, meidän on ensin löydettävä solmuun että on seuraavaksi suurin arvo, vaihtaa kaksi, ja sitten poistaa kyseisen solmun. Huomaa solmu, joka on seuraavaksi suurin arvo voi olla 2 lasta itseään koska sen vasen lapsi olisi parempi ehdokas seuraavaksi suurin. Siksi poistamalla solmu 2 lasta merkitsee vaihtamisen 2 solmua, ja poistamalla hoitaa 1 2 mainittuja sääntöjä. Esimerkiksi sanokaamme haluamme poistaa juurisolmu 13. Ensimmäinen asia mitä teemme on löydämme seuraavaksi suurimman arvon puussa , joka tässä tapauksessa on 21. Sitten vaihtaa 2 solmua, joten 13 lehtiä ja 21 Keski-ryhmän solmu. Nyt voimme yksinkertaisesti poistaa 13. 

Kuten on viitattu aikaisemmin, on olemassa monia mahdollisia tapoja tehdä voimassa binäärihakupuu. Valitettavasti meille, jotkut ovat pahempia kuin toiset. Esimerkiksi, mitä tapahtuu, kun me rakennamme binäärihakupuu alkaen järjestetty numeroiden luettelosta? Kaikki numerot ovat vain lisätään oikeaan jokaisessa vaiheessa. Kun haluamme etsiä numero, meillä ei ole muuta vaihtoehtoa kuin vain katsoa oikealla jokaisessa vaiheessa. Tämä ei ole parempi kuin lineaarinen haku lainkaan. Vaikka emme kata niitä täällä on muitakin, monimutkaisempia, tietorakenteita, varmista, että tämä ei tapahdu. Kuitenkin yksi yksinkertainen asia, joka voidaan tehdä välttää tämä on vain satunnaisesti shuffle lähtöarvot. On erittäin epätodennäköistä, että Sattumiin sekoitetaan listan numeroita lajitellaan. Jos näin olisi, kasinot eivät jatkamaan toimintaansa pitkään. 

Siinäpä se. Olet nyt tietää binary etsimistä ja binäärihakupuu puita. Olen Patrick Schmid, ja tämä on CS50. [CS50.TV] Yksi ilmeinen tapa olisi skannata luettelon ... [piip] ... Kappalemäärä ... jep [Nauraa] ... Post solmu 234 ... augh. >> Yay! , Joka oli -