[MUZIKO Ludante] DOUG LLOYD: Do ni estis inching proksime kaj pli proksimen, ke sankta grail de datumoj strukturoj, unu kiu ni povas enmeti en, forigi el, kaj rigardi supren en konstanta tempo. Dekstra. Tio estas speco de la golo. Ni volas povi fari aferojn tre, tre rapide. 

Tion ni trovis ŝin tie kiam ni parolas pri klopodoj? Nu, ni rigardu. Do ni vidis plurajn malsamaj datumstrukturoj tenantaj la surĵeto de tn ŝlosilo-valoro paroj, surĵeto iu peco de datumoj al alia peco de datumoj tial ni scias kie trovi informo en la strukturo. 

Do por tabelo, ekzemple, la ŝlosilo estas la elemento indekso aŭ tabelo ĉelo 0 aŭ tabelo 1 kaj tiel plu. Kaj la valoro estas la datumoj kiu ekzistas ĉe tiu loko. Do kio estas stokita en tabelo 0? Kio estas stokita en tabelo 1 kontre nur 0 kaj 1, kiuj estus la ŝlosilojn. 

Kun hash tablo estas ia la sama ideo. Kun hash tablo, ni havas ĉi hash funkcion kiu generas hash kodojn. Do la ŝlosilo estas la hash kodon de la datumoj. Kaj la valoro, aparte ni parolis pri ĉenante en la video sur hash tabloj, estas ke ligillisto de datumoj ke hashes al tiu hashcode. Dekstra. Kio pri alian alproksimiĝon tiu metodo, kvankam? Kio pri metodo kie la ŝlosilo estas garantiita esti unika, kontraste hash tablo, kie ni povis finos kun du pecoj de datumoj havantaj la saman hashcode. Kaj tiam ni devas trakti ke per ĉu tuŝoprobado aŭ pli prefere ĉenante ripari tiun problemon. 

Do nun ni povas garantii ke nia ŝlosilo estos unika. Kaj kio se nia valoro estis nur io tiel facila kiel vera kaj falsa kiu diras al ni, cxu aŭ ne ke peco de informo ekzistas en la strukturo? Al Bulea povus esti kiel simpla kiel iom. Realisme estas probable Bajto pli verŝajna ol iom. Sed tio estas multe pli malgranda ol stokante eble 50-signoĉenon, ekzemple. 

Do provas, simila al hash tabloj, kiu kombinas arrays kaj ligillisto, tries kombini arrays, strukturoj, kaj punteros kune por stoki datumoj en interesa maniero kiu estas bela malsama ion ni vidis ĝis nun. Nun ni uzas la datumojn kiel vojmapon navigi tiu datumstrukturo. Kaj se ni povas sekvi la vojmapon, se ni povas sekvi la datenoj de komencanta fini, ni scias ĉu tiu datumo ekzistas en la trie. 

Kaj se ni ne povas sekvi la mapo el signifanta finiĝu ĉiuj, la datumoj povas ne ekzisti. Denove, la klavoj jen garantiita esti unika. Kaj tiel kontraste hash tablo, ni neniam devos pritrakti koliziojn tie. Kaj ne du pecoj de datumoj havas ekzakte la saman vojmapon se tio datumoj estas identaj. 

Se ni enmeti Johanon, tiam Ni serĉu por John. Jen du identaj pecoj de datumoj, ĝuste, ni serĉas tra. Sed alie, iu du pecoj de datumoj estas garantiita havi unikan roadmaps tra ĉi datumstrukturo. Kaj ni tuj rigardu vida de tiu en nur momento. 

Ni faros tion per provo krei novan datumstrukturo, surĵeto la jenaj ŝlosilaj valoro paroj. En tiu kazo, ni ne tuj uzi iu tiel simpla kiel Bulea. Ni efektive konservos la kordo. Kaj ke kordoj tuj esti la nomo de universitato. 

Kaj la ŝlosilo tuj estos la jaro kiam tiu universitato estis fondita. Ĉiuj jaroj por universitatoj tuj estos kvar ciferoj. Kaj tial ni uzas tiujn kvar ciferoj por navigi tra tiu datumstrukturo. Kaj ni vidos, denove, kiom ni faru tion en nur dua. 

Fine de la pado, ni vidos la nomo de la universitato kiu respondas al tiu klavo, tiuj kvar ciferoj. La baza ideo malantaŭ trie Estas ni havas centran itineron. Do pensu pri ĝi kiel arbon. Kaj tiu estas simila en ortografio kaj en koncepto al arbo. Ĝenerale, kiam ni pensas pri arboj en la reala mondo, ili havas radikon kiu estas en la teron kaj kreskas supren kaj ili havas branĉojn kaj ili havas foliojn. Kaj esence la ideo de trie estas ekzakte la sama, krom ke radiko estas ankrumita ie en la ĉielo. Kaj la folioj estas en la fundo. 

Do ĝi estas speco de kiel preni arbo kaj ĝuste klakanta renversos. Sed estas ankoraŭ branĉoj. Kaj tiuj estus niaj vojoj, tiuj estos nia rilatoj de la radiko al la folioj. En tiu kazo, tiuj vojetoj, tiuj branĉoj estas etikedita kun ciferoj, kiuj montras kiun vojo iri de kie ni estas. 

Se ni vidas ĉirkaŭ 0, ni iras, ĉi tiu branĉo, se ni vidas 1, ni iras, ĉi tiu branĉo, kaj tiel kaj tiel plu. Nu, kion tio signifu? Nu, tio signifas ke ĉe ĉiu krucvojo punkto kaj ĉiu nodo en la mezo kaj ĉiu branĉo, ekzistas 10 eblaj lokoj kiujn ni povas iri. Do estas 10 punteros de ĉiu loko. 

Kaj tiu estas kie tries povas akiri iomete timiga por iu kiuj estas ne havas multajn sperto en komputiko antaŭe. Sed provoj estas vere bela awesome. Kaj se vi havas la eblecon labori kun ili kaj vi pretas fosi -in kaj sperti kun ili, ili estas vere sufiĉe interesa datumstrukturoj labori kun. Se ni volas enmeti ero en la trie, ĉiuj ni devas fari estas konstrui la ĝustan padon de la radiko al la folio. Jen kion ĉiupaŝe kune la vojo povus aspekti. Ni tuj difini novajn datumojn strukturon por nova nodo nomata trie. 

Kaj ene de tiu datumoj strukturo estas du pecoj. Ni tuj stoki la nomo de universitato. Kaj ni tuj stoki tabelo de punteros al aliaj nodoj de la sama tipo. Do, denove, ĉi tiu estas tia de koncepto de ĉie ni estas, ni ĉe 10 eblaj lokoj oni povas iri. Se ni vidas ĉirkaŭ 0, ni iras, tiu branĉo. Se ni vidas 1, ĉi tiu branĉo, kaj tiel plu kaj tiel plu kaj tiel plu. Se ni diras 9, ni iras malsupren tiu branĉo. Do je ĉiu punkto junton, ni povas iri 10 eblaj lokoj. Do ĉiu nodo havas enhavi 10 punteros al aliaj nodoj, al 10 aliaj nodoj. 

Kaj la datumoj ni stokante estas nur la nomo de la universitato. Do ni konstruu trie. Ni enmeti paron de erojn en nia trie. Do ĉe la plejsupro, jen nia radika nodo. Tio sendube estas tuj estos iu vi tuj tutmonde deklaras. Kaj vi tuj tutmonde subteni puntero al tiu nodo ĉiam. 

Vi tuj diros, radiko egalas, kaj vi estas tuj malloc mem trie nodo. Kaj vi neniam iras tuŝi radiko denove. Ĉiufoje vi volas komenci navigi tra, vi fiksis alian montrilon egala al radiko, kiel trav, kiu estas la ekzemplo mi uzi en multaj de miaj filmetoj tie sur stakoj kaj atendovicoj kaj karmo lertaj kaj tiel plu. 

Vi starigis alian montrilon nomata trav por trairado. Kaj vi uzas trav navigi tra la datumstrukturo. Do ni vidu kiel ĉi povus rigardi. Do nun, kio does nodo aspektas? Nu, ĝuste kiel nia datumoj strukturo deklaro indikis, ni havas ĉenon, kiu en tiu kazo estas malplena. Nenio ĉi tie. 

Kaj tabelo de 10 punteros. Kaj nun, ni nur havas 1 nodo en ĉi trie. Ekzistas nenio en ĝi. Do ĉiuj 10 el tiuj punteros punkto al nula. Tion la ruĝa indikas. 

Ni enŝovu la kordo Harvard. Ni enŝovu la Universitato de Harvard en ĉi trie, kiu estis fondita en la jaro 1636. Ni volas uzi la ŝlosilon, 1636, por diri al ni kie ni estas tuj stoki Harvard en la trie. Nun, kio povus ni faru tion? 

Eble aspektas tiel. Ni starti je la radiko. Kaj ni havas tiujn 10 lokoj oni povas iri. La radiko estas nur kiel ajna alia nodo de la trie. Ekzistas 10 lokoj ni povas iri de tie. 

Kie ni probable volas iri se la ŝlosilo estas 1636? Ekzistas vere du ebloj. Dekstra. Ni povas konstrui la ŝlosilo de dekstra al maldekstra kaj komenci kun 6. Aŭ ni povus konstrui la ŝlosilo de maldekstre dekstren kaj komenci kun 1. 

Estas probable pli intuicia kiel homo kompreni ni Nur iru maldekstre dekstren. Kaj do se mi volas enmeti Harvard en ĉi trie, Mi verŝajne volas komenci komencante ĉe la radiko, rigardante mian 10 ebloj antaŭ mi, kaj dirante Mi volas iri malsupren la 1 pado. BONE. 

Nun, 1 vojo estas nuntempe nula. Do, se mi volas daŭrigi laŭ tiu vojo enigi tiun elementon en la trie, Mi havas malloc novan nodon, havas 1 atentigi tie, kaj tiam mi estas bona iri. 

Do mi esence estas je punkto kie mi staris ĉe la radiko de la arbo aŭ la trie kaj ekzistas 10 branĉoj. Sed ĉiu branĉo havas pordego antaŭ ĝi. Dekstra. Ĉar estas nenio alia ekzistas. Neniu sekura trairejo. Tio signifas ke nenio estas malsupren iu el tiuj branĉoj. Se mi volas komenci konstruaĵo ion, mi volas forigi la pordego. Mi volas forigi la pordego antaŭ numeron 1. Kaj mi volas promeni malsupren tio. Kaj mi volas konstrui alia loko por mi iri. 

Kaj tio estas kion mi faris tie. Do 1 ne plu notas al nula. Mi jam diris ke estas sekure iri malsupren tien nun. Mi konstruis alia nodo. Kiam mi alvenas al tiu nodo, Mi havas alian decidon fari. Kie mi tuj iros de tie ĉi? 

Nu, mi jam subiris la 1. Do nun mi probable volas iri malsupren la 6an. Dekstra. Denove, mi havas 10 lokojn mi povas elekti. Do ni nun iru malsupren numero 6. Do mi malbari la pordego antaŭ numero 6. Kaj mi iras tien. Kaj Mi konstruos al alia nodo. Kaj mi atingis alian junton punkto. 

Denove, mi havas 10 elektoj cxar kie mi povas iri. Mi kopiis de 1 ĝis 6. Do nun mi probable volas iri al 3. 3, ekzistas nenie mi povas iri. Do mi devas liberigi la vojon kaj konstruos al mi novan spacon. Kaj tiam de 3, kie mi volas iri? Mi volas iri malsupren 6. 

Kaj, denove, mi devis liberigi la vojon por fari ĝin. Do nun mi uzis mian ŝlosilon enigi krei nodoj kaj komenci konstrui ĉi trie. Mi komencis ĉe la radiko. Mi iris malsupren 1636. Kaj nun mi estas ĉe la fundo tie en tiu nodo. Kaj vi eble povus vidi ĝin sur via ekrano. 

Ĝi estas elstarigita en flava. Tie estas kie mi nuntempe estas. Mia ŝlosilo estas farita. Mi jam elĉerpita ĉiu pozicio en mia ŝlosilo. Do mi ne povas iri plu. Do en ĉi tiu punkto, ĉiuj mi vere devas fari estas diri, OK. Estas ia ŝatas rigardanta malsupren al la planko, se vi antaŭvidante mem kiel tian vojon kun malsamaj rilatoj. Ia rigardante malsupren kaj ia ŝprucigi pentranta Harvard surgrunde. Tio estas la nomo de tiu. Sciu ke estas kio estas ĉe tiu loko. Se ni komencas je la radiko kaj ni iru malsupren 1 kaj poste 6 kaj tiam 3 kaj poste 6 kie ni estas? Nu, se ni rigardas malsupren kaj ni vidos Harvard, tiam ni scias ke Harvard estis fondita en 1636 surbaze de la maniero ni implementando ĉi datumstrukturo. Tiel estis espereble simpla. Ni tuj fari du pli inserciones. Kaj espereble tio helpos al vidu ĉi farita dufoje pli. 

Nun, ni enŝovu alia universitato. Ni enigi Yale en ĉi trie. Yale fondiĝis en 1701. Do ni komencu ĉe la radiko, kiel ni ĉiam faras. Kaj ni starigis al trairado montrilo. Ni tuj uzos tiun por movi tra. La unua afero ni volas fari estas iri malsupren la 1 pado. Tio estas la unua cifero de nia ŝlosilo. Feliĉe, tamen, ni ne devi fari ian laboron ĉi tempon. La 1 vojo jam estis malbarita. Mi malbaris lin antaŭe kiam mi estis enmeto Harvard je 1636. Do mi povas sekure movi malsupren 1 kaj simple iri tien. Se povas movi malsupren la 1. 

Nun, tamen, mi volas iri al 7. Mi malbaris la vojon ĉe 6. Mi scias mi povas sekure procedi malsupren la 6an pado. Sed mi devas iri sur la 7 pado. Do kion mi devas fari? Nu, samkiel antaŭe, mi nur bezonas malbari la pordego, liberigu la vojon, kaj konstruu novan nodon de la 7 pado. Ĝuste kiel ĉi. 

Do nun mi kopiis 1 kaj tiam 7. Kaj nun rimarkas, mi estas ia de sur tiu nova subramal. Dekstra. Ĉio alia el 16 on, mi ne zorgas pri. Mi ne faras 16 nenion. Mi faras 17 stuff. 

Do nun el 17 sur, mi devas ia Blaze novaj migrovojoj tie. La sekva cifero mia ŝlosilo estas 0. Mi klare ne povas ie. Mi nur konstruis ĉi nodo. Do mi scias ne estas padojn antaŭen de tie. Do mi devas fari unu mem. 

Do mi malloc nova nodo kaj havas 0 punkto tie. Kaj tiam unu pli tempon, mi malloc a nova nodo kaj havas unu punkto. Denove, mi elĉerpis mian ŝlosilon, 1701. Do mi rigardas malsupren kaj mi spray pentras Yale. Tio estas la nomo de tiu nodo. 

Kaj tial nun, se mi iam bezonas vidi se Yale Estas en ĉi trie, mi komencas je la radika, Mi iras malsupren 1701, kaj subrigardi. Kaj se mi vidas Yale spray pentrita sur la tero, tiam Mi scias Yale ekzistas en ĉi trie. Ni faru pli. Ni enigi Dartmouth en tiun trie, kiu estis fondita en 1769. 

Komencu ĉe la radiko denove. Mia unua cifero de mia ŝlosilo estas 1. Mi povas sekure movi malsupren ke vojo. Kiu jam ekzistas. La sekva cifero de mia ŝlosilo estas 7. Mi povas sekure movi malsupren ke vojo. Ekzistas ankaŭ. 

Mia sekvanta estas 6. De tie, de kie mi nuntempe estas en flava tie en tiu meza nodo, 6 estas nun ŝlosita for. Se mi volas iri malsupren tiu vojo, Mi devas konstrui mem. Do mi malloc nova nodo kaj havas 6 punkto tie. Kaj tiam, denove, mi estas flamadanta novaj migrovojoj tie. 

Do mi malloc nova nodo tiel ke de ke node-- padon nombro 9-- kaj tiam nun se mi vojaĝas 1769, kaj mi rigardas suben. Nenio aktuale ŝprucigi pentris tie. Mi povas skribi Dartmouth. Kaj mi insertita Dartmouth en la trie. 

Do jen enmeto aferojn en la trie. Nun ni volas serĉi aĵojn. Kiel ni serĉu por aĵoj en la trie? Nu, estas preskaux la sama ideo. Nun ni nur uzu la ciferojn de la klavon al vidi se ni povas navigi de la radiko al kie volas iri en la trie. 

Se ni batis sakstrato ĉe ajna punkto, tiam ni scias, ke tiu elemento ne ekzistas povas aŭ alia ke pado jam estis malbarita. Se ni faras ĝin la tutan vojon al Fine, ĉiuj ni devas fari estas malsupren rigardi kaj vidi se tio estas la elemento ni serĉas. Se jes, sukceso. Se ĝi ne estas, malsukcesi. 

Do ni serĉi Harvard en ĉi trie. Ni starti je la radiko. Kaj, denove, ni tuj krei trairado montrilon fari nian movoj por ni. El la radiko ni scias ke la Unue ni devas iri estas 1, ni faru tion? Jes ni povas. Se sekure ekzistas. Ni povas iri tie. 

Nun, la sekvanta loko ni devas iri estas 6. Ĉu la 6 padon ekzistas de ĉi tie? Jes, ĝi faras. Ni povas iri malsupren la 6an pado. Kaj ni finas tie. 

Ĉu ni povas iri malsupren la 3an padon de ĉi tie? Nu, kiel ĝi rezultas, jes, ke ekzistas ankaŭ. Kaj ni povas akiri sur la 6 padon de ĉi tie? Jes ni povas. 

Ni ne tute respondis la demandon ankoraŭ. Ekzistas ankoraŭ unu pli paŝo, kio estas nun ni devas rigardi malsupren kaj vidu se tio actually-- se ni serĉas Harvard, estas ke kion ni trovos post ni elĉerpas la klavo? En la ekzemplo ni uzas ĉi tie, la jaroj estas ĉiam kvar ciferoj. Sed vi povus esti uzante la ekzemplon kie vi amasigas vortaron de vortoj. 

Do anstataŭ havi 10 punteros cxar mia loko, vi eble havas 26. Unu por ĉiu litero de la alfabeto. Kaj estas kelkaj vortoj kiel vesperton, kiu estas subaro de aro, ekzemple. Kaj tiel eĉ se vi atingos la fino de la ŝlosilo kaj vi ekrigardos vi eble ne vidos kion vi serĉas. 

Do vi ĉiam devas _traverse_ la tutan vojon kaj tiam se vi estis sukcese povis kruci la tutan vojon, subrigardi kaj fari unu finan konfirmon. Ĉu tio kion mi serĉas? Nu, mi rigardas malsupren post komencado ĉe la supro kaj irante 1636. Mi rigardas malsupren. Mi vidas Harvard. Do, jes, mi sukcesis. Kio se kion mi serĉas ne estas en la trie, kvankam. Kio se mi serĉas Princeton, kiu estis fondita en 1746. Kaj do 1746 iĝas mian ŝlosilon navigi tra la trie. Nu, mi komencas je la radika. Kaj la unua loko kiun mi volas al iras malsupren la 1 pado. Ĉu mi povas fari ĝin? Jes mi povas. 

Ĉu mi povas iri malsupren la 7an vojon de tie? Jes, mi povas. Ke ekzistas tro. Sed mi povas iri malsupren la 4 vojo de tie ĉi? Tio estas kiel demandanta la demandon, ĉu Mi procedi malsupren ke kvadrateto ke mi reliefigis en flava? Nenio tie. Dekstra. 

Ne estas maniero antaŭen malsupren la 4 pado. Se Princeton estis en ĉi trie, ke 4 estus malbarita por ni jam. Kaj tiel ĉe tiu punkto ni atingis sakstraton. Ni ne povas iri plu. Kaj tial ni povas diri, definitive, ne. Princeton ne ekzistas en ĉi trie. 

Do kion signifas ĉi ĉiuj signifas? Dekstra. Estas multe okazas tie. Ekzistas indikoj tuta loko. Kaj, kiel vi povas vidi nur de la figuro, ekzistas multe de nodoj kiuj estas tiaj promenadoj ĉirkaŭ. Sed rimarki ĉiufoje ni volis kontroli ĉu io en la trie, ni nur devis fari 4 movojn. 

Ĉiufoje ni volis enmeti ion en la trie, ni devos fari 4 movojn, eventuale mallocing iuj aĵoj survoje. Sed kiel ni vidis kiam ni insertita Dartmouth en la trie, kelkfoje iuj de la vojo jam povus esti malbarita por ni. Kaj tiel kiel nia trie akiras pli grandan kaj pli granda, ni havas ion malgrandan laboron ĉiufoje enmeti novajn aferojn ĉar ni jam konstruis multajn mezajn branĉoj survoje. Se ni nur iam devas rigardi 4 aferoj, 4 estas nur konstanta. Ni vere estas speco de alproksimiĝanta konstanta tempo inserción kaj konstantan tempo lookup. La tradeoff, kompreneble, estante tiu ĉi trie, kiel vi versxajne povas diri, estas grandega. Ĉiu de ĉi tiuj nodoj okupas multe da spaco. 

Sed tio estas la tradeoff. Se ni volas vere rapida inserción, vere rapida forigo, kaj vere rapida lookup, ni devas havas multajn datumojn fluganta ĉirkaŭe. Ni devas flankenmetis multajn spaco kaj memoro por tiu datumstrukturo ekzisti. 

Kaj tiel tio estas la tradeoff. Sed ĝi aspektas kiel ni eble trovis gxin. Ni eble trovis ke sankta gralo de datumstrukturoj per rapidaj inserción, forigo, kaj lookup. Kaj eble tiu estos taŭga datumstrukturo uzi por kiaj informo ni provas vendejo. Mi Doug Lloyd, tiu estas CS50.