[Powered by Google Translate] [Search binè] [Patrick Schmid - Inivèsite Harvard] [Sa a se CS50. - CS50.TV] 

Si mwen te ban nou yon lis de Disney non karaktè yo nan lòd alfabetik epi li te mande ou jwenn Mickey Mouse, ki jan ou ta ale sou fè sa a? Youn nan fason evidan ta dwe analysis lis la depi nan konmansman an epi tcheke chak non yo wè si li nan Mickey. Men, pandan w ap li geladen, Alice, Ariel, ak pou fè, ou pral byen vit reyalize ke kòmanse an de sou devan lis la pa te yon bon lide. Okay, petèt ou ta dwe kòmanse travay bak soti nan nan fen lis la. Koulye a, ou li Tarzan, pikur, nèj Blan, ak pou fè. Toujou, sa a pa sanble tankou pi bon fason yo ale sou li. 

Oke, yon lòt fason ke ou ta ka ale sou fè sa se pou yo eseye etwat desann lis la nan non ki di ou gen fè yon gade nan. Depi ou konnen yo ke yo se nan òd alfabetik, ou ta ka jis gade nan non yo nan mitan an nan lis la epi tcheke si Mickey Mouse se anvan oswa apre sa a non. Gade nan non an dènye dezyèm kolòn nan ou ta reyalize ke M pou Mickey vin apre J pou Jasmine, konsa ou ta tou senpleman inyore pwemye mwatye nan lis la. Lè sa a, ou ta pwobableman gade nan tèt la nan dènye kolòn nan ak wè ke li kòmanse ak Rapunzel. Mickey vini anvan Rapunzel; sanble nou ka inyore dènye kolòn nan kòm byen. Kontinye estrateji rechèch la, ou pral byen vit wè ke Mickey se nan pwemye mwatye nan lis la rete nan non epi finalman jwenn Mickey kache ant mèrlen ak Minnie. 

Ki sa ou jis te fè fondamantalman binè rechèch. Kòm non sa implique, li fè chache estrateji li yo nan yon kesyon binè. Ki sa sa vle di? Oke, bay yon lis Ranje atik, algorithm nan rechèch binè pran yon desizyon binè - gòch la oswa dwa, pi gran pase oswa mwens pase, lòd avèk lèt ​​alfabè anvan oswa apre - nan chak pwen. Kounye a ke nou gen yon non ki ale ansanm ak sa a algorithm rechèch, kite pou yo gade nan yon lòt egzanp, men fwa sa a ak yon lis Ranje chif yo. Di nou ap chèche pou yon nimewo pou la 144 nan lis sa a nan Ranje chif yo. Jis tankou anvan, nou jwenn nimewo a ki nan menm nan mitan yo - ki nan ka sa a se 13 - ak wè si 144 se pi gran pase oswa mwens pase 13. Depi li a byen klè pi gran pase 13, nou ka inyore tout bagay ki se 13 oswa mwens ak jis konsantre sou mwatye nan rete yo. Depi nou kounye a gen yon nimewo menm nan atik kite, nou tou senpleman chwazi yon chif ki pi pre mitan yo. Nan ka sa a nou chwazi 55. Nou te ka genyen menm jan fasil chwazi 89. Oke. Yon fwa ankò, 144 se pi wo pase 55, konsa nou ale nan bò dwat la. Erezman pou nou, nimewo nan mitan pwochen se 144, yon sèl nan nou ap chèche pou. Se konsa, yo nan lòd jwenn 144 lè l sèvi avèk yon rechèch binè, nou ap kapab jwenn li nan se sèlman 3 etap. Si nou ta te itilize lineyè rechèch isit la, li ta yo te pran nou 12 etap. Kòm yon kesyon de reyalite, depi metòd sa a rechèch mwatye nimewo a nan atik li gen fè yon gade nan nan chak etap, li pral jwenn atik la li se pou chèche nan sou boutèy la, ki kantite bagay ki nan lis la. Kounye a ke nou te wè 2 egzanp, kite a pran yon gade nan kèk pseudocode pou yon fonksyon repetitif ki aplike rechèch binè. Kòmanse nan tèt la, nou wè ke nou gen sa yo jwenn yon fonksyon ki pran 4 agiman: kle yo, etalaj, min, ak max. Kle a se nimewo a ke nou ap chèche pou, se konsa 144 nan egzanp lan anvan yo. Etalaj se lis la nan nimewo ke nou ap chèche. Min ak max se endis yo nan pozisyon yo minimòm ak kantite maksimòm kounye a ke nou ap chèche a. Se konsa, lè nou kòmanse, min yo pral zewo ak max pral endèks la maksimòm de etalaj la. Kòm nou etwat rechèch la desann, nou pral mete ajou min ak max yo dwe jis ranje a ke nou toujou ap chèche pous 

Se pou nou Sote ale nan Pati a enteresan premye. Premye bagay nou fè se jwenn pwen milye a, endèks la ki se mwatye ant min a ak max nan etalaj la ke nou yo toujou ap konsidere. Lè sa a, nou gade nan valè a nan etalaj la nan ki kote pwen milye ak wè si nimewo a ke nou ap chèche pou se mwens pase sa kle. Si nimewo a nan pozisyon sa ki mwens lan, Lè sa a, sa vle di li kle a se pi gwo pase tout chif nan kite nan pozisyon sa. Se konsa, nou ka rele binè fonksyon rechèch ankò, men fwa sa a mete ajou min a ak paramèt max li jis mwatye nan ki pi gran pase oswa egal a valè a nou jis gade. Nan lòt men an, si kle a se mwens pase kantite a nan pwen milye aktyèl la nan etalaj la, nou vle pou yo ale nan bò gòch la ak inyore tout nonb ki se pi plis la. Yon fwa ankò, nou rele rechèch binè men fwa sa a ak ranje nan min ak max Updated genyen ladan yo jis mwatye nan pi ba yo. Si valè a nan pwen milye aktyèl la nan etalaj la se pa ni pi gwo pase ni pi piti pase kle a, lè sa a li dwe egal a kle a. Kidonk, nou ka tou senpleman tounen endèks pwen milye a, kounye a, epitou n ap fè a. Finalman, chèk sa-a isit la se pou ka a nimewo sa a nan se pa aktyèlman nan etalaj la nan nimewo nou ap chèche. Si endèks la maksimòm de ranje a ke nou ap chèche pou se tout tan mwens pase minimòm nan, ki vle di ke nou te ale twò lwen. Depi nimewo a pa t 'nan etalaj la D', nou tounen -1 pou montre pou ki pa gen anyen te jwenn. 

Ou ka gen remake ke pou sa a algorithm nan travay, lis la nan nimerik ki gen yo dwe klase. Nan lòt mo, nou ka sèlman jwenn 144 lè l sèvi avèk rechèch binè si tout nimewo yo ap bay lòd soti nan pi ba pi gwo a. Si sa pa t ka a, nou pa ta dwe kapab eskli mwatye nan nimewo ki nan chak etap. Se konsa, nou gen 2 opsyon. Swa nou ka pran yon lis klase epi klase l 'devan lè l sèvi avèk binè rechèch, oubyen nou ka asire w ke se lis la nan nimewo Ranje jan nou ajoute nimewo li. Se konsa,, olye pou yo jis Fouye lè nou gen nan rechèch, poukisa pa kenbe lis la Ranje nan tout fwa? 

Youn nan fason yo kenbe yon lis nimewo Ranje anmenm tan li ap pèmèt youn nan ajoute oswa deplase nimewo nan lis sa a se lè yo itilize yon bagay yo rele yon pyebwa rechèch binè. Yon pye bwa rechèch binè se yon estrikti done ki gen 3 pwopriyete yo. Premyèman, subtree gòch la nan nenpòt ki ne gen valè sèlman ki gen mwens pase oswa egal a valè ne la. Dezyèmman, dwa subtree a nan yon ne sèlman gen valè ki pi gran pase oswa egal a valè ne la. , E finalman, tou de agoch ​​ak adwat subtrees yo nan tout nœuds yo tou pye bwa rechèch binè. Se pou yo gade nan yon egzanp ak nonb yo menm nou itilize pi bonè. Pou moun nan nou ki pa janm wè yon pye bwa syans konpitè anvan, kite m 'kòmanse pa di ou ke yon pye bwa syans konpitè ap grandi bès. Wi, kontrèman ak pye bwa ou yo abitye, rasin nan yon pyebwa syans òdinatè se nan tèt la, Se ak fèy li yo se nan pati anba nan. Chak bwat ti kras rele yon ne, ak nœuds yo yo ki konekte nan chak lòt nan bor. Se konsa, rasin lan nan pyebwa sa a se yon valè ne ak valè a 13, ki te gen 2 timoun nœuds avèk valè ki 5 ak 34. Yon subtree se pyebwa sa a, ki te fòme yo senpleman gade sou yon seksyon nan pye bwa a tout antye. 

Pou egzanp, subtree gòch la nan 3 a ne se pye bwa a ki te kreye pa 0 nœuds yo, 1, ak 2. Se konsa, si nou tounen nan pwopriyete yo nan yon pye bwa rechèch binè, nou wè ke chak ne nan pye bwa a koresponn nan tout pwopriyete 3, savwa, subtree gòch la sèlman gen valè moral ki te gen mwens pase oswa egal a valè ne a; dwa subtree nan tout nœuds sèlman gen valè ki pi gran pase oswa egal a valè ne a; ak tou de agoch ​​ak adwat subtrees nan tout nœuds tou yo se pye bwa rechèch binè. Malgre ke pye bwa sa a parèt diferan, sa a se yon binè pyebwa ki valab rechèch pou mete nan menm nan nimewo yo. Kòm yon kesyon de reyalite, gen anpil fason posib ke ou kapab kreye yon valab rechèch binè pyebwa soti nan nimewo sa yo. Oke, kite la tounen nan youn nan premye nou te kreye. Se konsa, sa nou ka fè ak sa yo pyebwa yo? Oke, nou ka anpil tou senpleman jwenn valè yo minimòm ak maksimòm. Valè yo minimòm ka jwenn pa toujou ale nan bò gòch la jiskaske pa gen okenn plis nœuds nan vizit. Kontrèman, yo jwenn yon sèl nan maksimòm tou senpleman jis ale desann sou bò dwat la nan chak fwa. 

Jwenn nenpòt kantite lòt ki pa minimòm la oswa maksimòm la se jis kòm fasil. Di nou ap chèche pou yon nimewo pou la 89. Nou tou senpleman tcheke valè chak ne epi ale nan bò gòch la oswa dwa, depann sou si valè ne a se mwens pase oswa pi gran pase yon sèl nan nou ap chèche pou. Se konsa,, kòmanse nan rasin lan nan 13, nou wè ke 89 se pi gwo a, epi pou nou ale nan bò dwat la. Lè sa a, nou wè ne la pou 34, epi ankò nou ale a dwat la. 89 se toujou pi wo pase 55, se konsa nou kontinye ale nan bò dwat la. Nou Lè sa a, vini ak yon ne ak valè a nan 144 epi ale nan bò gòch li. Lo men koulye a, 89 se dwa la. 

Yon lòt bagay ke nou ka fè se enprime soti tout chif a fè yon parcourt inorder. Yon parcourt inorder vle di enprime tout bagay soti nan subtree gòch la ki te swiv pa enprime ne a li menm ak Lè sa a, ki te swiv pa enprime tout bagay soti nan subtree a dwat. Pou egzanp, kite a pran pi renmen pyebwa binè nou rechèch epi enprime soti chif yo nan Ranje lòd. Nou kòmanse nan rasin lan 13 la, men anvan enprime 13 nou dwe enprime soti tout sa ki nan subtree gòch la. Se konsa, nou ale nan 5. Nou toujou gen yo ale pi fon desann nan pyebwa a jiskaske nou jwenn ne nan bò goch la nèt, ki se zewo. Apre enprime zewo, nou tounen jiska 1 an epi enprime ki deyò. Lè sa a, nou ale nan subtree nan dwa, ki se 2, epi enprime ki deyò. Kounye a ke nou ap fè ak ki subtree, nou ka ale tounen moute nan 3 a ak enprime li. Kontinye tounen moute, nou enprime 5 an ak Lè sa a, 8 la. Kounye a ke nou te deja konplete tout la kite subtree, nou ka enprime soti 13 an ak kòmanse travay sou subtree a dwat. Nou hop desann nan 34, men anvan enprime 34 nou dwe enprime soti subtree gòch li yo. Se konsa, nou enprime soti 21; Lè sa a, nou jwenn yo enprime soti 34 ak vizite subtree dwa li yo. Depi 55 pa gen okenn subtree gòch, nou enprime li epi yo kontinye sou subtree dwa li yo. 144 a gen yon subtree agoch, epi pou nou enprime soti 89 an, ki te swiv pa 144 la, epi finalman ne nan dwa-pi fò nan 233. Genyen ou genyen li; tout nimewo yo ap enprime deyò nan lòd soti nan pi ba pi gwo a. 

Ajoute yon bagay bò pyebwa ki se relativman fèt san doulè kòm byen. Tout sa nou dwe fè se asire w ke nou swiv 3 pwopriyete binè pyebwa rechèch ak Lè sa a, insert valè a kote ki gen espas. Se pou nou di nou vle insert valè a 7. Depi 7 se mwens pase 13, nou ale nan bò gòch li. Men, li la pi gran pase 5, konsa nou Traverse a dwat la. Depi li nan mwens pase 8 ak 8 se yon ne fèy, nou ajoute 7 a timoun nan gòch nan 8. Vwala! Nou te ajoute yon nimewo bò pyebwa rechèch binè nou an. 

Si nou ka ajoute bagay sa yo, nou pi bon kapab efase bagay sa yo kòm byen. Malerezman pou nou, efase se yon ti jan ti kras pi plis konplike - pa anpil, men jis yon ti jan. Gen 3 senaryo diferan ke nou gen yo konsidere lè efase eleman soti nan pyebwa rechèch binè. Premyèman, ka a pi fasil se ke eleman an se yon ne fèy. Nan ka sa a, nou tou senpleman efase l ', li ale nan ak biznis nou an. Di nou vle efase 7 a ke nou jis te ajoute. Bon, nou tou senpleman jwenn li, retire li, epi ki nan li. Ka a pwochen se si ne a gen sèlman 1 timoun. Isit la nou kapab efase ne la, men nou premye dwe asire nou ke konekte subtree sa a, ki kounye a kite parentless bay paran an nan ne an nou jis efase. Di nou vle efase 3 fwi pyebwa nou yo. Nou pran eleman nan pitit la ki ne epi mete li ak paran an sou ne a. Nan ka sa a, nou ap kounye a atache 1 an a 5 an. Sa a ap travay san yo pa yon pwoblèm paske nou konnen, dapre pwopriyete a pyebwa rechèch binè, ke tout bagay nan subtree gòch la nan 3 te mwens pase 5. Kounye a ke nan 3 subtree se pran swen nan, nou ka efase li. Ka a twazyèm ak dènye ki pi konplèks la. Sa a se ka a lè ne a nou vle efase gen 2 timoun yo. Yo nan lòd yo fè sa, nou premye gen jwenn ne a ki gen valè nan pwochen pi gwo, swap de a, ak Lè sa a, efase ne a nan kesyon. Avi ne a ki gen pwochen valè a pi gwo pa ka gen 2 timoun pwòp tèt li depi timoun gòch li yo ta dwe yon kandida pi bon pou pi gwo kap vini an. Se poutèt sa, efase yon ne ak 2 timoun MONTAN LAJAN échanjé nan 2 nœuds, ak Lè sa a, efase se lantremiz 1 nan 2 règ yo susmansyone. Pou egzanp, kite a di nou vle efase ne nan rasin, 13. Premye bagay nou fè se nou jwenn pwochen valè a pi gwo nan pye bwa a ki, nan ka sa a, se 21. Nou Lè sa a, boukante nœuds yo 2 yo, ki fè 13 yon fèy ak 21 ne nan gwoup santral. Koulye a, nou ka senpleman efase 13. 

Kòm mansyone pi bonè, gen anpil fason posib fè yon binè valid pyebwa rechèch. Malerezman pou nou, gen kèk ki pi mal pase lòt moun. Pou egzanp, sa ki pase lè nou bati yon pyebwa rechèch binè nan yon lis Ranje nan nimewo? Tout nimewo yo se jis ajoute sou bò dwat la nan chak etap. Lè nou vle pou fè rechèch pou yon nonb, nou pa gen okenn chwa men se sèlman fè yon gade nan dwa a nan chak etap. Sa a se pa pi bon pase rechèch lineyè nan tout. Malgre ke nou pa pral kouvri yo isit la, gen lòt, plis konplèks, done estrikti ki asire w ke sa pa rive. Sepandan, yon sèl bagay senp ki kapab fè pou fè pou evite sa a se jis chefeul owaza valè yo kontribisyon. Li nan trè fasil ki pa chans o aza se yon lis shuffled nan nimewo Ranje. Si sa a yo te ka a, kazino pa t 'vle rete nan biznis pou lontan. 

Genyen ou genyen li. Ou kounye a konnen sou rechèch binè ak pye bwa rechèch binè. Mwen Patrick Schmid, e sa se CS50. [CS50.TV] Youn nan fason evidan ta dwe analysis lis la soti nan ... [BEEP] ... Nimewo a nan atik ... YEP [Ri] ... Afiche ne nan 234 ... augh. >> Ye! Se te -