[Musika jotzen] DOUG LLOYD: So izan dugu gertuago inching eta hurbilago dagoela datuak Grial santua egiturak, bat sartu ahal izango dugu sartu, ezabatu, eta itxura eman denbora etengabe. Eskuin. Hori da helburua moduko. Egiteko gai izan nahi dugu Gauzak oso, oso azkar. 

Dute hemen noiz aurkitu dugu dugun saiatzen ari gara hitz egiten? Beno, utzi ditzagun. Beraz, zenbait ikusi dugu Datu-egitura ezberdinak Horren mapping kudeatzeko deiturikoak gako-balioa bikoteak, datu-pieza batzuk kartografiatzeko beste datu-pieza batzuk beraz, badakigu nora aurkitu egituran, informazio. 

Beraz, array egiteko, esate baterako, gakoa elementu indize edo array da kokapena 0 edo array 1 eta abar. Eta balio du datua kokaleku hori existitzen. Beraz, zer da array 0 gordetzen dira? Zer da array 1 gordetzen dira besterik versus 0 eta 1, gakoak izango litzateke. 

Hash taula bat da, Ideia bera moduko. Hash taula bat, hash hau dugu Funtzio hori hash kodeak sortzen. Beraz, gakoa hash datuen kodea da. Eta balio du, batez ere, Hitz egin dugu kateatzea buruz hash taulak bideoa, lotuta datuen zerrenda dela Hori hashcode horretara egiaztapenekin. Eskuin. Hurbilketa bat buruz zer Metodo hau, ordea? Metodo bat buruz zer non gakoa bermatuta dago, berezia izango da, hash taula bat, non ezin izan dugu ez bezala azkenean bi datu zati batekin the hashcode bera izatea. Eta, ondoren, aurre egin behar dugu Hori bai, hariari edo gehiago ahal izanez gero, arazo hori konpondu kateatzea. 

Beraz, orain bermatu ahal izango dugu Gure gakoa berezia izango da. Eta geure balio bazegoen Zerbait erraza gisa egiazko eta gezurrezko duten ala ez esaten digu edo ez informazio pieza hori egitura existitzen? Boolean A bezala pixka bat bezain erraza izan daiteke. Errealistan seguruenik bat byte pixka bat baino gehiago, seguru. Baina hori baino askoz ere txikiagoa Agian gordetzeko 50-karaktere-katea, adibidez. 

Beraz, saiatzen, taulak hash antzeko, bertan konbinatu array eta lotutako zerrenda, Saiatuko konbinatu array, egiturak, eta erakusleak elkarrekin datuak gordetzeko Modu interesgarri bat hori da, nahiko ezberdina ezer orain arte ikusi dugu. Orain, datuak erabili ditugu mapa bat bezala Datu egitura nabigatzeko. Eta baldin jarraitu ahal izango dugu bide orria, ahal bada datuen jarraitu Hasieratik amaierara, dizkizugu Datu hori jakiteko trie existitzen. 

Eta ezin dugu bada mapa jarraitu den guztia amaituko esanahia, datuak ezin da existitzen. Berriz ere, gakoak hemen dira bermatuta berezia izan da. Eta beraz, hash taula bat ez bezala, inoiz ez dugu talkak aurre hemen. Eta bi datu zati ez zehazki bide orria bera dute Datu hori berdin-berdina ez bada. 

Sartu dugu John bada, orduan bilatu John for dugu. Hori da bi pieza berdin- datuak, eskuinera, bidez bilatzen ari gara. Baina bestela, edozein Bi datu zati dira bermatuta roadmaps berezia dute Datuen egitura honen bidez. Eta ari gara begirada bat hartu du honen bisuala une bat besterik ez. 

Egin dugu hau saiatuz Datuen egitura berri bat sortzeko, jarraian gako bikote kartografiatzeko. Kasu honetan, ez dugu erabili joan zerbait bezala boolear bat bezain erraza. Benetan dugu katea gordeko. Eta kate hori joan unibertsitate baten izena izan. 

Eta gakoa da urte osoan izango da betiere, unibertsitate hori sortu zen. Unibertsitateek urte Guztiak diren lau zifra izango da. Eta orain lau digituak horiek erabiliko dugu Datu egitura nabigatzeko. Eta egingo, ikusiko dugu berriro, nola egiten dugun bigarren batean. 

Bidearen amaieran, Ikusiko dugu izenean dagokion unibertsitatearen gako hori, lau zifra horiek. Oinarrizko ideia trie baten atzean ibilbide bat eduki dugu. Beraz, pentsatu zuhaitz bat bezala. Eta hau ortografia bertsua da eta zuhaitz bat kontzeptua ere. Oro har, pentsatzen dugu Mundu errealean zuhaitzak, erro hori ere egin dute Beheko eta gorantz hazten dira eta adarrak dute eta hostoak dute. Eta, batez ere ideiaren trie bat da berdin, ezik erro hori ainguratuta zerua nonbait. Eta hostoak behealdean daude. 

Beraz, mota da zuhaitz bat eramaten dute, eta besterik ez da iraultzeko goitik behera. Baina ez sukurtsal daude oraindik. Eta horiek gure bideetatik izango litzateke, horiek gure konexioak izango da hostoak errotik abiatuta. Kasu honetan, horiek bideak, adar horiek dira diguten zenbakiak etiketatu zein era non gauden joan. 

Ikusiko dugu 0 bada, arlo horrek behera joan gara, ikusten dugu 1 bat izanez gero, arlo horrek behera joan gara, eta abar eta abar. Beno, zer esan nahi du horrek? Beno, hori esan nahi du bidegurutzera puntu guztietan eta nodo guztietan erdiko eta adar guztietan, badira 10 posible Hori gaitezke lekuak. Beraz, ez dira 10 erakusle kokapena guztietatik. 

Eta hau da, non saiatzen bat eskuratu ahal Pixka norbaiti beldurra nor ez du asko izan informatikako aurretik esperientzia. Baina saiatzen benetan polita awesome dira. Eta baldin baduzu Aukera haiekin lan eta zu dig-ere prest eta horiekin esperimentatu, oso interesgarria ari dira benetan Datu-egitura berarekin lan. Elementu bat sartu nahi badugu trie sartu, guztiok egin behar dugu da bide zuzena eraikitzeko hostoa erro. Hona hemen zer guztietan urrats batera Bide agian itxura. Datu berri bat zehazten goaz nodo berri bat egitura trie bat deitzen. 

Eta datu horren barruan egitura ez bi pieza daude. Gordetzeko goaz unibertsitate baten izena. Eta ari gara gordetzeko joan erakusleak array bat beste mota bereko nodoak. Beraz, berriro ere, hau sort dela nonahi kontzeptua Gara, 10 posible lekuak joan ahal izango dugu. Ikusiko dugu 0 bada, jaitsiko gara arlo horrek. Ikusten dugu 1 bat izanez gero, arlo horrek, eta abar eta abar eta abar. Esan badugu 9 jaitsiko gara arlo horrek. Bidegurutzera puntu guztietan Beraz, 10 leku posible gaitezke. Beraz, nodo bakoitzean 10 erakusleak eduki du beste nodo, beste 10 nodoak dira. 

Eta datuak gordetzeko ari gara da besterik unibertsitatearen izenean. Hargatik eraikitzeko trie bat. Dezagun txertatzeko pare bat Gure trie sartu elementu. Oso goian beraz, hau gure erroko nodoa da. Hau da, ziurrenik, zerbait izango da zu deklarazioa globalean joan. Eta ari mantentzen globalean zoazen nodo hau beti erakuslea. 

Esateko ari zara, erro berdinen, eta zu yourself malloc trie nodo joan. Eta inoiz ez zaren joan erro berriro ukitzeko. Nahi duzun aldi bakoitzean hasteko nabigatzen, erakuslea beste ezarri duzun erro berdina, hala nola, txalupa bezala, bertan I adibidea da Nire bideoak askotan erabili Hemen Pilak eta ilarak on eta lotura-zerrendak eta abar. 

Erakuslea beste ezarri duzun Zeharkako txalupa b deitzen. Eta trav erabiltzen duzun nabigatu Datuen egitura bidez. Beraz, ikus dezagun nola hori begiratu. Beraz, oraintxe bertan, zer du nodo baten itxura? Beno, besterik gabe, gure datu gisa egitura deklarazio adierazitako, kate bat, ez dugu bertan Kasu honetan hutsik dago. Ez dago ezer hemen. 

Eta 10 erakusleak array bat. Eta oraintxe, ez dugu bakarrik 1 trie honetan nodo dute. Ez dago beste ezer atalean. Beraz, guztia horietako 10 erakusleak puntu null. Hori da, gorria, zer adierazten du. 

Dezagun txertatzeko katea Harvard. Dezagun txertatzeko Unibertsitateko Harvard trie honetan sartu, eta horrek Urtearen 1636 urtean sortu zen. Gakoa erabili nahi dugu, 1636, kontatzen digu, non gaude Harvard gordetzeko trie joan. Orain, nola egin genezake hori? 

Baliteke itxura hau izan zen. Erro hasiko dugu. Eta 10 leku horiek joan ahal izango dugu. Erroa soilik edozein bezalakoa da beste trie nodo. 10 leku hemendik joan gaitezke daude. 

Nora egin nahi dugu, ziurrenik, go gakoa 1636 bada? Ez da benetan bi aukera. Eskuin. Gakoa eraiki ahal izango dugu eskuinetik ezkerrera eta 6 hasten dira. Edo gakoa eraiki ahal izan dugu Ezkerretik eskuinera eta 1-ekin hasten dira. 

Seguruenik gehiago gizaki gisa intuitiboa dugu ulertu beharko Just joan ezkerretik eskuinera. Eta beraz, txertatu nahi badut Harvard trie honetan sartu, Seguruenik hasi nahi dut erro hasita arabera, Nire 10 Aukera begira nire aurrean, eta esanez Jaisteko 1 bidea egin nahi dut. ONDO DA. 

Orain, 1 bidea Une nulua da. Beraz, behera jarraitzeko bide hori nahi badut elementu honen txertatzeko trie sartu, Nodo berria malloc behar dut, izan 1 seinalatu, besterik ez, eta, ondoren, ona joan naiz. 

Beraz, funtsean batean nago Puntu non zutik dut Zuhaitzaren edo erro at trie eta badira 10 adarretan. Baina adar bakoitzak dauka bat horren aurrean atea. Eskuin. Zeren eta ez beste ezer ez dago. Ez pasarte segurua. Horrek esan nahi du ez dagoela ezer adarren horietako edozein behera. Eraikin hasi nahi dut bada zerbait, atea kendu nahi dut. Gate kendu nahi dut zenbakia 1 aurrean. Eta behera ibiltzeko nahi dut. Eta eraiki nahi dut Niretzat beste leku batera joan. 

Eta hemen zer egin dut hori. Beraz 1 jada ez puntu hau null. Esan dut, segurua da behera hemen orain joan. Nodo beste eraiki dut. Eta noiz iritsi nodo hori I, I egiteko beste erabakirik dute. Non naiz hemendik joan da? 

Beno, 1 behera dagoeneko ditudan joan. Beraz, gaur egun, ziurrenik, behera joan 6 nahi dut. Eskuin. Berriz ere, 10 kokapenak Ezin dut aukeratu dut. Beraz, goazen behera orain zenbakitik 6. Beraz gate garbituko dut 6. zenbakian aurrean. Eta oinez I behera dago. Eta beste nodo eraikitzeko dut. Eta zuk bidegurutzean beste puntu bat iritsi naiz. 

Berriz ere, 10 aukera daukat Nora joan nintzen da. Nik 1etik 6ra. Beraz, gaur egun, ziurrenik, 3 joan nahi dut. 3, ez da ezerezetik ezin dut joan. Beraz, bidea garbitu behar dut eta eraikitzeko neure burua espazio berri bat. Eta gero, 3, nora joan nahi dut from? Behera 6 joan nahi dut. 

Eta, berriro, izan nahi dut bidea garbitu egin behar den. Beraz, orain nire gakoa erabili dut sortu txertatzeko nodo eta hasi trie hau eraikitzeko. I erroan hasi dut. I 1636 behera joan. Eta orain nago behealdean dut ez nodo horretan. Eta gauza egin ditzakezu Ikusten da zure pantailan. 

Honez horiz nabarmenduta. Hori da, non gaur egun nago. Nire gakoa egiten da. Nire gakoetan behin agortu dut. Beraz, ezin dut joan urrunago. Beraz, puntu honetan, I guztiak benetan behar ez den esaten da, OK. Honez mota bezala bila lurrean behera, irudikatzeko ari bazara yourself bidea moduko hau bezala konexioak ezberdinekin. Moduko behera eta Ordena bila spray Harvard pintura lurrean. Hori honen izena da. Jakin hori zer da kokaleku honetan. Hasteko, errotik dugu bada eta behera joan gara 1 eta, ondoren, 6 eta gero, 3 eta ondoren, 6, non gauden? Beno behera begiratzen badugu eta ikusiko dugu Harvard, orduan Ezagutzen dugun Harvard zela 1636 urtean sortu oinarritutako bidean Datu egitura ezartzeko ari garen. Beraz, hori espero erraza izan zen. Bi sarrerak gehiago egin behar izan dugu. Eta zorionez, lagundu egingo da Ikusten honetan bi aldiz gehiago egin. 

Orain, dezagun txertatzeko, unibertsitateko beste. Dezagun txertatzeko Yale trie honetan sartu. Yale 1701 urtean sortu zen. Beraz, ez dugu bertan hasiko erro, beti egiten dugun bezala. Eta zeharkako erakuslea ezarri dugu. Bidez mugitzeko, erabili behar izan dugu. Lehenengo gauza egin nahi dugu ez da joan behera 1 bidea. Hori da gure gakoa lehen digituaren da. Zorionez, ordea, ez dugu edozein lan hau egiteko denbora izan. 1 bidea jadanik garbitu. Aurretik dudanean hura garbitu dut zen Harvard txertatzeak 1636 at. Beraz, segurtasunez mugitu ahal izango dut 1 gutxiago eta bakarrik joaten. Bada behera mugitu ahal izango 1 du. 

Orain, ordea, 7 joan nahi dut. Bidea garbitu dut 6. Badakit segurtasunez ahal dut jarraitzeko behera 6 bidea. Baina 7 bidea jarraitu behar dut. Beraz, zer egin behar dut? Beno, besterik ez bezala, aurretik, behar besterik ez dut gate garbitzeko, modu ateratzeko, eta 7 bidea nodo berri bat eraikitzeko. Just hau atsegin dute. 

Beraz, orain ez dut mugitu 1 eta ondoren 7. Eta orain konturatzen, sort naiz ren subbranch berri honetan. Eskuin. Dena 16tik beste an, ez dut axola. Ez dut 16 ezer egin. Egiten ari naiz 17 gauzak. 

Beraz, gaur egun 17 urtetik aurrera, izan dut Sort Blaze ibilbide berria hemen. Hurrengo zifra The nire gakoa 0 da. Gai naiz argi ezin edonon lortzeko. Nodo hau eraiki dut. Beraz, badakit ez dago bideak hemendik aurrera. Beraz, bat egiteko neure burua daukat. 

Beraz nodoaren malloc dut eta 0 puntu han. Eta gero, denbora gehiago, malloc I a nodo berria eta puntu bat ez izan. Berriz ere, agortu dut nire gakoa, 1701. Beraz, behera begiratu nuen eta margotzeko Yale bustitzen dut. Nodo honen izena da. 

Eta, beraz, gaur egun, inoiz behar den Yale bada ikusten dut da trie honetan, Erro hasiko naiz, 1701 behera joan nintzen, eta begiratu behera. Eta ikusten dut Yale spray bada lurraren gainean margotu, gero Badakit Yale trie honetan badago. En bat gehiago egin dezagun. Dezagun txertatzeko Dartmouth honetan sartu trie, izan zen 1769 urtean sortu zen. 

Erro etan hasiko da berriro. Nire lehen nire gako digituko 1 da. Ezin dut segurtasunez mugitzeko behera bide hori. Hori existitzen da dagoeneko. Hurrengo nire gako digitu 7 da. Ezin dut segurtasunez mugitzeko behera bide hori. Baita existitzen da. 

Nire hurrengo 6 da. Hemendik, non gaur egun, naiz bertatik horia dago erdiko nodo horretan ere, 6 Une blokeatuta dago off. Jaisteko bide hori nahi badut, Eraikitzeko neure burua daukat. Beraz nodoaren malloc dut eta 6 puntu han. Eta gero, berriz ere, naiz ibilbide berria ondo moldatuko hemen. 

Beraz nodoaren malloc dut, beraz, hasita duten nodo bidea kopurua 9 eta gero orain bidaiatzeko badut 1769an, eta behera begiratzen dut. Ez dago ezer gaur egun bustitzen ez margotua. Dartmouth idatzi ahal izango dut. Eta txertatuko dut, Trie sartu DARTMOUTH. 

Beraz, hori da txertatzeak trie sartu gauzak. Orain gauzak bilatzeko nahi dugu. Zelan bilatzen dugu trie gauzak egiteko? Beno, ideia bera nahiko askoz da. Orain gakoaren digituak erabili besterik ez dugu erro dugu nabigatu ahal izango bada ikusteko nora trie joan nahi dugun jakiteko. 

Hil amaieran hit badiogu edozein puntutan, eta ondoren, ezagutzen dugu elementu hori ezin dela existitzen edo, bestela, bide hori ez litzateke jadanik garbitu. Egiten badugu modu guztiak amaieran, guztiak egin behar dugu behera begiratu eta ikusi hori bada elementua bilatzen ari gara. , Arrakasta izanez gero. Ez bada, huts egin. 

Hargatik bilatu en Harvard trie honetan. Erro hasiko dugu. Eta, berriro, goazela sortu zeharkako erakuslea Gure mugitzen egin digu. Erro badakigu hori lehen postua joan behar gara 1, egin ahal dugu? Bai, ahal dugu. Segurtasunez aurretik badago. Hara joan ahal izango dugu. 

Orain, hurrengo leku batera joan behar dugu 6 da. 6 bide hori ez da existitzen hemendik aurrera? Bai, hala da. Jaitsiko gara 6 bidea. Eta azkenean irudirik. 

Hemendik 3 bidea behera goaz? Beno, bihurtzen da, Bai, hori ere badagoela. Eta ezin 6 bidea hemendik lortu dugu? Bai, ahal dugu. 

Ez dute nahiko erantzun dugu galderari oraindik. Ez da oraindik bat gehiago urratsa, hau da, orain Behera begiratu behar dugu eta Ikusten hori bada benetan Harvard guk nahi izanez gero, hau da, zer aurkituko dugu gakoa agortzen dugu ondoren? Adibide gisa hemen erabiltzen ari gara, Urteetan dira lau zifra beti. Baina, adibidez, non erabiliz dezakezu Hitzen hiztegi bat gordetzeko duzu. 

Eta 10 erakusleak, beraz, ordez beharrik Nire kokapena for, 26 izan ditzakezu. Alfabetoaren letra bakoitzeko bat. Eta han saguzarra bezalako hitz batzuk dira, bertan batch azpimultzo bat, adibidez. Eta, hala bada, nahiz eta zuk nahi gakoa amaieran eta behera begiratuz, Agian ez duzu zer ikusi Bila zabiltzan. 

Beraz, beti behar duzu zeharkatuko Bide-izen osoa eta, ondoren, Arrakastaz ziren gai baduzu Bidea osoa zeharkatuko du, begiratu behera eta azken berrespena bat egin. Hori al da zer bilatzen ari naiz? Beno, behera hasita zaintzen dut goialdean eta joan 1636. Behera begiratzen dut. Harvard ikusten dut. Beraz, bai, lortu nuen. Zer gertatuko da zer bila nabil Ez da trie batean, ordea. Zer gertatuko da Princeton bila nabil, izan zen 1746 urtean sortu zen. Eta beraz, 1746 nire gakoa bihurtzen trie bidez nabigatzeko. Beno, Erro hasiko dut. Eta lehen postua nahi dut behera doa 1 bidea. Ahal izango dut egin? Bai, ahal dudan. 

Ahal izango dut bertatik 7 bidea behera joan? Bai, ahal dudan. Hori ere badagoela. Baina Hemendik 4 bidea behera joaten naiz? Hori da galdera eskatuz bezala da, ahal Behera jarraitu dut karratu gutxi dagoela dudan nabarmenduta horiz? Ez dago ezer han. Eskuin. 

Ez dago modu aurrera 4 bidea behera. Princeton trie hau izan zen, bada, 4 zatekeen garbitu guretzat dagoeneko. Eta beraz, puntu honetan Nik hildako amaiera iritsi gara. Ezin dugu joan urrunago. Eta beraz, esan dezakegu, behin betiko, ez. Princeton ez du trie honetan existitzen. 

Beraz, zer esan nahi du honek guztiak? Eskuin. Ez da asko gertatzen da hemen da. Ez da, leku guztietan zehar erakusleak. Eta, ikusiko duzunez besterik diagraman, ez nodo asko da hori motatako inguruan hegan. Baina, nahi izan dugun bakoitzean nabarituko egiaztatu zerbait trie izan zen ala ez, bakarra izan genuen 4 mugitzen da egin. 

Denbora bakoitzak nahi dugu Zerbait txertatu trie batean, 4 mugimenduak egin behar dugu, seguru asko, Bidean gauza batzuk mallocing. Baina sartzean dugu ikusi dugun bezala Trie sartu Dartmouth, batzuetan bidea batzuk agian guretzat dagoeneko garbitu. Eta, beraz, gure trie lortzen handiagoa eta handiagoa, lan gutxiago aldi bakoitzean egin behar dugu gauza berriak txertatzeko Jadanik dugulako bitarteko horietariko asko eraiki bidean adarretan. Dugu inoiz izan begiratzen baduzu 4 gauzak, 4 konstante bat besterik ez da. Benetan mota dira hurbiltzen gara etengabeko denbora-sartzeak eta denbora etengabe bilatu. Denerako, noski, hori izanik trie honetan, duzu ziurrenik dira, izugarria da. Bakoitza nodo hauetako bat leku asko hartzen du. 

Baina hori denerako da. Benetan azkarra nahi badugu txertatzeko, ezabatzeko benetan azkarra, eta bilatu benetan azkar, behar dugu Datu asko inguruan hegan dute. Espazio asko alde batera utzi behar ditugu eta datu-egitura duten memoria existitzen. 

Eta beraz, denerako da. Baina itxura dugun bezala aurkitu dute agian. Baliteke dugu aurkitu dute Datu-egitura eta Grial Santua txertatze-arinak, ezabatzeko, eta bilaketa. Eta, agian, hau izanen da Datu-egitura egokiak edozein izanda ere, informazioa erabili denda saiatzen ari gara. Naiz Doug Lloyd, hau CS50 da.