1 00:00:00,000 --> 00:00:02,994 >> [Music kucheza] 2 00:00:02,994 --> 00:00:05,426 3 00:00:05,426 --> 00:00:08,550 DOUG LLOYD: Kwa hiyo tumekuwa inakaribia karibu na karibu kwamba takatifu grail ya data 4 00:00:08,550 --> 00:00:13,050 miundo, moja kwamba tunaweza kuingiza ndani ya, kufuta kutoka, na kuangalia juu 5 00:00:13,050 --> 00:00:15,440 muda mara kwa mara. 6 00:00:15,440 --> 00:00:16,270 Kulia. 7 00:00:16,270 --> 00:00:17,280 Hiyo ni aina ya lengo. 8 00:00:17,280 --> 00:00:19,720 Tunataka kuwa na uwezo wa kufanya mambo sana, kwa haraka sana. 9 00:00:19,720 --> 00:00:22,580 >> Na sisi kupatikana hapa wakati tunazungumzia inajaribu? 10 00:00:22,580 --> 00:00:23,670 Naam, hebu tuangalie. 11 00:00:23,670 --> 00:00:25,628 Hivyo tumeona kadhaa miundo mbalimbali data 12 00:00:25,628 --> 00:00:28,680 kwamba kushughulikia ramani ya kinachojulikana muhimu-thamani jozi, 13 00:00:28,680 --> 00:00:32,080 ramani baadhi kipande cha data kwa baadhi kipande nyingine ya data 14 00:00:32,080 --> 00:00:36,020 hivyo sisi kujua wapi kupata habari katika muundo. 15 00:00:36,020 --> 00:00:40,060 >> Hivyo kwa safu, kwa mfano, muhimu ni kipengele index au safu 16 00:00:40,060 --> 00:00:42,600 eneo 0 au safu ya 1 na kadhalika. 17 00:00:42,600 --> 00:00:46,140 Na thamani ya data ambayo ipo katika eneo hilo. 18 00:00:46,140 --> 00:00:48,550 Kwa hiyo kile ni kuhifadhiwa katika safu 0? 19 00:00:48,550 --> 00:00:54,290 Nini ni kuhifadhiwa katika safu 1 dhidi tu 0 na 1, ambayo itakuwa ni funguo. 20 00:00:54,290 --> 00:00:56,360 >> Kwa meza hash ni aina ya wazo moja. 21 00:00:56,360 --> 00:01:00,690 Kwa meza hash, tuna hash hii kazi ambayo inazalisha codes hash. 22 00:01:00,690 --> 00:01:03,670 Hivyo ni muhimu hash kanuni za data. 23 00:01:03,670 --> 00:01:06,530 Na thamani, hasa kuongelea chaining 24 00:01:06,530 --> 00:01:10,590 katika video juu ya meza hash, ni kwamba orodha wanaohusishwa ya data 25 00:01:10,590 --> 00:01:12,550 kwamba hashes kwa kuwa Msimboreli. 26 00:01:12,550 --> 00:01:14,050 Kulia. 27 00:01:14,050 --> 00:01:16,050 Je kuhusu mbinu nyingine njia hii, ingawa? 28 00:01:16,050 --> 00:01:21,000 Je kuhusu mbinu ambapo ufunguo ni uhakika kuwa ya kipekee, 29 00:01:21,000 --> 00:01:25,410 tofauti na hash meza, ambapo tunaweza kuishia na vipande viwili vya data 30 00:01:25,410 --> 00:01:27,200 kuwa Msimboreli huo. 31 00:01:27,200 --> 00:01:30,020 Na kisha sisi kuwa na kushughulika na kuwa na aidha uchunguzi au zaidi 32 00:01:30,020 --> 00:01:33,340 ikiwezekana chaining kurekebisha tatizo hilo. 33 00:01:33,340 --> 00:01:37,520 >> Hivyo sasa tunaweza kuhakikisha kuwa ufunguo yetu itakuwa ya kipekee. 34 00:01:37,520 --> 00:01:39,690 Na nini kama thamani yetu ilikuwa tu kitu kama rahisi 35 00:01:39,690 --> 00:01:44,080 kama kweli na uongo ambayo hutueleza ikiwa au si kwamba kipande cha habari 36 00:01:44,080 --> 00:01:45,610 ipo katika muundo? 37 00:01:45,610 --> 00:01:48,180 Boolean inaweza kuwa rahisi kama kidogo. 38 00:01:48,180 --> 00:01:52,660 Kwa kweli pengine ni Byte zaidi kuliko kidogo. 39 00:01:52,660 --> 00:01:55,410 Lakini hiyo ni mengi ndogo kuliko kuhifadhi labda kamba 50-tabia, 40 00:01:55,410 --> 00:01:57,360 kwa mfano. 41 00:01:57,360 --> 00:02:02,210 >> Hivyo inajaribu, sawa na hash meza, ambayo kuchanganya arrays na orodha wanaohusishwa, 42 00:02:02,210 --> 00:02:05,790 inajaribu kuchanganya arrays, miundo, na kuyatumia 43 00:02:05,790 --> 00:02:08,509 pamoja ili kuhifadhi data katika njia ya kuvutia hiyo ni 44 00:02:08,509 --> 00:02:11,550 pretty tofauti na chochote tumeona hadi sasa. 45 00:02:11,550 --> 00:02:16,750 Sasa sisi kutumia data kama mkakati navigate muundo huu data. 46 00:02:16,750 --> 00:02:18,710 Na kama tunaweza kufuata mpango wa, kama tunaweza 47 00:02:18,710 --> 00:02:22,390 kufuata takwimu kutoka mwanzo hadi mwisho, tutaweza 48 00:02:22,390 --> 00:02:24,945 kujua kama takwimu ambazo zipo katika trie. 49 00:02:24,945 --> 00:02:28,310 >> Na kama hatuwezi kufuata ramani kutoka kwa maana ya kumaliza kabisa, 50 00:02:28,310 --> 00:02:30,600 data haiwezi kuwepo. 51 00:02:30,600 --> 00:02:32,890 Tena, funguo hapa ni uhakika kuwa ya kipekee. 52 00:02:32,890 --> 00:02:36,020 Na hivyo tofauti na meza hash, tutaweza kamwe kuwa na kushughulika na migongano hapa. 53 00:02:36,020 --> 00:02:39,090 Na hakuna vipande viwili vya data na hasa mpango wa sawa 54 00:02:39,090 --> 00:02:40,530 isipokuwa takwimu ambazo ni kufanana. 55 00:02:40,530 --> 00:02:44,580 >> Kama sisi kuingiza John, basi sisi kutafuta John. 56 00:02:44,580 --> 00:02:47,430 Hiyo ni vipande viwili kufanana ya data, kulia, sisi ni kuangalia kwa. 57 00:02:47,430 --> 00:02:49,880 Lakini vinginevyo, yoyote vipande viwili vya data 58 00:02:49,880 --> 00:02:52,750 uhakika wa kuwa na roadmaps kipekee kupitia muundo huu data. 59 00:02:52,750 --> 00:02:56,210 Na tunakwenda tuangalie Visual ya hii katika muda tu. 60 00:02:56,210 --> 00:02:58,810 >> Tutaweza kufanya hivyo kwa kujaribu kujenga muundo mpya data, 61 00:02:58,810 --> 00:03:00,564 ramani ifuatayo thamani jozi ufunguo. 62 00:03:00,564 --> 00:03:03,480 Katika kesi hiyo, sisi siyo kwenda kutumia kitu rahisi kama Boolean. 63 00:03:03,480 --> 00:03:06,200 Sisi kwa kweli itakuwa kuhifadhi kamba. 64 00:03:06,200 --> 00:03:08,690 Na kamba hiyo ni kwenda kuwa jina la chuo kikuu. 65 00:03:08,690 --> 00:03:12,140 >> Na ufunguo ni kwenda kuwa mwaka wakati chuo kikuu kuwa ilianzishwa. 66 00:03:12,140 --> 00:03:15,380 Miaka yote kwa vyuo vikuu ni kwenda kuwa tarakimu nne. 67 00:03:15,380 --> 00:03:19,840 Na hivyo tutaweza kutumia wale tarakimu nne kwa navigate kupitia muundo huu data. 68 00:03:19,840 --> 00:03:22,270 Na tutaweza kuona, tena, jinsi sisi kufanya hivyo katika haki ya pili. 69 00:03:22,270 --> 00:03:25,110 >> Mwishoni mwa njia, tutaona jina 70 00:03:25,110 --> 00:03:30,250 ya chuo kikuu kwamba sambamba kwa kuwa suala muhimu, tarakimu wale wanne. 71 00:03:30,250 --> 00:03:34,390 Wazo msingi nyuma ya trie ni tuna njia ya kati. 72 00:03:34,390 --> 00:03:35,640 Hivyo kufikiri juu yake kama mti. 73 00:03:35,640 --> 00:03:39,211 Na hii ni sawa katika herufi na katika dhana ya mti. 74 00:03:39,211 --> 00:03:41,460 Kwa ujumla wakati sisi kufikiri juu miti katika ulimwengu wa kweli, 75 00:03:41,460 --> 00:03:44,090 wana mizizi hiyo ni katika ardhi na wao kukua zaidi 76 00:03:44,090 --> 00:03:46,830 na wana matawi na wana majani. 77 00:03:46,830 --> 00:03:49,450 Na kimsingi wazo la trie ni sawa, 78 00:03:49,450 --> 00:03:51,755 ila kwa kuwa mizizi ni nanga mahali fulani katika anga. 79 00:03:51,755 --> 00:03:53,130 Na majani ni chini. 80 00:03:53,130 --> 00:03:55,750 >> Hivyo ni aina ya kama kuchukua mti na tu flipping kichwa chini. 81 00:03:55,750 --> 00:03:56,880 Lakini bado kuna matawi. 82 00:03:56,880 --> 00:03:59,463 Na wale itakuwa njia yetu, wale itakuwa uhusiano wetu 83 00:03:59,463 --> 00:04:02,220 kutoka mizizi kwa majani. 84 00:04:02,220 --> 00:04:04,200 Katika kesi hiyo, wale njia, matawi hayo 85 00:04:04,200 --> 00:04:08,490 ni kinachoitwa na tarakimu kuwa kutuambia ambayo njia ya kwenda kutoka ambapo sisi ni. 86 00:04:08,490 --> 00:04:11,800 >> Kama tunaona 0, sisi kwenda chini tawi hili, kama tunaona 1, sisi kwenda chini tawi hili, 87 00:04:11,800 --> 00:04:12,900 na hivyo na kadhalika. 88 00:04:12,900 --> 00:04:14,060 Naam, hii ina maana gani? 89 00:04:14,060 --> 00:04:16,519 Naam, hiyo ina maana kwamba katika kila hatua ya makutano 90 00:04:16,519 --> 00:04:19,260 na kila nodi katika katikati na kila tawi, 91 00:04:19,260 --> 00:04:23,020 kuna watu 10 iwezekanavyo maeneo ambayo tunaweza kwenda. 92 00:04:23,020 --> 00:04:27,690 Hivyo kuna kuyatumia 10 kutoka kila eneo. 93 00:04:27,690 --> 00:04:30,610 >> Na hii ni mahali ambapo inajaribu wanaweza kupata kidogo vitisho kwa mtu 94 00:04:30,610 --> 00:04:34,460 ambaye ni hana mengi ya uzoefu katika sayansi ya kompyuta kabla. 95 00:04:34,460 --> 00:04:35,960 Lakini inajaribu ni kweli pretty kutisha. 96 00:04:35,960 --> 00:04:37,793 Na kama una nafasi ya kufanya kazi pamoja nao 97 00:04:37,793 --> 00:04:40,420 na uko tayari kuchimba katika na majaribio na wao, 98 00:04:40,420 --> 00:04:44,234 wao ni kweli ya kuvutia kabisa miundo data kufanya kazi pamoja. 99 00:04:44,234 --> 00:04:46,900 Kama tunataka kuingiza kipengele ndani ya trie, kila tunahitaji kufanya 100 00:04:46,900 --> 00:04:51,360 ni kujenga njia sahihi kutoka mizizi kwa jani. 101 00:04:51,360 --> 00:04:55,390 Hapa ni nini kila hatua pamoja njia ili kuangalia kama. 102 00:04:55,390 --> 00:04:59,660 Tunakwenda kufafanua takwimu mpya muundo wa nodi mpya iitwayo trie. 103 00:04:59,660 --> 00:05:02,560 >> Na ndani ya takwimu kwamba muundo kuna vipande viwili. 104 00:05:02,560 --> 00:05:05,460 Tunakwenda kuhifadhi jina la chuo kikuu. 105 00:05:05,460 --> 00:05:09,410 Na tunakwenda kuhifadhi safu ya kuyatumia 106 00:05:09,410 --> 00:05:12,190 kwa nodes nyingine ya aina moja. 107 00:05:12,190 --> 00:05:14,780 Hivyo, tena, hii ni aina hiyo kwa dhana ya kila mahali 108 00:05:14,780 --> 00:05:18,567 sisi ni, sisi saa 10 iwezekanavyo maeneo tunaweza kwenda. 109 00:05:18,567 --> 00:05:20,150 Kama tunaona 0, sisi kwenda chini tawi hilo. 110 00:05:20,150 --> 00:05:22,690 Kama tunaona 1, tawi hili, na kadhalika na kadhalika na kadhalika. 111 00:05:22,690 --> 00:05:25,160 Tukisema 9, sisi kwenda chini tawi hilo. 112 00:05:25,160 --> 00:05:28,220 Hivyo katika kila hatua ya makutano, tunaweza kwenda 10 maeneo iwezekanavyo. 113 00:05:28,220 --> 00:05:35,740 Hivyo kila node ana vyenye kuyatumia 10 kwa nodes nyingine, hadi 10 nodes nyingine. 114 00:05:35,740 --> 00:05:39,810 >> Na data sisi ni hifadhi ni tu jina la chuo kikuu. 115 00:05:39,810 --> 00:05:41,060 Basi hebu kujenga trie. 116 00:05:41,060 --> 00:05:44,860 Hebu kuingiza wanandoa ya vitu ndani ya trie yetu. 117 00:05:44,860 --> 00:05:46,740 Hivyo katika sana juu, hii ni nodi mizizi yetu. 118 00:05:46,740 --> 00:05:49,740 Hii pengine ni kwenda kuwa kitu wewe ni kwenda kimataifa kutangaza. 119 00:05:49,740 --> 00:05:53,450 Na wewe ni kwenda duniani kudumisha pointer nodi hii daima. 120 00:05:53,450 --> 00:05:55,360 >> Wewe ni kwenda kusema, mzizi sawa, na uko 121 00:05:55,360 --> 00:05:57,580 kwenda malloc mwenyewe trie nodi. 122 00:05:57,580 --> 00:05:59,850 Na wewe kamwe kwenda kugusa mzizi tena. 123 00:05:59,850 --> 00:06:02,300 Kila wakati unataka kuanza punde kwa njia, 124 00:06:02,300 --> 00:06:05,802 kuweka pointer mwingine sawa na mizizi, kama vile trav, 125 00:06:05,802 --> 00:06:07,760 ambayo ni mfano mimi kutumia katika wengi wa video yangu 126 00:06:07,760 --> 00:06:11,090 hapa mwingi na foleni na orodha kiungo na kadhalika. 127 00:06:11,090 --> 00:06:13,320 >> Kuweka pointer mwingine aitwaye trav kwa traversal. 128 00:06:13,320 --> 00:06:15,890 Na matumizi trav navigate kwa njia ya muundo data. 129 00:06:15,890 --> 00:06:17,500 Basi hebu angalia jinsi hii ili kuangalia. 130 00:06:17,500 --> 00:06:19,880 Hivyo sasa hivi, nini haina nodi kuangalia kama? 131 00:06:19,880 --> 00:06:22,920 Naam, tu kama takwimu zetu muundo wa tamko unahitajika, 132 00:06:22,920 --> 00:06:26,906 tuna kamba, ambayo katika kesi hii ni tupu. 133 00:06:26,906 --> 00:06:27,780 Kuna kitu hapa. 134 00:06:27,780 --> 00:06:29,550 >> Na safu ya kuyatumia 10. 135 00:06:29,550 --> 00:06:31,790 Na hivi sasa, sisi tu 1 nodi katika trie hii. 136 00:06:31,790 --> 00:06:33,110 Kuna kitu kingine ndani yake. 137 00:06:33,110 --> 00:06:36,020 Hivyo yote 10 ya wale kuyatumia hatua kwa null. 138 00:06:36,020 --> 00:06:38,090 Hiyo ni nini nyekundu inaonyesha. 139 00:06:38,090 --> 00:06:39,500 >> Hebu kuingiza kamba Harvard. 140 00:06:39,500 --> 00:06:41,999 Hebu kuingiza Chuo Kikuu cha Harvard katika trie hii, ambayo 141 00:06:41,999 --> 00:06:43,940 ilianzishwa mwaka 1636. 142 00:06:43,940 --> 00:06:48,220 Tunataka kutumia ufunguo, 1636, kutuambia ambapo tuko 143 00:06:48,220 --> 00:06:50,140 kwenda kuhifadhi Harvard katika trie. 144 00:06:50,140 --> 00:06:51,470 Sasa, tunawezaje kufanya hivyo? 145 00:06:51,470 --> 00:06:52,886 >> Inaweza kuangalia kitu kama hiki. 146 00:06:52,886 --> 00:06:54,160 Sisi kuanza katika mizizi. 147 00:06:54,160 --> 00:06:56,920 Na tuna hizi maeneo 10 tunaweza kwenda. 148 00:06:56,920 --> 00:06:59,900 Mzizi ni kama yoyote nodi wengine wa trie. 149 00:06:59,900 --> 00:07:02,850 Kuna sehemu 10 tunaweza kwenda kutoka hapa. 150 00:07:02,850 --> 00:07:07,215 >> Ambapo kufanya sisi pengine wanataka kwenda kama ufunguo ni 1636? 151 00:07:07,215 --> 00:07:08,340 Kuna kweli chaguzi mbili. 152 00:07:08,340 --> 00:07:08,450 Kulia. 153 00:07:08,450 --> 00:07:10,825 Tunaweza kujenga muhimu kutoka kulia na kushoto na kuanza na 6. 154 00:07:10,825 --> 00:07:14,000 Au tunaweza kujenga muhimu kutoka kushoto na kulia na kuanza na 1. 155 00:07:14,000 --> 00:07:16,140 >> Ni pengine zaidi Intuitive kama mwanadamu 156 00:07:16,140 --> 00:07:18,110 kuelewa tutaweza tu kwenda kushoto na haki. 157 00:07:18,110 --> 00:07:21,140 Na hivyo kama nataka kuingiza Harvard katika trie hii, 158 00:07:21,140 --> 00:07:23,560 Mimi labda unataka kuanza na kuanzia saa mizizi, 159 00:07:23,560 --> 00:07:25,720 kuangalia chaguzi wangu 10 mbele yangu, na kusema 160 00:07:25,720 --> 00:07:28,700 Nataka kwenda chini 1 njia. 161 00:07:28,700 --> 00:07:29,700 SAWA. 162 00:07:29,700 --> 00:07:31,810 >> Sasa, 1 njia sasa null. 163 00:07:31,810 --> 00:07:35,920 Hivyo kama nataka kuendelea chini njia kwamba kuingiza kipengele hiki katika trie, 164 00:07:35,920 --> 00:07:42,040 Mimi na malloc nodi mpya, na 1 uhakika huko, na kisha mimi nina nzuri ya kwenda. 165 00:07:42,040 --> 00:07:46,460 >> Hivyo mimi kimsingi niko kwenye mahali ambapo mimi nina amesimama 166 00:07:46,460 --> 00:07:50,270 mizizi ya mti au trie na kuna matawi 10. 167 00:07:50,270 --> 00:07:52,260 Lakini kila tawi ina lango mbele yake. 168 00:07:52,260 --> 00:07:53,060 Kulia. 169 00:07:53,060 --> 00:07:54,850 Kwa sababu kuna kitu kingine kuna. 170 00:07:54,850 --> 00:07:56,522 Hakuna kifungu salama. 171 00:07:56,522 --> 00:07:58,980 Hiyo ina maana kwamba kuna kitu chini yoyote ya matawi hayo. 172 00:07:58,980 --> 00:08:02,532 Kama mimi nataka kuanza kujenga kitu, nataka kuondoa lango. 173 00:08:02,532 --> 00:08:04,490 Nataka kuondoa lango mbele ya namba 1. 174 00:08:04,490 --> 00:08:05,698 Na mimi nataka kutembea chini kwamba. 175 00:08:05,698 --> 00:08:08,060 Na mimi nataka kujenga mahali pengine kwa niende. 176 00:08:08,060 --> 00:08:09,470 >> Na kwamba ni nini mimi tumefanya hapa. 177 00:08:09,470 --> 00:08:11,430 Hivyo 1 tena pointi null. 178 00:08:11,430 --> 00:08:13,830 Nilivyosema ni salama kwenda chini hapa sasa. 179 00:08:13,830 --> 00:08:15,789 Mimi kujengwa nodi mwingine. 180 00:08:15,789 --> 00:08:18,330 Na wakati mimi kupata kwamba nodi, mimi kuwa uamuzi nyingine ya kufanya. 181 00:08:18,330 --> 00:08:20,890 Ambapo mimi kwenda kwenda kutoka hapa? 182 00:08:20,890 --> 00:08:22,700 >> Naam, nimekuwa tayari wamekwenda chini 1. 183 00:08:22,700 --> 00:08:24,470 Hivyo sasa mimi pengine wanataka kwenda chini 6. 184 00:08:24,470 --> 00:08:24,970 Kulia. 185 00:08:24,970 --> 00:08:27,100 Tena, nina maeneo 10 Naweza kuchagua. 186 00:08:27,100 --> 00:08:30,060 Basi hebu sasa kwenda chini namba 6. 187 00:08:30,060 --> 00:08:32,280 Hivyo mimi wazi mlango mbele ya namba 6. 188 00:08:32,280 --> 00:08:33,250 Na mimi kutembea chini pale. 189 00:08:33,250 --> 00:08:34,580 Na mimi kujenga nodi mwingine. 190 00:08:34,580 --> 00:08:37,630 Na nimekuwa imefikia hatua nyingine makutano. 191 00:08:37,630 --> 00:08:40,289 >> Tena, nina 10 uchaguzi kwa ambapo naweza kwenda. 192 00:08:40,289 --> 00:08:42,799 Nimekuwa wakiongozwa 1-6. 193 00:08:42,799 --> 00:08:44,215 Hivyo sasa mimi pengine wanataka kwenda 3. 194 00:08:44,215 --> 00:08:45,381 3, kuna mahali pa siwezi kwenda. 195 00:08:45,381 --> 00:08:48,980 Hivyo nina kusafisha njia na kujenga mwenyewe nafasi mpya. 196 00:08:48,980 --> 00:08:50,870 Na kisha kutoka 3, ambapo mimi nataka kwenda? 197 00:08:50,870 --> 00:08:52,450 Nataka kwenda chini 6. 198 00:08:52,450 --> 00:08:54,770 >> Na, tena, nilikuwa na kusafisha njia ya kufanya hivyo. 199 00:08:54,770 --> 00:08:59,179 Hivyo sasa nimekuwa kutumika ufunguo wangu kuingiza kujenga nodes na kuanza kujenga trie hii. 200 00:08:59,179 --> 00:09:00,220 Nimeanza kwenye mizizi. 201 00:09:00,220 --> 00:09:03,666 Nimekuwa wamekwenda chini 1636. 202 00:09:03,666 --> 00:09:05,540 Na sasa mimi nina chini huko juu kwamba nodi. 203 00:09:05,540 --> 00:09:06,610 Na unaweza kuwa na uwezo wa kuona kwenye kioo. 204 00:09:06,610 --> 00:09:07,735 >> Ni yalionyesha katika njano. 205 00:09:07,735 --> 00:09:10,020 Hiyo ambapo mimi sasa niko. 206 00:09:10,020 --> 00:09:11,300 Ufunguo wangu ni kosa. 207 00:09:11,300 --> 00:09:13,030 Nimekuwa nimechoka kila nafasi katika ufunguo wangu. 208 00:09:13,030 --> 00:09:15,040 Hivyo siwezi kwenda yoyote zaidi. 209 00:09:15,040 --> 00:09:17,720 Hivyo katika hatua hii, wote mimi kweli wanahitaji kufanya ni kusema, sawa. 210 00:09:17,720 --> 00:09:18,990 Ni aina ya kama kuangalia chini ya ardhi, 211 00:09:18,990 --> 00:09:21,115 kama wewe ni envisioning mwenyewe kama aina hii ya njia 212 00:09:21,115 --> 00:09:22,350 wenye uhusiano tofauti. 213 00:09:22,350 --> 00:09:25,800 Aina ya kuangalia chini na aina ya dawa uchoraji Harvard juu ya ardhi. 214 00:09:25,800 --> 00:09:26,800 Hiyo ni jina la hii. 215 00:09:26,800 --> 00:09:28,300 Kujua kwamba ni nini katika eneo hili. 216 00:09:28,300 --> 00:09:31,870 Kama sisi kuanza katika mizizi na sisi kwenda chini 1 na kisha 6 na kisha 3 na kisha 6, 217 00:09:31,870 --> 00:09:32,780 ambapo ni sisi? 218 00:09:32,780 --> 00:09:35,640 Vizuri kama sisi kuangalia chini na tunaona Kikuu cha Harvard, kisha 219 00:09:35,640 --> 00:09:38,960 Tunajua kwamba Harvard alikuwa ilianzishwa mwaka 1636 kulingana na njia 220 00:09:38,960 --> 00:09:41,400 sisi ni utekelezaji wa muundo huu data. 221 00:09:41,400 --> 00:09:43,177 Ili kwamba ilikuwa hopefully moja kwa moja. 222 00:09:43,177 --> 00:09:44,760 Sisi ni kwenda kufanya insertions mbili zaidi. 223 00:09:44,760 --> 00:09:50,060 Na hopefully utakuwa msaada kwa kuona hii kufanyika mara mbili zaidi. 224 00:09:50,060 --> 00:09:52,210 >> Sasa, hebu kuingiza chuo kikuu mwingine. 225 00:09:52,210 --> 00:09:54,630 Hebu kuingiza Yale katika trie hii. 226 00:09:54,630 --> 00:09:57,037 Yale ilianzishwa mwaka 1701. 227 00:09:57,037 --> 00:09:58,870 Hivyo tutaweza kuanza saa mizizi, kama sisi daima kufanya. 228 00:09:58,870 --> 00:09:59,890 Na sisi kuweka traversal pointer. 229 00:09:59,890 --> 00:10:01,624 Tunakwenda kutumia kwamba hoja kwa njia ya. 230 00:10:01,624 --> 00:10:03,790 Jambo la kwanza tunataka kufanya ni kwenda chini 1 njia. 231 00:10:03,790 --> 00:10:05,830 Hiyo ni tarakimu ya kwanza ya ufunguo yetu. 232 00:10:05,830 --> 00:10:08,420 Kwa bahati nzuri, ingawa, hatufanyi una kufanya kazi yoyote wakati huu. 233 00:10:08,420 --> 00:10:09,919 Njia 1 imekwisha akalipa. 234 00:10:09,919 --> 00:10:13,520 Mimi akalipa ni awali wakati mimi ilikuwa kuingiza Harvard katika 1636. 235 00:10:13,520 --> 00:10:18,090 Hivyo siwezi salama hoja chini ya 1 na tu kwenda huko. 236 00:10:18,090 --> 00:10:20,150 Kama unaweza hoja chini 1. 237 00:10:20,150 --> 00:10:22,930 >> Hata hivyo, sasa nataka kwenda hadi 7. 238 00:10:22,930 --> 00:10:24,280 Mimi akalipa njia saa 6. 239 00:10:24,280 --> 00:10:27,050 Najua naweza salama kuendelea chini 6 njia. 240 00:10:27,050 --> 00:10:29,220 Lakini nahitaji kuendelea juu 7 njia. 241 00:10:29,220 --> 00:10:30,580 Basi je, mimi haja ya kufanya? 242 00:10:30,580 --> 00:10:35,070 Naam, tu kama kabla, mimi tu haja wazi mlango, kutoka nje ya njia, 243 00:10:35,070 --> 00:10:38,740 na kujenga nodi mpya kutoka 7 njia. 244 00:10:38,740 --> 00:10:40,250 Tu kama hii. 245 00:10:40,250 --> 00:10:42,930 >> Hivyo sasa nimekuwa wakiongozwa 1 na kisha 7. 246 00:10:42,930 --> 00:10:45,550 Na sasa taarifa, mimi nina aina ya juu ya subbranch hii mpya. 247 00:10:45,550 --> 00:10:46,050 Kulia. 248 00:10:46,050 --> 00:10:49,260 Kila kitu kingine kutoka 16 juu, mimi hawajali. 249 00:10:49,260 --> 00:10:50,720 Mimi si kufanya kitu chochote 16. 250 00:10:50,720 --> 00:10:51,750 Mimi nina kufanya 17 mambo ya ajabu. 251 00:10:51,750 --> 00:10:58,380 >> Hivyo sasa kutoka 17 na kuendelea, nina aina ya kuwaka trails mpya hapa. 252 00:10:58,380 --> 00:11:00,462 Tarakimu ijayo muhimu yangu ni 0. 253 00:11:00,462 --> 00:11:01,670 Mimi wazi hawawezi kupata mahali popote. 254 00:11:01,670 --> 00:11:02,628 I just kujengwa nodi hii. 255 00:11:02,628 --> 00:11:04,550 Hivyo najua hakuna njia mbele kutoka hapa. 256 00:11:04,550 --> 00:11:06,370 Hivyo nina kufanya moja mwenyewe. 257 00:11:06,370 --> 00:11:09,360 >> Hivyo mimi malloc nodi mpya na 0 hatua huko. 258 00:11:09,360 --> 00:11:12,770 Na kisha mara moja zaidi, mimi malloc nodi mpya na kuwa moja ya hatua huko. 259 00:11:12,770 --> 00:11:15,870 Tena, nimekuwa nimechoka ufunguo wangu, 1701. 260 00:11:15,870 --> 00:11:18,472 Hivyo mimi kuangalia chini na mimi dawa rangi Yale. 261 00:11:18,472 --> 00:11:19,680 Hiyo ni jina la nodi hii. 262 00:11:19,680 --> 00:11:24,660 >> Na hivyo sasa kama mimi milele haja ya kuona kama Yale ni katika trie hii, mimi kuanza katika mizizi, 263 00:11:24,660 --> 00:11:27,060 Mimi kwenda chini 1701, na kuangalia chini. 264 00:11:27,060 --> 00:11:30,030 Na kama mimi kuona Yale dawa walijenga kwenye ardhi, kisha 265 00:11:30,030 --> 00:11:32,200 Najua Yale ipo katika trie hii. 266 00:11:32,200 --> 00:11:32,950 Hebu kufanya moja zaidi. 267 00:11:32,950 --> 00:11:36,430 Hebu kuingiza Dartmouth katika hili trie, ambayo ilianzishwa mwaka 1769. 268 00:11:36,430 --> 00:11:37,750 >> Kuanza katika mizizi tena. 269 00:11:37,750 --> 00:11:39,445 Tarakimu wangu wa kwanza wa ufunguo wangu ni 1. 270 00:11:39,445 --> 00:11:40,820 Siwezi salama hoja chini njia hiyo. 271 00:11:40,820 --> 00:11:42,400 Ambayo tayari zipo. 272 00:11:42,400 --> 00:11:44,040 Tarakimu kijacho cha muhimu yangu ni 7. 273 00:11:44,040 --> 00:11:45,890 Siwezi salama hoja chini njia hiyo. 274 00:11:45,890 --> 00:11:47,540 Ipo pia. 275 00:11:47,540 --> 00:11:49,000 >> Yangu ijayo ni 6. 276 00:11:49,000 --> 00:11:52,860 Kutoka hapa, kutoka ambapo mimi sasa niko katika njano huko katika nodi kwamba katikati, 277 00:11:52,860 --> 00:11:56,060 6 sasa imefungwa mbali. 278 00:11:56,060 --> 00:11:58,830 Kama Nataka kwenda chini njia hiyo, Nina kujenga mwenyewe. 279 00:11:58,830 --> 00:12:02,250 Hivyo mimi itabidi malloc nodi mpya na 6 hatua huko. 280 00:12:02,250 --> 00:12:04,250 Na kisha, tena, mimi nina mkali trails mwezi hapa. 281 00:12:04,250 --> 00:12:10,750 >> Hivyo mimi malloc nodi mpya ili kutoka kwamba node-- njia idadi 9-- na kisha sasa 282 00:12:10,750 --> 00:12:13,584 kama mimi kusafiri 1769, na mimi kuangalia chini. 283 00:12:13,584 --> 00:12:15,500 Kuna kitu kwa sasa dawa walijenga huko. 284 00:12:15,500 --> 00:12:16,930 Siwezi kuandika Dartmouth. 285 00:12:16,930 --> 00:12:20,710 Na nimekuwa kuingizwa DARTMOUTH katika trie. 286 00:12:20,710 --> 00:12:23,450 >> Hivyo hiyo ni kuingiza mambo ndani trie. 287 00:12:23,450 --> 00:12:25,384 Sasa tunataka kutafuta mambo. 288 00:12:25,384 --> 00:12:27,050 Je, sisi kutafuta mambo katika trie? 289 00:12:27,050 --> 00:12:29,170 Naam, ni wazo moja kiasi pretty. 290 00:12:29,170 --> 00:12:33,620 Sasa sisi tu kutumia ufunguo wa tarakimu ili kuona kama tunaweza kuvuka kutoka mzizi 291 00:12:33,620 --> 00:12:37,170 ambapo tunataka kwenda katika trie. 292 00:12:37,170 --> 00:12:41,620 >> Kama sisi kugonga maiti ya mwisho katika hatua yoyote, basi Tunajua kwamba kwamba kipengele hawawezi ipo 293 00:12:41,620 --> 00:12:44,500 au mwingine njia ambayo ingekuwa tayari akalipa. 294 00:12:44,500 --> 00:12:45,930 Kama sisi kufanya hivyo njia yote ya mwisho, kila tunahitaji kufanya 295 00:12:45,930 --> 00:12:48,471 ni kuangalia chini na kuona kama hiyo ni kipengele sisi ni kuangalia kwa. 296 00:12:48,471 --> 00:12:49,335 Kama ni, mafanikio. 297 00:12:49,335 --> 00:12:52,610 Kama siyo, kushindwa. 298 00:12:52,610 --> 00:12:54,940 >> Basi hebu kutafuta Harvard katika trie hii. 299 00:12:54,940 --> 00:12:56,020 Sisi kuanza katika mizizi. 300 00:12:56,020 --> 00:12:58,228 Na, tena, tunakwenda kujenga traversal pointer 301 00:12:58,228 --> 00:12:59,390 kufanya hatua yetu kwa ajili yetu. 302 00:12:59,390 --> 00:13:02,080 Kutoka mizizi tunajua kwamba nafasi ya kwanza tunahitaji kwenda ni 1, 303 00:13:02,080 --> 00:13:03,390 Tunaweza kufanya hivyo? 304 00:13:03,390 --> 00:13:03,982 Ndio tunaweza. 305 00:13:03,982 --> 00:13:04,690 Kama salama lipo. 306 00:13:04,690 --> 00:13:06,660 Tunaweza kwenda huko. 307 00:13:06,660 --> 00:13:08,440 >> Sasa, nafasi ya pili tunahitaji kwenda ni 6. 308 00:13:08,440 --> 00:13:10,557 Je 6 njia zipo kutoka hapa? 309 00:13:10,557 --> 00:13:11,140 Yeah, ni gani. 310 00:13:11,140 --> 00:13:12,690 Tunaweza kwenda chini 6 njia. 311 00:13:12,690 --> 00:13:13,905 Na sisi kuishia hapa. 312 00:13:13,905 --> 00:13:16,130 >> Tunaweza kwenda chini njia 3 kutoka hapa? 313 00:13:16,130 --> 00:13:18,450 Naam, kama ni zamu nje, ndiyo, kwamba ipo pia. 314 00:13:18,450 --> 00:13:20,790 Na tunaweza kupata katika njia 6 kutoka hapa? 315 00:13:20,790 --> 00:13:21,982 Ndio tunaweza. 316 00:13:21,982 --> 00:13:24,002 >> Sisi si kabisa akajibu swali bado. 317 00:13:24,002 --> 00:13:25,710 Bado kuna moja zaidi hatua, ambayo sasa ni 318 00:13:25,710 --> 00:13:28,520 tunahitaji kuangalia chini na kuona kama hiyo ni actually-- 319 00:13:28,520 --> 00:13:32,660 kama sisi ni kuangalia kwa Kikuu cha Harvard, ni kwamba nini tunaona baada ya sisi kuziondoa muhimu? 320 00:13:32,660 --> 00:13:35,430 Katika mfano sisi ni kutumia hapa, Miaka daima tarakimu nne. 321 00:13:35,430 --> 00:13:40,280 Lakini unaweza kuwa na kutumia mfano ambapo wewe ni hifadhi kamusi ya maneno. 322 00:13:40,280 --> 00:13:44,060 >> Na hivyo badala ya kuwa kuyatumia 10 kwa eneo yangu, unaweza kuwa na 26. 323 00:13:44,060 --> 00:13:46,040 Moja kwa kila barua ya alfabeti. 324 00:13:46,040 --> 00:13:50,350 Na kuna baadhi ya maneno kama popo, ambayo ni subset ya kundi, kwa mfano. 325 00:13:50,350 --> 00:13:53,511 Na hivyo hata kama wewe kupata Mwisho wa ufunguo na wewe kuangalia chini, 326 00:13:53,511 --> 00:13:55,260 wewe wanaweza kuona nini wewe ni kuangalia kwa. 327 00:13:55,260 --> 00:13:58,500 >> Hivyo daima kuwa traverse njia nzima na kisha 328 00:13:58,500 --> 00:14:01,540 kama ungekuwa na uwezo mafanikio traverse njia nzima, 329 00:14:01,540 --> 00:14:03,440 kuangalia chini na kufanya uthibitisho moja ya mwisho. 330 00:14:03,440 --> 00:14:05,120 Ni kwamba kile mimi nina kuangalia kwa? 331 00:14:05,120 --> 00:14:07,740 Naam, mimi kuangalia chini baada ya kuanza juu na kwenda 1636. 332 00:14:07,740 --> 00:14:08,240 Mimi kuangalia chini. 333 00:14:08,240 --> 00:14:09,400 Mimi naona Harvard. 334 00:14:09,400 --> 00:14:11,689 Kwa hiyo, ndiyo, mimi wamefanikiwa. 335 00:14:11,689 --> 00:14:13,980 Nini kama nini mimi kuangalia kwa si katika trie, ingawa. 336 00:14:13,980 --> 00:14:17,200 Nini kama mimi nina kuangalia kwa Princeton, ambayo ilianzishwa mwaka 1746. 337 00:14:17,200 --> 00:14:20,875 Na hivyo inakuwa muhimu yangu 1746 navigate kupitia trie. 338 00:14:20,875 --> 00:14:22,040 Naam, mimi kuanza katika mizizi. 339 00:14:22,040 --> 00:14:24,760 Na nafasi ya kwanza nataka kwa inakwenda chini 1 njia. 340 00:14:24,760 --> 00:14:25,590 Naweza kufanya nini? 341 00:14:25,590 --> 00:14:26,490 Ndiyo ninaweza. 342 00:14:26,490 --> 00:14:28,730 >> Naweza kwenda chini njia 7 kutoka huko? 343 00:14:28,730 --> 00:14:29,230 Naam, naweza. 344 00:14:29,230 --> 00:14:30,750 Ambayo ipo pia. 345 00:14:30,750 --> 00:14:32,460 Lakini siwezi kwenda chini 4 njia kutoka hapa? 346 00:14:32,460 --> 00:14:35,550 Hiyo ni kama kuuliza swali, wanaweza Mimi kuendelea chini kwamba mraba kidogo 347 00:14:35,550 --> 00:14:37,114 kwamba nimepata yalionyesha katika njano? 348 00:14:37,114 --> 00:14:38,030 Kuna kitu huko. 349 00:14:38,030 --> 00:14:38,610 Kulia. 350 00:14:38,610 --> 00:14:41,310 >> Kuna njia hakuna mbele chini 4 njia. 351 00:14:41,310 --> 00:14:46,480 Kama Princeton alikuwa katika trie hii, kwamba 4 ingekuwa akalipa kwa ajili yetu tayari. 352 00:14:46,480 --> 00:14:49,130 Na hivyo katika hatua hii tumekuwa kufikiwa mwisho wafu. 353 00:14:49,130 --> 00:14:50,250 Hatuwezi kwenda yoyote zaidi. 354 00:14:50,250 --> 00:14:53,440 Na hivyo tunaweza kusema, kipekee, hakuna. 355 00:14:53,440 --> 00:14:56,760 Princeton haipo katika trie hii. 356 00:14:56,760 --> 00:14:58,860 >> Basi nini hii yote ina maana gani? 357 00:14:58,860 --> 00:14:59,360 Kulia. 358 00:14:59,360 --> 00:15:01,000 Kuna mengi kinachoendelea hapa. 359 00:15:01,000 --> 00:15:02,500 Kuna kuyatumia kila mahali. 360 00:15:02,500 --> 00:15:04,249 Na, kama unaweza kuona tu kutoka mchoro, 361 00:15:04,249 --> 00:15:07,010 kuna mengi ya nodes kwamba ni aina ya kuruka karibu. 362 00:15:07,010 --> 00:15:13,480 Lakini taarifa kila wakati sisi alitaka kuangalia kama kuna jambo katika trie, 363 00:15:13,480 --> 00:15:15,000 sisi tu alikuwa na kufanya 4 hatua. 364 00:15:15,000 --> 00:15:17,208 >> Kila wakati sisi alitaka kuingiza kitu katika trie, 365 00:15:17,208 --> 00:15:20,440 tuna kufanya 4 hatua, pengine mallocing baadhi ya mambo njiani. 366 00:15:20,440 --> 00:15:23,482 Lakini kama tuliona wakati sisi kuingizwa DARTMOUTH katika trie, 367 00:15:23,482 --> 00:15:25,940 wakati mwingine baadhi ya njia huenda tayari kuwa na akalipa kwa ajili yetu. 368 00:15:25,940 --> 00:15:30,520 Na hivyo kama trie yetu anapata kubwa na kubwa zaidi, tuna kufanya kazi chini kila wakati 369 00:15:30,520 --> 00:15:32,270 kuingiza vitu vipya kwa sababu tumekuwa tayari 370 00:15:32,270 --> 00:15:35,746 kujengwa mengi ya kati matawi njiani. 371 00:15:35,746 --> 00:15:38,370 Kama sisi milele tu na kuangalia 4 mambo, 4 ni mara kwa mara. 372 00:15:38,370 --> 00:15:41,750 Sisi kwa kweli ni aina ya inakaribia mara kwa mara wakati insertion 373 00:15:41,750 --> 00:15:44,501 na mara kwa mara wakati Luke. 374 00:15:44,501 --> 00:15:47,500 Tradeoff, bila shaka, ikiwa ni kwamba trie hii, kama pengine unaweza kusema, 375 00:15:47,500 --> 00:15:49,030 ni kubwa. 376 00:15:49,030 --> 00:15:51,040 Kila moja ya nodes hizi unachukua nafasi kubwa mno. 377 00:15:51,040 --> 00:15:52,090 >> Lakini hiyo ni tradeoff. 378 00:15:52,090 --> 00:15:55,260 Kama tunataka kweli haraka kuingizwa, kufutwa kweli haraka, 379 00:15:55,260 --> 00:15:59,630 na chaguo-kweli haraka, inabidi una mengi ya data wanaruka kote. 380 00:15:59,630 --> 00:16:03,590 Tuna kutenga mengi ya nafasi na kumbukumbu kwa kuwa muundo wa data 381 00:16:03,590 --> 00:16:04,290 kuwepo. 382 00:16:04,290 --> 00:16:05,415 >> Na hivyo ndiyo tradeoff. 383 00:16:05,415 --> 00:16:07,310 Lakini inaonekana kama sisi anaweza kuwa kupatikana. 384 00:16:07,310 --> 00:16:09,560 Tunaweza wamegundua kwamba takatifu grail wa miundo data 385 00:16:09,560 --> 00:16:12,264 na kuingizwa haraka, kufutwa, na Luke. 386 00:16:12,264 --> 00:16:14,430 Na labda hii itakuwa muundo sahihi data 387 00:16:14,430 --> 00:16:18,890 kutumia kwa maelezo chochote sisi ni kujaribu duka. 388 00:16:18,890 --> 00:16:21,860 Mimi nina Doug Lloyd, hii ni cs50. 389 00:16:21,860 --> 00:16:23,433