[Muzikos grojimo] Doug LLOYD: Taigi mes jau pamaÅ¾u virsta arÄiau ir arÄiau, kad Gralis duomenÅ³ struktÅ«ros, vienas, kad mes galime Ä¯terpti Ä¯, iÅ¡trinti iÅ¡, ir ieÅ¡koti nuolat laiko. TeisÄ. Å tai tarsi Ä¯ vartus. Mes norime, kad bÅ«tÅ³ galima daryti viskas labai, labai greitai. 

Ar mes jÄ radau Äia, kai mes kalbame apie bando? Na, leiskite paÅ¾velgti. Taigi mes matÄme keletÄ Ä¯vairios duomenÅ³ struktÅ«ros kad rankena Å¾emÄlapiÅ³ taip vadinamas raktas-reikÅ¡mÄs poros, kartografavimo kai duomenÅ³ gabalas su kitokiu gabalas duomenÅ³ todÄl mes Å¾inome, kur rasti informacija Ä¯ struktÅ«rÄ. 

Taigi, masyvÄ, pavyzdÅ¾iui, Svarbiausia yra elementas indeksas arba masyvo vietÄ 0 arba 1 masyvas ir taip toliau. Ir yra, vertÄs nÄra duomenÅ³ kad egzistuoja toje vietoje. Taigi, kas yra saugomi masyve 0? Kas yra saugomi masyve 1 prieÅ¡ tiesiog 0, o 1, kuris bÅ«tÅ³ raktai. 

Su maiÅ¡os lentelÄ tai RÅ«Å¡iuoti tos paÄios idÄjos. Su maiÅ¡os lentelÄ, mes turime Å¡Ä¯ maiÅ¡os funkcija, kuri generuoja maiÅ¡os kodai. Taigi raktas yra maiÅ¡os kodÄ iÅ¡ duomenÅ³. Ir vertÄ, ypaÄ mes kalbÄjome apie Grupavimo Kai dÄl maiÅ¡os lentelÄmis vaizdo, yra tai, kad susijÄs sÄraÅ¡Ä duomenÅ³ kad maiÅ¡os tos hashCode. TeisÄ. KÄ apie kitÄ metodÄ Å¡is metodas, nors? KÄ apie metodu, kai raktas garantuoja, kad bus unikalus, skirtingai nuo maiÅ¡os lentelÄ, kur mes galÄtume galÅ³ gale su dviem gabaliukais duomenis turintys tÄ patÄ¯ hashCode. Ir tada mes turime elgtis su , kad vienos ar daugiau zondavimo pageidautina Grupavimo nustatyti Å¡iÄ problemÄ. 

Taigi, dabar mes galime garantuoti kad mÅ«sÅ³ raktas bus unikalus. Ir kÄ daryti, jei mÅ«sÅ³ vertÄ buvo tiesiog kaÅ¾kas taip paprasta, kaip teisinga ir neteisinga, kad pasakoja, ar ar ne todÄl, kad gabalas informacijos egzistuoja struktÅ«ros? Loginius operatorius gali bÅ«ti taip paprasta, kaip Å¡iek tiek. Realiai tai tikriausiai BYTE labiau nei truputÄ¯. Bet tai daug maÅ¾esnis nei saugoti gal 50-simboliÅ³, pavyzdÅ¾iui. 

Taigi bando, panaÅ¡Å«s Ä¯ maiÅ¡os lenteles, kuri sujungia matricas ir susijÄ sÄraÅ¡as bando sujungti matricos, struktÅ«ros, o patarimÅ³ kartu saugoti duomenis Ä¯domus bÅ«das tai gana skiriasi nuo kÄ mes matÄme iki Å¡iol. Dabar mes naudojame informacijÄ, kaip plano narÅ¡yti Å¡iuos duomenis struktÅ«rÄ. Ir jei mes galime stebÄti veiksmÅ³ planas, jei mes galime sekti duomenis iÅ¡ pradÅ¾ios iki pabaigos, mes Å¾inoti, ar tais duomenimis egzistuoja TRIE. 

Ir jei mes negalime sekti Å¾emÄlapÄ¯ nuo ty baigti ne visi, duomenys gali neegzistuoja. VÄlgi, raktai Äia yra garantuoja, kad bus unikalus. Ir taip skirtingai maiÅ¡os lentelÄs, mes niekada tenka susidurti su susidÅ«rimÅ³ Äia. Ir ne du gabalai duomenis turi lygiai tÄ patÄ¯ planÄ iÅ¡skyrus atvejus, kai duomenys yra identiÅ¡ki. 

Jei mes Ä¯terpti JonÄ, tada mes ieÅ¡kome Jono. Å tai du identiÅ¡ki gabalus duomenys, tiesa, mes ieÅ¡kome per. Bet kitaip, bet koks dviejÅ³ daliÅ³ duomenys garantuoja, kad turi unikaliÄ planus per Å¡ios duomenÅ³ struktÅ«ros. Ir mes ketiname paÅ¾velgti vizualiai tai vos akimirkÄ. 

Mes tai padaryti bando sukurti naujÄ duomenÅ³ struktÅ«rÄ, kartografavimo Å¡iuos pagrindinius vertÄs poras. Tokiu atveju, mes neketiname naudoti kaÅ¾kas taip paprasta, kaip BÅ«lio. Mes iÅ¡ tikrÅ³jÅ³ bus saugomi eilutÄ. Ir tai styginiÅ³ ketina bÅ«ti universiteto pavadinimÄ. 

Ir svarbiausia bus metai kai buvo Ä¯kurta, kad universitetÅ³. Visi universitetams metÅ³ ketina sudaryti keturi skaitmenys. Ir todÄl mes naudosime tuos keturis skaitmenis Ä¯ narÅ¡yti Å¡ios duomenÅ³ struktÅ«ros. Ir mes pamatysime, vÄlgi, kaip mes darome, kad vos per sekundÄ. 

Tuo kelio pabaigoje, matysime pavadinimÄ Universiteto, kuris atitinka Ä¯ Å¡Ä¯ raktÄ, Å¡ie keturi skaitmenys. PagrindinÄ idÄja yra TRIE yra mes turime pagrindinÄ¯ marÅ¡rutÄ. Taigi apie tai galvoti kaip medis. Ir tai yra panaÅ¡ios raÅ¡ymo ir koncepcijos iki medÄ¯. Paprastai, kai mes galvojame apie medÅ¾iai ir realiame pasaulyje, jie turi Å¡aknÄ¯, kad yra Ä¯ Å¾emÄs ir jie auga aukÅ¡tyn ir jie turi filialus ir jie turi lapus. Ir iÅ¡ esmÄs yra idÄja Trie yra lygiai tas pats, iÅ¡skyrus tai, kad Å¡aknys yra Ä¯tvirtinta kaÅ¾kur danguje. Ir lapai yra apaÄioje. 

Taigi, tai lyg atsiÅ¾velgiant Ä¯ medÄ¯ ir tiesiog prakeiktas jis aukÅ¡tyn kojom. TaÄiau vis dar yra filialai. Ir tie bÅ«tÅ³ mÅ«sÅ³ keliai, tie bus mÅ«sÅ³ jungtys nuo iki lapÅ³ Å¡aknis. Å iuo atveju, tie, takai, Å¡ie filialai yra paÅ¾enklintos skaitmenÅ³ kad pasakys mus kuriuo keliu eiti iÅ¡ kur mes esame. 

Jei mes matome 0, mes eiti Å¡io filialo, jei matome 1, mes eiti Å¡io filialo, ir taip ir taip toliau. Na, kÄ tai reiÅ¡kia? Na, tai reiÅ¡kia, kad kiekviename sankryÅ¾os taÅ¡ko ir kiekvienas mazgas viduryje ir kiekvienÄ filialas, Yra 10 galima vietos, kad mes galime eiti. Taigi yra 10 patarimÅ³ iÅ¡ kiekvienos vietos. 

Ir tai, kai bando galite gauti Å¡iek tiek bauginanti kaÅ¾kam kas neturi daug patirtis kompiuteriÅ³ mokslo anksÄiau. Bet bando tikrai gana awesome. Ir jei jÅ«s turite galimybÄ dirbti su jais ir jÅ«s esate pasirengÄ kasti-in ir eksperimentuoti su jais, jie tikrai gana Ä¯domi duomenÅ³ struktÅ«ros dirbti. Jei norime Ä¯terpti elementÄ Ä¯ TRIE, visi mes turime daryti yra sukurti teisingÄ keliÄ iÅ¡ Ä¯ lapÅ³ Å¡aknÅ³. Å tai kÄ kiekvienas Å¾ingsnis kartu bÅ«das gali atrodyti. Mes ketiname nustatyti naujÄ duomenÅ³ struktÅ«ra naujÄ mazgo vadinamas TRIE. 

Ir viduje, kad duomenys struktÅ«ra yra du gabalai. Mes ketiname saugoti Pavadinimas universitete. Ir mes ketiname saugoti AN nurodymus masyvo kitÅ³ mazgÅ³ to paties tipo. Taigi, vÄl, tai yra tai, kad rÅ«Å¡iuoti nuo koncepcijos visur mes esame, mes ne 10 galima vietos, mes galime eiti. Jei mes matome 0, mes eiti Å¡iuo filialÄ. Jei mes matome 1, tai filialas, ir taip toliau, ir taip toliau, ir taip toliau. Jei mes sakome, 9, mes eiti Å¡iuo filialÄ. Taigi kiekviename sandÅ«ros taÅ¡ke, mes galime eiti 10 galimÅ³ vietÅ³. Taigi kiekvienas mazgas turi bÅ«ti 10 patarimÅ³ kitÅ³ mazgÅ³, daugiau kaip 10 kitÅ³ mazgÅ³. 

Ir duomenys mes saugoti yra Tiesiog universiteto pavadinimÄ. Taigi leiskite statyti TRIE. Leiskite Ä¯dÄti pora daiktÅ³ Ä¯ mÅ«sÅ³ TRIE. Taigi paÄiame virÅ¡uje, tai yra mÅ«sÅ³ Å¡aknys mazgas. Tai turbÅ«t bus kaÅ¾kas jÅ«s ketinate globaliai skelbiame. Ir jÅ«s ketinate globaliai iÅ¡laikyti rodyklÄ Ä¯ Å¡Ä¯ mazgÄ visada. 

JÅ«s ketinate pasakyti, Å¡aknis lygi, ir jÅ«s ketina malloc sau TRIE mazgas. Ir jÅ«s niekada vÄl paliesti Å¡aknis. KiekvienÄ kartÄ, kai norite pradÄti narÅ¡yti, galite nustatyti kitÄ rodyklÄ lygus Å¡aknis, pavyzdÅ¾iui, Trav, kuris yra pavyzdys, naudoti daugelis mano video Äia kaminai ir eilÄse ir nuoroda sÄraÅ¡ai ir pan. 

JÅ«s nustatote vienÄ Å¾ymiklÄ¯ vadinamas Trav uÅ¾ SankryÃ¾os. Ir jÅ«s naudojate Trav narÅ¡yti per duomenÅ³ struktÅ«ra. Taigi paÅ¾iÅ«rÄkime, kaip tai gali atrodyti. Taigi dabar, kÄ Ar mazgas atrodo? Na, kaip mÅ«sÅ³ duomenÅ³ struktÅ«ra deklaracija nurodÄ, turime eilutÄ, kuri Å¡iuo atveju yra tuÅ¡Äias. NÄra nieko Äia. 

Ir po 10 patarimÅ³ masyvo. Ir dabar, mes tik Turiu 1 mazgas Å¡iame TRIE. NÄra nieko dar jame. Taigi visi tie 10 rodyklÄs taÅ¡kas Ä¯ NULL. Å tai kÄ raudona rodo. 

Leiskite Ä¯terpti eilutÄ Harvardo. Leiskite Ä¯raÅ¡yti universitetas Harvardo Ä¯ Å¡Ä¯ TRIE, kuris buvo Ä¯kurta metÅ³ 1636. Mes norime naudoti raktÄ, 1636, pasakyti mums, kur mes ketina laikyti Harvardo Ä¯ TRIE. Dabar, kaip gali mes tai darome? 

Tai gali atrodyti kaÅ¾kÄ panaÅ¡aus Ä¯ tai. Mes pradedame Å¡aknis. Ir mes turime Å¡iuos 10 vietÅ³, mes galime eiti. Å aknis yra kaip bet kuris kitas mazgas TRIE. Yra 10 vietÅ³, mes galime eiti iÅ¡ Äia. 

Kur mes tikriausiai nori eiti, jei raktas yra 1636? Yra tikrai du variantai. TeisÄ. Galime pastatyti nuo raktÄ iÅ¡ deÅ¡inÄs Ä¯ kairÄ ir pradÄti su 6. Arba mes galime sukurti iÅ¡ raktÄ Ä¯ kairÄ Ä¯ deÅ¡inÄ ir pradÄti 1 d. 

Tai tikriausiai daugiau intuityvi kaip Å¾mogus Mes suprantame, kad bus Tiesiog eikite Ä¯ kairÄ Ä¯ deÅ¡inÄ. Ir taip, jei noriu Ä¯terpti Harvardo Ä¯ Å¡Ä¯ TRIE, AÅ¡ tikriausiai norite pradÄti pradedant Å¡aknis, Å¾iÅ«ri mano 10 variantÅ³ prieÅ¡ais mane, ir sako: Noriu eiti Ä¯ 1 keliu. GERAI. 

Dabar, 1 kelias Å¡iuo metu yra tuÅ¡Äias. Taigi, jei aÅ¡ noriu tÄsti Å¡iuo keliu Ä¯terpti Å¡Ä¯ elementÄ Ä¯ TRIE, Turiu malloc naujÄ mazgas, turime 1 ten rodo, o tada aÅ¡ gerai eiti. 

Taigi aÅ¡ iÅ¡ esmÄs esu ne vieta, kur aÅ¡ stoviu tuo medÅ¾io arba iÅ¡ Å¡aknies Trie ir yra 10 skyriai. Bet kiekvienas filialas turi vartai prieÅ¡ais jÄ¯. TeisÄ. Nes ten nieko nÄra. NÄra saugÅ³. Tai reiÅ¡kia, kad ten nieko Å¾emyn nors iÅ¡ Å¡iÅ³ Å¡akÅ³. Jei aÅ¡ noriu pradÄti statyti kaÅ¾kas, aÅ¡ noriu paÅ¡alinti vartai. Noriu paÅ¡alinti vartai prieÅ¡ais skaiÄius 1. Ir aÅ¡ noriu vaikÅ¡Äioti Å¾emyn, kad. Ir aÅ¡ noriu statyti kita man kur eiti. 

Ir tai, kÄ aÅ¡ padariau Äia. Taigi 1 nebÄra nurodo null. Sakiau tai saugu eiti Äia dabar. AÅ¡ pastatyti dar vienÄ mazgÄ. Ir kai aÅ¡ gauti tÄ mazgÄ, aÅ¡ turi kitÄ sprendimÄ padaryti. Kur aÅ¡ ketinu eiti nuo Äia? 

Na, aÅ¡ jau sumaÅ¾Äjo 1. Taigi, dabar aÅ¡ tikriausiai norite eiti Ä¯ 6 d. TeisÄ. VÄlgi, aÅ¡ turiu 10 vietas galiu rinktis. Taigi leiskite dabar eiti numeriu 6. Taigi aÅ¡ iÅ¡valyti vartai prieÅ¡ais numeriu 6. Ir aÅ¡ vaikÅ¡Äioti ten. Ir aÅ¡ statyti dar mazgas. Ir aÅ¡ pasiekÄ kitÄ sankryÅ¾os taÅ¡kÄ. 

VÄlgi, aÅ¡ turiu 10 pasirinkimus o kur aÅ¡ galiu eiti. AÅ¡ persikÄlÄ nuo 1 iki 6. Taigi, dabar aÅ¡ tikriausiai norite eiti Ä¯ 3 dalis. 3, ten kur aÅ¡ galiu eiti. Taigi turiu iÅ¡valyti keliÄ ir kurti sau naujÄ erdvÄ. Ir tada iÅ¡ 3, kur aÅ¡ noriu eiti? Noriu eiti 6. 

Ir vÄl, aÅ¡ turÄjau iÅ¡valyti keliÄ tai padaryti. Taigi, dabar aÅ¡ naudojamas mano klaviÅ¡Ä Ä¯terpti sukurti mazgai ir pradÄti statyti TRIE. AÅ¡ pradÄjau Å¡aknis. AÅ¡ sumaÅ¾Äjo 1636. Ir dabar aÅ¡ apaÄioje ten tÄ mazgÄ. Ir jums gali bÅ«ti suteikta galimybÄ matyti ekrane. 

Jis pabrÄÅ¾Ä, geltonos spalvos. Å tai kur aÅ¡ Å¡iuo metu esu. Mano pagrindinÄ daroma. AÅ¡ iÅ¡naudojo kiekvienÄ pozicijÄ mano raktu. Taigi aÅ¡ negaliu eiti toliau. Taigi Å¡iuo metu, viskas, kÄ aÅ¡ tikrai reikia padaryti, tai pasakyti, Gerai. Tai lyg ieÅ¡kote Å¾emyn Ä¯ Å¾emÄ, jei jÅ«s vizijos BÅ«k kaip Å¡io kelio rÅ«Å¡iuoti su skirtingÅ³ jungÄiÅ³. RÅ«Å¡iuoti Å¾iÅ«ri ir tarsi DaÅ¾ymas purkÅ¡tuvu, Harvardo ant Å¾emÄs. Å tai Å¡iuo vardu. Å½inokite, kad tai, kas Å¡ioje vietoje. Jei pradÄsime Å¡aknis ir mes eiti 1 ir tada 6 ir tada 3 ir tada 6, Kur mes esame? Na, jei mes Å¾iÅ«rime Å¾emyn ir matome Harvardo, tada mes Å¾inome, kad Harvardo buvo Ä¯kurta 1636 remiasi bÅ«du mes Ä¯gyvendinti Å¡iuos duomenis struktÅ«rÄ. Taigi, tai buvo tikiuosi paprasta. Mes ketiname padaryti du intarpais. Ir tikiuosi, kad bus padÄti pamatyti tai padaryti du kartus daugiau. 

Dabar galime Ä¯terpti kitÄ universitetÄ. Leiskite Ä¯dÄti Ä¯ Å¡Ä¯ Yale TRIE. Yale "buvo Ä¯kurta 1701 m. Taigi mes pradÄsime ne Å¡aknis, kaip mes visada darome. Ir mes nustatyti SankryÃ¾os Å¾ymeklÄ¯. Mes ketiname naudoti, kad pereiti per. Pirmas dalykas, mes norime padaryti, tai eiti Ä¯ 1 keliu. Å tai pirmas skaitmuo mÅ«sÅ³ raktu. Laimei, nors mes ne daryti bet kokÄ¯ darbÄ Å¡Ä¯ kartÄ. 1 m kelias jau buvo iÅ¡valytas. AÅ¡ vartÅ³ anksÄiau, kai aÅ¡ buvo Ä¯terpiant Harvardo 1636. Taigi aÅ¡ galiu saugiai judÄti Å¾emyn 1 ir tiesiog eiti ten. Jei gali judÄti Å¾emyn 1 d. 

Dabar, nors, aÅ¡ noriu eiti Ä¯ 7. AÅ¡ atvÄrÄs keliÄ po 6. Å½inau, kad galiu saugiai pereiti Å¾emyn 6 keliÄ. Bet man reikia pradÄti nuo 7 keliu. Taigi, kÄ man reikia daryti? Na, kaip ir anksÄiau, aÅ¡ tiesiog reikia iÅ¡valyti vartai, gauti iÅ¡ kelio, ir kurti naujÄ mazgÄ iÅ¡ 7 keliu. Tiesiog, kaip Å¡is. 

Taigi dabar aÅ¡ persikÄlÄ 1 ir tada 7. Ir dabar pastebÄsite, aÅ¡ rÅ«Å¡iuoti dÄl Å¡ios naujos subbranch. TeisÄ. Visa kita nuo 16 , aÅ¡ nerÅ«pi. AÅ¡ nesu daro 16 nieko. Darau 17 stuff. 

Taigi dabar nuo 17, aÅ¡ turiu rÅ«Å¡iuoti naujÅ³ bÅ«dÅ³ Äia. Kitas skaitmenÅ³ mano raktas yra 0. AÅ¡ aiÅ¡kiai negali gauti bet kur. AÅ¡ tiesiog pastatÄ Å¡Ä¯ mazgÄ. Taigi aÅ¡ Å¾inau, nÄra keliai Ä¯ priekÄ¯ nuo Äia. Taigi turiu padaryti vienÄ save. 

Taigi aÅ¡ malloc naujÄ mazgas ir turi 0 balÅ³ ten. Ir tada dar kartÄ, aÅ¡ malloc Naujas mazgas ir turi vienÄ taÅ¡kÄ ten. VÄlgi, aÅ¡ iÅ¡naudojo savo raktÄ, 1701. Taigi man atrodo, ir aÅ¡ daÅ¾Å³ purkÅ¡tuvu Yale. Å tai Å¡io mazgo vardas. 

Ir todÄl dabar, jei aÅ¡ kada nors reikÄs pamatyti, jei Yale yra Å¡iame TRIE, aÅ¡ pradedu tuo Å¡aknis, AÅ¡ eiti 1701 ir Å¾iÅ«rÄti Å¾emyn. Ir jei matau Yale purkÅ¡tuvÄ daÅ¾yti ant Å¾emÄs, tada Å½inau Jeilio egzistuoja Å¡iame TRIE. Padarykim dar vienÄ. Leiskite Ä¯dÄkite Dartmouth Ä¯ tai Trie, kuri buvo Ä¯kurta 1769 m. 

Prasideda Å¡aknies iÅ¡ naujo. Mano pirmasis skaitmuo mano raktas yra 1. Galiu drÄsiai judÄti Å¡iuo keliu. Tai jau egzistuoja. Kitas skaitmuo mano raktas yra 7. Galiu drÄsiai judÄti Å¡iuo keliu. Ji egzistuoja, taip pat. 

Mano Å¡alia yra 6. IÅ¡ Äia, iÅ¡ kur aÅ¡ esu Å¡iuo metu geltonai ten toje vidurinÄje mazgas, 6 Å¡iuo metu yra uÅ¾rakinta iÅ¡jungtas. Jei aÅ¡ noriu eiti Å¡iuo keliu, Turiu jÄ kurti save. Taigi aÅ¡ malloc naujÄ mazgas ir turi 6 punktas ten. Ir tada vÄl, aÅ¡ Blazing naujÅ³ takai Äia. 

Taigi aÅ¡ malloc naujÄ mazgÄ taip, kad iÅ¡ kad node-- kelio numeris 9-- ir tada dabar jei aÅ¡ keliauti 1769 ir Å¾iÅ«riu Å¾emyn. NÄra nieko Å¡iuo metu purkÅ¡ti ten daÅ¾ytos. Gebu raÅ¡yti Dartmouth. Ir aÅ¡ Ä¯terpti Dartmouth Ä¯ TRIE. 

Taigi, kad Ä¯terpiant viskas Ä¯ TRIE. Dabar mes norime ieÅ¡koti dalykÅ³. Kaip mes ieÅ¡koti dalykÅ³ TRIE? Na, tai beveik tas pats idÄja. Dabar mes tiesiog naudoti rakto skaitmenÅ³ pamatyti, jei mes galime narÅ¡yti nuo Å¡aknÅ³ kur mes norime eiti Ä¯ TRIE. 

Jei mes paspauskite aklavietÄ bet kuriame taÅ¡ke, tada mes Å¾inome, kad Å¡is elementas negali egzistuoja arba kita, kad planas bÅ«tÅ³ jau buvo paÅ¡alinta. Jei mes padarysime tai visÄ keliÄ Ä¯ pabaiga, viskas, kÄ reikia padaryti, tai paÅ¾velgti ir pamatyti, jei tai elementas mes ieÅ¡kome. Jei taip, tai sÄkmÄs. Jei taip nÄra, nepavyks. 

Taigi leiskite ieÅ¡koti Harvardo Å¡iame TRIE. Mes pradedame Å¡aknis. Ir, vÄlgi, mes ketiname sukurti SankryÃ¾os Å¾ymiklÄ¯ padaryti mÅ«sÅ³ juda uÅ¾ mus. Nuo Å¡aknÅ³ mes Å¾inome, kad Pirmoji vieta turime eiti yra 1, mes galime padaryti, kad? Taip, mes galime. Jei saugiai egzistuoja. Mes galime eiti ten. 

Dabar, kitÄ vietÄ turime eiti yra 6. Ar 6 kelias egzistuoja iÅ¡ Äia? Taip, tai daro. Mes galime eiti Ä¯ 6 keliÄ. Ir mes galÅ³ gale Äia. 

Ar mes galime eiti Ä¯ 3 kelio nuo Äia? Na, kaip it turns out, Taip, kad egzistuoja per daug. Ir mes galime gauti apie 6 kelio nuo Äia? Taip, mes galime. 

Mes ne visai atsakÄ klausimas dar. Yra dar viena daugiau Å¾ingsnis, kuris yra dabar mes turime paÅ¾velgti Å¾emyn ir pamatyti, jei tai actually-- jei mes ieÅ¡kome Harvardo, yra tai, kad KÄ mes randame, kai mes iÅ¡naudoti raktÄ? Pavyzdyje mes naudojame Äia metams visada keturi skaitmenys. TaÄiau jums gali bÅ«ti naudojant pavyzdÅ¾iui, kai JÅ«s saugoti Å¾odÅ¾iÅ³ Å¾odynÄ. 

Ir taip uÅ¾uot 10 patarimÅ³ mano vietÄ, galite turÄti 26. Vienas kiekvienos abÄcÄlÄs raidÄs. Ir ten yra keletas, kaip Å¡ikÅ¡nosparniÅ³ Å¾odÅ¾iai kuris yra partijos poaibis, pavyzdÅ¾iui. Ir net jei jÅ«s gaunate Ä¯ pabaiga raktÄ ir jums paÅ¾velgti Å¾emyn, galbÅ«t nematote, kÄ JÅ«s ieÅ¡kote. 

Taigi jÅ«s visada turite feed visÄ keliÄ ir tada jei buvo sÄkmingai galÄtÅ³ feed visÄ keliÄ, Å¾iÅ«rÄti Å¾emyn ir padaryti vienÄ galutinÄ¯ patvirtinimÄ. Ar tai, kÄ aÅ¡ ieÅ¡kote? Na, aÅ¡ paÅ¾velgti Å¾emyn pradÄjus virÅ¡uje ir vyksta 1636. Å½iÅ«riu Å¾emyn. Matau Harvardo. Taigi, taip, man pavyko. KÄ daryti, jei aÅ¡ ko yra ne TRIE, nors. KÄ daryti, jei aÅ¡ ieÅ¡kau Princeton, kuri buvo Ä¯kurta 1746 m. Ir taip 1746 tampa mano raktas narÅ¡yti TRIE. Na, aÅ¡ pradedu tuo Å¡aknis. Ir pirmoji vieta Noriu Ä¯ krinta 1 keliu. Ar galiu tai padaryti? Taip, aÅ¡ galiu. 

Ar galiu eiti Ä¯ 7 kelio nuo ten? Taip, galiu. Tai egzistuoja per daug. Bet aÅ¡ galiu eiti Ä¯ 4 keliÄ iÅ¡ Äia? Å tai tarsi klausia klausimÄ, gali AÅ¡ toliau nustatyta, kad maÅ¾ai aikÅ¡tÄ kad aÅ¡ paryÅ¡kinamas geltonai? NÄra nieko ten. TeisÄ. 

NÄra Å¾ingsnis Ä¯ priekÄ¯ Å¾emyn 4 keliu. Jei Prinstono buvo Å¡iame TRIE, kad 4 bÅ«tÅ³ buvÄ prieki mums jau. Ir kad Å¡iuo metu mes pasiekÄ aklavietÄ. Mes negalime eiti toliau. Ir taip, mes galime pasakyti, galutinai, ne. Prinstono neegzistuoja Å¡iame TRIE. 

Taigi, kÄ visa tai reiÅ¡kia? TeisÄ. Yra daug vyksta Äia. Yra patarimÅ³ visur. Ir, kaip jÅ«s galite pamatyti, tik iÅ¡ diagramos, ten mazgÅ³ daug, kad yra rÅ«Å¡ies plaukioja aplink. TaÄiau pastebÄti kiekvienÄ kartÄ norÄjome patikrinti, ar kaÅ¾kas buvo Ä¯ TRIE, mes tik turÄjo padaryti 4 Å¾ingsnius. 

KiekvienÄ kartÄ, kai mes norÄjome Ä¯terpti kaÅ¾kÄ TRIE, mes turime padaryti 4 Å¾ingsnius, galbÅ«t mallocing kai pakeliui stuff. Bet, kaip matÄme, kai mes Ä¯dÄta Dartmouth Ä¯ TRIE, kartais kai kurie iÅ¡ kelio gali bÅ«ti jau prieki uÅ¾ mus. Ir taip mÅ«sÅ³ Trie gauna didesni ir didesni, mes turime padaryti maÅ¾iau darbo kiekvienÄ kartÄ Ä¯terpti naujus dalykus nes mes jau ve pastatÄ tarpinis daug filialai pakeliui. Jei mes tik kada nors paÅ¾velgti Ä¯ 4 dalykai, 4 yra tik konstanta. Mes tikrai yra natÅ«ra artÄja pastovus laikas Ä¯terpimo ir nuolatinis laiko perÅ¾valgos. Kompromisas, Å¾inoma, yra ta, kad tai Trie, kaip jÅ«s galite galbÅ«t pasakys, yra didÅ¾iulis. Kiekvienas iÅ¡ Å¡iÅ³ mazgÅ³ uÅ¾ima daug vietos. 

Bet tai kompromisas. Jei norime tikrai greitai Ä¯terpimo, tikrai greitai iÅ¡braukta, ir tikrai greitai perÅ¾valgos, turime turi daug duomenÅ³ plaukioja aplink. Mes turime atidÄti daug vietos ir atminties uÅ¾ tÄ duomenÅ³ struktÅ«ros egzistuoti. 

Ir taip tai kompromisas. TaÄiau atrodo, kad mes galÄjo jÄ radau. Mes nustatÄme, kad gali Gralis duomenÅ³ struktÅ«rÅ³ su greito Ä¯kiÅ¡imo iÅ¡braukta ir perÅ¾valgos. O gal tai bus tinkamÅ³ duomenÅ³ struktÅ«ra naudoti dÄl kokios nors informacijos mes bandome parduotuvÄje. AÅ¡ Doug Lloyd, tai CS50.