[Powered by Google Translate] [Binary Search] [Patrick Schmid - Harvard University] [Þetta er CS50. - CS50.TV] 

Ef ég gaf þér lista af Disney eðli nöfn í stafrófsröð og spurði þig að finna Mikki Mús, hvernig myndir þú fara að gera þetta? Ein augljós leið væri að skanna lista frá upphafi og athuga hvert nafn til að sjá hvort það er Mickey. En eins og þú lesið Aladdin, Alice, Ariel, og svo framvegis, þú munt fljótt grein fyrir því að byrja á the andlit af listanum var ekki góð hugmynd. Jæja, kannski þú ættir að byrja að vinna aftur á bak frá lokum listanum. Nú að lesa Tarzan, sauma, snjó hvítt, og svo framvegis. Samt, það virðist ekki eins og besta leiðin til að fara um hana. 

Jæja, önnur leið sem þú getur farið að gera þetta er að reyna að þrengja niður lista af nöfnum sem þú þarft til að líta á. Þar sem þú veist að þeir eru í stafrófsröð, þú gætir bara að líta á nöfn í miðjum listanum og athuga hvort Mikki Mús er fyrir eða eftir þessu nafni. Þegar litið er á síðasta nafn í öðrum dálki þú vilt skilja að M Mickey kemur eftir J fyrir Jasmine, þannig að þú vilt einfaldlega hunsa fyrri hluta listanum. Síðan sem þú vilt sennilega að líta efst í síðasta dálki og sjá að það byrjar með Rapunzel. Mickey kemur fyrir Rapunzel, lítur út eins og við getum að hunsa síðasta dálki eins og heilbrigður. Áframhaldandi leit tækni, munt þú fljótt sjá að Mickey er í fyrri hluta sem eftir lista yfir nöfn og að lokum finna Mickey felum milli Merlin og Minnie. 

Það sem þú gerðir var bara í rauninni tvöfaldur leit. Eins þetta nafn gefur til kynna, það virkar að leita stefnu sinni í a tvöfaldur efni. Hvað þýðir þetta? Jæja, í ljósi lista yfir raðað atriði, leita tvöfaldur reiknirit gerir tvöfaldur ákvörðun - vinstri eða hægri, meiri en eða minna en, í stafrófsröð áður eða eftir - á hverjum stað. Nú þegar við höfum nafn sem fer með þessa leit reiknirit, skulum líta á annað dæmi, en í þetta skiptið með lista yfir raðað númer. Segja að við séum að leita að númer 144 á þessum lista raðað númer. Rétt eins og áður, finnum við fjölda sem er í miðju - sem í þessu tilfelli er 13 - og sjá hvort 144 er meiri en eða minna en 13. Þar sem það er greinilega meiri en 13, getum við hunsa allt sem er 13 eða minna og bara einbeita sér að hinum helming. Þar sem við höfum nú jafnvel fjölda af hlutum til vinstri, við veljum einfaldlega að tala sem er nálægt miðju. Í þessu tilfelli erum við að velja 55. Við gætum hafa bara eins auðveldlega valið 89. Allt í lagi. Aftur, 144 er meira en 55, þannig að við förum til hægri. Sem betur fer fyrir okkur, næsta miðju talan er 144, sá sem við erum að leita að. Svo í röð til að finna 144 með tvöfaldur leita, erum við fær um að finna það í aðeins 3 skrefum. Ef við hefðum notað línulegan leita hér, hefði það tekið okkur 12 skref. Eins og a staðreynd, þar sem þetta leita aðferð helminga fjölda liða það þarf að líta á í hverju skrefi, það verður að finna hlutinn sem það er að leita að í um þig inn á fjölda staka í listanum. Nú þegar við höfum séð 2 dæmi, við skulum taka a líta á sumir sauðakóðanum fyrir endurkvæma fall sem útfærir tvöfaldur leit. Byrjar efst, sjáum við að við verðum að finna fall sem tekur 4 rök: lykill, array, mín og max. Lykilatriðið er tala sem við erum að leita að, svo 144 í fyrra dæmi. Array er listi yfir númer sem við erum að leita. Min og Max eru vísitölur á lágmarks og hámarks stöðu sem við erum nú að horfa á. Svo þegar við byrjum, mín verður að vera núll og Max verður hámark vísitölu fylkisins. Eins og við þrengja leitina niður, munum við uppfæra min og max að vera bara allt sem við erum enn að leita inn 

Við skulum sleppa að áhugaverður hluti fyrst. The fyrstur hlutur sem við gerum er að finna miðpunkt, vísitalan sem er miðja vegu á milli min og max í fjölda sem við erum enn að íhuga. Þá erum við að líta á gildi fylkisins á þeim miðpunkt stað og sjá hvort sú tala sem við erum að leita að er minna en þessi lykill. Ef tala á þeirri stöðu er minna, þá þýðir það að lykillinn er stærri en öll númer vinstra megin við þá stöðu. Þannig að við getum kalla tvöfaldur leita virka aftur, en í þetta skiptið að uppfæra mín og Max breytur til að lesa bara helminginn sem er meiri en eða jafnt og gildi sem við horfði bara á. Á hinn bóginn, ef lykillinn er minni en fjöldi í núverandi miðju fylkisins, við viljum fara til vinstri og hunsa allar tölur sem eru stærri. Aftur, köllum tvöfaldur leita en í þetta skiptið með ýmsum mín og Max uppfært að fela bara neðri helminginn. Ef verð á núverandi miðju í fylkinu er hvorki stærri en né minna en lykillinn, þá verður það að vera jafn á takka. Þannig getum við einfaldlega aftur núverandi miðpunkt vísitölu, og við erum að gera. Að lokum, þetta athuga hér er um að ræða að fjöldi er í raun ekki í array af tölum sem við erum að leita. Ef hámarks Vísitala svið sem við erum að leita að er alltaf minna en lágmarki, sem þýðir að við höfum gengið of langt. Þar sem fjöldi var ekki í inntak fylking, aftur við -1 benda til þess að ekkert fannst. 

Þú gætir hafa tekið eftir því að þessi reiknirit til að vinna, listi af númerum þarf að vera flokkaður. Með öðrum orðum, getum við aðeins að finna 144 með tvöfaldur leit ef allar tölur eru pöntuð frá lægsta til hæsta. Ef þetta væri ekki raunin, myndum við ekki vera fær um að útiloka helming tölurnar í hverju skrefi. Þannig að við höfum 2 möguleika. Annaðhvort getum við tekið óflokkuðu lista og raða því áður en þú notar tvöfaldur leit eða við getum verið fullviss um að listi af tölum er raðað eins og við bæta tölur til þess. Svona, í stað þess að flokka bara þegar við þurfum að leita að, hvers vegna ekki að halda lista raðað á öllum tímum? 

Ein leið til að halda lista yfir númer raðað jafnframt leyfa einn til að bæta við eða flytja númer úr þessum lista er með því að nota eitthvað sem kallast tvöfaldur leita tré. Leit tvöfaldur tré er gögn uppbygging sem hefur 3 eiginleika. Fyrst vinstri subtree hvaða hnút eru aðeins gildi sem eru minni en eða jöfn gildi hnúturinn er. Í öðru lagi, rétt subtree á hnút inniheldur aðeins gildi sem eru hærri en eða jöfn gildi hnúturinn er. Og að lokum, bæði vinstri og hægri subtrees allra hnúður eru einnig tvöfaldur tré leita. Við skulum líta á dæmi með sömu tölur sem við notuðum áður. Fyrir þá sem hafa aldrei séð tölvunarfræðinemi tré áður, Leyfðu mér að byrja með því að segja þér að vísindi tölva tré vex niður. Já, ólíkt tré sem þú ert vön að, rót á tölvunarfræði tré er efst, og leyfi eru neðst. Hver lítill kassi er kallað hnút og hnútar eru tengdir hver öðrum með brúnum. Svo er rót þessa tré hnút gildi við gildi 13, sem hefur 2 börn hnúður með gildi 5 og 34.. A subtree er tré, sem er mynduð með því að horfa á lið af öllu tré. 

Til dæmis, vinstri subtree í hnút 3 er tré búin af hnúður 0, 1 og 2. Svo ef við förum aftur til eiginleika leita tvöfaldur tré, sjáum við að hver hnútur í trénu samræmi við alla 3 eiginleika, þ.e., vinstri subtree inniheldur aðeins gildi sem eru minna en eða jafnt og gildi hnúturinn er; rétt subtree allra hnúður inniheldur aðeins gildi sem eru stærri en eða jöfn gildi hnúturinn er, og bæði til vinstri og hægri subtrees allra hnúta eru einnig tvöfaldur leita tré. Þó að þessi tré lítur öðruvísi, þetta er gild tvöfaldur leita tré fyrir sama mengi af tölum. Eins og a staðreynd, there ert margir mögulegar leiðir sem þú getur búið gilt tvöfaldur leita tré frá þessum tölum. Jæja, við skulum fara aftur til fyrsta við bjuggum. Og hvað getum við gert við þessum trjám? Jæja, við getum mjög einfaldlega að finna lágmarks og hámarks gildi. Lágmarksgildi má finna með því að alltaf að fara til vinstri þangað til það eru ekki fleiri hnútar til að heimsækja. Hins vegar að finna hámarks einfaldlega fer bara niður til hægri á hverjum tíma. 

Finna önnur tala sem er ekki lágmarks-eða hámarks er alveg jafn auðvelt. Segja að við erum að leita að númer 89.. Við athuga einfaldlega gildi hvern hnút og fara til vinstri eða hægri fer eftir því hvort gildið hnúturinn er minna en eða meira en sá sem við erum að leita að. Svo, byrja á the rót af 13, sjáum við að 89 er meira og svo förum við til hægri. Þá sjáum við hnút í 34, og aftur við að fara til hægri. 89 er enn meiri en 55, þannig að við höldum áfram að fara til hægri. Við komum svo upp með hnút með verðmæti 144 og fara til vinstri. Lo og sjá, 89 er rétt þar. 

Annar hlutur sem við getum gert er að prenta út öll númer með því að framkvæma á inorder traversal. An inorder traversal þýðir að prenta allt út í vinstri subtree eftir prentun hnúturinn sig og þá á eftir að prenta allt út í rétt subtree. Til dæmis, við skulum taka uppáhalds tvöfaldur leita tré okkar og prenta út tölur í raðað röð. Við byrjum á the rót af 13, en áður en prentun 13 verðum við að prenta út allt í vinstri subtree. Svo við förum í 5. Við höfum enn að fara dýpra ofan í trénu þar sem við finna vinstri-mest hnút, sem er núll. Eftir prentun núll, förum við aftur upp á 1 og prenta það út. Þá erum við að fara til hægri subtree, sem er 2, og prenta það út. Nú þegar við erum búin með það subtree, getum við farið aftur upp í 3 og prenta það út. Áframhaldandi aftur upp, prenta við 5 og þá 8. Nú þegar við höfum lokið öllu eftir subtree, getum við prentað út 13 og byrja að vinna á rétt subtree. Við hoppa niður í 34, en áður en prentun 34 við þurfum að prenta út vinstri subtree þess. Þannig að við að prenta út 21, þá fáum við að prenta út 34 og fara rétt subtree þess. Þar sem 55 hefur engin vinstri subtree, prenta við það út og halda áfram til hægri subtree þess. 144 hefur vinstri subtree, og svo við að prenta út 89, á eftir 144, og loks hægri mest hnút 233. There þú hafa það, allar tölur eru prentaðar út í röð frá lægstu til hæsta. 

Bæti einhverju við tré er tiltölulega sársaukalaus eins og heilbrigður. Allt sem við þurfum að gera er að tryggja að við fylgjum 3 tvöfaldur leita tré eignir og þá setja gildi þar er pláss. Segjum að við viljum að setja gildi 7. Síðan 7 er minna en 13, förum við til vinstri. En það er meira en 5, þannig að við að fara yfir til hægri. Þar sem það er minna en 8 og 8 er blaða hnút, bæta við 7 til vinstri barn 8. Voila! Við höfum bætt við fjölda til tvöfaldur leita tré okkar. 

Ef við getum bætt það, að við betur í stakk búnir til að eyða hlutum eins og heilbrigður. Því miður fyrir okkur, að eyða er svolítið flóknara - ekki mikið, en bara svolítið. Það eru 3 mismunandi aðstæður sem við verðum að íhuga þegar þú eyðir þætti frá tvíundartré leit. First, auðveldasta málið er að þátturinn er blaða hnút. Í þessu tilviki, eyða við einfaldlega það og fara með viðskipti okkar. Segjum að við viljum eyða 7 sem við lögðum bara. Jæja, við finnum einfaldlega það, fjarlægja það, og það er það. Næsta mál er ef hnúturinn hefur aðeins 1 barn. Hér getum við að eyða hnút, en við verðum fyrst að ganga úr skugga um að tengja subtree sem er nú eftir foreldralausra til foreldris í hnút við eytt bara. Segjum að við viljum eyða 3 af trénu okkar. Við tökum barnið þáttur þeirrar hnút og festa það við foreldri hnút. Í þessu tilfelli erum við nú að festa 1 til 5. Þetta virkar án vandamál vegna þess að við vitum, samkvæmt leita tvíundartré eign, að allt í vinstri subtree af 3 var minna en 5. Nú er 3 subtree er gætt af, við getum eytt. Þriðja og síðasta málið er flóknasta. Þetta er raunin þegar hnúturinn við viljum að eyða á 2 börn. Til að gera þetta, verðum við fyrst að finna hnút sem hefur næstu stærsta gildi, skipti tvö, og síðan eyða hnút ræðir. Takið hnúturinn sem hefur næsta stærsta gildi getur ekki haft 2 börn sig frá vinstri barnið hennar væri betri frambjóðandi fyrir næsta stærsta. Því að eyða hnút með 2 börn nemur swap 2 hnúta, og þá að eyða er stjórnað af 1 af 2 framangreindum reglum. Til dæmis, segjum skulum við viljum eyða rót hnút, 13. The fyrstur hlutur sem við gerum er að við að finna næsta stærsta gildi í trénu sem í þessu tilfelli er 21. Við skipti síðan á 2 hnúta, að 13 lauf og 21 Mið hópur hnút. Nú getum við einfaldlega eytt 13. 

Eins benti á áðan, þá eru margar mögulegar leiðir til að gera gilt tvöfaldur leita tré. Því miður fyrir okkur, sumir eru verri en aðrir. Til dæmis, hvað gerist þegar við að byggja upp tvöfaldur leita tré frá raðaða lista af tölum? Allar tölur eru bara bætt við til hægri á hverju skrefi. Þegar við viljum að leita að tala, við höfum ekkert val en bara að líta á the réttur í hverju skrefi. Þetta er ekki betri en línuleg leit yfirleitt. Þó við munum ekki ná þeim hér, það eru hins vegar flóknari, gögn uppbygging sem tryggja að þetta gerist ekki. Hvernig sem, einn einfaldur hlutur sem hægt er að gera til að koma í veg fyrir þetta er að bara af handahófi uppstokkun inntak gildi. Það er mjög ólíklegt að með því að handahófi tækifæri sem stokkuð lista af tölum er raðað. Ef þetta væri raunin, spilavítum myndi ekki vera í viðskiptum lengi. 

There þú hafa það. Þú veist nú um tvöfaldur leit og tvöfaldur leita tré. Ég er Patrick Schmid, og þetta er CS50. [CS50.TV] Ein augljós leið væri að skanna lista frá ... [píp] ... Fjöldi hluta ... Já [Hlær] ... Senda hnút 234 ... augh. >> Yay! Það var -