[Mūzikas atskaņošanai] Doug LLOYD: Tātad mēs esam inching tuvāk un tuvāk ka Svētais Grāls datu struktūras, viens, ka mēs varam ievietot vērā, dzēst no, un meklēt pastāvīgā laikā. Tiesības. Tas ir sava veida vārtiem. Mēs vēlamies, lai varētu to izdarīt lietas ļoti, ļoti ātri. 

Vai mēs atradām to šeit, kad mēs runājam par mēģinājumiem? Nu, pieņemsim to apskatīt. Tāpēc mēs esam redzējuši vairākas dažādas datu struktūras ka rokturis kartēšanu tā saukto atslēgu vērtību pārus, kartēšanas kādu gabals datu uz kādu citu gabals datu tāpēc mēs zinām, kur atrast informācija struktūrā. 

Tā, lai masīvs, piemēram, Galvenais ir elements indekss vai masīvs vieta 0 vai masīvs 1 un tā tālāk. Un vērtība ir datu kas pastāv šajā vietā. Tātad, kas ir glabāti masīvā 0? Kas tiek glabāti masīvā 1 pret tikko 0 un 1, kas būtu atslēgas. 

Ar hash tabulā tas ir kārtot to pašu ideju. Ar hash tabulu, mums ir šī hash funkcija, kas ģenerē hash kodus. Tātad galvenais ir hash kodu no datiem. Un vērtība, it īpaši mēs runājām par Ķēžu šajā video hash tabulas, ir tas, ka saistīts saraksts datu ka hashes šai hashcode. Tiesības. Kas par citu pieeju Šī metode, lai gan? Kas par metodi, kurā atslēga ir garantēta unikāls, atšķirībā no hash tabulu, kur mēs varētu galu galā ar diviem gabaliem datu ar tādu pašu hashcode. Un tad mums ir tikt galā ar ka vai nu zondēšana vai vairāk vēlams Ķēžu noteikt šo problēmu. 

Tāpēc tagad mēs varam garantēt ka mūsu galvenais būs unikāls. Un ko tad, ja mūsu vērtība bija tikai kaut kā viegli kā patiess un nepatiess, kas stāsta mums, vai vai ne, ka informācijas vienību pastāv struktūrā? Būla varētu būt tikpat vienkārša kā mazliet. Reāli tas ir iespējams, baitu biežāk nekā mazliet. Bet tas ir daudz mazāks nekā uzglabājot varbūt 50 rakstzīmju virkne, piemēram. 

Tātad mēģina, līdzīgi hash tabulas, kas apvieno bloki un saistīts saraksts, mēģina apvienot bloki, konstrukcijas, un norādes kopā uzglabāt datus interesants veids, kas ir diezgan atšķirīgs no kaut ko mēs esam redzējuši līdz šim. Tagad mēs izmantot datus kā ceļvedis orientēties šo datu struktūra. Un, ja mēs varam sekot Ceļvedī, ja mēs varam sekojiet datus no sākuma līdz beigām, mēs zināt, vai šiem datiem pastāv TRIE. 

Un, ja mēs nevaram sekot karti no nozīmē beigt vispār, datus nevar pastāvēt. Atkal, taustiņi šeit ir garantēta unikāls. Un tā atšķirībā no hash tabulu, mēs nekad jātiek galā ar sadursmes šeit. Un nav divu gabali datu ir tieši tāds pats ceļvedi ja vien, ka dati ir identiski. 

Ja mēs ievietotu Jāni, tad mēs meklētu John. Tas ir divas identiskas gabali dati, labi, mēs meklējam cauri. Bet citādi, jebkura divi gabali dati ir garantēta, ir unikālas ceļvežus izmantojot šo datu struktūru. Un mēs esam gatavojas veikt apskatīt vizuāli tas tikai brīdi. 

Mēs to darām, mēģinot izveidot jaunu datu struktūra, kartēšanas šādas galvenās vērtības pārus. Šajā gadījumā, mēs nebrauksim, lai izmantotu kaut kas tik vienkāršs kā Būla. Mēs faktiski saglabās virkni. Un tas string gatavojas būt nosaukums universitātē. 

Un galvenais, būs gads ja šī universitāte tika dibināta. Visi gadi augstskolām gribam būt četri cipari. Un tāpēc mēs izmantosim šos četrus ciparus uz pārvietoties pa šo datu struktūru. Un mēs redzēsim, atkal, kā mēs darīt, ka tikai sekundi. 

Beigās ceļu, mēs redzēsim vārdu no universitātes, kas atbilst šai atslēgai, šie četri cipari. Pamatideja ir TRIE ir mums ir centrālā ceļu. Tāpēc domāju par to, kā koks. Un tas ir līdzīgs pareizrakstības un koncepcijas, lai kokā. Parasti, kad mēs domājam par koki reālajā pasaulē, viņiem ir saknes, kas ir iekļauts zemes un tie aug uz augšu un tie ir filiāles un tie ir lapas. Un būtībā ideja trie ir tieši tas pats, izņemot to, ka sakne ir noenkurots kaut kur debesīs. Un lapas ir apakšā. 

Tātad, tas ir veids, piemēram, ņemot koks un tikai flipping otrādi. Bet ir vēl filiāles. Un tie būtu mūsu ceļi, tie būs mūsu savienojumi no saknes līdz lapām. Šajā gadījumā, tie takas, šie zari ir apzīmēti ar cipariem, kas pateiks mums kādā veidā iet no kurienes mēs esam. 

Ja mēs redzam 0, mēs ejam uz leju šo darbības veidu, ja mēs redzam 1, mēs ejam uz leju šo darbības veidu, un tā un tā tālāk. Nu, ko tas nozīmē? Nu, tas nozīmē, ka katrā krustojuma vietā un katru mezglu vidū un katru filiāle, tur ir 10 iespējas vietas, ka mēs varam iet. Tātad ir 10 norādes No katras vietas. 

Un tas ir, ja mēģina var iegūt mazliet biedējoša kādu kurš nav daudz pieredze datorzinātnēs pirms. Bet mēģina ir tiešām diezgan laba. Un, ja jums ir iespēja strādāt ar viņiem un jūs esat gatavi rakt-in un eksperimentēt ar tām, viņi tiešām diezgan interesanti datu struktūras strādāt. Ja mēs vēlamies, lai ievietotu elementu uz TRIE, viss, kas mums jādara, ir veidot pareizo ceļu no saknes uz lapas. Lūk, ko katrs solis kopā veids varētu izskatīties. Mēs ejam, lai definētu jaunu datu struktūra par jaunu mezglu sauc trie. 

Un iekšpusē šo datu struktūra ir divi gabali. Mēs ejam, lai saglabātu Nosaukums universitātē. Un mēs ejam, lai saglabātu masīvs norādes uz citiem punktiem tā paša tipa. Tātad, atkal, tas ir, ka sava par jēdziena visur mēs esam, mēs pie 10 iespējams vietas, mēs varam iet. Ja mēs redzam 0, mēs ejam pa šo filiāli. Ja mēs redzam 1, šī filiāle, un tā tālāk, un tā tālāk, un tā tālāk. Ja mēs sakām 9, mēs ejam pa šo filiāli. Tātad katrā krustojuma vietā, mēs varam iet 10 iespējamās vietas. Tātad katrs mezgls ir jāsatur 10 norādes uz citiem mezgliem, uz 10 citiem mezgliem. 

Un dati mēs glabāšanai ir tikai nosaukums universitātes. Tātad pieņemsim būvēt trie. Pieņemsim ievietot pāris vienību mūsu TRIE. Tātad pašā augšā, Tas ir mūsu saknes mezgla. Tas ir iespējams, būs kaut kas jūs gatavojas globāli deklarēt. Un jūs gatavojas globāli saglabāt rādītājs šajā mezglā vienmēr. 

Jūs gatavojas teikt, sakne ir vienāds, un jūs esat gatavojas malloc sev trie mezglā. Un jūs nekad gatavojas pieskarties saknes atkal. Katru reizi, kad jūs vēlaties sākt navigāciju pa, jums noteikt citu rādītāju vienāds ar saknes, piemēram, trav, kas ir piemērs es izmantot daudzi mani video šeit skursteņi un rindas un saite sarakstus un tā tālāk. 

Jūs noteikt citu rādītāju aicināja Trav par šķērsošana. Un jūs izmantojat trav orientēties caur datu struktūru. Tātad, pieņemsim redzēt, kā tas varētu izskatīties. Tāpēc tieši tagad, ko tas mezglu izskatās? Nu, tāpat kā mūsu datiem struktūra deklarācija norādīja, mums ir virkne, kas šajā gadījumā ir tukšs. Tur nekas šeit. 

Un masīvs 10 norādes. Un tieši tagad, mēs tikai ir 1 mezglu šajā TRIE. Tur nekas cits tajā. Tātad visi 10 no tiem norādes punkts null. Tas ir tas, ko sarkanā norāda. 

Pieņemsim ievietot virkni Harvard. Pieņemsim ievietot Universitāte Harvard šajā TRIE, kas tika nodibināta gadā 1636. Mēs vēlamies izmantot šo taustiņu, 1636, lai pastāstītu mums, kur mēs esam gatavojas glabāt Harvard šajā TRIE. Tagad, kā varētu mēs to darām? 

Tas varētu izskatīties kaut kas līdzīgs šim. Sākam pie saknes. Un mums ir šie 10 vietas, mēs varam iet. Saknes ir tāpat kā jebkurš cita mezgla TRIE. Ir 10 vietas, mēs varam aiziet no šejienes. 

Kur mēs, iespējams, vēlas lai iet, ja atslēga ir 1636? Tur tiešām divas iespējas. Tiesības. Mēs varam veidot atslēgu labās puses uz kreiso, un sākt ar 6. Vai mēs varētu veidot atslēgu kreisās uz labo un sākt ar 1. 

Tas ir iespējams, vairāk intuitīva kā cilvēks izprast mēs vienkārši iet pa kreisi uz labo. Un tāpēc, ja es gribu, lai ievietotu Harvard šajā TRIE, Es, iespējams, vēlas sākt sākot pie saknes, skatoties uz maniem 10 iespējas man priekšā, un sakot Es gribu iet uz leju 1 ceļu. LABI. 

Tagad, 1 ceļš šobrīd null. Tātad, ja es gribu turpināt noteikts, ka ceļu lai ievietotu šo elementu vērā TRIE, Man ir malloc jaunu mezglu, ir 1 punktu tur, un tad es esmu labi iet. 

Tāpēc es būtībā esmu pie punkts, kur es stāvu pie koka saknēm vai trie un tur ir 10 filiāles. Bet katrai filiālei has a vārtu priekšā no tā. Tiesības. Jo tur ir nekas cits tur ir. Nav droši pārvietoties. Tas nozīmē, ka tur nekas noteikti kāds no šiem zariem. Ja es gribu, lai sāktu ēkas kaut ko, es gribu, lai noņemtu vārtiem. Es gribu, lai novērstu vārtiem priekšā numuru 1. Un es gribu iet uz leju, ka. Un es gribu, lai izveidotu vēl viena vieta, kur man iet. 

Un tas, ko es esmu darījusi šeit. Tātad 1 vairs norāda null. Man teica, ka ir droši iet uz leju šeit tagad. Man būvētas vēl mezglā. Un, kad es nokļūt uz šo mezglu, es ir vēl viens lēmums padarīt. Kur es esmu gatavojas aiziet no šejienes? 

Nu, es esmu jau gājusi uz leju 1. Tāpēc tagad es droši vien gribu iet uz leju 6. Tiesības. Atkal, man ir 10 vietas, es varu izvēlēties. Tātad pieņemsim, tagad iet uz leju numuru 6. Tāpēc es notīrīt vārtiem priekšā skaita 6. Un es iet tur lejā. Un es būvēt vēl vienu mezglu. Un es esmu sasniedzis vēl krustojumam punktu. 

Atkal, man ir 10 izvēles lai kur es varu iet. Man pārvietots no 1 līdz 6. Tāpēc tagad es, iespējams, vēlas doties uz 3. 3, tur ir nekur es varu iet. Tāpēc man ir, lai pavērtu ceļu un veidot sev jaunu telpu. Un tad no 3, kur vēlos iet? Es gribu iet uz leju 6. 

Un atkal, man nācās pavērtu ceļu, lai to izdarītu. Tāpēc tagad es esmu, ko izmanto savu atslēgu, lai ievietotu radītu mezglus un sākt veidot šo trie. Esmu sācis pie saknes. Es esmu gājusi uz leju 1636. Un tagad es esmu apakšā tur šajā mezglā. Un jūs varētu redzēt ekrānā. 

Tas ir izcelta dzeltenā krāsā. Tas ir, ja es šobrīd esmu. Mans galvenais ir izdarīts. Esmu izsmeltas visas pozīcijas manā atslēgu. Tāpēc es nevaru iet tālāk. Tātad šajā brīdī, visi man tiešām ir nepieciešams darīt, ir teikt, OK. Tas ir veids, piemēram meklē lejup uz zemi, ja jūs Paredzot sevi kā šāda veida ceļš ar dažādiem savienojumiem. Kārtot skatoties uz leju un veida spray glezna Harvard uz zemes. Tas ir vārds no tā. Zinu, ka tas, kas ir šajā vietā. Ja sākam pie saknes, un mēs ejam uz leju 1 un pēc tam 6 un pēc tam 3 un pēc tam 6, Kur mēs esam? Nu, ja mēs skatāmies uz leju un mēs redzam Harvard, tad mēs zinām, ka Harvard bija dibināta 1636, pamatojoties uz to, kā mēs īstenojot šo datu struktūra. Tā, ka bija cerams vienkārša. Mēs darīsim vēl divas ievietošanas. Un cerams, tas būs palīdzēt skatīt darīts divas reizes vairāk. 

Tagad, pieņemsim ievietot citā augstskolā. Pieņemsim ievietot Yale šajā TRIE. Yale tika dibināta 1701. gadā. Tāpēc mēs sāksim pie saknes, jo mēs vienmēr darīt. Un mēs noteikti šķērsošana rādītāju. Mēs spēsim izmantot šo, lai pārvietotos pa. Pirmā lieta, ko mēs gribam darīt, ir iet uz leju 1 ceļu. Tas ir pirmais cipars mūsu atslēgu. Par laimi, lai gan, mums nav ir darīt jebkuru darbu šajā laikā. 1 ceļš jau ir noskaidroti. Es noskaidroti to iepriekš, kad es tika ievietojot Harvard 1636. Lai es varētu droši pārvietot leju 1 un tikai iet uz turieni. Ja var pārvietot uz leju 1. 

Tagad, lai gan, es gribu iet uz 7. Es pavērusi ceļu pie 6. Es zinu, ka varu droši turpināt pa 6 ceļu. Bet man ir nepieciešams, lai turpinātu par 7 ceļu. Tātad, kas man jādara? Nu, tāpat kā agrāk, es vienkārši vajag lai notīrītu vārtiem, izkļūt no tā, un veidot jaunu mezglu no 7. ceļa. Tāpat kā šis. 

Tāpēc tagad es esmu pārcelts 1 un pēc tam 7. Un tagad paziņojums, es esmu veida par šo jauno apakšnozare. Tiesības. Viss pārējais no 16 tālāk, man nav rūp. Es to nedaru 16 neko. Es esmu darot 17 lietas. 

Tātad tagad no 17 uz, man kārtot aizsvilties jaunas takas šeit. Nākamais cipars mans galvenais ir 0. Es skaidri nevaru nokļūt jebkur. Es tikko uzcelta šī mezglā. Tāpēc es zinu, tur nav ceļi uz priekšu no šejienes. Tāpēc man ir veikt vienu sevi. 

Tāpēc es malloc jaunu mezglu un ir 0 punktu tur. Un tad vēl vienu reizi, es malloc jaunu mezglu un ir viens punkts tur. Atkal, es esmu izsmēlusi savu atslēgu, 1701. Tāpēc es skatos, un es aerosola krāsu Yale. Tas ir vārds šajā mezglā. 

Un tāpēc tagad, ja man kādreiz vajadzēs, lai redzētu, Yale ir šajā TRIE, es sāku pie saknes, Es iet uz leju 1701, un skatīties uz leju. Un, ja es redzu Yale aerosols krāsoti uz zemes, tad Es zinu, Yale pastāv šajā TRIE. Darīsim vienu vairāk. Pieņemsim ievietot Dartmouth vērā šo trie, kas tika dibināta 1769.. 

Sākt pie saknes vēlreiz. Mans pirmais cipars no maniem galvenajiem ir 1. Es varu droši virzīties lejup šo ceļu. Ka jau eksistē. Nākamais cipars no maniem galvenajiem ir 7. Es varu droši virzīties lejup šo ceļu. Tā pastāv kā labi. 

Mans nākamais ir 6. No šejienes, no kurienes es esmu šobrīd dzeltenā tur šajā vidū mezglā, 6. pašlaik bloķēta off. Ja es gribu iet uz leju, ka ceļu, Man ir veidot to pats. Tāpēc es ņemšu malloc jaunu mezglu un ir 6. punktu tur. Un tad, atkal, es esmu degošs jaunas takas šeit. 

Tāpēc es malloc jaunu mezglu, lai no ka node-- ceļa numurs 9-- un tad tagad ja es ceļot 1769, un es skatos. Nav nekas šobrīd aerosols krāsotas tur. Es varu uzrakstīt Dartmouth. Un es esmu ievietots Dartmouth uz TRIE. 

Tātad tas ir ievietojot lietas fani TRIE. Tagad mēs vēlamies, lai meklētu lietas. Kā mēs meklētu lietām TRIE? Nu, tas ir diezgan daudz to pašu ideju. Tagad mēs tikai izmantot ciparus atslēgu lai redzētu, vai mēs varam pārvietoties no saknes lai kur mēs gribam iet uz TRIE. 

Ja mēs hit strupceļā jebkurā brīdī, tad mēs zinām, ka šis elements nevar eksistē vai arī, ka ceļš būtu jau ir noskaidroti. Ja mēs to visu ceļu uz beigas, viss, kas mums jādara, ir skatīties uz leju un redzēt, ja tas ir elements mēs meklējam. Ja tā ir, veiksme. Ja tā nav, neizdoties. 

Tātad pieņemsim meklēt Harvard šajā TRIE. Sākam pie saknes. Un atkal, mēs ejam, lai izveidot šķērsošana rādītāju darīt mūsu kustas mums. No saknes, mēs zinām, ka pirmā vieta, mums ir jāiet, ir 1, mēs varam darīt? Jā mēs varam. Ja droši eksistē. Mēs varam iet uz turieni. 

Tagad nākamais vieta, mums ir nepieciešams, lai iet, ir 6. Vai 6 ceļš pastāv no šejienes? Jā, tā dara. Mēs varam iet uz leju 6 ceļu. Un mēs galu galā šeit. 

Vai mēs varam iet uz leju 3 ceļu no šejienes? Nu, kā izrādās, jā, ka pastāv pārāk. Un mēs varam iegūt par 6 ceļu no šejienes? Jā mēs varam. 

Mēs neesam gluži atbildēja jautājums vēl. Tur ir vēl viens solis, kas tagad mums ir jāskatās uz leju un redzēt, ja tas ir actually-- ja mēs meklējam Harvard, ir tas, ka Ko mēs redzam, kad mēs izplūdes atslēgu? Šajā piemērā mēs izmantojam šeit, gadi vienmēr ir četri cipari. Bet jūs varētu būt, izmantojot, piemēram, ja jums ir uzglabātu vārdnīcas vārdiem. 

Un tā vietā, 10 norādes manu atrašanās vietu, jūs varētu būt 26. Viena katram alfabēta burtam. Un tur ir daži vārdi, piemēram, nūja, kas ir apakškopa partijas, piemēram. Un, pat ja jums uz no galvenajiem beigas un paskatās uz leju, jūs nevarēsiet redzēt, ko jūs meklējat. 

Tātad jums vienmēr ir traversa visu ceļu un pēc tam ja Jums bija iespēja veiksmīgi lai šķērsotu visu ceļu, skatīties uz leju un darīt vienu galīgo apstiprinājumu. Vai tas, ko es meklēju? Nu, es skatos pēc sākuma augšā un iet 1636. Es skatos uz leju. Es redzu Harvard. Tātad, jā, man izdevās. Ko darīt, ja tas, ko es esmu meklē neatrodas TRIE, lai gan. Ko darīt, ja es esmu meklē Princeton, kas tika dibināta 1746. Un tā 1746. kļūst mana atslēga lai pārvietotos pa TRIE. Nu, es sāku pie saknes. Un pirmā vieta es gribu lai iet uz leju 1 ceļu. Vai es varu to darīt? Jā es varu. 

Vai es varu iet uz leju 7 ceļu no turienes? Jā, es varu. Ka pastāv pārāk. Bet es varu iet uz leju 4 ceļu no šejienes? Tas ir tāpat kā uzdodot jautājumu, var Es doties uz leju, ka maz kvadrātveida ka es esmu izcelta dzeltenā krāsā? Nav nekas tur. Tiesības. 

Nav veids, kā virzīties uz leju 4 ceļu. Ja Princeton bija šajā TRIE, ka 4 būtu noskaidroti mums jau. Un lai šajā brīdī mēs esam sasnieguši strupceļā. Mēs nevaram iet tālāk. Un tā mēs varam teikt, galīgi, nē. Princeton neeksistē šajā TRIE. 

Tātad, ko tas viss nozīmē? Tiesības. Tur ir daudz kas notiek šeit. Tur ir norādes visā vietā. Un, kā jūs varat redzēt tikai no diagrammas, tur ir daudz mezglu, kas ir sava veida peld apkārt. Bet paziņojums katru reizi, kad mēs vēlējāmies pārbaudīt, vai kaut kas bija TRIE, mums tikai bija jāveic 4 gājienus. 

Katru reizi, kad mēs vēlējāmies ievietot kaut ko TRIE, mums ir jāveic 4 gājienus, iespējams, mallocing daži sīkumi gar ceļu. Bet kā mēs redzējām, kad mēs ievietota Dartmouth uz TRIE, dažreiz daži no ceļa iespējams, jau ir noskaidroti mums. Un tā kā mūsu trie kļūst lielāka un lielāks, mums ir jādara mazāk darba ikreiz ievietot jaunas lietas jo mēs esam jau built daudz starpprodukta Nozares gar ceļu. Ja mēs tikai kādreiz ir apskatīt 4 lietas, 4 ir tikai nemainīga. Mēs patiešām ir sava veida tuvojas konstante laiks ievietošana un nemainīgs laiks lookup. Tradeoff, protams, ir tas, ka Tas trie, kā jūs, iespējams, varat pateikt, ir milzīgs. Katrs no šiem mezgliem aizņem daudz vietas. 

Bet tas ir tradeoff. Ja mēs gribam tiešām ātri ievietošanas, tiešām ātri dzēšanu, un tiešām ātri lookup, mums ir ir daudz datu peld apkārt. Mums ir atcelt daudz vietas un atmiņas par šo datu struktūras pastāvēt. 

Un tā tas ir tradeoff. Bet izskatās, ka mums varētu būt atradis. Mēs, iespējams, ir konstatēts, ka svēts grail datu struktūras ar ātru ievietošanas, dzēšanu, un lookup. Un varbūt tas būs gadījumā datu struktūra izmantot kāda informācija mēs cenšamies veikalā. Es esmu Doug Lloyd, tas ir CS50.