[Powered by Google Translate] [Fittex Binarju] [Patrick Schmid - Università ta 'Harvard] [Dan huwa CS50. - CS50.TV] 

Jekk jiena ħadt lista ta 'ismijiet karattru Disney f'ordni alfabetiku u talab li inti ssib Mickey Mouse, kif tista 'tmur dwar kif isir dan? Mod wieħed ovvju ikun li skennjati l-lista mill-bidu u jivverifikaw kull isem biex tara jekk huwa Mickey. Imma kif inti taqra Aladdin, Alice, Ariel, u oħrajn, inti ser malajr tirrealizza li jibdew fuq quddiem tal-lista ma tkunx idea tajba. Okay, forsi inti għandek tibda taħdem lura mill-aħħar tal-lista. Issa inti taqra Tarzan, stitch, Snow White, u oħrajn. Still, dan ma jidher l-aħjar mod biex imorru dwar dan. 

Ukoll, ieħor mod li inti tista 'tmur dwar kif isir dan huwa li tipprova biex iċekknu l-lista ta 'ismijiet li inti għandek tfittex fil. Peress li inti taf li dawn huma fl-ordni alfabetiku, inti tista 'biss tħares lejn l-ismijiet fin-nofs tal-lista u jivverifika jekk Mickey Mouse tkun qabel jew wara dan l-isem. Ħarsa lejn l-isem aħħar fit-tieni kolonna youd tirrealizza li M għal Mickey wasal wara J għal Jasmine, hekk youd sempliċiment tinjora l-ewwel nofs tal-lista. Imbagħad youd probabilment tħares lejn il-quċċata tal-aħħar kolonna u tara li jibda bil Rapunzel. Mickey jasal quddiem Rapunzel; qisu nistgħu ninjoraw l-aħħar kolonna ukoll. Jitkompla l-istrateġija tat-tiftix, inti ser malajr tara li Mickey huwa fl-ewwel nofs tal-lista li jifdal ta 'l-ismijiet u finalment issib Mickey ħabi bejn Merlin u Minnie. 

Dak li inti biss ma kien tfittxija bażikament binarja. Kif dan l-isem jimplika, li jwettaq l-istrateġija tiftix tagħha fi kwistjoni binarja. Xi jfisser dan? Ukoll, tingħata lista ta 'oġġetti magħżula, l-algoritmu tfittxija binarja jagħmel deċiżjoni binarja - lemin jew xellug, akbar minn jew inqas minn, alfabetikament qabel jew wara - f'kull punt. Issa li għandna isem li jmur flimkien ma 'dan algoritmu tfittxija, ejja nħarsu lejn eżempju ieħor, iżda din id-darba ma 'lista ta' numri magħżula. Say aħna qegħdin ifittxu l-għadd 144 f'din il-lista ta 'numri magħżula. Eżatt bħal qabel, insibu n-numru li fil-nofs - li f'dan il-każ huwa 13 - u ara jekk 144 ikun ikbar jew inqas minn 13. Peress li huwa ċar ikbar minn 13, nistgħu ninjoraw dak kollu li huwa 13 jew anqas u biss jikkonċentraw fuq il-nofs l-ieħor. Peress li issa għandna anke numru ta 'oġġetti tax-xellug, aħna sempliċiment jagħżlu numru li huwa qrib il-linji. F'dan il-każ nagħżlu 55. Aħna setgħet daqstant faċilment magħżula 89. Okay. Għal darb'oħra, 144 huwa akbar minn 55, hekk immorru lejn il-lemin. Fortunatament għalina, in-numru tan-nofs li jmiss huwa 144, l-waħda aħna qed tfittex. Allura biex isibu 144 użu ta 'tfittxija binarja, aħna kapaċi li ssib fil biss 3 passi. Jekk aħna użaw tfittxija lineari hawn, kien jieħu us 12 passi. Bħala kwistjoni ta 'fatt, peress li dan il-metodu tfittxija nofsijiet-numru ta' oġġetti hija għandha tħares lejn f'kull stadju, se ssib l-oġġett li qed tfittex f'madwar l-ġurnal tan-numru ta 'oġġetti fil-lista. Issa li aħna stajt tidher 2 eżempji, ejja tagħti ħarsa lejn xi pseudocode għal funzjoni rikursivi li timplimenta tfittxija binarja. Tibda fil-quċċata, naraw li għandna biex isibu funzjoni li jieħu 4 argumenti: , ewlenin array, min, u max. Il-muftieħ huwa n-numru li qed infittxu, hekk 144 fl-eżempju preċedenti. Array hija l-lista ta 'numri li aħna tiftix. Min u max huma l-indiċijiet tal-pożizzjonijiet minimi u massimi li aħna bħalissa tfittex fuq. Allura meta nibdew, min se jkun żero u max se jkun l-indiċi massimu tal-firxa. Kif aħna dejqa-tfittxija isfel, aħna se taġġorna min u max li jkun biss il-medda li għadna tfittex pulzieri 

Ejja skip għall-parti interessanti ewwel. L-ewwel ħaġa li għandna tagħmel hu li ssib l-punt fokali, l-indiċi li huwa fin-nofs bejn il-min u max ta 'l-array li għadna jikkunsidraw. Imbagħad aħna nħarsu lejn il-valur ta 'l-array f'dak il-post punt tan-nofs u ara jekk in-numru li qed infittxu huwa inqas minn dak ċavetta. Jekk in-numru f'dik il-pożizzjoni huwa inqas, allura dan ifisser il-muftieħ huwa akbar minn numri kollha lejn ix-xellug ta 'dik il-pożizzjoni. Allura nistgħu sejħa funzjoni ta 'tfittxija binarja mill-ġdid, iżda din id-darba l-aġġornament il-min u parametri max li taqra biss in-nofs li huwa ikbar minn jew ugwali għall-valur aħna biss ħares lejn. Min-naħa l-oħra, jekk il-muftieħ huwa anqas minn numru fil-punt tan-nofs attwali tal-firxa, irridu imorru lejn ix-xellug u jinjora numri kollha li huma akbar. Għal darb'oħra, nagħmlu sejħa tfittxija binarja iżda din id-darba mal-firxa ta 'min u max aġġornata li tinkludi biss l-nofs t'isfel. Jekk il-valur fil-punt tan-nofs attwali fil-firxa la akbar minn lanqas iżgħar minn l-ewlenin, allura għandu jkun ugwali għad-ċavetta. Għalhekk, nistgħu sempliċement lura l-indiċi punt fokali attwali, u aħna qed isir. Fl-aħħarnett, dan il-kontroll hawnhekk huwa għall-każ li n-numru ma tkunx attwalment fil-firxa ta 'numri aħna tiftix. Jekk l-indiċi massimu tal-grad li aħna qed ifittxu għall- huwa dejjem anqas mill-minimu, dan ifisser li aħna stajt marret wisq. Peress li n-numru ma kienx fil-firxa input, nerġgħu lura -1 li jindika li xejn ma nstab. 

Inti jista 'jkollok ndunat li għal dan il-algoritmu li taħdem, il-lista ta 'numri għandha tkun magħżula. Fi kliem ieħor, nistgħu biss isibu 144 bl-użu tfittxija binarju jekk il-numri huma ordnati mill-iżgħar sa l-ogħla. Jekk dan ma jkunx il-każ, aħna mhux se tkun tista 'teskludi nofs il-numri f'kull pass. Allura aħna għandna 2 għażliet. Jew nistgħu nieħdu lista mhux magħżul u sort qabel tuża tfittxija binarja, jew nistgħu kun żgur li l-lista ta 'numri huwa magħżul kif aħna żid in-numri lilha. Għalhekk, minflok l-għażla biss meta għandna biex tfittex, għaliex ma żżomm il-lista magħżula fil-ħinijiet kollha? 

Mod wieħed biex iżommu lista ta 'numri magħżula filwaqt li fl-istess ħin jippermettu wieħed biex iżżid jew jiċċaqalqu numri minn din il-lista huwa bl-użu xi ħaġa imsejħa siġra tfittxija binarja. A siġra tfittxija binarju huwa struttura tad-data li għandha 3 proprjetajiet. L-ewwel, il-subtree xellug ta 'kwalunkwe node fih valuri biss li huma inqas minn jew ugwali għall-valur tal-node s. It-tieni nett, id-dritt subtree ta 'nodu fiha biss valuri li huma akbar minn jew ugwali għall-valur tal-node s. U, finalment, kemm il-subtrees xellug u lemin ta 'kull għoqiedi huma wkoll siġar tat-tiftix binarja. Ejja nħarsu lejn eżempju bl-istess numri aħna użati qabel. Għal dawk minnkom li qatt ma raw siġra xjenza tal-kompjuter qabel, let me tibda billi tghidlek li siġra xjenza tal-kompjuter tikber isfel. Iva, b'differenza siġar inti mdorri, l-għerq ta 'siġra xjenza tal-kompjuter hija fil-quċċata, u l-weraq huma fil-qiegħ. Kull kaxxa ftit jissejjaħ node, u l-lymph huma konnessi ma 'xulxin mill-truf. Allura l-għerq ta 'din is-siġra hija valur node mal-valur 13, li tkun 2 nodi tat-tfal mal-valuri 5 u 34. A subtree hi s-siġra li huwa ffurmat biss billi tħares lejn subsezzjoni tas-siġra kollu. 

Per eżempju, il-subtree xellug tal-magna 3 node huwa l-siġra maħluqa mill-lymph 0, 1, u 2. Għalhekk, jekk immorru lura għall-proprjetajiet ta 'siġra tfittxija binarju, naraw li kull node fil-siġra jikkonforma mal-proprjetajiet kollha 3, jiġifieri, the subtree xellug fih biss valuri li huma inqas minn jew ugwali għal valur tal-node ta; id-dritt subtree ta 'l-lymph fiha biss valuri li huma ikbar minn jew ugwali għall-valur tal-node-organizzazzjoni u subtrees kemm tax-xellug u lemin ta 'kull lymph wkoll huma siġar tat-tiftix binarja. Għalkemm din is-siġra jistenna differenti, din hija siġra valida tfittxija binarju għall-istess sett ta 'numri. Bħala kwistjoni ta 'fatt, hemm bosta modi possibbli li inti tista' toħloq validu binarja tfittxija siġra minn dawn in-numri. Ukoll, ejja mur lura għall-ewwel waħda ħloqna. Allura x'nistgħu nagħmlu ma 'dawn is-siġar? Well, nistgħu ħafna sempliċement issib il-valuri minimi u massimi. Il-valuri minimi tista 'tinstab billi dejjem tmur lejn ix-xellug sakemm ma jkunx hemm għoqiedi mhux aktar li jżuru. Bil-maqlub, biex isibu l-waħda massimu sempliċiment biss jinżel lejn il-lemin f'kull ħin. 

Tfittxija kwalunkwe numru ieħor li mhuwiex il-minimu jew il-massimu huwa daqstant faċli. Say aħna qed tfittex għall-numru 89. Aħna sempliċiment jivverifika l-valur ta 'kull node u jmorru lejn ix-xellug jew il-lemin, skond jekk il-valur tal-node hija inqas minn jew akbar minn l-waħda aħna qed tfittex. Allura, tibda fil-għerq ta '13, naraw li 89 hija akbar, u għalhekk immorru lejn il-lemin. Imbagħad naraw il-node għal 34, u għal darb'oħra immorru lejn il-lemin. 89 għadu akbar minn 55, hekk aħna tkompli tmur lejn il-lemin. Aħna mbagħad toħroġ bi node mal-valur ta '144 u jmorru lejn ix-xellug. Lo u behold, 89 huwa dritt hemmhekk. 

Ħaġa oħra li nistgħu nagħmlu huwa jistampa numri kollha billi jwettqu traversal inorder. L traversal inorder ifisser li jistampa kollox fil-subtree xellug segwita mill-istampar tal-node innifsu u mbagħad segwit minn stampar kollox fl-dritt subtree. Per eżempju, ejja tagħti siġra favoriti tagħna tfittxija binarja u jistampa in-numri fl-ordni magħżula. Nibdew fil-għerq ta '13, iżda qabel l-istampar 13 rridu li jistampa kollox fil-subtree xellug. Allura aħna jmorru sa 5. Għad għandna biex tmur fil-fond fl-siġra sakemm insibu l-node tax-kbira, li huwa żero. Wara l-istampar żero, immorru lura sa l-1 u jistampa l barra. Imbagħad immorru l-subtree dritt, li huwa 2, u jistampa l barra. Issa li aħna qed isir ma 'dan subtree, nistgħu mmorru lura sa l-3 u ipprintjaha. Kontinwa back up, aħna jistampaw il-5 u allura l-8. Issa li aħna temmew l kollu xellug subtree, nistgħu jistampa l-13 u jibdew jaħdmu fuq il-lemin subtree. Aħna tal-ħops sa 34, iżda qabel l-istampar 34 għandna li jistampa subtree xellug tagħha. Allura aħna jistampa 21; allura aħna nikseb li jistampa 34 u żur dritt subtree tagħha. Peress li 55 m'għandha l-ebda subtree xellug, aħna ipprintjaha u tkompli fuq li subtree dritt tiegħu. 144 għandha subtree xellug, u hekk aħna jistampa l-89, segwita mill-144, u finalment il-node dritt aktar ta '233. Hemm ikollok; il-numri huma stampati fl-ordni mill-iżgħar sa l-ogħla. 

Żieda xi ħaġa li l-siġra huwa relattivament mingħajr tbatija kif ukoll. Kollha għandna tagħmel hu li tagħmel żgur li aħna isegwu 3 proprjetajiet binarji tas-siġar tat-tiftix u mbagħad daħħal l-valur fejn ikun hemm spazju. Ejja ngħidu aħna tixtieq li daħħal il-valur ta '7. Peress 7 huwa inqas minn 13, immorru lejn ix-xellug. Iżda huwa ikbar minn 5, hekk aħna travers il-lemin. Peress li huwa inqas minn 8 u 8 hija node weraq, aħna żid 7 lill-wild xellug ta '8. Voila! Imxejna miżjud f'numru li siġra tagħna tfittxija binarja. 

Jekk aħna tista 'żżid affarijiet, aħna aħjar tkun tista' tħassar l-affarijiet ukoll. Sfortunatament għalina, tħassir huwa ftit aktar kumplikata - mhux wisq, iżda biss ftit. Hemm 3 xenarji differenti li għandna biex jikkunsidraw meta tħassir elementi minn siġar tat-tiftix binarja. L-ewwel, il-każ huwa eħfef li l-element huwa node weraq. F'dan il-każ, aħna sempliċiment iħassarha u jmorru fuq man-negozju tagħna. Say irridu li titħassar il-7 li aħna biss miżjud. Well, aħna sempliċiment jsibuha, neħħi dan, u li hu. Il-każ li jmiss hija jekk l-node għandha biss 1 tat-tfal. Hawnhekk nistgħu tħassar l-node, iżda aħna l-ewwel ikollhom jagħmlu ċert biex jgħaqqdu l-subtree li issa qed jitħalla f'idejn parentless lill-ġenitur ta 'l-node aħna biss mħassar. Say irridu li tħassar 3 minn siġra tagħna. Nieħdu l-element minuri ta 'dik node u jagħtu lill-ġenitur ta' l-node. F'dan il-każ, aħna qed issa jitwaħħal l-1 għall-5. Dan jaħdem mingħajr problema għaliex aħna nafu, skond il-binarju tfittxija siġra tal-proprjetà, li kollox fil-subtree xellug ta '3 kien inqas minn 5. Issa li l-subtree 3 huwa tittieħed kura ta ', nistgħu iħassarha. Il-każ tielet u finali hija l-aktar kumplessi. Dan huwa l-każ meta l-node irridu li titħassar għandu 2 tfal. Sabiex tagħmel dan, aħna l-ewwel iridu jsibu l-node li għandu l-valur li jmiss akbar, tpartit it-tnejn, u imbagħad tħassar l-node in kwistjoni. Avviż tal-node li għandu l-valur li jmiss akbar ma jistax ikollok 2 tfal stess peress tifel xellug tagħha tkun kandidat aħjar għall-ikbar li jmiss. Għalhekk, it-tħassir node ma '2-tfal jammonta għal iskambji ta '2 għoqiedi, u imbagħad tħassar tiġi ttrattata mill-1 tar-regoli msemmija qabel 2. Per eżempju, ejja ngħidu li rridu li jitħassar il-node għerq, 13. L-ewwel ħaġa li nagħmlu huwa insibu l-valur li jmiss akbar fl-siġra li, f'dan il-każ, huwa 21. Aħna mbagħad tpartit l-lymph 2, tagħmel 13 a werqa u 21-node grupp ċentrali. Issa nistgħu sempliċement titħassar 13. 

Kif allużjoni għall preċedenti, hemm bosta modi possibbli biex tagħmel siġra valida tfittxija binarja. Sfortunatament għalina, xi wħud huma agħar minn oħrajn. Per eżempju, dak li jiġri meta aħna nibnu siġra tfittxija binarju minn lista magħżula ta 'numri? Kollha numri huma biss miżjud għad-dritt f'kull pass. Meta aħna trid tfittex għal numru, għandna l-ebda għażla ħlief biss li tħares lejn il-lemin f'kull pass. Dan mhux aħjar minn tfittxija lineari fil-livelli kollha. Għalkemm aħna mhux se jkopri lilhom hawnhekk, hemm oħrajn, aktar kumplessi, data strutturi li jagħmlu ċert li dan ma jseħħx. Madankollu, ħaġa waħda sempliċi li jista 'jsir biex jiġi evitat dan huwa biss saltwarjament shuffle-valuri ta 'input. Huwa ferm improbabbli li b'kumbinazzjoni każwali lista shuffled ta 'numri huwa magħżul. Jekk dan kien il-każ, casinos ma jibqgħu fin-negozju għal żmien twil. 

Hemm ikollok. Inti issa taf dwar tiftix binarju u siġar tfittxija binarja. Jien Patrick Schmid, u dan huwa CS50. [CS50.TV] Mod wieħed ovvju ikun li skennjati l-lista minn ... [ħoss] ... L-għadd ta 'oġġetti ... Yep [Laughs] ... Post node ta '234 ... augh. ! Yay >> Dan kien -