[Powered by Google Translate] [Chwilio Binary] [Patrick Schmid - Harvard University] [Mae hyn yn CS50. - CS50.TV] 

Os byddaf yn rhoi i chi restr o enwau cymeriad Disney yn nhrefn yr wyddor ac yn gofyn i chi ddod o hyd i Mickey Mouse, sut fyddech chi'n mynd ati i wneud hyn? Un ffordd amlwg fyddai i sganio y rhestr o'r cychwyn ac yn gwirio pob enw i weld os yw'n Mickey. Ond wrth i chi ddarllen Aladdin, Alice, Ariel, ac yn y blaen, byddwch yn gyflym yn sylweddoli nad yw dechrau ar flaen y rhestr yn syniad da. Iawn, efallai y dylech ddechrau gweithio tuag yn ôl o ddiwedd y rhestr. Nawr eich bod yn darllen Tarzan, Pwyth, Snow White, ac yn y blaen. Still, nid yw hyn yn ymddangos fel y ffordd orau o fynd o'i chwmpas hi. 

Wel, mewn ffordd arall y gallech fynd ati i wneud hyn yw i geisio cyfyngu'r i lawr y rhestr o enwau sydd yn rhaid i chi edrych ar. Gan eich bod yn gwybod eu bod yn nhrefn yr wyddor, fe allech chi jyst yn edrych ar yr enwau yn y nghanol y rhestr a gwirio os yw Mickey Mouse yn cyn neu ar ôl yr enw hwn. O edrych ar yr enw olaf yn yr ail golofn byddech yn sylweddoli bod M am Mickey dod ar ôl J am Jasmine, felly byddech yn anwybyddu'r hanner cyntaf y rhestr. Yna mae'n debyg y byddech yn edrych ar frig y golofn olaf a gweld ei fod yn dechrau gyda Rapunzel. Mickey dod cyn Rapunzel; edrych fel y gallwn anwybyddu'r golofn olaf yn ogystal. Gan barhau â'r strategaeth chwilio, byddwch yn gyflym yn gweld bod Mickey yn hanner cyntaf y rhestr sy'n weddill o enwau ac yn olaf dod o hyd i Mickey cuddio rhwng Merlin a Minnie. 

Hyn yr ydych yn unig oedd yn chwilio yn y bôn deuaidd. Gan fod y enw'n awgrymu, mae'n cyflawni ei strategaeth chwilio mewn mater deuaidd. Beth yw ystyr hyn? Wel, o ystyried rhestr o eitemau didoli, y deuaidd algorithm chwilio yn gwneud penderfyniad deuaidd - chwith neu i'r dde, yn fwy na neu'n llai na, yn nhrefn yr wyddor cyn neu ar ôl - ar bob pwynt. Nawr bod gennym enw sy'n mynd ynghyd â hyn algorithm chwilio, gadewch i ni edrych ar enghraifft arall, ond y tro hwn gyda rhestr o rifau didoli. Dweud rydym yn chwilio am y rhif 144 yn y rhestr hon o rifau didoli. Yn union fel o'r blaen, rydym yn dod o hyd i'r rhif sydd yn y canol - sydd yn yr achos hwn yn 13 - a gweld os 144 yn fwy na neu'n llai na 13. Ers mae'n amlwg yn fwy na 13, gallwn anwybyddu popeth sy'n 13 neu lai a dim ond yn canolbwyntio ar yr hanner arall. Ers i ni yn awr yn cael nifer hyd yn oed o eitemau ar ôl, rydym yn syml ddewis rhif sy'n agos at y canol. Yn yr achos hwn rydym yn dewis 55. Gallem fod wedi yr un mor hawdd dewis 89. Iawn. Unwaith eto, 144 yn fwy na 55, felly rydym yn mynd i'r dde. Yn ffodus i ni, y rhif canol nesaf yw 144, un yr ydym yn chwilio amdano. Felly, er mwyn dod o hyd i 144 gan ddefnyddio chwiliad deuaidd, rydym yn gallu ddod o hyd iddo mewn dim ond 3 camau. Os ydym wedi defnyddio chwiliad llinol yma, byddai wedi cymryd 12 cam i ni. Fel mater o ffaith, gan fod y dull hwn chwilio yn haneru'r nifer o eitemau mae'n rhaid iddo edrych ar ar bob cam, bydd yn dod o hyd i'r eitem ei fod yn chwilio am mewn tua y log y nifer o eitemau yn y rhestr. Nawr ein bod wedi gweld 2 enghraifft, gadewch i ni edrych ar rhywfaint o pseudocode ar gyfer swyddogaeth recursive sy'n gweithredu chwiliad deuaidd. Gan ddechrau ar y top, rydym yn gweld bod yn rhaid inni ddod o hyd i swyddogaeth sy'n cymryd 4 dadleuon: allweddol, array, mun, a max. Yr allwedd yw nifer yr ydym yn chwilio amdanynt, fel 144 yn yr enghraifft flaenorol. Array yn y rhestr o niferoedd yr ydym yn ei chwilio. Min a max yn y mynegeion o'r swyddi isaf ac uchaf ein bod ar hyn o bryd yn edrych ar. Felly, pan fyddwn yn dechrau, bydd min yn sero, a bydd uchafswm fydd y mynegai mwyaf y rhesi. Wrth i ni gyfyngu'r chwilio i lawr, byddwn yn diweddaru mun a max i fod yr un ystod ein bod yn dal i chwilio i mewn 

Gadewch i sgip i'r rhan ddiddorol yn gyntaf. Y peth cyntaf a wnawn yw dod o hyd i'r man canol, y mynegai sydd hanner ffordd rhwng y lleiafswm a'r uchafswm y rhesi yr ydym yn dal i ystyried. Yna rydym yn edrych ar y gwerth y rhesi yn y lleoliad hwnnw bwynt canol a gweld os bydd y nifer yr ydym yn chwilio am yn llai na hynny allweddol. Os yw'r nifer yn y sefyllfa honno yn llai, yna mae'n golygu bod y allweddol yn fwy na'r holl rhifau i'r chwith y sefyllfa honno. Felly, gallwn alw swyddogaeth chwilio deuaidd eto, ond y tro hwn diweddaru'r mun a paramedrau max i ddarllen dim ond hanner sy'n fwy na neu'n hafal i werth ydym yn unig yn edrych ar. Ar y llaw arall, os yw'r allweddol yn llai na'r nifer yn y man canol ar hyn o bryd y rhesi, ydym am fynd i'r chwith ac yn anwybyddu'r holl rifau sy'n fwy. Unwaith eto, rydym yn galw chwiliad deuaidd ond y tro hwn gyda'r ystod o mun a max updated i gynnwys dim ond yr hanner isaf. Os yw'r gwerth yn y man canol ar hyn o bryd yn yr amrywiaeth yw'n mwy na nac yn llai nag yn allwedd, yna rhaid iddo fod yn hafal i'r allwedd. Felly, gallwn yn syml ddychwelyd y mynegai man canol ar hyn o bryd, ac rydym yn ei wneud. Yn olaf, mae'r gwiriad yma ar gyfer yr achos bod y nifer Nid yw mewn gwirionedd yn yr amrywiaeth o niferoedd yr ydym yn ei chwilio. Os yw'r mynegai uchafswm yr ystod ein bod yn chwilio am byth yn llai na'r isafswm, mae hynny'n golygu ein bod wedi mynd yn rhy bell. Gan nad yw'r nifer yn yn yr amrywiaeth mewnbwn, byddwn yn dychwelyd -1 i ddangos bod ni ddaethpwyd o hyd. 

Efallai eich bod wedi sylwi bod ar gyfer y algorithm i weithio, y rhestr o rifau wedi rhoi trefn arno. Mewn geiriau eraill, ni allwn ond dod o hyd i 144 gan ddefnyddio chwiliad deuaidd os yw'r holl rifau yn cael eu harchebu gan isaf i'r uchaf. Os nad yw hyn yn wir, ni fyddem yn gallu gwahardd hanner y niferoedd ar bob cam. Felly, rydym wedi 2 ddewis. Naill ai y gallwn gymryd rhestr heb eu didoli ac yn datrys y broblem cyn defnyddio chwiliad deuaidd, neu gallwn wneud yn siŵr fod y rhestr o rifau yn cael ei ddidoli wrth i ni ychwanegu rhifau ato. Felly, yn hytrach na didoli dim ond pan fydd yn rhaid i chwilio, beth am gadw rhestr datrys ar bob adeg? 

Un ffordd i gadw rhestr o rifau didoli ar yr un pryd caniatáu un i ychwanegu neu symud rhifau o'r rhestr hon yw drwy ddefnyddio rhywbeth o'r enw coeden chwiliad deuaidd. Mae deuaidd coeden chwilio yn strwythur data sydd 3 eiddo. Yn gyntaf, y Terfynau Chwilio chwith i unrhyw nod yn cynnwys werthoedd yn unig sydd yn llai na neu'n hafal i werth y nod yn. Yn ail, yr hawl Terfynau Chwilio o nod yn unig yn cynnwys gwerthoedd sy'n fwy na neu'n hafal i werth y nod yn. Ac, yn olaf, y subtrees chwith a dde yr holl nodau hefyd coed chwiliad deuaidd. Gadewch i ni edrych ar enghraifft gyda'r rhifau un a ddefnyddiwyd gennym yn gynharach. I'r rhai ohonoch nad ydynt erioed wedi gweld gwyddoniaeth gyfrifiadurol coeden o'r blaen, gadewch i mi ddechrau drwy ddweud wrthych fod cyfrifiadur coed gwyddoniaeth yn tyfu tuag at i lawr. Ie, yn wahanol i goed yr ydych yn gyfarwydd â, gwraidd gwyddoniaeth gyfrifiadurol goeden ar y brig, ac mae'r dail ar y gwaelod. Mae pob blwch bach a elwir yn nod, a'r nodau yn cael eu cysylltu â'i gilydd gan ymylon. Felly, wrth wraidd y goeden hon yn werth nod gyda'r gwerth 13, sydd â 2 nodau plant â'r gwerthoedd 5 a 34. Mae Terfynau Chwilio yw'r goeden sy'n cael ei ffurfio dim ond drwy edrych ar is-adran y goeden gyfan. 

Er enghraifft, y Terfynau Chwilio chwith y 3 nod yn y goeden a grëwyd gan y 0 nodau, 1, a 2. Felly, os ydym yn mynd yn ôl at y priodweddau chwiliad deuaidd coed, rydym yn gweld bod pob nod yn y goeden yn cydymffurfio â'r holl eiddo 3, sef, y Terfynau Chwilio chwith yn unig yn cynnwys gwerthoedd sy'n llai na neu'n hafal i werth y nod hwnnw; yr hawl Terfynau Chwilio pob nodau ond yn cynnwys gwerthoedd sy'n fwy na neu'n hafal i werth y nod; a subtrees chwith a'r dde yr holl nodau hefyd yn cael eu coed chwiliad deuaidd. Er bod y goeden yn edrych yn wahanol, mae hyn yn goeden ddeuol chwilio dilys am yr un set o rifau. Fel mater o ffaith, mae ffyrdd posibl llawer y gallwch greu coeden ddeuaidd chwilio ddilys o'r rhifau hyn. Wel, gadewch i ni fynd yn ôl i'r un cyntaf i ni greu. Felly, beth allwn ni ei wneud gyda'r coed? Wel, gallwn yn syml iawn dod o hyd i'r gwerthoedd isaf ac uchaf. Gall y gwerthoedd lleiaf ar gael drwy bob amser yn mynd i'r chwith nes nad oes nodau dim mwy i ymweld ag ef. I'r gwrthwyneb, i ddod o hyd i'r un mwyaf syml yn unig yn mynd i lawr i'r dde ar bob adeg. 

Dod o hyd i unrhyw rif arall nad yw'r isafswm neu'r uchafswm yr un mor hawdd. Dweud rydym yn chwilio am y rhif 89. Rydym yn syml weld beth yw gwerth pob nod a mynd i'r chwith neu i'r dde, yn dibynnu ar a yw gwerth y nod yn llai na neu'n fwy na un yr ydym yn chwilio amdano. Felly, gan ddechrau wrth wraidd 13, gwelwn fod 89 yn fwy, ac felly rydym yn mynd i'r dde. Yna rydym yn gweld y nod ar gyfer 34, ac unwaith eto rydym yn mynd i'r dde. 89 yn dal yn fwy na 55, felly rydym yn parhau i fynd i'r dde. Yna byddwn yn dod o hyd yn nod gyda gwerth o 144 ac yn mynd i'r chwith. Lo ac wele, 89 yn iawn yno. 

Peth arall y gallwn ei wneud yw argraffu holl rifau drwy berfformio groesi inorder. Mae groesi inorder olygu i argraffu popeth allan yn y Terfynau Chwilio chwith ddilyn gan argraffu'r nod ei hun ac yn dilyn hynny drwy argraffu popeth allan yn yr hawl Terfynau Chwilio. Er enghraifft, gadewch i ni gymryd ein goeden ddeuol chwilio hoff ac yn argraffu'r rhifau yn eu trefn sortio. Rydym yn dechrau wrth wraidd o 13, ond cyn argraffu 13 mae'n rhaid i ni argraffu popeth yn y Terfynau Chwilio chwith. Felly, rydym yn mynd i 5. Rydym yn dal rhaid i ni fynd ddyfnach i lawr yn y goeden nes i ni ddod o hyd i'r nod chwith y rhan fwyaf, sydd yn sero. Ar ôl argraffu sero, rydym yn mynd yn ôl i fyny i'r 1 ac argraffu hynny. Yna rydym yn mynd i'r Terfynau Chwilio dde, sef 2, ac argraffu hynny. Nawr ein bod chi'n ei wneud gyda hynny Terfynau Chwilio, gallwn fynd yn ôl i fyny at y 3 a'i hargraffu. Parhaus yn ôl i fyny, rydym yn argraffu'r y 5 ac yna'r 8. Nawr ein bod wedi cwblhau'r cyfan adael Terfynau Chwilio, gallwn argraffu allan o'r 13 a dechrau gweithio ar y dde Terfynau Chwilio. Rydym hop i lawr i 34, ond cyn argraffu 34 mae'n rhaid i ni argraffu ei Terfynau Chwilio chwith. Felly, rydym yn argraffu 21; yna rydym yn mynd i'w argraffu 34 a ymweld â'i hawl Terfynau Chwilio. Ers 55 Nid oes gan Terfynau Chwilio chwith, rydym yn ei hargraffu ac yn parhau ar ei Terfynau Chwilio dde. 144 Mae gan Terfynau Chwilio chwith, ac felly rydym yn argraffu'r 89, wedi'i ddilyn gan y 144, ac yn olaf y nod dde y rhan fwyaf o 233. Dyna ni; yr holl rhifau yn cael eu hargraffu mewn trefn o'r isaf i'r uchaf. 

Ychwanegu rhywbeth at y goeden yn gymharol ddi-boen yn ogystal. Mae pob mae'n rhaid i chi ei wneud yw gwneud yn siŵr ein bod yn dilyn 3 deuaidd eiddo chwilio coed ac yna rhowch y gwerth lle mae gofod. Lets 'ddeud rydym am i fewnosod gwerth 7. Ers 7 yn llai na 13, rydym yn mynd i'r chwith. Ond mae'n fwy na 5, felly rydym yn croesi i'r dde. Gan ei fod yn llai nag 8 ac 8 yn nod deilen, rydym yn ychwanegu 7 i blentyn chwith 8. Voila! Rydym wedi ychwanegu at ein rhif deuaidd coed chwilio. 

Os gallwn ychwanegu pethau, fe fyddai'n well yn gallu dileu pethau yn ogystal. Yn anffodus i ni, dileu yn ychydig yn fwy cymhleth - dim llawer, ond dim ond ychydig bach. Mae yna 3 senarios gwahanol y mae'n rhaid i ni ystyried wrth ddileu elfennau o goed chwiliad deuaidd. Yn gyntaf, mae'r achos hawsaf yw bod yr elfen yn nod deilen. Yn yr achos hwn, rydym yn syml ddileu a mynd ymlaen â'n busnes. Dweud ein bod am ddileu'r y 7 yr ydym newydd ei hychwanegu. Wel, rydym yn syml o hyd iddo, ei symud, a dyna ni. Mae'r achos nesaf yw os bydd y nod wedi dim ond 1 plentyn. Yma, gallwn ddileu'r nod, ond i ni yn gyntaf rhaid i ni sicrhau i gysylltu'r Terfynau Chwilio sydd ar ôl bellach riant o i riant y nod ydym yn dileu yn unig. Dweud ein bod am ddileu'r 3 o o'n goeden. Rydym yn cymryd yr elfen blentyn i'r nod a'i hatodi at riant y nod. Yn yr achos hwn, rydym yn awr yn cysylltu'r 1 i 5. Mae hyn yn gweithio heb broblem oherwydd ein bod yn gwybod, yn ôl i'r eiddo chwiliad deuaidd coed, bod popeth yn y Terfynau Chwilio chwith o 3 yn llai na 5. Nawr bod 3 yn Terfynau Chwilio yn cael ei gymryd gofal, gallwn ei ddileu. Mae'r achos drydydd ac yn olaf y mwyaf cymhleth. Mae hyn yn wir pan fydd y nod yr ydym am ei ddileu gan 2 o blant. Er mwyn gwneud hyn, rydym yn gyntaf rhaid i ni ddod o hyd i'r nod sydd â'r gwerth mwyaf nesaf, gyfnewid y ddau, ac yna dilëwch y nod dan sylw. Sylwch ar y nod sydd wedi ni all y gwerth mwyaf nesaf 2 o blant ei hun gan y byddai ei phlentyn ar y chwith fod yn ymgeisydd gwell ar gyfer y mwyaf nesaf. Felly, dileu nod gyda 2 o blant gyfystyr â gyfnewid o 2 nodau, ac yna dileu cael ei drin gan 1 o'r 2 rheolau uchod. Er enghraifft, gadewch i ni ddweud ein bod am ddileu'r, nod gwraidd 13. Y peth cyntaf a wnawn yw ein bod dod o hyd i'r gwerth mwyaf nesaf yn y goeden sydd, yn yr achos hwn, yn 21. Yna, byddwn yn cyfnewid y 2 nodau, gan wneud 13 a dail a 21 y nod grŵp canolog. Nawr gallwn yn syml dileu 13. 

Fel y cyfeiriodd yn gynharach, mae yna lawer o ffyrdd posibl i wneud coeden ddeuaidd chwilio dilys. Yn anffodus i ni, mae rhai yn waeth nag eraill. Er enghraifft, beth sy'n digwydd pan fyddwn yn adeiladu coeden chwiliad deuaidd o restr o rifau datrys? Mae pob rhif yn cael eu hychwanegu ychydig i'r dde ar bob cam. Pan rydym am i chwilio am rif, nid oes gennym ddewis ond dim ond i edrych ar yr hawl ar bob cam. Nid yw hyn yn well na chwiliad llinol o gwbl. Er na fyddwn yn ymdrin â nhw yma, mae yna eraill, yn fwy cymhleth, strwythurau data sy'n gwneud yn siŵr nad yw hyn yn digwydd. Fodd bynnag, un peth syml y gellir ei wneud i osgoi hyn yw i ychydig ar hap siffrwd y gwerthoedd mewnbwn. Mae'n annhebygol iawn y trwy hap a damwain ar hap rhestr cymysgu o rifau yn cael ei datrys. Os yw hyn yn wir, ni fyddai casinos yn aros mewn busnes yn hir. 

Dyna ni. Rydych nawr yn gwybod am chwilio deuaidd a choed chwiliad deuaidd. Rwy'n Patrick Schmid, ac mae hyn yn CS50. [CS50.TV] Un ffordd amlwg fyddai i sganio y rhestr o ... [Canu] ... Nifer yr eitemau ... yep [Chwerthin] Bostio ... nod o 234 ... augh. >> Yay! Dyna oedd -