[Powered by Google Translate] [Binary Search] [Patrick Schmid - Harvard Unibertsitatea] [Hau CS50 da. - CS50.TV] 

Eman dut baduzu Disney pertsonaia izenak zerrenda ordena alfabetikoan zaizu eta Mickey Mouse aurkitu, nola hau egiten al duzu? One bistako hasieratik zerrenda eskaneatu izango litzateke eta egiaztatu izena da Mickey bada bakoitzean ikusteko. Baina irakurri nahi Aladdin, Alice, Ariel, eta abar, zerrendan aurrean hasita azkar duzu konturatzen ez zela ideia ona. Ados, agian atzeraka lan zerrendaren bukaeran hasi behar duzu. Orain Tarzan, Stitch, Snow White, eta abar irakurri duzu. Hala eta guztiz ere, ez dirudi buruz joan modurik onena bezala. 

Beno, beste modu bat izan duzula horretan buruz behera mugatu saiatzeko izenak zerrenda begiratzen duzula. Badakizu, ordena alfabetikoan dira geroztik, izenak begiratu besterik ez izan zerrendaren erdian eta egiaztatu Mickey Mouse izen hori aurretik edo ondoren bada. Bigarren zutabean abizena begira konturatzen Mickey M Jasmine for J ondoren dator nahi duzuna beraz, besterik ez dituzu, ez ikusi egin zerrenda lehen erdia. Ondoren, seguruenik litzaidake duzu azken zutabean goialdean bilatzeko ikusi eta Rapunzel hasten dela. Mickey Rapunzel aurretik dator; azken zutabean itxura dugu ahaztu bezala baita. Etengabeko bilaketa-estrategia, azkar ikusiko dituzu Mickey dela gainerako zerrenda izenak lehenengo seihilekoan eta, azkenik, Mickey Merlin eta Minnie artean ezkutatzen dira. 

Zer egin besterik ez duzu, funtsean, bitar bilaketa izan zen. Izen hori dakar, bere bilaketa-estrategia egiten da materia bitar bat. Zer esan nahi du horrek? Beno, horrela antolatu elementu zerrenda bat ematen da, binary bilaketa algoritmoa bitarrak erabaki bat hartu du ezkerrera edo eskuinera, baino handiagoa edo txikiagoa, baino aurretik edo ondoren alfabetikoki puntu bakoitzean. Orain bilaketa-algoritmo honekin batera doan izen bat dugula, dezagun beste adibide bat begiratu, baina oraingo honetan zenbakiak ordenatuko zerrenda bat. Esan kopurua 144 zenbakiak ordenatuko zerrenda hau bilatzen ari gara. Just nahi baino lehen, zenbaki erdian aurkituko dugu kasu honetan 13 eta 144 baino handiagoa edo 13 baino gutxiago bada. Da argi eta garbi 13 baino handiagoa izan denez, dena alde batetara utzi ahal izango dugu, hau da, 13 edo gutxiago eta gainerako erdia da. Orain dugu geroztik, nahiz eta utzi bat elementu kopurua, erditik hurbil da zenbaki bat aukeratu besterik ez dugu. Kasu honetan, 55 aukeratu dugu. Izan bezain erraz izan dugu aukeratu 89. Ongi da. Berriz ere, 144 55 baino handiagoa da, beraz, joateko eskubidea dugu. Zorionez, gurekin, hurrengo erdian kopurua 144 da, eta bat bilatzen ari gara. Beraz, ordena 144 bitarrak bilaketa bat erabiliz, gai da bakarrik 3 urrats aurkituko gara. Erabiltzen dugu izanez gero hemen lineal bilaketa, hartu litzateke 12 urrats. Izan ere, materia gisa, bilaketa-metodo hau aurrera elementu kopurua halves Urrats bakoitzean begiratu du, elementua aurkitu ahal izango da bilatzen zerrendako elementu kopurua log buruz. Orain ikusten ditudan 2 pieza dezagun, bada, itxura batean funtzioa errekurtsiboa bilaketa bitarra ezartzen pseudocode batzuk. Goialdean hasita, 4 argumenturik hartzen dituen funtzio bat aurkitu dugula ikusiko dugu: gakoa, array, min, eta max. Gakoa ari garela, beraz, aurreko Adibidez 144 zenbakia da. Array ari garen zenbakien zerrenda bilatzen da. Min eta gutxieneko eta gehieneko posizio max indizeak ari gara gaur egun begira. Beraz abiarazten dugunean, min zero izango da eta max array gehienezko indizea izango da. Mugatu gara bilaketa behera, min eta max eguneratu egingo dugu sorta ari garela oraindik sartu bilatzen 

Dezagun interesgarria parte saltatzeko lehen. Egiten dugun lehen gauza da aurkitu erdigunea, indizea array oraindik ari garela kontuan hartuta, min eta max arteko erdibidean da. Ondoren, begiratu array balioa dugu erdigunea kokapena hartan ikusi eta bila ari garela gako bat baino gutxiago bada. Posizio hartan kopurua txikiagoa bada, sakatu posizio horren ezkerreko zenbakiak guztiak baino handiagoa da esan nahi du. Beraz, bilaketa-funtzioa bitarraren deitu ahal izango dugu berriro, baina oraingo honetan min eta max parametroak eguneratzeko erdia besterik ez irakurri hau da, begiratu besterik ez dugu at balioa baino handiagoa edo berdina. Beste alde batetik, gakoa da array egungo erdigunea kopurua baino txikiagoa bada, ezkerrera joan eta guztiak dira handiagoa zenbakiak alde batetara utzi nahi dugu. Berriz ere, min eta max eguneraketa gama bitarra bilatu, baina denbora honetan deitzen dugun besterik ez beheko erdian. Array uneko erdigunea balioa ez da bada baino handiagoa, ezta gakoa baino txikiagoa da, orduan gakoa berdina izan behar du. Horrela, besterik gabe, ahal izango dugu itzultzeko uneko erdigunea indizea, eta egin gaude. Azkenik, hau hemen check kasuan kopurua ez da benetan zenbakiak bilatzen ari gara array. Gama gehienezko indizea bila ari garela bada gutxieneko inoiz baino txikiagoa da, horrek esan nahi du joan ditudan urrunegi. Kopurua ez zen aurrera sarrera array, -1 itzuliko gara ezer ez adierazi aurkitu zen. 

Konturatuko algoritmo hau lan egin dezakezu, zenbakien zerrenda ordenatuko diren. Beste era batera esanda, baino ezin dugu aurkitu 144 bitar bilaketa erabiliz zenbaki guztiak dira txikiena etatik handiena agindu zuen. Hori gutxi ez bada, ez genuke urrats bakoitzaren zenbakiak erdia kanpoan utzi ahal izango. Hori dela eta, 2 aukera ditugu. Edo Unsorted zerrenda bat hartu ahal izango dugu, eta ordenatzeko bilaketa bitarra erabiliz aurretik, edo ziurtatu zenbakien zerrendan gehitu ditugu zenbakiak bezala hori horrela antolatu ahal izango dugu. Horrela, bakarrik bilatu behar dugu ordenatzeko ordez, zergatik ez gorde uneoro antolatuta zerrendan? 

Joanekoa zenbakien zerrenda bat gorde ordenatuko aldi berean aukera ematen du gehitu edo bat mugitu zenbakiak zerrenda honetan zerbait izeneko bilaketa zuhaitz bitar bat erabiliz. A binary bilaketa-zuhaitz bat datuak egitura 3 propietate ditu. Lehenik eta behin, ezker nodo edozein Azpizuhaitza diren balioak baino gutxiago bakarrik ditu edo nodo balio berdinak. Bigarrenik, nodo bat Azpizuhaitza eskubidea baino ez diren balioak baino handiagoa edo nodo balio berdinak. Eta, azkenik, nodo guztiak subtrees bai ezkerreko eta eskuineko bilaketa zuhaitz bitarra. Dezagun adibide bat bilatzeko lehenago erabiltzen dugun zenbaki bereko. Dutenek ez dute inoiz ikusi ez informatika zuhaitza aurretik, utzi hasiko diozu informatika zuhaitza hazten beherantz by me. Bai, zuhaitzak dira ohituta ez bezala, informatika zuhaitza root goialdean da, eta hostoak, behealdean. Little box bakoitzak nodo bat deitzen da, eta nodoak dira ertzak by elkarren artean lotuta. Beraz, Zuhaitz hau root 13 balioa balio nodo bat da, 2 balioak 5 eta 34 seme-alabak nodoak ditu. Azpizuhaitza A zuhaitz hori zuhaitz osoa azpiataletan begira eratu da. 

Adibidez, nodo 3 Azpizuhaitza ezkerreko nodo 0, 1, eta 2 sortutako zuhaitza da. Beraz, joaten gara itzuliz gero bilaketa zuhaitz bitar propietateak, zuhaitza nodo bakoitzean 3 propietate, hala nola egokitzen duen ikusiko dugu, ezker Azpizuhaitza baino gutxiago edo nodo balio berdinak diren balioak baino ez ditu; nodo guztiak Azpizuhaitza baino ez diren balioak baino handiagoa edo nodo balio berdinak; bai ezkerreko eta eskuineko nodo guztiak subtrees ere binary bilaketa zuhaitzak dira. Zuhaitz hau itxura ezberdina izan arren, hau da baliozko bitar bilaketa zuhaitza da zenbakiak multzo berean. Izan ere, materia gisa, ahalik eta modu asko daude, sortzen dituzun baliozko bitar bilaketa zenbaki horiek zuhaitz bat. Beno, goazen bat sortu dugu lehen itzuli. Beraz, zer egin dezaket dugu zuhaitz horiek? Beno, oso besterik gabe, gutxieneko eta gehieneko balioak aurkituko ditugu. Gutxieneko balioak beti ezkerreko aurkitu daitezke no gehiago daude nodo bisitatzeko arte. Aitzitik, gehienezko bat aurkitzeko, besterik gabe, besterik ez jaisten eskubidea aldi bakoitzean. 

Beste edozein zenbaki aurkitzea ez da gutxieneko edo gehieneko bezain erraza da. Esan 89 zenbakia bilatzen ari gara. Nodo bakoitzaren balioa egiaztatu besterik ez dugu, eta joan ezkerrera edo eskuinera, Nodo balioa baino txikiagoa edo baino handiagoa den ala ez arabera bat bilatzen ari gara. Beraz, 13 erro hasita, 89 handiagoa ikusiko dugu, eta, beraz, eskubidea dugu. Ondoren, 34 nodo ikusiko dugu, eta berriro joateko eskubidea dugu. 89 55 baino handiagoa da oraindik, beraz, eskuinera jarraituko dugu. Ondoren etorri gara 144 balioa nodo bat eta ezkerrera joan. Lo eta behold, 89 bertan. 

Inorder traversal bat egitean zenbakiak guztiak inprimatu ahal izango dugu beste gauza bat da. Traversal inorder bat esan nahi guztia inprimatu ezkerreko Azpizuhaitza nodoaren inprimatzean berak eta, ondoren, guztia inprimatzeko eskubidea Azpizuhaitza ondoren. Esate baterako, dezagun gure gogoko binary bilaketa zuhaitz inprimatu eta ordena ordenatuko zenbakiak. Erro 13 hasiko gara, baina inprimatze 13 baino lehen inprimatu behar dugu ezkerreko Azpizuhaitza dena. Beraz, 5. Dugu oraindik sakonago behera joan zuhaitza aurkitzen dugu ezker-nodo arte, hau da, zero. Inprimaketa zero ondoren, atzera egin dugu 1 eta out duten inprimatzeko. Ondoren, joan eskuinera Azpizuhaitza, hau da, 2, eta out duten inprimatzeko. Orain gaude Azpizuhaitza hori egiten, itzuli ahal izango da, gehienez ere 3 eta inprimatu. Atzera Etengabeko sortu, 5 inprimatu dugu eta, ondoren, 8. Orain dugun osoa utzi Azpizuhaitza inprimatu ahal izango dugu 13 eta eskubidea Azpizuhaitza lanean hasteko. Behera hop dugu 34, baina inprimatze 34 baino lehen haren ezkerreko Azpizuhaitza inprimatu ditugu. Beraz, inprimatu dugu, 21; gero inprimatu eta 34 lortzen dugu eta haren eskuinaldean Azpizuhaitza bisitatzeko. 55 ditu ezker Azpizuhaitza ez denez, inprimatu dugu eta jarraitzeko bere eskubidea Azpizuhaitza. 144 ezker Azpizuhaitza ditu, eta, beraz, inprimatu ditugu, 89, 144, eta ondoren, eta, azkenik, 233 nodo eskuin-gehienak. Hor duzu, zenbaki guztiak dira inprimatutako txikiena etatik handiena ordena. 

Zuhaitzaren zerbait gehitzea nahiko erraza baita. Guztiak egin behar dugu, ziur jarraituko dugula 3 bitarra bilaketa zuhaitz propietate egin da eta, ondoren sartu balioa non dago espazioa. Demagun balioa 7 txertatu nahi dugu. 7 baino txikiagoa da 13 urteaz geroztik, joan ezkerrera dugu. Baina 5 baino handiagoa da, eta, beraz, zeharkatzeko eskubidea dugu. Baino gutxiago 8 eta 8 hosto nodo bat denez, 7 gehitzen badiogu, 8 seme-alaba ezker. Voila! Zenbaki bat gehitu dugu gure bitar bilaketa zuhaitza. 

Gauzak gehitzen badiogu, hobe dugu gauzak ezabatu baita. Zoritxarrez guretzat, ezabatzen da, pixka bat zailagoa ez da hainbeste, baina apur bat. Badira 3 dugula kontuan hartu beharreko hainbat eszenatoki elementuak ezabatzen bilaketa zuhaitz bitarra from. Lehenik eta behin, kasu errazena da elementu hosto nodo bat da. Kasu honetan, ezabatu besterik ez dugu eta gure enpresa. Esan 7 besterik ez dugu gehitu ezabatu nahi dugu. Beno, besterik gabe aurkituko dugu, kendu, eta hori da. Hurrengo kasua da nodoaren 1 seme-alaba ditu. Hemen nodoak ezabatu ahal izango dugu, baina lehen, ziurtatu Azpizuhaitza hori utzi parentless konektatu nodo guraso ezabatu besterik ez dugu. Esan 3 ezabatu nahi dugu, gure zuhaitz. Nodo horren elementu seme-alabak hartuko dugu, eta nodo guraso erantsi. Kasu honetan, gaur egun ari gara 1 5 erantsiz. Hau arazo bat izan gabe lan egiten du ezagutzen dugulako, binary bilaketa zuhaitz jabetza arabera, 3 ezker Azpizuhaitza dena 5 baino gutxiago izan zen. Orain dela 3 Azpizuhaitza tratua da, ezabatu ahal izango dugu. Hirugarren eta azken kasu konplexuena da. Kasu honetan nodo ezabatu nahi dugun 2 seme-alaba ditu. Horretarako, lehen nodoa hurrengo balio handiena aurkituko dugu, Trukatu bi, eta ondoren galdera nodo ezabatu. Iragarki hurrengo balio handiena ezin izan 2 haur bera duen nodo haren ezkerreko seme hurrengo handiena hobeto hautagai bat izango litzateke. Beraz, 2 seme-alabekin nodo bat ezabatzen 2 nodoen aldaketa kopuruei eta, ondoren, ezabatzen 1 2 arau horietako kudeatu. Esate baterako, demagun erroko nodoa, 13 ezabatu nahi dugu. Egiten dugun lehen gauza da zuhaitza hurrengo balioa handiena aurkituko dugu Izan ere, kasu honetan, 21. 2 nodo swap dugu, hosto bat 13 eta 21 talde erdiko nodo egiteko. Orain, besterik gabe, ezabatu ahal izango dugu 13. 

Bezala lehenago aipatu, ahalik eta modu asko daude baliozko bitar bilaketa zuhaitza egiteko. Zoritxarrez guretzat, batzuk besteak baino okerragoak dira. Esate baterako, zer gertatzen den bilaketa bitarra zuhaitz bat eraikitzen dugu zenbakien zerrenda ordenatuko? Zenbaki guztiak eskuinera gehitu besterik ez dira urrats bakoitzean. Zenbaki bat bilatu nahi dugu, aukeratu dugu, baina soilik eskuinera begiratu Urrats bakoitzean. Hau ez da bilaketa lineala guztiak baino hobea da. Estali egingo dugu ez den arren hemen, ez dago beste, konplexuagoak dira, datuen egitura hau ez dela gertatuko ziurtatu. Hala eta guztiz ere, simple gauza bat egin daiteke hori saihesteko besterik ez ausaz nahastu sarrerako balioak. Oso nekez da aukera ausazko zenbakien zerrenda nahastu bat ordenatuko da. Kasu bada, casinos ez litzateke enpresa egonaldi luzea. 

Hor aukera izango duzu. Bilatzeko bilaketa bitarra eta bitarra zuhaitz buruz gaur egun ezagutzen duzu. Patrick Schmid naiz, eta hau da CS50. [CS50.TV] One bistako zerrenda eskaneatuko litzateke ... [beep] ... Elementu kopurua ... Bai [Barreak] ... 234 ... augh nodo bidaltzeko. >> Yay! Hori izan zen