[Powered by Google Translate] [Kërko Binary] [Patrick Schmid - Universiteti i Harvardit] [Kjo është CS50. - CS50.TV] 

Nëse unë ju dha një listë të emrave të karakterit Disney në rend alfabetik dhe i kërkoi që ju të gjeni Mickey Mouse, si do të shkojë për të bërë këtë? Një mënyrë e qartë do të jetë për të scan listë nga fillimi dhe kontrolloni çdo emër për të parë nëse ajo është Mickey. Por si ju lexoni Aladdin, Alice, Ariel, dhe kështu me radhë, ju do të shpejt të kuptojë se duke filluar në pjesën e përparme të listës nuk ishte një ide e mirë. Mirë, ndoshta ju duhet të fillojnë të punojnë prapa nga fundi i listës. Tani ju lexoni Tarzan, thur, borë të bardhë, dhe kështu me radhë. Megjithatë, kjo nuk duket si mënyra më e mirë për të shkuar në lidhje me të. 

E pra, një tjetër mënyrë që ju mund të shkoni për të bërë këtë është që të përpiqen për të ngushta poshtë lista e emrave që ju duhet të shikoni në. Që ju e dini se ata janë në rend alfabetik, ju mund të shikoni vetëm në emrat e në mes të listës dhe kontrolloni nëse Mickey Mouse është para apo pas këtij emri. Kërkoni në emrin e fundit në kolonën e dytë ju do të kuptojë se M për Mickey J vjen pas për Jasmine, kështu që ju do të thjesht injoroni gjysmën e parë të listës. Atëherë ju ndoshta do të shikoni në krye të kolonës e fundit dhe të shohim se ajo fillon me Rapunzel. Mickey vjen para Rapunzel, duket sikur ne mund të injorojë kolonën e fundit si. Vazhdimi strategjinë e kërkimit, ju do të shpejt të shihni se Mickey është në gjysmën e parë të listës së mbetur të emrave dhe më në fund të gjeni Mickey fshehur mes Merlin dhe Minnie. 

Çfarë ju vetëm e bëri ishte kërko thelb binar. Si kjo emri nënkupton, ajo kryen strategjinë e saj të kërkoni në një çështje binar. Çfarë do të thotë kjo? E pra, jepet një listë e artikujve të renditura, kërko binar algorithm merr një vendim binar - majtas ose djathtas, më i madh sesa ose më pak se, alfabetike para ose pas - në çdo pikë. Tani që ne kemi një emër që shkon së bashku me këtë algorithm e kërkimit, le të shohim një shembull tjetër, por këtë herë me një listë të numrave të renditura. Thonë se ne jemi duke kërkuar për numrin 144 në këtë listë të numrave të renditura. Ashtu si më parë, kemi gjetur numrin që është në mes - e cila në këtë rast është 13 - dhe të shohim nëse është më i madh se 144 apo më pak se 13. Që nga ajo është e qartë më i madh se 13, ne mund të injorojë gjithçka që është 13 ose më pak dhe vetëm të përqëndrohet në gjysmën e mbetur. Që nga viti ne kemi tani një numër të artikujve edhe majtas, ne thjesht zgjidhni një numër që është i afërt në mes. Në këtë rast kemi zgjedhur 55. Ne mund të kemi po aq e lehtë zgjedhur 89. Rregull. Përsëri, 144 është më i madh se 55, kështu që ne do të shkojmë në të djathtë. Për fat të mirë për ne, numri ardhshëm mesme është 144, një ne jemi duke kërkuar për të. Pra, në mënyrë që të gjeni një kërkim duke përdorur 144 binar, ne jemi në gjendje për të gjetur atë në vetëm 3 hapa. Në qoftë se ne do të kemi përdorur kërkim linear këtu, kjo do të marrë hapa na 12. Si një çështje të vërtetë, pasi kjo metodë kërkim gjysmave numrin e artikujve ajo ka për të parë në në çdo hap, ajo do të gjeni pika ajo është në kërkim për të në lidhje me log të numrit të artikujve në listë. Tani që ne kemi parë 2 shembuj, le të marrin një vështrim në disa pseudokod për një funksion rekursiv që zbaton kërkimin binar. Duke filluar në krye, shohim se kemi për të gjetur një funksion që merr 4 argumente: , kyç array, min, max dhe. Çelësi është numri që ne jemi duke kërkuar për të, kështu 144 në shembullin e mëparshëm. Array është lista e numrave që ne jemi në kërkim. Min dhe max janë indekset e pozicioneve minimale dhe maksimale se ne jemi aktualisht në kërkim në. Kështu që kur kemi filluar, do të jetë zero min dhe max do të jetë indeksi maksimal të grup. Siç kemi ngushtuar kërkimin poshtë, ne do update min dhe max të jetë vetëm varg që ne jemi ende në kërkim in 

Le të kaloni në pjesën interesante parë. Gjëja e parë që ne bëjmë është të gjeni midpoint, indeksi që është në gjysmë të rrugës në mes të min dhe max e grup që ne jemi ende duke konsideruar. Atëherë ne shikojmë në vlerën e vektorit në atë vend midpoint dhe të shohim nëse numri që ne jemi duke kërkuar për të është më pak se ajo kyç. Nëse numri në atë pozicion është më pak, atëherë kjo do të thotë se çelësi është më i madh se të gjithë numrat në të majtë të atij pozitë. Kështu që ne mund ta quajmë funksion binar kërkimit përsëri, por këtë herë përditësimin e min dhe parametrat max për të lexuar vetëm gjysmën e që është më e madhe se ose e barabartë me vlerën ne vetëm shikoi. Nga ana tjetër, nëse çelësi është më pak se numri në midpoint e tanishme e array, ne duam të shkojnë në të majtë dhe të injorojë të gjitha numrat që janë më të mëdha. Përsëri, ne e quajmë kërkimin binar, por këtë herë me varg e min dhe max UPDATED të përfshijë vetëm gjysma e ulët. Nëse vlera në midpoint e tanishme në grup nuk është as madhe se as më e vogël se çelësi, atëherë ajo duhet të jetë e barabartë me kyç. Kështu, ne thjesht mund të kthehen indeksin aktual midpoint, dhe ne jemi duke bërë. Së fundi, ky çek këtu është për rastet kur numri nuk është në të vërtetë në rrjet të numrave ne jemi në kërkim. Nëse indeksi maksimal i varg që ne jemi duke kërkuar për është gjithnjë e më pak se minimale, që do të thotë se ne kemi shkuar shumë larg. Që nga numri nuk ishte në rrjet input, ne kthim -1 për të treguar se asgjë nuk u gjet. 

Ju mund të keni vënë re se për këtë algoritëm për të punuar, lista e numrave duhet të zgjidhet. Me fjalë të tjera, ne mund të gjeni vetëm 144 duke përdorur search binar nëse të gjithë numrat janë urdhëruar nga më të ulët për më të larta. Nëse kjo nuk ishte kështu, ne nuk do të jetë në gjendje për të përjashtuar gjysmën e numrave në çdo hap. Pra, ne kemi 2 opsione. Ose ne mund të marrë një listë Unsorted dhe zgjidhur atë para duke përdorur search binar, ose ne mund të sigurohemi se lista e numrave është renditur si ne shtoni numra për të. Kështu, në vend të zgjidhja vetëm kur kemi për të kërkuar, pse nuk e mbajnë listën e renditura në çdo kohë? 

Një mënyrë për të mbajtur një listë të numrave të zgjidhet, ndërsa në të njëjtën kohë duke i lejuar një për të shtuar apo veprim numrat nga kjo listë është duke përdorur diçka që quhet një pemë binare kërkim. Një kërkim binar pemë është një strukturë e të dhënave që ka 3 veti. Së pari, subtree e majtë të çdo nyje përmban vlera vetëm që janë më pak se ose e barabartë me vlerën nyjen së. Së dyti, e drejta e një subtree nyje përmban vetëm vlerat që janë më të mëdha se ose e barabartë me vlerën nyjen së. Dhe, në fund, të dyja tregoje majtë dhe të djathtë të të gjitha nyjet edhe pemë binare e kërkimit. Le të shikojmë një shembull me të njëjtin numër kemi përdorur më herët. Për ata prej jush që kurrë nuk kanë parë një pemë përpara shkenca kompjuterike, më lejoni të filloj duke ju thënë se një shkencë kompjuterike pema rritet poshtë. Po, ndryshe nga pemët që janë mësuar të, rrënja e një peme shkenca kompjuterike është në krye, dhe gjethet janë në fund. Çdo kuti të vogël quhet një nyje, dhe nyjet janë të lidhura me njëri-tjetrin nga skajet. Pra, rrënja e kësaj peme është një vlerë nyje me vlerë 13, i cili ka 2 fëmijë nyjet me vlerat 5 dhe 34. Një subtree është pemë që është e përbërë vetëm duke shikuar në një nënseksioni e pemë të tërë. 

Për shembull, subtree majtë e 3 nyjen është pemë e krijuar nga nyjet 0, 1, dhe 2. Pra, nëse ne do të shkojmë përsëri në pronat e një pemë kërkim dyor, ne shohim se çdo nyje në pemë përputhet me të gjitha pronat 3, domethënë, the subtree majtë përmban vetëm vlerat që janë më pak se ose e barabartë me vlerën nyjen-së; e drejta e të gjitha nyjet subtree përmban vetëm vlerat që janë më të mëdha se ose e barabartë me vlerën nyjen së dhe subtrees dy majtë dhe të djathtë të të gjitha nyjet janë gjithashtu pemë binare e kërkimit. Edhe pse kjo pemë duket ndryshe, kjo është një kërkim i vlefshëm binar pemë për të njëjtat e numrave. Si një çështje të vërtetë, ka shumë mënyra të mundshme që ju mund të krijojë e vlefshme kërkimit binar pema nga këto numra. E pra, le të kthehemi në një të parë kemi krijuar. Pra, çfarë mund të bëjmë me këto pemë? E pra, ne mund të gjeni shumë thjesht vlerat minimale dhe maksimale. Vlerat minimale mund të gjenden duke shkuar gjithnjë në të majtë derisa ka nyje ka më shumë për të vizituar. Anasjelltas, për të gjetur një maksimal thjesht vetëm shkon poshtë për të drejtën në çdo kohë. 

Gjetur ndonjë numër tjetër që nuk është minimale apo maksimale është po aq e lehtë. Thonë se ne jemi duke kërkuar për numrin 89. Ne thjesht kontrolloni vlerën e çdo nyje dhe të shkoni në të majtë apo të djathtë, varësi të faktit nëse vlera Nyja është më pak se ose e madhe se një ne jemi duke kërkuar për të. Kështu, duke filluar në rrënjë të 13, shohim se 89 është më e madhe, dhe kështu ne do të shkojmë në të djathtë. Pastaj ne e shohim për nyjen 34, dhe përsëri ne do të shkojmë në të djathtë. 89 është ende më i madh se 55, kështu që ne vazhdojmë duke shkuar në të djathtë. Ne pastaj të dalë me një nyje me vlerën e 144 dhe të shkoni në të majtë. Ja dhe ja, 89 është e drejtë atje. 

Një tjetër gjë që mund të bëjmë është të shtypura nga të gjitha numrat duke kryer një traversal inorder. Një traversal inorder do të thotë për të shtypur çdo gjë në subtree majtë ndjekur nga shtypi nyjen vetë dhe më pas duke shtypur çdo gjë në të drejtën subtree. Për shembull, le të marrin favorite tonë të kërkimit pemë binare dhe të shtypura nga numrat në mënyrë renditura. Ne të fillojë në rrënjë të 13, por para printimit 13 ne duhet të shtypura nga gjithçka në subtree majtë. Pra, ne do të shkojmë deri në 5. Ne ende kemi për të shkuar më thellë poshtë në pemë deri ne gjeni nyjen e majtë më të madhe, cila është zero. Pas shtypjes zero, ne kthehemi deri në 1 dhe të shtypura atë jashtë. Pastaj ne do të shkojmë në të djathtë subtree, e cila është 2, dhe të shtypura atë jashtë. Tani që ne jemi bërë me atë subtree, ne mund të shkojë mbrapa deri në 3 dhe të shtypura it out. Vazhdimi back up, ne printoni 5 dhe pastaj 8. Tani që ne kemi përfunduar tërë la subtree, ne mund të shtypura nga 13 dhe fillojnë të punojnë në të djathtë subtree. Ne hop deri 34, por para printimit 34 ne duhet të shtypura nga subtree e saj të majtë. Pra, ne të shtypura nga 21, pastaj ne kemi marrë për të printuar jashtë dhe do të vizitojë 34 subtree të drejtën e saj. Që 55 nuk ka subtree majtas, ne print it out dhe të vazhdojë në të subtree e saj të drejtë. 144 ka një subtree majtë, dhe kështu që ne të shtypura nga 89, e ndjekur nga 144, dhe në fund të djathtë më të nyje e 233. Nuk keni atë, të gjithë numrat janë të shtypura në mënyrë të ulët në më të lartë. 

Shtimi diçka tek pema është relativisht pa dhimbje si. Të gjithë ne duhet të bëni është të bëni të sigurtë që ne ndjekim 3 search pronat binare pemë dhe pastaj futur vlera ku ka hapësirë. Le të thonë se ne duam të futur vlerën e 7. Që nga 7 është më pak se 13, ne do të shkojmë në të majtë. Por kjo është më e madhe se 5, kështu që ne përshkojë në të djathtë. Që nga ajo është më pak se 8 dhe 8 është një nyje gjethe, ne shtoni 7 me fëmijën e majtë të 8. Voila! Ne kemi shtuar një numër në pemë binare e kërkimit tonë. 

Nëse ne mund të shtoni gjërat, ne më mirë të jetë në gjendje për të fshini gjërat si. Fatkeqësisht për ne, fshirjes është pak më e komplikuar - jo shumë, por vetëm pak. Ka 3 skenarë të ndryshëm që ne duhet të marrin në konsideratë kur fshirjes elemente nga pemë binare e kërkimit. Së pari, çështja më e lehtë është që elementi është një nyje gjethe. Në këtë rast, ne thjesht fshini atë dhe të vazhdojë me biznesin tonë. Thonë se ne duam të fshini 7 që ne vetëm shtuar. E pra, ne thjesht të gjeni atë, hiqni atë, dhe kjo është ajo. Rasti tjetër është, nëse nyja ka vetëm fëmijë 1. Këtu mund të fshini nyjen, por ne së pari duhet të sigurohemi të lidhë subtree që ka mbetur tani pa prindër për prindin e nyjeve ne fshihet vetëm. Thonë se ne duam të fshini 3 nga pema tonë. Ne kemi marrë elementin fëmijës e asaj nyje dhe atë të bashkëngjitni prind e nyjeve. Në këtë rast, ne jemi tani bashkëngjitur 1 në 5. Kjo punon pa problem, sepse ne e dimë, në bazë të kërkimit binar pronës pemë, se çdo gjë në subtree majtë e 3 ishte më pak se 5. Tani që e 3 subtree është marrë kujdesin e, ne mund të fshini atë. Rasti i tretë dhe i fundit është më komplekse. Ky është rasti kur nyje ne duam të fshini ka 2 fëmijë. Në mënyrë që të bëni këtë, ne së pari duhet të gjejnë nyjen që ka vlerën më të madh, bie në ujdi dy, dhe pastaj fshini nyjen në fjalë. Njoftim nyjen që ka vlera më e madhe e ardhshme nuk mund të ketë 2 fëmijë vetë që fëmija i tij të majtë do të jetë një kandidat i mirë për të madhe ardhshëm. Prandaj, fshirjes një nyje me 2 fëmijë arrin të shkëmbejnë prej 2 nyje, dhe pastaj fshirjes është trajtuar nga 1 e 2 rregullave të lartpërmendura. Për shembull, le të thonë se ne duam të fshini nyjen rrënjë, 13. Gjëja e parë që ne bëjmë është që ne të gjeni vlerën më të madh në pemë cila, në këtë rast, është 21. Ne pastaj shkëmbim 2 nyje, duke e bërë 13 një fletë dhe 21 nyjen qendrore grup. Tani ne thjesht mund të fshini 13. 

Aludoi për sa më herët, ka shumë mënyra të mundshme për të bërë një kërkim të vlefshme pemë binare. Për fat të keq për ne, disa janë më keq se të tjerët. Për shembull, çfarë ndodh kur ne kemi ndërtuar një pemë binare kërkimi nga një listë të renditura të numrave? Të gjithë numrat janë shtuar vetëm për të drejtën në çdo hap. Kur ne duam të kërkoni për një numër, ne nuk kemi asnjë zgjidhje, por vetëm shikoni në të drejtën në çdo hap. Kjo nuk është më e mirë se kërkim linear në të gjitha. Edhe pse ne nuk do të mbulojë ata këtu, ka të tjera, më komplekse, dhënave struktura që bëjnë të sigurt se kjo nuk do të ndodhë. Megjithatë, një gjë e thjeshtë që mund të bëhet për të shmangur këtë është në vetëm riorganizimi rastësisht vlerat hyrëse. Është shumë gjasa që rastësisht një listë riorganizoi e numrave është e renditura. Nëse ky ishte rasti, kazinove nuk do të qëndrojë në biznes për kohë të gjatë. 

Nuk keni atë. Ju tani e dini në lidhje me kërkimin dhe pemë binare e kërkimit binar. Unë jam Patrick Schmid, dhe kjo është CS50. [CS50.TV] Një mënyrë e qartë do të jetë për të scan listë nga ... [bip] Numri ... i artikujve yep ... [Qesh] Postoni ... nyje e 234 ... augh. Yay >>! Kjo ishte -