[Powered by Google Translate] [Binary Tafuta] [Patrick Schmid - Chuo Kikuu cha Harvard] [Hii ni CS50. - CS50.TV] 

Kama Mimi niliwapeni orodha ya majina ya tabia Disney katika herufi na aliuliza wewe kupata Mickey Mouse, jinsi gani unaweza kwenda juu ya kufanya hii? Moja ya njia dhahiri itakuwa Scan orodha tangu mwanzo na kuangalia kila jina ili kuona kama ni Mickey. Lakini kama wewe kusoma Aladdin, Alice, Arieli, na kadhalika, utasikia haraka kutambua kwamba kuanzia saa mbele ya orodha ilikuwa si wazo nzuri. Sawa, labda unapaswa kuanza kufanya kazi nyuma kutoka mwisho wa orodha. Sasa unaweza kusoma Tarzan, Stitch, Snow White, na kadhalika. Hata hivyo, hii haionekani kama njia bora ya kwenda juu yake. 

Naam, njia nyingine ambayo unaweza kwenda juu ya kufanya hii ni kujaribu nyembamba chini orodha ya majina ya kwamba una kuangalia. Tangu unajua kwamba wao ni katika mpango wa herufi, unaweza tu kuangalia majina katikati ya orodha na kuangalia kama Mickey Mouse ni kabla au baada ya jina hili. Kuangalia jina la mwisho katika safu ya pili Ningependa kutambua kwamba M kwa ajili ya Mickey inakuja baada ya J kwa Jasmine, hivyo wewe d tu kupuuza nusu ya kwanza ya orodha. Kisha wewe d pengine kuangalia juu ya safu ya mwisho na kuona kwamba huanza na Rapunzel. Mickey inakuja kabla Rapunzel; inaonekana kama tunaweza kupuuza safu mwisho pia. Inaendelea na mkakati tafuta, itabidi haraka kuona kwamba Mickey ni katika nusu ya kwanza ya orodha ya majina iliyobaki na hatimaye kupata Mickey mafichoni kati ya Merlin na Minnie. 

Nini wewe tu alifanya alikuwa kimsingi binary tafuta. Kama jina hii ina maana, hufanya kutafuta yake mkakati katika suala binary. Hii ina maana gani? Naam, kutokana na orodha ya vitu sorted, tafuta binary algorithm hufanya uamuzi binary - kushoto au kulia, zaidi au chini, alphabetically kabla au baada ya - katika hatua kila mmoja. Sasa kwa kuwa tuna jina kwamba huenda pamoja na algorithm hii tafuta, hebu tuangalie mfano mwingine, lakini wakati huu na orodha ya idadi Iliyopangwa. Sema sisi ni kuangalia kwa idadi 144 katika orodha hii ya idadi Iliyopangwa. Tu kama kabla, sisi kupata idadi hiyo ni katika katikati - ambayo katika kesi hii ni 13 - 144 na kuona kama ni zaidi au chini ya 13. Tangu ni wazi zaidi kuliko 13, tunaweza kupuuza kila kitu kuwa ni 13 au chini na tu makini na nusu iliyobaki. Tangu sasa tuna idadi ya vitu hata kushoto, sisi tu kuchagua idadi ambayo ni karibu na katikati. Katika kesi hii sisi kuchagua 55. Tungeweza urahisi tu kama waliochaguliwa 89. Sawa. Tena, 144, ni mkubwa kuliko 55, hivyo sisi kwenda kulia. Bahati nzuri kwa ajili yetu, karibu katikati idadi ni 144, moja sisi ni kuangalia kwa. Hivyo ili kupata 144 kwa kutumia tafuta binary, sisi ni uwezo wa kupata hiyo katika hatua 3 tu. Kama sisi ingekuwa kutumika tafuta linear hapa, ingekuwa kuchukuliwa hatua sisi 12. Kama jambo la kweli, tangu njia hii tafuta halves idadi ya vitu ina kuangalia kila hatua, itakuwa kupata bidhaa hiyo ni kwa ajili ya kutafuta katika kuhusu logi ya idadi ya vitu katika orodha. Sasa kwa kuwa tumeona mifano 2, hebu tuangalie baadhi pseudocode kwa ajili ya kazi ya kujirudia kwamba kutekeleza tafuta binary. Kuanzia juu, tunaona kwamba tuna kupata kazi ambayo inachukua hoja 4: muhimu, safu, min, na max. muhimu ni kwamba idadi hiyo sisi ni kuangalia kwa, hivyo 144 katika mfano uliopita. Array ni orodha ya namba kwamba sisi ni kutafuta. Min na max ni fahirisi ya nafasi ya chini na upeo kwamba sisi sasa ni kuangalia. Hivyo wakati sisi kuanza, min itakuwa sifuri na max itakuwa index upeo wa safu. Kama sisi nyembamba tafuta chini, sisi update min na max kwa kuwa tu mbalimbali kwamba sisi bado ni kuangalia in 

Hebu ruka kwa sehemu ya kuvutia ya kwanza. Jambo la kwanza sisi kufanya ni kupata midpoint, index kwamba ni nusu kati ya dk na max ya safu ya kwamba sisi ni bado kuzingatia. Kisha sisi kuangalia thamani ya safu katika eneo kwamba midpoint na kuona kama idadi ya kwamba sisi ni kuangalia kwa ni chini ya muhimu ambayo. Kama idadi katika nafasi ya kuwa ni chini, basi ina maana muhimu ni kubwa kuliko idadi yote ya kushoto ya nafasi hiyo. Hivyo tunaweza kuwaita binary tafuta kazi tena, lakini wakati huu uppdatering min na vigezo max kusoma tu nusu kwamba, ni mkubwa kuliko au sawa na thamani sisi alimwangalia. Kwa upande mwingine, kama ufunguo ni chini ya idadi ya sasa katika midpoint wa safu, tunataka kwenda kwa upande wa kushoto na kupuuza idadi yote kwamba ni kubwa zaidi. Tena, sisi kuwaita binary tafuta lakini wakati huu na aina mbalimbali ya dk na max updated kwa pamoja na nusu tu ya chini. Kama thamani katika midpoint ya sasa katika safu ni wala kubwa kuliko wala ndogo kuliko muhimu, basi ni lazima kuwa sawa na muhimu. Hivyo, tunaweza tu kurudi sasa midpoint index, na sisi ni kosa. Hatimaye, hii hapa ni kuangalia kwa kesi hiyo namba si kweli katika safu ya idadi sisi ni kutafuta. Kama index upeo wa mbalimbali kwamba sisi ni kuangalia kwa ni milele chini ya kiwango cha chini, hiyo ina maana kwamba tumeenda mbali sana. Tangu idadi ilikuwa si katika safu ya pembejeo, sisi kurudi -1 zinaonyesha kwamba hakuna found. 

Unaweza kuwa niliona kuwa kwa algorithm hii kazi, orodha ya idadi ina sorted. Kwa maneno mengine, tunaweza tu kupata 144 kwa kutumia binary tafuta ikiwa idadi yote ni amri kutoka chini mpaka juu. Kama huyu si kesi, tunataka kuwa na uwezo wa kuwatenga nusu ya idadi ya kila hatua. Hivyo tuna chaguzi 2. Aidha tunaweza kuchukua orodha zisizochambuliwa na aina hiyo kabla ya kutumia search binary, au tunaweza kuhakikisha kwamba orodha ya namba ni Iliyopangwa kama sisi kuongeza idadi hiyo. Hivyo, badala ya kuchagua tu wakati tuna kutafuta, kwa nini kuweka orodha Iliyopangwa wakati wote? 

Moja ya njia ya kuweka orodha ya namba sorted wakati huo huo kuruhusu moja ya kuongeza au hoja namba kutoka kwenye orodha hii ni kwa kutumia kitu kinachoitwa binary tafuta mti. tafuta binary mti ni muundo data kwamba ana mali 3. Kwanza, subtree kushoto wa nodi ina maadili tu kwamba ni chini ya au sawa na thamani ya nodi. Pili, haki subtree ya nodi tu ina maadili ambayo ni kubwa kuliko au sawa na thamani ya nodi. Na, hatimaye, wote subtrees kushoto na kulia ya nodes wote ni pia binary tafuta miti. Hebu tuangalie mfano kwa idadi sawa sisi kutumika mapema. Kwa wale ambao hawajawahi kuonekana sayansi ya kompyuta mti kabla, napenda kuanza kwa kuwaambia kwamba sayansi ya kompyuta mti huu hukua chini. Ndiyo, tofauti na miti wewe wamezoea, mizizi ya mti sayansi ya kompyuta ni saa ya juu, na majani yake ni ya chini. Kila sanduku kidogo inaitwa nodi, na tezi ni kushikamana na kila mmoja kwa edges. Hivyo mizizi ya mti huu ni thamani ya nodi thamani 13, ambayo ina watoto 2 nodes na maadili 5 na 34. subtree ni mti ni sumu tu kwa kuangalia kifungu cha mti mzima. 

Kwa mfano, subtree kushoto wa 3 nodi ni mti umba nodes 0, 1, na 2. Hivyo, kama sisi kwenda nyuma ya mali ya mti tafuta binary, sisi kuona kuwa kila nodi katika mti inajilainisha na mali yote 3, yaani, subtree kushoto tu ina maadili ambayo ni chini ya au sawa na thamani ya nodi; haki subtree ya nodes wote tu ina maadili ambayo ni kubwa kuliko au sawa na thamani ya nodi; na subtrees wote wa kushoto na wa kulia wa nodi yote pia ni binary tafuta miti. Ingawa mti huu huonekana tofauti, hii ni halali binary tafuta mti kwa seti moja ya namba. Kama jambo la kweli, kuna wengi iwezekanavyo njia ambazo unaweza kuunda halali binary tafuta mti kutokana na namba hizi. Naam, hebu kwenda nyuma ya kwanza sisi aliumba. Basi nini tunaweza kufanya kwa miti hii? Naam, tunaweza sana tu kupata maadili ya chini na kiwango cha juu. maadili ya chini inaweza kupatikana kwa mara kwenda kushoto mpaka hakuna zaidi nodes kutembelea. Kinyume chake, na kupata moja upeo tu tu inakwenda chini kwa haki wakati kila. 

Kupata namba nyingine yoyote ambayo si chini au upeo ni kama rahisi. Sema sisi ni kuangalia kwa idadi 89. Sisi tu kuangalia thamani ya nodi ya kila na kwenda kushoto au kulia, kutegemea kama thamani nodi ni chini ya au kubwa kuliko moja sisi ni kuangalia kwa. Hivyo, kuanzia saa mizizi ya 13, tunaona kuwa 89 ni mkuu, na hivyo sisi kwenda kulia. Kisha sisi kuona nodi kwa 34, na tena sisi kwenda kulia. 89 bado ni kubwa kuliko 55, hivyo tunaendelea kwenda kulia. Sisi basi kuja na nodi na thamani ya 144 na kwenda kushoto. Hakika na tazama, 89 ni haki pale. 

Kitu kingine kwamba tunaweza kufanya ni kuchapa nje namba zote kwa kufanya traversal ili kuweza. traversal ili kuweza maana ya magazeti kila kitu nje katika subtree kushoto ikifuatiwa na uchapishaji nodi yenyewe na kisha kufuatiwa na uchapishaji kila kitu nje katika haki subtree. Kwa mfano, hebu kuchukua binary wetu favorite tafuta mti na magazeti nje ya idadi ili Iliyopangwa. Sisi kuanza katika mizizi ya 13, lakini kabla ya uchapishaji 13 tuna magazeti nje kila kitu katika subtree kushoto. Hivyo sisi kwenda 5. Sisi bado tuna kwenda zaidi chini katika mti hata sisi kupata nodi kushoto-wengi, ambayo ni sifuri. Baada ya uchapishaji sifuri, sisi kurudi nyuma hadi 1 na magazeti kwamba nje. Kisha sisi kwenda subtree haki, ambayo ni 2, na magazeti kwamba nje. Sasa kwa kuwa sisi ni kosa na kwamba subtree, tunaweza kurudi nyuma hadi 3 na magazeti nje. Kuendelea nyuma juu, sisi magazeti 5 na kisha 8. Sasa kwa kuwa tuna kukamilika nzima kushoto subtree, tunaweza magazeti nje 13 na kuanza kazi haki subtree. Sisi hop chini ya 34, lakini kabla ya uchapishaji 34 tuna magazeti nje subtree wake wa kushoto. Hivyo sisi magazeti nje 21; basi sisi kupata magazeti nje 34 na kutembelea wake wa kulia subtree. Tangu 55 hana subtree kushoto, sisi magazeti ni nje na kuendelea kwa subtree wake wa kulia. 144 ina subtree kushoto, na hivyo sisi magazeti nje 89, ikifuatiwa na 144, na hatimaye nodi haki-zaidi ya 233. Kuna nayo; namba zote ni kuchapishwa kwa amri kutoka chini mpaka juu. 

Kuongeza kitu mti ni kiasi painless pia. Wote sisi kufanya ni kuhakikisha kwamba sisi kufuata 3 binary mali mti tafuta na kisha Insert thamani ambapo kuna nafasi. Hebu sema tunataka Insert thamani ya 7. Tangu 7 ni chini ya 13, sisi kwenda kushoto. Lakini ni mkuu zaidi kuliko 5, hivyo sisi tembeeni kwa haki. Tangu ni chini ya 8 na 8 ni nodi jani, sisi kuongeza 7 kwa mtoto wa kushoto wa 8. Voilà! Tumeongeza idadi ya mti binary yetu ya utafutaji. 

Kama tunaweza kuongeza mambo, sisi ni bora kuwa na uwezo wa kufuta mambo kama vizuri. Bahati mbaya kwa ajili yetu, kufuta ni kidogo ngumu zaidi - si mengi, lakini kidogo tu. Kuna 3 tofauti matukio kwamba tuna kufikiria wakati kufuta vipengele kutoka miti binary tafuta. Kwanza, kesi rahisi ni kwamba kipengele ni nodi jani. Katika kesi hiyo, sisi kufuta tu na kuendelea na biashara yetu. Sema sisi unataka kufuta 7 kwamba sisi tu aliongeza. Naam, sisi tu kupata hiyo, kuondoa hiyo, na hiyo ni yake. kesi ya pili ni kama nodi ina tu 1 mtoto. Hapa tunaweza kufuta nodi, lakini sisi kwanza kuwa na kuhakikisha kuungana subtree kwamba ni sasa kushoto wazazi kwa mzazi wa nodi sisi tu ilifutwa. Sema sisi unataka kufuta 3 kutoka mti wetu. Sisi kuchukua kipengele mtoto wa nodi kwamba na ambatisha kwa mzazi wa nodi. Katika kesi hii, sisi ni sasa attaching 1-5. Hii kazi bila tatizo kwa sababu tunajua, kulingana na tafuta binary mali mti, kwamba kila kitu katika subtree kushoto wa 3 ilikuwa chini ya 5. Sasa kwa kuwa wa 3 subtree ni kuchukuliwa huduma ya, tunaweza kufuta. kesi ya tatu na ya mwisho ni ngumu zaidi. Hii ni kesi wakati nodi sisi unataka kufuta ana watoto 2. Ili kufanya hivyo, sisi kwanza na kupata nodi ambayo ina thamani kubwa ijayo, wabadilishane mbili, kisha kufuta nodi katika swali. Notice nodi ambayo ina thamani kubwa ijayo hawezi kuwa na watoto 2 yenyewe tangu mtoto wake wa kushoto ungekuwa mgombea bora kwa ukubwa ijayo. Kwa hiyo, kufuta nodi na watoto 2 ni sawa na swapping ya nodes 2, na kisha kufuta ni kubebwa na 1 ya kanuni 2 aforementioned. Kwa mfano, hebu kusema tunataka kufuta nodi mizizi, 13. Jambo la kwanza sisi kufanya ni sisi kupata ijayo kubwa thamani katika mti ambayo, katika kesi hii, ni 21. Sisi basi wabadilishane nodes 2, na kufanya 13 na 21 kati jani kundi nodi. Sasa tunaweza kufuta tu 13. 

Kama alluded awali, kuna wengi iwezekanavyo njia ya kufanya halali binary tafuta mti. Bahati mbaya kwa ajili yetu, baadhi ni mbaya zaidi kuliko wengine. Kwa mfano, kile kinachotokea wakati sisi kujenga binary tafuta mti kutoka orodha Iliyopangwa ya namba? Idadi yote ni aliongeza tu kwa haki kwa kila hatua. Wakati tunataka kutafuta namba, hatuna uchaguzi bali tu kwa kuangalia haki kwa kila hatua. Hii si bora kuliko tafuta linear wakati wote. Ingawa sisi si cover yao hapa, kuna wengine, ngumu zaidi, data miundo kwamba kuhakikisha kwamba hii haina kutokea. Hata hivyo, moja rahisi kitu ambayo yanaweza kufanyika ili kuepuka hili ni tu nasibu shuffle maadili ya pembejeo. Ni uwezekano mkubwa kwamba kwa bahati random orodha huchanganywa ya idadi ni Iliyopangwa. Kama hii walikuwa kesi, kasinon hakutaka kukaa katika biashara kwa muda mrefu. 

Kuna una hiyo. Wewe sasa kujua kuhusu kutafuta binary na miti binary tafuta. Mimi nina Patrick Schmid, na hii ni CS50. [CS50.TV] Moja ya njia dhahiri itakuwa Scan orodha kutoka ... [beep] ... Idadi ya vitu ... yep [Atacheka] ... Post ya nodi ya 234 ... augh. >> Yay! Hiyo ilikuwa -