[Powered by Google Translate] [Duuma Serĉu] [Patrick Schmid - Universitato Harvard] [Jen CS50. - CS50.TV] 

Se mi donis al vi liston de Disney karaktero nomojn en alfabeta ordo kaj demandis vin trovi Mickey Mouse, kiel vi irados tra faras tion? Unu evidenta maniero estus skani la listo de la komenco kaj kontrolu ĉiun nomon por vidi se ĝi estas Mickey. Sed kiel vi legas Aladino, Alicia, Ariel, kaj tiel plu, vi rapide rimarkas ke ekde la fronto de la listo ne estis bona ideo. Konsentite, eble vi devus komenci labori malantaŭen de la fino de la listo. Nun vi legis Tarzan, Stitch, Snow White, kaj tiel plu. Ankoraŭ, ĉi tio ne ŝajnas kiel la pli bona maniero por iri sur ĝi. 

Nu, alia vojo, kiun vi povus iri pri fari ĉi estas provi mallarĝigi malsupren la listo de nomoj kiuj vi devas rigardi. Ĉar vi scias, ke ili estas en alfabeta ordo, vi povus simple rigardu la nomojn en la mezo de la listo kaj kontrolu ĉu Mickey Mouse estas antaŭ aŭ post ĉi nomo. Rigardante la familinomo en la dua kolumno vi volas kompreni ke M por Mickey venas post J por Jasmine, tiel vi volas simple ignoru la unua duono de la listo. Tiam vi havus verŝajne rigardu la supron de la lasta kolumno kaj vidu, ke ĝi komencas kun Rapunzel. Mickey venas antaux Rapunzel; aspektas kiel ni povas ignori la lasta kolumno tiel. Daŭrigante la serĉo strategio, vi rapide vidas ke Mickey estas en la unua duono de la cetera listo de nomoj kaj fine trovos Mickey kaŝas inter Merlin kaj Minnie. 

Kion vi ĵus faris estis esence duuma serĉo. Kiel ĉi nomo implicas, ĝi realigas lian traserĉado strategio en duuma afero. Kion tio signifas? Nu, donita listo de ordo erojn, la duuma serĉo algoritmo faras duuma decido - maldekstra aŭ dekstra, pli granda ol aŭ malpli ol, alfabete antaŭ aŭ post - je ĉiu punkto. Nun ke ni havas nomon kiu iras kune kun ĉi tiu serĉo algoritmo, ni rigardu alian ekzemplon, sed ĉi-foje kun listo de ordo numerojn. Diru ni serĉas la numeron 144 en la listo de ordo numerojn. Ĝuste kiel antaŭe, ni trovas la numero kiu estas en la mezo - kiu en ĉi tiu kazo estas 13 - kaj vidi se 144 estas pli granda ol aŭ malpli ol 13. Ekde ĝi estas klare pli granda ol 13, ni povas ignori cxion tio estas 13 aŭ malpli kaj nur koncentriĝi sur la ceteraj duono. Ĉar ni nun havas para kvanto de eroj restis, ni simple elektu numeron kiu estas proksima al la centro. En ĉi tiu kazo ni elekti 55. Ni povis esti nur tiel facile elektita 89. Okay. Denove, 144 estas pli granda ol 55, do ni iru al la rajto. Feliĉe por ni, la sekva duona nombro estas 144, la ni serĉas. Do, por trovi 144 uzanta duuma serĉo, ni povis trovi ĝin en nur 3 paŝoj. Se ni estus uzinta lineara serĉo tie, ĝi estus prenita ni 12 paŝoj. Kiel Efektive, ekde ĉi serĉo metodo duonoj la nombro de artikoloj ĝi devas rigardi je ĉiu paŝo, ke trovos la eron ĝi serĉas en ĉirkaŭ la logo de la nombro de artikoloj en la listo. Nun kiam ni vidis 2 ekzemploj, ni rigardu iuj _pseudocode_ por rekursie funkcio kiu implementa duuma serĉo. Ekde la supro, ni vidas ke ni devas trovi funkcio kiu prenas 4 argumentoj: klavo, tabelo, min, kaj max. La ŝlosilo estas la numero kiu ni serĉas, do 144 en la antaŭa ekzemplo. Array estas la listo de nombroj kiun ni sercxas. Min kaj max estas la indeksoj de la minimuma kaj maksimuma pozicioj ke ni nuntempe rigardante. Do kiam ni komencas, min estos nulo kaj max estos la maksimuma indekso de la tabelo. Kiel ni malpligrandigi la serĉo sube, ni ĝisdatigi min kaj max esti nur la rango kiun ni daŭre serĉas in 

Ni salti al la interesa parto unua. La unua aĵo kiun ni faras estas trovi la mezpunkto, la indekso tio estas duonvoje inter la min kaj max de la tabelo, ke ni ankoraŭ konsiderante. Tiam ni rigardas la valoro de la tabelo en tiu mezpunkto situo kaj vidi se la numero kiun ni serĉas estas malpli ol tiu ŝlosilo. Se la nombro en tiu pozicio estas malpli, tiam signifas la ŝlosilo estas pli granda ol ĉiuj nombroj maldekstre de tiu pozicio. Do ni povas nomi duuma serĉo funkcio denove, sed ĉi tiu fojo ĝisdatigi la min kaj max parametroj por legi nur la duono kiu estas pli granda ol aŭ egala al la valoro ni nur rigardis. Aliflanke, se la ŝlosilo estas malpli ol la nombro en la nuna mezpunkto de la tabelo, ni volas iri al la maldekstra kaj ignori ĉiuj nombroj kiuj estas pli grandaj. Denove, ni nomas duuma serĉo sed ĉi-foje kun la gamo de min kaj max ĝisdatigita enmeti nur la suba duono. Se la valoro je la nuna mezpunkto en la tabelo estas nek pli granda ol nek pli malgranda ol la ŝlosilo, tiam devas esti egala al la ŝlosilo. Tiel, ni povas simple reveni la nuna mezpunkto indekso, kaj oni faris. Fine, tiu ĉeko jen por la kazo ke la numero ne estas vere en la tabelo de nombroj kiun ni sercxas. Se la maksimuma indekso de la gamo, ke ni serĉas estas iam malpli ol la minimumo, ke signifas, ke ni iris tro for. Ekde la nombro ne estis en la enigo tabelo, ni revenas -1 por indiki, ke nenio estis trovita. 

Vi eble rimarkis, ke por ĉi tiu algoritmo por labori, la listo de nombroj devas esti ordo. En aliaj vortoj, ni nur povas trovi 144 uzanta duuma serĉo se ĉiuj nombroj estas ordigitaj de plej malalta al plej alta. Se ĉi tiu ne estis la kazo, ni ne povus ekskludi la duono de la nombroj en ĉiu paŝo. Do ni havas 2 eblojn. Ĉu ni povas preni unsorted listo kaj ordigi ĝin antaŭ uzante duuma serĉo, aŭ ni povas certigi, ke la listo de nombroj estas ordo, kiel ni aldonu nombroj al ĝi. Tiel, anstataŭ ordigi ĝuste kiam ni devas esplori, kial ne subteni la listo ordo ĉiutempe? 

Unu maniero teni liston de nombroj ordo samtempe permesi unu por aldoni aŭ movi nombroj de ĉi tiu listo estas per uzo iun nomita duuma serĉarbo. A duuma serĉarbo estas datumstrukturo kiu havas 3 propraĵoj. Unue, la maldekstra subarbo de ajna nodo enhavas nur valoroj kiuj estas malpli ol aŭ egala al la nodo valoron. Due, la dekstra subárbol de nodo nur enhavas valorojn kiuj estas pli granda ol aŭ egala al la nodo valoron. Kaj, fine, tiel la maldekstra kaj dekstra subárboles de ĉiuj nodoj Ankaŭ estas duuma serĉo arboj. Ni rigardu ekzemplon kun la samaj numeroj ni uzis antaŭe. Por tiuj el vi, kiuj neniam vidis komputika arbo antaŭe, lasu min komenci per diras al vi ke komputika arbo kreskas suben. Jes, kontraste arboj vi kutimas, la radiko de komputika arbo estas ĉe la supro, kaj la folioj estas en la fundo. Ĉiu malgranda skatolo estas nomita nodo, kaj la nodoj estas konektitaj inter aliaj per randoj. Do la radiko de la arbo estas nodo valoron kun la valoro 13, kiu havas 2 infanoj nodoj kun la valoroj 5 kaj 34. Al subárbol estas la arbo kiu estas formita nur rigardas subsekcio de la tuta arbo. 

Ekzemple, la maldekstra subarbo de la nodo 3 estas la arbo kreita de la nodoj 0, 1, kaj 2. Do, se ni reiru al la propraĵoj de duuma serĉo arbo, ni vidas ke ĉiu nodo en la arbo sekvas ĉiuj 3 propraĵoj, nome, la maldekstra subarbo nur enhavas valorojn kiuj estas malpli ol aŭ egala al la nodo valoron; Dekstre subárbol de ĉiuj nodoj nur enhavas valorojn kiuj estas pli granda ol aŭ egala al la nodo valoron, kaj ambaŭ maldekstra kaj dekstra subárboles de ĉiuj nodoj ankaŭ estas duuma serĉo arboj. Kvankam ĉi tiu arbo aspektas malsamaj, tio estas valida duuma serĉarbo por la sama aro de nombroj. Kiel Efektive, estas multaj eblaj manieroj kiuj vi povas krei valida duuma serĉarbo el tiuj numeroj. Nu, ni reiru al la unua ni kreis. Do kion ni povas fari kun tiuj arboj? Nu, ni povas tre simple trovi la minimuma kaj maksimuma valoro. La minimuma valoroj povas troviĝi per ĉiam tuj la maldekstra ĝis estas ne pli nodoj viziti. Male, por trovi la maksimuma oni simple nur iras malsupren al la rajto je ĉiu tempo. 

Finding ajna alia nombro kiu ne estas la minimumo aŭ la maksimuma estas tiel facila. Diru ni serĉas la numeron 89. Ni simple kontrolu la valoron de ĉiu nodo kaj iru sur la maldekstra aŭ dekstra, dependanta sur ĉu la nodo valoro estas malpli ol aŭ pli granda ol la ni serĉas. Do, ekde la radiko de 13, ni vidas ke 89 estas pli granda, kaj tiel ni iros al la rajto. Tiam ni vidu la nodo por 34, kaj ni denove iros al dekstre. 89 estas ankoraŭ pli granda ol 55, do ni daŭre tuj dekstre. Ni tiam venu kun nodo kun la valoro de 144 kaj iru al la maldekstra. Jen kaj jen, 89 estas prava. 

Alia afero kiun ni povas fari estas presi ĉiuj nombroj per plenumante la inorder traversal. An inorder traversal signifas presi ĉio el la maldekstra subarbo sekvata de presi la nodo mem kaj tiam sekvis per presi ĉio el la dekstra subárbol. Ekzemple, ni prenu nian preferataj duuma serĉarbo kaj presi la nombroj en ordo ordo. Ni komencu ĉe la radiko de 13, sed antaŭ presado 13 ni devas presi ĉiu en la maldekstra subarbo. Do ni iru al 5. Ni ankoraŭ devas iri profunden malsupre en la arbo ĝis ni trovos la maldekstra plej nodo, kiu estas nulo. Post impreso nulo, ni reiru al la 1 kaj presi ke eksteren. Tiam ni iros al la dekstra subárbol, kiu estas 2, kaj presi ke eksteren. Nun ke ni faris kun tiu subárbol, ni povas reiri al la 3 kaj presi ĝin. Daŭrigante back up, ni presas la 5 kaj tiam la 8. Nun kiam ni finis la tutan lasis subárbol, ni povas presi la 13 kaj komenci labori sur la dekstra subárbol. Ni hop suben al 34, sed antaŭ presado 34 ni devas presi lian maldekstran subárbol. Do ni presi 21, tiam ni preni presi 34 kaj vizitu lian dekstran subárbol. Ekde 55 ne havas maldekstran subárbol, ni presas ĝin kaj daŭrigi liajn rajtojn subárbol. 144 havas maldekstra subarbo, kaj tiel ni presi la 89, sekvita de la 144, kaj fine la dekstra plej nodo de 233. Tie vi havas ĝin; ĉiuj nombroj estas presita el en ordo de plej malalta al plej alta. 

Aldoni ion al la arbo estas relative indolora tiel. Ĉiuj ni devas fari estas certiĝi, ke ni sekvu 3 duuma serĉarbo propraĵoj kaj poste enmeti la valoro kie estas spaco. Supozu ke ni volas enmeti la valoron de 7. Ekde 7 estas malpli ol 13, ni iru al la maldekstra. Sed estas pli granda ol 5, do ni trairi al dekstre. Ekde ĝi estas malpli ol 8 kaj 8 estas nodo folio, ni aldonos 7 al la maldekstra infano de 8. Voila! Ni aldonis kelkajn al nia duuma serĉarbo. 

Se ni povas aldoni aĵojn, ni pli bone povos forviŝi tion ankaŭ. Bedaŭrinde por ni, viŝante estas iomete pli komplika - ne tre, sed nur iomete. Estas 3 diversaj scenaroj, ke ni devas konsideri kiam viŝante elementojn de duumaj arboj de serĉo. Unue, la plej facila afero estas, ke la ero estas nodo folio. En ĉi tiu kazo, ni simple forigi ĝin kaj daŭrigi kun nia afero. Ke ni volas forviŝi la 7 por ke ni ĵus aldonis. Nu, ni simple trovi ĝin, eltiri ĝin, kaj tio estas ĝi. La sekva kazo estas se la nodo havas nur 1 infano. Ĉi tie ni povas forigi la nodon, sed ni devas unue certigi por kunligi la subárbol kiu nun forlasis parentless al la patro de la nodo ni simple forigita. Ke ni volas forviŝi 3 de niaj arbo. Ni prenu la knabeton elemento de tiu nodo kaj aligu ĝin al la patro de la nodo. En ĉi tiu kazo, ni nun alfiksanta la 1 al la 5. Tiu funkcias sen problemo ĉar ni scias, laŭ la duuma serĉarbo proprieto, ke ĉiu en la maldekstra subarbo de 3 estis malpli ol 5. Nun ke 3 estas subárbol atentas, ni povas forigi ĝin. La tria kaj lasta kazo estas la plej kompleksa. Ĉi tiu estas la kazo kiam la nodo ni volas forigi havas 2 infanojn. Por fari tion, ni unue devas trovi la nodo kiu havas la sekva plej granda valoro, interŝanĝi la du, kaj poste forigi la nodon en demando. Rimarki la nodo kiu havas la sekva plej granda valoro ne povas havi 2 idoj mem ekde ĝia maldekstra infano estus bona kandidato por la venonta pli granda. Sekve, viŝante nodo kun 2 infanoj kvantoj por interŝanĝi de 2 verticoj, kaj poste forigi estas manipulita per 1 el la 2 menciita reguloj. Ekzemple, ni diras, ke ni volas forigi la radika vertico, 13. La unua aĵo kiun ni faras estas ni trovas la venonta plej granda valoro en la arbo kiu, en ĉi tiu kazo, estas 21. Ni tiam interŝanĝi la 2 nodoj, farante 13 folio kaj 21 la centra grupo nodo. Nun ni povas simple forigi 13. 

Kiel aludis al pli frua, estas multaj eblaj manieroj fari validan duuma serĉarbo. Bedaŭrinde por ni, iuj estas pli malbona ol aliaj. Ekzemple, kio okazas kiam ni konstruos duuma serĉarbo de ordo listo de nombroj? Ĉiuj nombroj estas nur aldonis al la rajto je ĉiu paŝo. Kiam ni volas serĉi numeron, ni ne havas elekton, sed nur rigardi la rajton je ĉiu paŝo. Ĉi tiu ne estas pli bona ol lineara serĉo por nenio. Kvankam ni ne kovru ilin ĉi tie, estas aliaj, pli kompleksa, datumstrukturoj ke certigi ke ĉi tio ne okazos. Tamen, unu simpla afero kiu povas esti farita por eviti ĉi estas justaj hazarde barajar la enigo valoroj. Estas tre malverŝajne ke per hazarda hazardo barajan listo de nombroj estas ordo. Se ĉi tiu estis la kazo, kazinoj ne resti en negoco por longe. 

Tie vi havas ĝin. Vi nun scias pri duuma serĉo kaj duuma serĉo arboj. Mi estas Patrick Schmid, kaj ĉi tiu estas CS50. [CS50.TV] Unu evidenta maniero estus skani la listo de ... [pepi] ... La nombro de artikoloj ... yep [Ridas] ... Afiŝi nodo de 234 ... augh. >> Yay! Tio estis -