[Powered by Google Translate] [Dvejetainis Paieška] [Patrick Schmid - Harvardo universiteto] [Tai CS50. - CS50.TV] 

Jei aš davė jums Disney simbolių vardai abėcėlinį sąrašą ir paprašė rasti Mickey Mouse, kaip jums eiti apie tai daryti? Vienas akivaizdus būdas būtų nuskaityti nuo pradžios ir patikrinkite kiekvieną pavadinimą, kad pamatytumėte, jei tai Mickey. Bet, kaip jūs skaitote ALADDIN, Alice, Arielis, ir tt, jūs greitai suprasite, kad pradedant nuo sąrašo priekyje nebuvo gera idėja. Gerai, galbūt jums reikia pradėti darbo atgal iš sąrašo pabaigoje. Dabar jūs skaityti Tarzan, Stitch, Snieguolė, ir taip toliau. Vis dėlto, tai neatrodo, kad geriausias būdas eiti apie tai. 

Na, dar vienas būdas, kad galite eiti apie tai daryti yra bandyti susiaurinti pavadinimų sąrašas, kad jūs turite pažvelgti. , Nes jūs žinote, kad jie yra abėcėlės tvarka, galite tiesiog pažvelgti pavadinimų sąrašo viduryje ir patikrinkite, ar Peliukas Mikis yra prieš arba po šiuo pavadinimu. Žiūri į antrąjį stulpelį, pavardės jums reikia suprasti, kad M Mickey ateina po J Jasmine, todėl jūs tiesiog ignoruoti sąraše pirmąją pusę. Tada jūs tikriausiai pažvelgti paskutinio stulpelio viršuje ir pamatysite, kad jis prasideda Rapunzel. Mickey ateina prieš Rapunzel, atrodo, kad mes negali ignoruoti paskutinį stulpelį taip pat. Tęstinis paieškos strategijos, jūs greitai pamatyti, kad Mickey pirmoje pusėje likusios pavadinimų sąrašą ir pagaliau rasti Mickey slepiasi tarp "Merlin" ir Minnie. 

Ką tik padarė, buvo iš esmės dvejetainis paieškos. Kadangi šis pavadinimas reiškia, ji atlieka savo Searching strategijos dvejetainis medžiagos. Ką tai reiškia? Na, atsižvelgiant išdėstyti elementai sąrašas, dvejetainis paieškos algoritmas leidžia dvejetainis sprendimą - kairę arba į dešinę didesnis arba mažesnis, nei, pagal abėcėlę prieš arba po - kiekviename taške. Dabar, mes turime vardą, kad eina su šios paieškos algoritmas, leiskite pažvelgti į kitą, pavyzdžiui, bet šį kartą su rūšiuotų numerių sąrašą. Pasakykite, mes ieškome skaičius 144 šioje rūšiuotų numerių sąrašą. Tiesiog kaip ir anksčiau, mes rasti numerį, kad viduryje - , kuris šiuo atveju yra 13, ir pamatyti, jei 144 yra didesnis arba mažesnis nei 13. Kadangi tai yra aiškiai didesnis nei 13, mes galime ignoruoti viską, kas yra 13 ar mažiau ir tiesiog sutelkti dėmesį į kitą pusę. Kadangi dabar mes turime net jų pozicijų skaičių į kairę, mes tiesiog pasirinkti skaičių, kuris yra beveik viduryje. Šiuo atveju mes pasirinkti 55. Mes galėjo taip pat lengvai, pasirinktas 89. Gerai. Vėlgi, 144 yra didesnis nei 55, todėl mes einame į dešinę. Laimei mums, kitas vidutinio numeris yra 144, vienas, mes ieškome. Taigi, siekiant rasti 144 Dvejetainė paieška, mes galime jį rasti tik 3 žingsniai. Jei būtume čia naudojamas linijinis paiešką, jis ėmėsi 12 veiksmus. Tiesą sakant, nes tai paieškos metodas puselės pozicijų skaičių ji turi atrodyti ne kiekviename žingsnyje, ji ras elementą, jis ieško apie žurnalą elementų sąrašą. Dabar, kad mes matėme 2 pavyzdžius, galime pažvelgti kai rekursinis funkcija, kuri įgyvendina Dvejetainė paieška Pseudocode. Pradėdami nuo viršaus, matome, kad turime rasti funkciją, kuri trunka 4 argumentus: raktas, masyvas, min ir max. Svarbiausia yra skaičius, kad mes ieškome, 144 ankstesniame pavyzdyje pan. Masyvas yra numerių sąrašą, kad mes ieškome. Min ir max yra minimalūs ir maksimalūs pozicijas indeksai , kad mes šiuo metu ieško. Taigi, kai mes pradedame, min bus lygus nuliui, ir max bus maksimalus masyvo indeksas. Kaip mes susiaurinti paiešką, mes atnaujinsime MIN ir MAX būti tik asortimentą, kad mes vis dar ieškome. 

Leiskite pereiti prie įdomiausia dalis. Pirmas dalykas, ką mes darome, yra rasti įpusėjo, indeksas, kuris yra pusiaukelėje tarp MIN ir MAX masyvo, kad mes vis dar svarsto. Tada mes pažvelgti iš masyvo vertę tuo Midpoint vietą ir pamatyti, jei skaičius yra mažesnis nei to mygtuko, kad mes ieškome. Jei toje vietoje yra mažiau, tai reiškia, raktas yra didesnis nei visos tos pozicijos kairėje numerių. Taigi, mes galime vėl skambinti dvejetainis paieškos funkcija, bet šį kartą atnaujinti MIN ir MAX parametrus skaityti tik 1/2 , kuris yra didesnis nei arba lygus mes tiesiog pažvelgė vertės. Kita vertus, jei raktas yra mažesnis nei esant dabartiniam Mediana masyvo, mes norime eiti į kairę ir ignoruoti visus skaičius, kurios yra didesnės. Vėlgi, mes vadiname Dvejetainė paieška, bet šį kartą su MIN ir MAX Atnaujinta diapazone įtraukti tik apatinėje. , Jei esant dabartiniam Mediana masyve vertė nėra nei nei didesnis nei mažesnis nei rakto, tada ji turi būti lygi iki rakto. Taigi, mes galime tiesiog grįžti esamą Midpoint indeksą, ir baigsime. Galiausiai, šis tikrinimas turi čia yra atveju, kad numeris nėra faktiškai Ieškome skaičių masyvas. Jei maksimali asortimentą, kad mes ieškome indeksas yra vis mažiau ir mažiau nei minimalus, o tai reiškia, kad mes per toli. Kadangi nebuvo įvesties masyvo, mes grįžti -1 rodo, kad nieko buvo rasta. 

Galbūt jūs pastebėjote, kad šis algoritmas dirbti, numerių sąrašą turi būti rūšiuojami. Kitaip tariant, mes galime rasti tik 144 Dvejetainė paieška jei visi numeriai yra rūšiuojami nuo žemiausios iki aukščiausios. Jei tai ne tas atvejis, mes negalėtų išskirti pusę skaičių kiekviename žingsnyje. Taigi, mes turime 2 variantai. Arba mes galime imtis nerūšiuotų sąrašą ir rūšiuoti jį prieš naudojant Dvejetainė paieška ar mes galime įsitikinti, kad numerių sąrašas surūšiuotas kaip mes pridėti numerius. Taigi, vietoj to rūšiavimas, tik tada, kai mes turime ieškoti, kodėl gi ne išlaikyti visais laikais sąrašas, surūšiuotas? 

Surūšiuoti vienas būdas išlaikyti numerių sąrašą, ir tuo pat metu leidžiant pridėti, arba perkelti numerius iš šio sąrašo naudojant kažką vadinama dvejetainis paieškos medis. Dvejetainis paieškos medis yra duomenų struktūra, kuri turi 3 savybes. Pirma, bet kokio mazgo šaka kairėje yra tik tas vertybes, kurios yra mažiau nei arba lygus mazgas vertės. Antra, teisė šaka mazgas yra tik vertybes, kurios yra didesnės nei arba lygus mazgas vertės. Ir, pagaliau, tiek į kairę ir dešinę subtrees visų mazgų taip pat yra dvejetainiai paieškos medžiai. Pažvelkime į pavyzdį pačiais numeriais, mes naudojamas anksčiau. Tiems iš jūsų, kurie niekada nematė kompiuteris mokslas medis prieš, leiskite man pradėti, sakau, kad kompiuterių mokslas medis auga į apačią. Taip, skirtingai nei medžių esate įpratę, informatikos medžio šaknis yra viršuje, ir lapai yra apačioje. Kiekviena maža dėžutė yra vadinama mazgas, ir mazgai yra sujungti vienas su kitu kraštais. Taigi šio medžio šaknis yra mazgas, kurių vertė 13 vertė, kuris turi 2 vaikus mazgai su vertėmis, 5 ir 34. Šaka yra medis, kuris susidaro tiesiog žiūri visą medžio poskirsnyje. 

Pavyzdžiui, kairėje šaka mazgo 3 medis sukurtas mazgų 0, 1, ir 2. Taigi, jei mes grįžti į dvejetainis paieškos medis savybių, matome, kad kiekvienas medžio mazgas atitinka visus 3 savybės, ty, kairėje šaka yra tik vertybes, kurios yra mažesnė arba lygi mazgas vertės; teisė šaka visų mazgų yra tik vertybes, kurios yra didesnis nei arba lygus mazgas vertės ir kairės ir dešinės subtrees visų mazgų, taip pat yra dvejetainiai paieškos medžiai. Nors šis medis atrodo kitaip, tai leistinas dvejetainis paieškos medis už tą patį skaičių rinkinio. Tiesą sakant, yra daug galimų būdų, kad jūs galite sukurti galioja dvejetainis paieškos medis iš šių numerių. Na, grįžkime į pirmąjį, mes sukūrėme. Taigi, ką mes galime padaryti su šių medžių? Na, mes galime labai paprastai rasti minimalūs ir maksimalūs dydžiai. Mažiausios vertės galima rasti visada bus į kairę kol yra ne daugiau mazgų aplankyti. Priešingai, gauti maksimalų tiesiog tiesiog krinta į dešinę kiekvieną kartą. 

Apie bet kokį kitą numerį, kad nėra minimalus arba maksimalus yra lygiai taip pat lengva. Pasakykite, mes ieškome skaičius 89. Mes tiesiog patikrinti kiekvieno mazgo reikšmę ir eiti į kairę arba į dešinę, priklausomai nuo to, ar mazgas vertė yra mažesnė arba didesnė už vienas, mes ieškome. Taigi, pradedant nuo 13 metų šaknis, mes matome, kad 89 yra didesnis, ir taip mes einame į dešinę. Tada mes matome, kad už 34 mazgas, vėl eina į dešinę. 89 vis dar yra didesnis nei 55, todėl mes ir toliau ketiname į dešinę. Mes tada sugalvoti su 144 vertės mazgas ir eiti į kairę. Štai ir štai, 89 yra teisus ten. 

Kitas dalykas, kad mes galime padaryti spausdinti visus numerius atlikti Inorder apeiti. Inorder Sankryþos spausdinti viską į kairę šaka spausdinimo mazgas save , o po to spausdinti viską iš teisė šaka. Pavyzdžiui, galime imtis mūsų mėgstamiausia dvejetainis paieškos medis ir atsispausdinti numerius rūšiuotų tvarka. Mes pradedame nuo 13 metų šaknis, bet 13 prieš spausdinant turime atsispausdinti viskas į kairę šaka. Taigi mes einame iki 5. Mes vis dar turime gilintis į medį, kol randame kairę pačią mazgas, kuris yra lygus nuliui. Po spausdinimo nulio, mes grįžti iki 1 ir atspausdinti, kad iš. Tada mes einame į dešinę šaka, kuri yra 2, ir atspausdinti, kad iš. Dabar, kai mes su šaka, galime grįžti į 3 ir atsispausdinti. Ir toliau atgal, mes spausdinti 5 ir 8. Dabar, kad mes užbaigėme visą paliko šaka, mes galime atspausdinti iš 13 ir pradėti dirbti dėl teisės šaka. Mes hop iki 34, bet 34 prieš spausdinant mes turime atsispausdinti jos kairysis šaka. Taigi, mes spausdinti iš 21, tada mes gauname atsispausdinti 34 ir aplankyti savo teise šaka. Nuo 55 neturi kairėje šaka, spausdinti, ir toliau savo teisės šaka. 144 yra kairėje šaka, tad ir išspausdinti 89, 144, ir, galiausiai, dešiniuoju pelės labiausiai mazgas 233. Jūs turite jį, visi numeriai spausdinami, kad nuo žemiausios iki aukščiausios. 

Įrašyta kažką į medį, taip pat yra gana neskausmingas. Visi mes turime padaryti, tai įsitikinkite, kad mes laikomės 3 dvejetainis paieškos medis savybes ir įdėkite verte tuomet, kai yra vietos. Tarkime, mes norime įterpti 7 vertę. Nuo 7 yra mažesnis nei 13, mes einame į kairę. Bet tai didesnis nei 5, todėl mes feed į dešinę. Kadangi tai yra mažiau kaip 8 ir 8 lapų mazgas, kuriuos mes įtraukiame 7 į kairę vaiką 8. Voila! Mes pridėjome numerį į mūsų dvejetainis paieškos medis. 

Jei mes galime pridėti dalykų, mes geriau būtų galima pašalinti dalykų, taip pat. Deja, mums, išbraukiant yra šiek tiek sudėtingesnis - nėra daug, bet tik šiek tiek. Yra 3 skirtingi scenarijai, kad mes turime apsvarstyti ištrinti elementus iš dvejetainiai paieškos medžiai. Pirmasis, paprasčiausias atvejis, kad elementas yra lapų mazgas. Šiuo atveju, mes tiesiog ištrinti jį ir eiti su mūsų verslo. Tarkime, mes norime ištrinti, kad mes ką tik įdėjote 7. Na, mes tiesiog rasti, ją pašalinkite, ir viskas. Kitas atvejis, jei mazgas turi tik 1 vaikas. Čia mes galime ištrinti mazgas, tačiau mes pirmiausia turite įsitikinti, kad prijungti šaka, kad dabar yra paliktas tėvų tik mazgas tėvų mes tiesiog ištrinti. Tarkime, mes norime ištrinti 3 iš mūsų medžio. Mes priimame vaikų to mazgo elementas ir pridėti jį prie tėvų mazgo. Šiuo atveju, mes dabar pritvirtinti 1 į 5. Tai veikia be problemų, nes mes žinome, pagal dvejetainis paieškos medis turto, kad viskas į kairę šaka iš 3 mažesnis nei 5. Dabar, kad 3 pomedžio pasirūpinta, mes jį ištrinti. Trečiasis ir paskutinis atvejis yra sudėtingas. Tai tas atvejis, kai norime ištrinti mazgas turi 2 vaikus. Siekiant tai padaryti, mes pirmiausia turi rasti mazgas, kuris turi kitą didžiausią reikšmę, apsikeitimo dviejų, ir tada ištrinti atitinkamą mazgas. Atkreipkite dėmesį mazgas, turi kitas didžiausia vertė negali turėti 2 vaikus, pati nes jos kairysis vaikas būtų geresnis kandidatas Kitas didžiausias. Todėl, ištrinti mazgas su 2 vaikais Swapping 2 mazgų, ir tada ištrinti perkrauta 1 iš 2 minėtų taisyklių. Pavyzdžiui, tarkime, kad mes norime ištrinti šaknų mazgas, 13. Pirmas dalykas, ką mes darome, yra rasti kitą didžiausią reikšmę medyje , kuris, šiuo atveju, yra 21. Mes tada apsikeitimo 2 mazgus, 13 lapų ir 21 Centrinė grupė mazgas. Dabar mes galime tiesiog ištrinti 13. 

Kaip užsiminiau anksčiau, yra daug galimų būdų, kaip padaryti galiojantį dvejetainis paieškos medis. Deja, mums, kai yra blogiau nei kiti. Pavyzdžiui, kas atsitinka, kai mes sukurti dvejetainis paieškos medis rūšiuotų sąrašą skaičius? Visi skaičiai yra tik įdėjote į dešinę kiekviename žingsnyje. Kai mes norime ieškoti skaičiaus, mes neturime kito pasirinkimo, tačiau tik pažvelgti į dešinėje kiekviename žingsnyje. Tai ne geriau nei tiesiškai paieškoje. Nors mes padengti juos čia, yra ir kitų, vis sudėtingesni, duomenų struktūros, įsitikinkite, kad tai neįvyks. Tačiau vienas paprastas dalykas, kad galima padaryti, kad būtų išvengta šios tiesiog atsitiktinai shuffle įvesties reikšmių. Tai labai mažai tikėtina, kad atsitiktine atsitiktinai išmaišytos numerių sąrašas yra rūšiuojama. Jei taip nutiktų, kazino nebūtų likti versle ilgai. 

Čia jūs turite jį. Dabar jūs žinote apie dvejetainis paieškos ir dvejetainiai paieškos medžiai. Aš esu Patrick Schmid, ir tai yra CS50. [CS50.TV] Vienas akivaizdus būdas būtų nuskaityti sąrašą iš ... [pyptelėjimas] ... Elementų skaičius ... yep [Juokiasi] ... Po 234 ... augh mazgas. >> Valio! Tai buvo