1 00:00:00,000 --> 00:00:02,994 >> [Glazbom] 2 00:00:02,994 --> 00:00:05,426 3 00:00:05,426 --> 00:00:08,550 Doug LLOYD: Tako smo skroz bliže i bliže da sveti gral podataka 4 00:00:08,550 --> 00:00:13,050 strukture, onaj koji se može umetnuti u, izbrisati iz, i gledati 5 00:00:13,050 --> 00:00:15,440 u stalnom vremenu. 6 00:00:15,440 --> 00:00:16,270 Tako je. 7 00:00:16,270 --> 00:00:17,280 To je vrsta cilja. 8 00:00:17,280 --> 00:00:19,720 Želimo biti u mogućnosti učiniti stvari vrlo, vrlo brzo. 9 00:00:19,720 --> 00:00:22,580 >> Jesmo li ga pronaći ovdje kada govorimo o pokušaja? 10 00:00:22,580 --> 00:00:23,670 Pa, neka je pogledati. 11 00:00:23,670 --> 00:00:25,628 Dakle, vidjeli smo nekoliko različite strukture podataka 12 00:00:25,628 --> 00:00:28,680 što nose mapiranje Takozvani ključ-vrijednost parova, 13 00:00:28,680 --> 00:00:32,080 mapiranje neki komad podataka na neki drugi dio podataka 14 00:00:32,080 --> 00:00:36,020 tako da znamo gdje se nalazimo Informacije u strukturi. 15 00:00:36,020 --> 00:00:40,060 >> Tako je za niz, na primjer, Ključ je indeks element ili niz 16 00:00:40,060 --> 00:00:42,600 Mjesto 0 ili 1 polje i tako dalje. 17 00:00:42,600 --> 00:00:46,140 A vrijednost podataka koji postoji na tom mjestu. 18 00:00:46,140 --> 00:00:48,550 Pa što je pohranjena u nizu 0? 19 00:00:48,550 --> 00:00:54,290 Ono što je pohranjena u nizu 1 u odnosu na samo 0 i 1, što bi bilo ključevi. 20 00:00:54,290 --> 00:00:56,360 >> Uz hash tablici je vrsta istom idejom. 21 00:00:56,360 --> 00:01:00,690 Uz hash tablici, imamo ovu hash funkcija koja stvara hash kodove. 22 00:01:00,690 --> 00:01:03,670 Dakle, ključ je hash broj podataka. 23 00:01:03,670 --> 00:01:06,530 A vrijednost, osobito razgovarali smo o ulančavanje 24 00:01:06,530 --> 00:01:10,590 u video na hash tablica, da je vezan popis podataka 25 00:01:10,590 --> 00:01:12,550 da hashes toj Hash broj. 26 00:01:12,550 --> 00:01:14,050 Tako je. 27 00:01:14,050 --> 00:01:16,050 Što je s drugom pristupu ovaj postupak, iako? 28 00:01:16,050 --> 00:01:21,000 Što o metodi gdje je Ključ je zajamčena biti jedinstven, 29 00:01:21,000 --> 00:01:25,410 za razliku od hash tablici, gdje smo mogli završiti s dva komada podataka 30 00:01:25,410 --> 00:01:27,200 imaju istu Hash. 31 00:01:27,200 --> 00:01:30,020 A onda se moramo nositi s da je bilo sondiranja ili više 32 00:01:30,020 --> 00:01:33,340 ponajprije ulančavanje popraviti taj problem. 33 00:01:33,340 --> 00:01:37,520 >> Tako sada možemo garantirati da je naš ključ će biti jedinstveni. 34 00:01:37,520 --> 00:01:39,690 A što ako je naš vrijednost bila samo nešto tako lako 35 00:01:39,690 --> 00:01:44,080 kao istinito i lažno da nam kaže da li ili ne da je dio informacija 36 00:01:44,080 --> 00:01:45,610 postoji u strukturi? 37 00:01:45,610 --> 00:01:48,180 Booleova može biti kao jednostavan kao malo. 38 00:01:48,180 --> 00:01:52,660 Realno je vjerojatno Byte češće nego malo. 39 00:01:52,660 --> 00:01:55,410 Ali to je puno manje od spremanje možda niz od 50 znakova, 40 00:01:55,410 --> 00:01:57,360 na primjer. 41 00:01:57,360 --> 00:02:02,210 >> Dakle pokušaja, slično hash tablica, koje kombiniraju polja i povezane popis, 42 00:02:02,210 --> 00:02:05,790 pokušava kombinirati polja, strukture i pokazivače 43 00:02:05,790 --> 00:02:08,509 zajedno za pohranu podataka u zanimljiv način na koji je 44 00:02:08,509 --> 00:02:11,550 prilično razlikuje od sve smo vidjeli do sada. 45 00:02:11,550 --> 00:02:16,750 Sada ćemo podatke koristiti kao putokaz za navigaciju ovu strukturu podataka. 46 00:02:16,750 --> 00:02:18,710 I ako možemo pratiti Plan, ako mi može 47 00:02:18,710 --> 00:02:22,390 slijedite podatke iz početka do kraja, mi ćemo 48 00:02:22,390 --> 00:02:24,945 Znaš li te podatke postoje u Trie. 49 00:02:24,945 --> 00:02:28,310 >> A ako ne možemo slijediti kartu iz smisao završiti na sve, 50 00:02:28,310 --> 00:02:30,600 podaci ne mogu postojati. 51 00:02:30,600 --> 00:02:32,890 Opet, ključevi ovdje zasigurno biti jedinstveno. 52 00:02:32,890 --> 00:02:36,020 I tako za razliku od hash tablici, nikada nećemo morati baviti sudara ovdje. 53 00:02:36,020 --> 00:02:39,090 A nema dva komada podataka imaju točno istu plan 54 00:02:39,090 --> 00:02:40,530 osim ako su podaci identični. 55 00:02:40,530 --> 00:02:44,580 >> Ako uložite Ivan, a zatim tražimo Ivana. 56 00:02:44,580 --> 00:02:47,430 To je dva identična komada podataka, pravo, tražimo kroz. 57 00:02:47,430 --> 00:02:49,880 Ali inače, bilo dva komada podataka su 58 00:02:49,880 --> 00:02:52,750 zajamčeno da imaju jedinstvene planova kroz ove strukture podataka. 59 00:02:52,750 --> 00:02:56,210 A mi ćemo se pogledati vizualni to u samo trenutak. 60 00:02:56,210 --> 00:02:58,810 >> Mi ćemo to učiniti pokušavajući stvoriti novu strukturu podataka, 61 00:02:58,810 --> 00:03:00,564 mapiranje sljedeće ključne parove vrijednosti. 62 00:03:00,564 --> 00:03:03,480 U tom slučaju, nećemo koristiti nešto kao jednostavan kao Boolean. 63 00:03:03,480 --> 00:03:06,200 Mi zapravo će pohraniti string. 64 00:03:06,200 --> 00:03:08,690 I to string će se naziv sveučilišta. 65 00:03:08,690 --> 00:03:12,140 >> A ključ će biti godina kada je osnovana da sveučilište. 66 00:03:12,140 --> 00:03:15,380 Sve godine za sveučilišta će biti četiri znamenke. 67 00:03:15,380 --> 00:03:19,840 I tako ćemo koristiti te četiri znamenke navigaciju kroz ove strukture podataka. 68 00:03:19,840 --> 00:03:22,270 A vidjet ćemo, opet, kako možemo učiniti u samo sekundi. 69 00:03:22,270 --> 00:03:25,110 >> Na kraju staze, vidjet ćemo ime 70 00:03:25,110 --> 00:03:30,250 sveučilišta koji odgovara na tom ključu, te četiri znamenke. 71 00:03:30,250 --> 00:03:34,390 Osnovna ideja iza Trie je da imamo središnju put. 72 00:03:34,390 --> 00:03:35,640 Dakle, razmišljam o tome kao stablo. 73 00:03:35,640 --> 00:03:39,211 A to je slično u pravopisu i koncept na stablo. 74 00:03:39,211 --> 00:03:41,460 Općenito, kada mislimo o stabala u stvarnom svijetu, 75 00:03:41,460 --> 00:03:44,090 imaju korijen koji je u zemlju i oni rastu prema gore 76 00:03:44,090 --> 00:03:46,830 i oni imaju podružnice i oni imaju lišće. 77 00:03:46,830 --> 00:03:49,450 A u osnovi ideja Trie je točno isto, 78 00:03:49,450 --> 00:03:51,755 osim što korijen usidrena negdje na nebu. 79 00:03:51,755 --> 00:03:53,130 A listovi su na dnu. 80 00:03:53,130 --> 00:03:55,750 >> Dakle, to je vrsta kao što je uzimanje stablo i samo ga flipping naopako. 81 00:03:55,750 --> 00:03:56,880 No, još uvijek postoje grane. 82 00:03:56,880 --> 00:03:59,463 A oni će biti naši putevi, oni će biti naši veze 83 00:03:59,463 --> 00:04:02,220 od korijena do listova. 84 00:04:02,220 --> 00:04:04,200 U tom slučaju, oni staze, one grane 85 00:04:04,200 --> 00:04:08,490 su označeni s brojkama koje nam na koji način da ide odakle smo. 86 00:04:08,490 --> 00:04:11,800 >> Ako vidimo 0, idemo dolje ove grane, ako vidimo 1, idemo dolje ove grane, 87 00:04:11,800 --> 00:04:12,900 i tako i tako dalje. 88 00:04:12,900 --> 00:04:14,060 Pa, što to znači? 89 00:04:14,060 --> 00:04:16,519 Pa, to znači da je na svakom čvorištu 90 00:04:16,519 --> 00:04:19,260 i svaki čvor u srednje i svaki ogranak, 91 00:04:19,260 --> 00:04:23,020 postoje 10 moguće mjesta koja možemo ići. 92 00:04:23,020 --> 00:04:27,690 Dakle, tu su 10 pokazivače iz svakog mjesta. 93 00:04:27,690 --> 00:04:30,610 >> I ovo je mjesto gdje pokušava može dobiti malo zastrašujuće za nekoga 94 00:04:30,610 --> 00:04:34,460 tko nema puno iskustvo u računalnoj znanosti prije. 95 00:04:34,460 --> 00:04:35,960 Ali pokušava stvarno prilično strašan. 96 00:04:35,960 --> 00:04:37,793 A ako imate priliku raditi s njima 97 00:04:37,793 --> 00:04:40,420 i da ste spremni da kopaju-u i eksperimentirati s njima, 98 00:04:40,420 --> 00:04:44,234 oni su zapravo prilično zanimljiva strukture podataka raditi. 99 00:04:44,234 --> 00:04:46,900 Ako želite umetnuti element u Trie, sve što trebate učiniti 100 00:04:46,900 --> 00:04:51,360 je izgraditi ispravan put iz korijena do lista. 101 00:04:51,360 --> 00:04:55,390 Evo što svaki korak zajedno način moglo izgledati. 102 00:04:55,390 --> 00:04:59,660 Idemo definirati nove podatke Struktura za novi čvor naziva Trie. 103 00:04:59,660 --> 00:05:02,560 >> A unutar tog podataka Struktura postoje dva komada. 104 00:05:02,560 --> 00:05:05,460 Idemo pohraniti naziv sveučilišta. 105 00:05:05,460 --> 00:05:09,410 A mi ćemo pohraniti niz pokazivača 106 00:05:09,410 --> 00:05:12,190 s drugim čvorovima istog tipa. 107 00:05:12,190 --> 00:05:14,780 Dakle, opet, to je da vrsta koncepta svugdje 108 00:05:14,780 --> 00:05:18,567 mi smo, mi na 10 moguće mjesta možemo ići. 109 00:05:18,567 --> 00:05:20,150 Ako vidimo 0, idemo dolje ovu granu. 110 00:05:20,150 --> 00:05:22,690 Ako vidimo 1, ova grana, i tako dalje i tako dalje i tako dalje. 111 00:05:22,690 --> 00:05:25,160 Ako kažemo 9, idemo dolje ovu granu. 112 00:05:25,160 --> 00:05:28,220 Dakle, na svakom čvorištu, možemo ići 10 mogućih mjesta. 113 00:05:28,220 --> 00:05:35,740 Dakle, svaki čvor mora sadržavati 10 pokazivače s drugim čvorovima, 10 drugih čvorova. 114 00:05:35,740 --> 00:05:39,810 >> A podaci smo pohranjivanje je Upravo naziv sveučilišta. 115 00:05:39,810 --> 00:05:41,060 Tako ćemo sagraditi Trie. 116 00:05:41,060 --> 00:05:44,860 Idemo ubacite par stavki u naš Trie. 117 00:05:44,860 --> 00:05:46,740 Dakle, na samom vrhu, to je naš korijen čvor. 118 00:05:46,740 --> 00:05:49,740 To je vjerojatno će biti nešto idete na globalnoj razini proglasiti. 119 00:05:49,740 --> 00:05:53,450 I ti ćeš na globalnoj razini održavanje pointer na ovom čvoru uvijek. 120 00:05:53,450 --> 00:05:55,360 >> Ti ćeš reći, Korijen jednako, a vi ste 121 00:05:55,360 --> 00:05:57,580 će malloc sebi Trie čvor. 122 00:05:57,580 --> 00:05:59,850 I nikad ne ide opet dotaknuti korijen. 123 00:05:59,850 --> 00:06:02,300 Svaki put kada želite početi s navigacijom kroz, 124 00:06:02,300 --> 00:06:05,802 postavite pokazivač drugi jednaka korijenu, kao što Trav, 125 00:06:05,802 --> 00:06:07,760 koji je sam primjer koristiti u mnogim od mojih videa 126 00:06:07,760 --> 00:06:11,090 ovdje na hrpe i redova i veza popisa i tako dalje. 127 00:06:11,090 --> 00:06:13,320 >> Možete postaviti još jedan pokazivač pozvao trav za obuhvaćanje. 128 00:06:13,320 --> 00:06:15,890 A vi koristite Trav za navigaciju kroz strukturu podataka. 129 00:06:15,890 --> 00:06:17,500 Tako ćemo vidjeti kako to može izgledati. 130 00:06:17,500 --> 00:06:19,880 Pa sada, što nema čvor izgledati? 131 00:06:19,880 --> 00:06:22,920 Pa, baš kao i naše podataka Struktura izjava naznačeno, 132 00:06:22,920 --> 00:06:26,906 imamo niz koji u ovom slučaju je prazna. 133 00:06:26,906 --> 00:06:27,780 Nema ničega ovdje. 134 00:06:27,780 --> 00:06:29,550 >> I niz od 10 upućuje. 135 00:06:29,550 --> 00:06:31,790 A sada, samo mi ima 1 čvor u ovom Trie. 136 00:06:31,790 --> 00:06:33,110 Nema ništa u njoj. 137 00:06:33,110 --> 00:06:36,020 Dakle, sve 10 od onih upućuje točka na nulu. 138 00:06:36,020 --> 00:06:38,090 To je ono što je crvena označava. 139 00:06:38,090 --> 00:06:39,500 >> Idemo umetnite niz Harvard. 140 00:06:39,500 --> 00:06:41,999 Idemo umetnite Sveučilište Harvard u ovom Trie, koji 141 00:06:41,999 --> 00:06:43,940 osnovana je 1636 godine. 142 00:06:43,940 --> 00:06:48,220 Želimo iskoristiti ključ, 1636, da nam kaže gdje smo 143 00:06:48,220 --> 00:06:50,140 će pohraniti Harvarda u Trie. 144 00:06:50,140 --> 00:06:51,470 Sada, kako bismo mogli to učiniti? 145 00:06:51,470 --> 00:06:52,886 >> To bi moglo izgledati nešto poput ovoga. 146 00:06:52,886 --> 00:06:54,160 Krećemo u korijenu. 147 00:06:54,160 --> 00:06:56,920 I mi smo ovih 10 mjesta možemo ići. 148 00:06:56,920 --> 00:06:59,900 Korijen je baš kao i bilo drugi čvor Trie. 149 00:06:59,900 --> 00:07:02,850 Ima 10 mjesta možemo otići odavde. 150 00:07:02,850 --> 00:07:07,215 >> Gdje ćemo vjerojatno želite ići ako je ključ 1636? 151 00:07:07,215 --> 00:07:08,340 Tu je stvarno dvije opcije. 152 00:07:08,340 --> 00:07:08,450 Tako je. 153 00:07:08,450 --> 00:07:10,825 Možemo graditi ključ iz desna na lijevo i početi sa 6. 154 00:07:10,825 --> 00:07:14,000 Ili bismo mogli izgraditi ključ iz s lijeva na desno i počnite s 1. 155 00:07:14,000 --> 00:07:16,140 >> To je vjerojatno i više intuitivno kao ljudsko biće 156 00:07:16,140 --> 00:07:18,110 da razumijemo ćemo Dovoljno je otići s lijeva na desno. 157 00:07:18,110 --> 00:07:21,140 I tako, ako želim umetnuti Harvard u ovom Trie, 158 00:07:21,140 --> 00:07:23,560 Vjerojatno želite započeti počevši u korijenu, 159 00:07:23,560 --> 00:07:25,720 gleda na moje 10 mogućnosti ispred mene i rekao 160 00:07:25,720 --> 00:07:28,700 Želim ići dolje 1 put. 161 00:07:28,700 --> 00:07:29,700 U REDU. 162 00:07:29,700 --> 00:07:31,810 >> Sada, 1 put je trenutno null. 163 00:07:31,810 --> 00:07:35,920 Dakle, ako želim nastaviti niz taj put umetnuti taj element u Trie, 164 00:07:35,920 --> 00:07:42,040 Moram malloc novi čvor, imaju 1 usmjerite tamo, a onda sam dobar to ići. 165 00:07:42,040 --> 00:07:46,460 >> Tako sam zapravo sam u točka u kojoj ja stojim 166 00:07:46,460 --> 00:07:50,270 u korijenu stabla ili Trie i ima 10 podružnica. 167 00:07:50,270 --> 00:07:52,260 No, svaka grana ima Vrata ispred njega. 168 00:07:52,260 --> 00:07:53,060 Tako je. 169 00:07:53,060 --> 00:07:54,850 Budući da ništa drugo nema. 170 00:07:54,850 --> 00:07:56,522 Ne siguran prolaz. 171 00:07:56,522 --> 00:07:58,980 To znači da nema ništa dolje bilo koji od tih grana. 172 00:07:58,980 --> 00:08:02,532 Ako želim početi graditi nešto, želim ukloniti vrata. 173 00:08:02,532 --> 00:08:04,490 Želim da uklonite vrata ispred broja 1. 174 00:08:04,490 --> 00:08:05,698 I želim prošetati toga. 175 00:08:05,698 --> 00:08:08,060 I ja želim izgraditi drugo mjesto za mene to ići. 176 00:08:08,060 --> 00:08:09,470 >> I to je ono što sam učinio ovdje. 177 00:08:09,470 --> 00:08:11,430 Dakle 1 više ne ukazuje na null. 178 00:08:11,430 --> 00:08:13,830 Ja sam rekao da je sigurno ići dolje sada ovdje. 179 00:08:13,830 --> 00:08:15,789 Napravio sam još jedan čvor. 180 00:08:15,789 --> 00:08:18,330 A kad sam doći do tog čvora, ja još jedan odluku. 181 00:08:18,330 --> 00:08:20,890 Gdje ću otići odavde? 182 00:08:20,890 --> 00:08:22,700 >> Pa, već sam sišao 1. 183 00:08:22,700 --> 00:08:24,470 Dakle, sada sam vjerojatno želite ići dolje 6. 184 00:08:24,470 --> 00:08:24,970 Tako je. 185 00:08:24,970 --> 00:08:27,100 Opet, imam 10 lokacija mogu izabrati. 186 00:08:27,100 --> 00:08:30,060 Tako ćemo sada ići dolje broj 6. 187 00:08:30,060 --> 00:08:32,280 Tako sam jasan vrata ispred broja 6. 188 00:08:32,280 --> 00:08:33,250 I prošetati tamo dolje. 189 00:08:33,250 --> 00:08:34,580 I izgraditi još čvor. 190 00:08:34,580 --> 00:08:37,630 I sam stigao još jedan čvorište. 191 00:08:37,630 --> 00:08:40,289 >> Opet, imam 10 izbora za gdje mogu ići. 192 00:08:40,289 --> 00:08:42,799 Ja sam se preselio od 1 do 6. 193 00:08:42,799 --> 00:08:44,215 Dakle, sada sam vjerojatno želite ići na 3. 194 00:08:44,215 --> 00:08:45,381 3, postoji nigdje ne mogu otići. 195 00:08:45,381 --> 00:08:48,980 Dakle, moram očistiti put i izgraditi sebi novi prostor. 196 00:08:48,980 --> 00:08:50,870 A onda od 3, gdje želim ići? 197 00:08:50,870 --> 00:08:52,450 Želim ići dolje 6. 198 00:08:52,450 --> 00:08:54,770 >> A, opet, morao sam jasan način to učiniti. 199 00:08:54,770 --> 00:08:59,179 Dakle, sada sam koristio moje ključ za umetanje izradu čvorovi i početi graditi taj Trie. 200 00:08:59,179 --> 00:09:00,220 Ja sam počeo u korijenu. 201 00:09:00,220 --> 00:09:03,666 Ja sam sišao 1636. 202 00:09:03,666 --> 00:09:05,540 I sad sam na dnu tamo na tom čvoru. 203 00:09:05,540 --> 00:09:06,610 A ti bi mogao vidjeti ga na zaslonu. 204 00:09:06,610 --> 00:09:07,735 >> To je istaknuto u žuto. 205 00:09:07,735 --> 00:09:10,020 To je mjesto gdje sam trenutno. 206 00:09:10,020 --> 00:09:11,300 Moj ključ je učinio. 207 00:09:11,300 --> 00:09:13,030 Ja sam iscrpljen svaki položaj na moj ključ. 208 00:09:13,030 --> 00:09:15,040 Dakle, ja ne mogu ići dalje. 209 00:09:15,040 --> 00:09:17,720 Dakle, u ovom trenutku, sve što sam stvarno trebate učiniti je reći, u redu. 210 00:09:17,720 --> 00:09:18,990 To je vrsta kao što izgleda dolje na zemlju, 211 00:09:18,990 --> 00:09:21,115 Ako ste predviđajući sebe kao ovu vrstu puta 212 00:09:21,115 --> 00:09:22,350 s različitim priključcima. 213 00:09:22,350 --> 00:09:25,800 Sortiraj gleda prema dolje i vrsta sprej slikarstvo Harvard na terenu. 214 00:09:25,800 --> 00:09:26,800 To je naziv za to. 215 00:09:26,800 --> 00:09:28,300 Znajte da je ono što je na tom mjestu. 216 00:09:28,300 --> 00:09:31,870 Ako počnemo u korijenu i idemo dolje 1, a zatim 6, a potom 3 i zatim 6, 217 00:09:31,870 --> 00:09:32,780 gdje se nalazimo? 218 00:09:32,780 --> 00:09:35,640 Pa ako ćemo gledati prema dolje i vidimo Harvarda, zatim 219 00:09:35,640 --> 00:09:38,960 znamo da je na Harvardu osnovana 1636. temelji se na putu 220 00:09:38,960 --> 00:09:41,400 mi smo provedbu ove strukture podataka. 221 00:09:41,400 --> 00:09:43,177 Tako da je, nadamo jednostavan. 222 00:09:43,177 --> 00:09:44,760 Idemo napraviti još dva umetanja. 223 00:09:44,760 --> 00:09:50,060 I nadam se da ću pomoći vidi to učinio dva puta. 224 00:09:50,060 --> 00:09:52,210 >> Sada, neka je umetnite drugom sveučilištu. 225 00:09:52,210 --> 00:09:54,630 Idemo umetnite Yale u ovom Trie. 226 00:09:54,630 --> 00:09:57,037 Yale je osnovana 1701. godine. 227 00:09:57,037 --> 00:09:58,870 Tako ćemo početi na Korijen, kao što smo uvijek. 228 00:09:58,870 --> 00:09:59,890 A mi postaviti obuhvaćanje pokazivač. 229 00:09:59,890 --> 00:10:01,624 Ćemo koristiti kako za kretanje kroz. 230 00:10:01,624 --> 00:10:03,790 Prva stvar koju želimo učiniti je otići dolje 1 put. 231 00:10:03,790 --> 00:10:05,830 To je prvi broj našeg ključa. 232 00:10:05,830 --> 00:10:08,420 Srećom, ipak, mi ne moraju ništa raditi ovaj put. 233 00:10:08,420 --> 00:10:09,919 U 1. put je već izbrisan. 234 00:10:09,919 --> 00:10:13,520 Ja ga izbacila prije kada sam je umetanje Harvard u 1636. 235 00:10:13,520 --> 00:10:18,090 Pa ja sigurno mogu kretati niz 1 i samo tamo. 236 00:10:18,090 --> 00:10:20,150 Ako se može pomicati prema dolje 1. 237 00:10:20,150 --> 00:10:22,930 >> Sada, međutim, želim otići do 7. 238 00:10:22,930 --> 00:10:24,280 Izbrisani sam način na 6. 239 00:10:24,280 --> 00:10:27,050 Znam sigurno nastavite niz 6 put. 240 00:10:27,050 --> 00:10:29,220 Ali moram nastaviti na 7 put. 241 00:10:29,220 --> 00:10:30,580 Pa što trebam učiniti? 242 00:10:30,580 --> 00:10:35,070 Pa, baš kao i prije, samo trebam očistiti vrata, izaći na putu, 243 00:10:35,070 --> 00:10:38,740 i izgraditi novi čvor od 7 puta. 244 00:10:38,740 --> 00:10:40,250 Baš ovako. 245 00:10:40,250 --> 00:10:42,930 >> Dakle, sada sam se preselio 1, a zatim 7. 246 00:10:42,930 --> 00:10:45,550 A sada primjetiti, ja sam neka vrsta od ovog novog Subbranch. 247 00:10:45,550 --> 00:10:46,050 Tako je. 248 00:10:46,050 --> 00:10:49,260 Sve ostalo od 16 o, ja ne stalo. 249 00:10:49,260 --> 00:10:50,720 Ja ne radim 16 ništa. 250 00:10:50,720 --> 00:10:51,750 Radim 17 stvari. 251 00:10:51,750 --> 00:10:58,380 >> Tako sada od 17, ja moram vrsta sjala nova staza ovdje. 252 00:10:58,380 --> 00:11:00,462 Sljedeći znamenkasti moj ključ je 0. 253 00:11:00,462 --> 00:11:01,670 Ja očito ne mogu dobiti nigdje. 254 00:11:01,670 --> 00:11:02,628 Upravo sam sagradio ovaj čvor. 255 00:11:02,628 --> 00:11:04,550 Dakle, ja znam da nema putevi naprijed odavde. 256 00:11:04,550 --> 00:11:06,370 Pa moram napraviti jedan sebe. 257 00:11:06,370 --> 00:11:09,360 >> Tako sam malloc novi čvor i imaju 0 bod. 258 00:11:09,360 --> 00:11:12,770 I onda još jednom, ja malloc novi čvor i ima jedan bod. 259 00:11:12,770 --> 00:11:15,870 Opet, ja sam iscrpljena moj ključ, 1701. 260 00:11:15,870 --> 00:11:18,472 Dakle, ja gledati prema dolje i sam sprej boje Yale. 261 00:11:18,472 --> 00:11:19,680 To je naziv ovog čvora. 262 00:11:19,680 --> 00:11:24,660 >> I tako sada, ako sam ikada trebati vidjeti ako Yale je u ovom Trie, počnem u korijenu, 263 00:11:24,660 --> 00:11:27,060 Idem dolje 1701., i gledati prema dolje. 264 00:11:27,060 --> 00:11:30,030 A ako vidim Yale sprej slikano na tlo, a zatim 265 00:11:30,030 --> 00:11:32,200 Znam Yale postoji u ovom Trie. 266 00:11:32,200 --> 00:11:32,950 Učinimo još jedan. 267 00:11:32,950 --> 00:11:36,430 Idemo umetnite Dartmouth u ovo Trie, koja je osnovana u 1769. 268 00:11:36,430 --> 00:11:37,750 >> Počnite u korijenu opet. 269 00:11:37,750 --> 00:11:39,445 Moja prva znamenka moje ključ je 1. 270 00:11:39,445 --> 00:11:40,820 Ja sigurno mogu kretati prema dolje taj put. 271 00:11:40,820 --> 00:11:42,400 To već postoji. 272 00:11:42,400 --> 00:11:44,040 Sljedeći znamenkasti mog ključ je 7. 273 00:11:44,040 --> 00:11:45,890 Ja sigurno mogu kretati prema dolje taj put. 274 00:11:45,890 --> 00:11:47,540 Ona postoji kao dobro. 275 00:11:47,540 --> 00:11:49,000 >> Moj sljedeći je 6. 276 00:11:49,000 --> 00:11:52,860 S ovog mjesta, odakle sam trenutno uto tamo u toj sredini čvor, 277 00:11:52,860 --> 00:11:56,060 6 je trenutno zaključana off. 278 00:11:56,060 --> 00:11:58,830 Ako želim ići dolje taj put, Moram ga graditi sebe. 279 00:11:58,830 --> 00:12:02,250 Tako ću malloc novi čvor i imaju 6 bod. 280 00:12:02,250 --> 00:12:04,250 A onda, opet, ja sam plamen nove staze ovdje. 281 00:12:04,250 --> 00:12:10,750 >> Tako sam malloc novi čvor, tako da od da node-- broj staza 9-- i onda sada 282 00:12:10,750 --> 00:12:13,584 ako sam putovati 1769, i ja gledati prema dolje. 283 00:12:13,584 --> 00:12:15,500 Nema ništa trenutno sprej oslikana tamo. 284 00:12:15,500 --> 00:12:16,930 Mogu napisati Dartmouth. 285 00:12:16,930 --> 00:12:20,710 I ja sam umetnuta Dartmouth u Trie. 286 00:12:20,710 --> 00:12:23,450 >> Tako da je umetanje stvari u Trie. 287 00:12:23,450 --> 00:12:25,384 Sada želimo tražiti stvari. 288 00:12:25,384 --> 00:12:27,050 Kako ćemo tražiti stvari u Trie? 289 00:12:27,050 --> 00:12:29,170 Pa, to je ljepušan velik dio isti ideja. 290 00:12:29,170 --> 00:12:33,620 Sada smo samo koristiti znamenki ključa vidjeti ako možemo kretati iz korijena 291 00:12:33,620 --> 00:12:37,170 gdje želimo ići u Trie. 292 00:12:37,170 --> 00:12:41,620 >> Ako pogodak ćorsokak u bilo kojem trenutku, a zatim Znamo da je taj element ne može postoji 293 00:12:41,620 --> 00:12:44,500 Inače taj put bi već izbrisani. 294 00:12:44,500 --> 00:12:45,930 Ako bi ga sve do kraj, sve što trebate učiniti 295 00:12:45,930 --> 00:12:48,471 je pogledati dolje i vidjeti ako je to element tražimo. 296 00:12:48,471 --> 00:12:49,335 Ako je uspjeh. 297 00:12:49,335 --> 00:12:52,610 Ako to nije, uspjeti. 298 00:12:52,610 --> 00:12:54,940 >> Tako ćemo tražiti Harvard u ovom Trie. 299 00:12:54,940 --> 00:12:56,020 Krećemo u korijenu. 300 00:12:56,020 --> 00:12:58,228 A, opet, mi ćemo stvoriti obuhvaćanje pokazivač 301 00:12:58,228 --> 00:12:59,390 učiniti naše poteze za nas. 302 00:12:59,390 --> 00:13:02,080 Iz korijena mi znamo da je Prvo mjesto moramo ići 1, 303 00:13:02,080 --> 00:13:03,390 možemo učiniti? 304 00:13:03,390 --> 00:13:03,982 Da možemo. 305 00:13:03,982 --> 00:13:04,690 Ako sigurno postoji. 306 00:13:04,690 --> 00:13:06,660 Možemo otići tamo. 307 00:13:06,660 --> 00:13:08,440 >> Sada, sljedeći mjesto moramo ići je 6. 308 00:13:08,440 --> 00:13:10,557 Da li postoji 6 put odavde? 309 00:13:10,557 --> 00:13:11,140 Da, tako je. 310 00:13:11,140 --> 00:13:12,690 Možemo ići dolje 6 put. 311 00:13:12,690 --> 00:13:13,905 I mi završiti ovdje. 312 00:13:13,905 --> 00:13:16,130 >> Možemo ići dolje 3 put odavde? 313 00:13:16,130 --> 00:13:18,450 Pa, kao što se ispostavilo, Da, da postoji previše. 314 00:13:18,450 --> 00:13:20,790 I možemo dobiti na 6. put odavde? 315 00:13:20,790 --> 00:13:21,982 Da možemo. 316 00:13:21,982 --> 00:13:24,002 >> Nismo baš odgovorio pitanje još. 317 00:13:24,002 --> 00:13:25,710 Postoji još jedan korak, koji je sada 318 00:13:25,710 --> 00:13:28,520 trebamo gledati prema dolje i vidjeti ako je to actually-- 319 00:13:28,520 --> 00:13:32,660 ako tražimo Harvardu, da što smo pronašli nakon što smo iscrpili ključ? 320 00:13:32,660 --> 00:13:35,430 U primjeru smo pomoću ovdje godine su uvijek četiri znamenke. 321 00:13:35,430 --> 00:13:40,280 Ali možda se na primjeru gdje pohranjujete rječnika riječi. 322 00:13:40,280 --> 00:13:44,060 >> I tako, umjesto da 10 pokazivače za moje mjesto, možda imate 26. 323 00:13:44,060 --> 00:13:46,040 Jedan za svako slovo abecede. 324 00:13:46,040 --> 00:13:50,350 A tu su i neke riječi poput šišmiša, što je podskup serije, na primjer. 325 00:13:50,350 --> 00:13:53,511 I tako, čak i ako se na kraj tipke i gledati prema dolje, 326 00:13:53,511 --> 00:13:55,260 možda nećete vidjeti što tražiš. 327 00:13:55,260 --> 00:13:58,500 >> Dakle, uvijek morate proći cijeli put, a zatim 328 00:13:58,500 --> 00:14:01,540 ako ste bili u mogućnosti uspješno prijeći cijeli put, 329 00:14:01,540 --> 00:14:03,440 pogledati dolje i napraviti jednu konačnu potvrdu. 330 00:14:03,440 --> 00:14:05,120 Je li to ono što ja tražim? 331 00:14:05,120 --> 00:14:07,740 Pa, gledam dolje nakon početka na vrhu i ide 1636. 332 00:14:07,740 --> 00:14:08,240 Gledam dolje. 333 00:14:08,240 --> 00:14:09,400 Vidim Harvarda. 334 00:14:09,400 --> 00:14:11,689 Dakle, da, uspio sam. 335 00:14:11,689 --> 00:14:13,980 Što ako je ono što tražim nije u Trie, ipak. 336 00:14:13,980 --> 00:14:17,200 Što ako tražim Princeton, koja je osnovana u 1746. 337 00:14:17,200 --> 00:14:20,875 I tako 1746. postaje moj ključ za navigaciju kroz Trie. 338 00:14:20,875 --> 00:14:22,040 Pa, ja početi u korijenu. 339 00:14:22,040 --> 00:14:24,760 A prvo mjesto želim da ide dolje na 1 put. 340 00:14:24,760 --> 00:14:25,590 Mogu li to učiniti? 341 00:14:25,590 --> 00:14:26,490 Da ja mogu. 342 00:14:26,490 --> 00:14:28,730 >> Mogu li ići dolje na 7 put od tamo? 343 00:14:28,730 --> 00:14:29,230 Da, mogu. 344 00:14:29,230 --> 00:14:30,750 Što postoji previše. 345 00:14:30,750 --> 00:14:32,460 Ali ja mogu ići dolje na 4. put odavde? 346 00:14:32,460 --> 00:14:35,550 To je kao da postavlja pitanje, može I nastavite niz onaj mali trg 347 00:14:35,550 --> 00:14:37,114 koje sam istaknuo u žuto? 348 00:14:37,114 --> 00:14:38,030 Nema ništa tamo. 349 00:14:38,030 --> 00:14:38,610 Tako je. 350 00:14:38,610 --> 00:14:41,310 >> Nema šanse naprijed niz 4 puta. 351 00:14:41,310 --> 00:14:46,480 Ako Princeton je u ovom Trie, da 4 bi bio jasan za nas već. 352 00:14:46,480 --> 00:14:49,130 I tako u ovom trenutku smo stigli u slijepu ulicu. 353 00:14:49,130 --> 00:14:50,250 Mi ne možemo ići dalje. 354 00:14:50,250 --> 00:14:53,440 I tako možemo reći, definitivno, ne. 355 00:14:53,440 --> 00:14:56,760 Princeton ne postoji u ovom Trie. 356 00:14:56,760 --> 00:14:58,860 >> Pa što to sve znači? 357 00:14:58,860 --> 00:14:59,360 Tako je. 358 00:14:59,360 --> 00:15:01,000 Postoji mnogo događa ovdje. 359 00:15:01,000 --> 00:15:02,500 Postoji naputke sve više mjesta. 360 00:15:02,500 --> 00:15:04,249 I, kao što možete vidjeti Upravo iz dijagrama, 361 00:15:04,249 --> 00:15:07,010 postoji puno čvorova da su vrsta leti okolo. 362 00:15:07,010 --> 00:15:13,480 Ali primijetite svaki put smo htjeli provjerite je li nešto nije u Trie, 363 00:15:13,480 --> 00:15:15,000 imali smo samo napraviti 4 poteze. 364 00:15:15,000 --> 00:15:17,208 >> Svaki put kad smo htjeli ubacite nešto u Trie, 365 00:15:17,208 --> 00:15:20,440 moramo napraviti 4 poteze, možda mallocing neke stvari na putu. 366 00:15:20,440 --> 00:15:23,482 No, kao što smo vidjeli kad smo umetnuta Dartmouth u Trie, 367 00:15:23,482 --> 00:15:25,940 ponekad nekim naprijed možda već biti izbrisani za nas. 368 00:15:25,940 --> 00:15:30,520 I tako je naš Trie dobiva veći i veći, moramo učiniti manje posla svaki put 369 00:15:30,520 --> 00:15:32,270 umetnuti nove stvari jer smo već 370 00:15:32,270 --> 00:15:35,746 izgrađen puno intermedijer grana na putu. 371 00:15:35,746 --> 00:15:38,370 Ako mi samo ikada pogledati 4 stvari, 4 je samo konstantna. 372 00:15:38,370 --> 00:15:41,750 Mi zapravo vrsta približava konstanta umetanje vrijeme 373 00:15:41,750 --> 00:15:44,501 i stalno Vrijeme pretraživanja. 374 00:15:44,501 --> 00:15:47,500 Tradeoff, naravno, u tome što ovo Trie, kao što vjerojatno možete reći, 375 00:15:47,500 --> 00:15:49,030 je ogroman. 376 00:15:49,030 --> 00:15:51,040 Svaka od tih čvorova zauzima puno prostora. 377 00:15:51,040 --> 00:15:52,090 >> Ali to je tradeoff. 378 00:15:52,090 --> 00:15:55,260 Ako želimo stvarno brzo umetanje, stvarno brzo brisanje, 379 00:15:55,260 --> 00:15:59,630 i stvarno brzo pretraživanje, moramo ima puno podataka leti okolo. 380 00:15:59,630 --> 00:16:03,590 Moramo izdvojiti puno prostora i memorija za tu strukturu podataka 381 00:16:03,590 --> 00:16:04,290 postojati. 382 00:16:04,290 --> 00:16:05,415 >> I tako to je tradeoff. 383 00:16:05,415 --> 00:16:07,310 No, izgleda da Možda su ga pronašli. 384 00:16:07,310 --> 00:16:09,560 Možda smo otkrili da Sveti gral strukture podataka 385 00:16:09,560 --> 00:16:12,264 s brzim umetanje, brisanje i pretraživanje. 386 00:16:12,264 --> 00:16:14,430 A možda će to biti odgovarajuća struktura podataka 387 00:16:14,430 --> 00:16:18,890 koristiti za bilo informacija Pokušavamo trgovine. 388 00:16:18,890 --> 00:16:21,860 Ja sam Doug Lloyd, ovo je cs50. 389 00:16:21,860 --> 00:16:23,433