1
00:00:00,000 --> 00:00:02,994
>> [Zenelejátszási]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Szóval mi már araszolnak közelebb
és közelebb a szent grál adatok

4
00:00:08,550 --> 00:00:13,050
struktúrák, az egyik, hogy mi lehet beszúrni
be, törölni, és felnéz

5
00:00:13,050 --> 00:00:15,440
konstans idõ alatt.

6
00:00:15,440 --> 00:00:16,270
Jobb.

7
00:00:16,270 --> 00:00:17,280
Ez a fajta a cél.

8
00:00:17,280 --> 00:00:19,720
Azt akarjuk, hogy képes megtenni
dolgok nagyon, nagyon gyorsan.

9
00:00:19,720 --> 00:00:22,580
>> Már megtaláltuk itt, amikor
beszélünk megpróbálja?

10
00:00:22,580 --> 00:00:23,670
Nos, vessünk egy pillantást.

11
00:00:23,670 --> 00:00:25,628
Így már látott több
adatstruktúrát

12
00:00:25,628 --> 00:00:28,680
hogy kezelni a feltérképezése
úgynevezett kulcsértékpárok,

13
00:00:28,680 --> 00:00:32,080
feltérképezése néhány adat
hogy néhány más adatot

14
00:00:32,080 --> 00:00:36,020
így tudjuk, hogy hol találja
információ a szerkezetben.

15
00:00:36,020 --> 00:00:40,060
>> Tehát tömb, például a
kulcs az elem indexe vagy tömb

16
00:00:40,060 --> 00:00:42,600
helyen 0 vagy tömb 1, és így tovább.

17
00:00:42,600 --> 00:00:46,140
És az értéket az adatok
hogy a megadott helyen található.

18
00:00:46,140 --> 00:00:48,550
Tehát mi a array 0?

19
00:00:48,550 --> 00:00:54,290
Mi a array 1 szemben mindössze
0 és 1, ami a kulcsokat.

20
00:00:54,290 --> 00:00:56,360
>> A hash tábla, hogy ez
fajta ugyanezt a gondolatot.

21
00:00:56,360 --> 00:01:00,690
A hash tábla, itt van ez a hash
funkciót, amely létrehozza hash kódok.

22
00:01:00,690 --> 00:01:03,670
Tehát a kulcs a hash kódot az adatok.

23
00:01:03,670 --> 00:01:06,530
És az értéket, különösen
beszélgettünk láncolással

24
00:01:06,530 --> 00:01:10,590
A videó hash táblák,
az, hogy a kapcsolt adatok listája

25
00:01:10,590 --> 00:01:12,550
hogy hash e hashcode.

26
00:01:12,550 --> 00:01:14,050
Jobb.

27
00:01:14,050 --> 00:01:16,050
Mi a helyzet más megközelítést
ez a módszer, bár?

28
00:01:16,050 --> 00:01:21,000
Mi a helyzet a módszer, ahol a
kulcs garantáltan egyedi,

29
00:01:21,000 --> 00:01:25,410
ellentétben a hash tábla, ahol sikerült
végén két adat

30
00:01:25,410 --> 00:01:27,200
amelyek azonos hashcode.

31
00:01:27,200 --> 00:01:30,020
És akkor azt kell kezelni
hogy akár tapintás vagy több

32
00:01:30,020 --> 00:01:33,340
lehetőleg láncolt kijavítani a problémát.

33
00:01:33,340 --> 00:01:37,520
>> Szóval most tudjuk garantálni
hogy mi a legfontosabb egyedi lesz.

34
00:01:37,520 --> 00:01:39,690
És mi van, ha a mi érték volt
csak valami olyan egyszerű,

35
00:01:39,690 --> 00:01:44,080
igaz és hamis, hogy azt mondja, hogy
vagy sem, hogy a darab információk

36
00:01:44,080 --> 00:01:45,610
létezik a szerkezet?

37
00:01:45,610 --> 00:01:48,180
Egy logikai lehet olyan egyszerű, mint egy kicsit.

38
00:01:48,180 --> 00:01:52,660
Reálisan ez talán egy
byte valószínűbb, mint egy kicsit.

39
00:01:52,660 --> 00:01:55,410
De ez sokkal kisebb, mint
tárolására talán egy 50-karakterlánc,

40
00:01:55,410 --> 00:01:57,360
például.

41
00:01:57,360 --> 00:02:02,210
>> Így próbál, hasonló hash táblák,
amelyek ötvözik a tömbök és láncolt lista,

42
00:02:02,210 --> 00:02:05,790
próbálkozás kombinálni tömbök,
struktúrák, és a mutatók

43
00:02:05,790 --> 00:02:08,509
együtt tárolni az adatokat
Érdekes módon, hogy az

44
00:02:08,509 --> 00:02:11,550
eléggé különbözik az
bármi, amit eddig láttunk.

45
00:02:11,550 --> 00:02:16,750
Most használd az adatokat egy ütemtervet
navigálni az adatok szerkezetét.

46
00:02:16,750 --> 00:02:18,710
És ha tudjuk követni
Az ütemterv, ha tudjuk

47
00:02:18,710 --> 00:02:22,390
kövesse az adatokat
elejétől a végéig, akkor

48
00:02:22,390 --> 00:02:24,945
tudom, hogy az adatokat
létezik a Trie.

49
00:02:24,945 --> 00:02:28,310
>> És ha nem tudjuk követni a térképen
re jelenti, hogy vessen véget minden,

50
00:02:28,310 --> 00:02:30,600
az adatok nem léteznek.

51
00:02:30,600 --> 00:02:32,890
Ismét a kulcsok itt vannak
garantáltan egyedi.

52
00:02:32,890 --> 00:02:36,020
És annyira nem egy hash tábla, soha nem fogjuk
kell foglalkozni ütközések itt.

53
00:02:36,020 --> 00:02:39,090
És nem két adat
pontosan ugyanazt a menetrendet

54
00:02:39,090 --> 00:02:40,530
kivéve, ha ezek az adatok azonosak.

55
00:02:40,530 --> 00:02:44,580
>> Ha betesszük John, majd
keresünk John.

56
00:02:44,580 --> 00:02:47,430
Ez két egyforma darab
adatok, igaz, mi keresünk keresztül.

57
00:02:47,430 --> 00:02:49,880
De egyébként, bármilyen
két darab adat

58
00:02:49,880 --> 00:02:52,750
Garantált, hogy egyedülálló menetrendek
ezen keresztül adatszerkezet.

59
00:02:52,750 --> 00:02:56,210
És megyünk megnézzük
vizuális ennek csak egy pillanatra.

60
00:02:56,210 --> 00:02:58,810
>> Majd ezt azzal, hogy megpróbálja
hozzon létre egy új adatszerkezetet,

61
00:02:58,810 --> 00:03:00,564
feltérképezése a következő kulcsfontosságú érték párokat.

62
00:03:00,564 --> 00:03:03,480
Ebben az esetben nem fogunk használni
valami olyan egyszerű, mint egy logikai.

63
00:03:03,480 --> 00:03:06,200
Igazából tárolja a húr.

64
00:03:06,200 --> 00:03:08,690
És ez a karakterlánc fog
legyen a neve egy egyetem.

65
00:03:08,690 --> 00:03:12,140
>> És a legfontosabb lesz az év
amikor az egyetemi-ben alakult.

66
00:03:12,140 --> 00:03:15,380
Minden évben az egyetemek
lesznek négy számjegy.

67
00:03:15,380 --> 00:03:19,840
És így fogjuk használni a négy számjegyek
eligazodni az adatok szerkezetét.

68
00:03:19,840 --> 00:03:22,270
És majd meglátjuk, megint, hogyan
teszünk, hogy egy pillanat.

69
00:03:22,270 --> 00:03:25,110
>> Végén az út,
fogjuk látni a nevét

70
00:03:25,110 --> 00:03:30,250
Az egyetem, amely megfelel
a kulcshoz, a négy számjegy.

71
00:03:30,250 --> 00:03:34,390
Az alapgondolata egy Trie
az, hogy van egy központi útvonalat.

72
00:03:34,390 --> 00:03:35,640
Így gondolok rá, mint egy fa.

73
00:03:35,640 --> 00:03:39,211
És ez hasonlóképpen helyesírási
és a koncepció, hogy egy fa.

74
00:03:39,211 --> 00:03:41,460
Általában, ha belegondolunk
fák a valós világban,

75
00:03:41,460 --> 00:03:44,090
van egy gyökér ez a
talaj és nőnek felfelé

76
00:03:44,090 --> 00:03:46,830
és ágak
és nekik van a levelek.

77
00:03:46,830 --> 00:03:49,450
És alapvetően azt az elképzelést,
egy Trie pontosan ugyanaz,

78
00:03:49,450 --> 00:03:51,755
kivéve, hogy a root egybehangzik
Valahol az égen.

79
00:03:51,755 --> 00:03:53,130
És a levelek alján.

80
00:03:53,130 --> 00:03:55,750
>> Szóval ez olyan, mint egy fa figyelembe
és csak essek fejjel lefelé.

81
00:03:55,750 --> 00:03:56,880
De még mindig vannak ágak.

82
00:03:56,880 --> 00:03:59,463
És azok lennének a mi utak,
azok lesznek a kapcsolatok

83
00:03:59,463 --> 00:04:02,220
a gyökér a levelek.

84
00:04:02,220 --> 00:04:04,200
Ebben az esetben, az említett
utak, azok az ágazatok,

85
00:04:04,200 --> 00:04:08,490
címkével vannak számjegy ez nekünk
merre kell menni, ahol vagyunk.

86
00:04:08,490 --> 00:04:11,800
>> Ha látunk egy 0, lemegyünk az ág,
ha látunk egy 1, lemegyünk az ág,

87
00:04:11,800 --> 00:04:12,900
és így és így tovább.

88
00:04:12,900 --> 00:04:14,060
Nos, mit jelent ez?

89
00:04:14,060 --> 00:04:16,519
Nos, ez azt jelenti, hogy
minden csomópontjában

90
00:04:16,519 --> 00:04:19,260
és minden csomópont a
középső és minden ág,

91
00:04:19,260 --> 00:04:23,020
van 10 lehetséges
helyen, hogy mi lehet menni.

92
00:04:23,020 --> 00:04:27,690
Tehát van 10 mutató
minden helyen.

93
00:04:27,690 --> 00:04:30,610
>> És ez az, ahol megpróbálja kaphat
kicsit ijesztő, hogy valaki

94
00:04:30,610 --> 00:04:34,460
aki nem sok
tapasztalat számítástechnika előtt.

95
00:04:34,460 --> 00:04:35,960
De igyekszik tényleg elég félelmetes.

96
00:04:35,960 --> 00:04:37,793
És ha megvan az
esélye, hogy működjön együtt velük

97
00:04:37,793 --> 00:04:40,420
és te hajlandó ásni-ben
és kísérletezni velük,

98
00:04:40,420 --> 00:04:44,234
ők tényleg elég érdekes
adatstruktúrák dolgozni.

99
00:04:44,234 --> 00:04:46,900
Ha azt akarjuk, hogy helyezzen be egy elemet
a Trie, csak annyit kell tennie

100
00:04:46,900 --> 00:04:51,360
A építeni a helyes utat
a gyökér a levél.

101
00:04:51,360 --> 00:04:55,390
Itt van, amit minden lépése során
ahogy nézhet.

102
00:04:55,390 --> 00:04:59,660
Fogunk meg egy új adatok
szerkezetet egy új csomópont úgynevezett Trie.

103
00:04:59,660 --> 00:05:02,560
>> És aztán az adatok
szerkezete van két darab.

104
00:05:02,560 --> 00:05:05,460
Megyünk tárolni
Íme egy egyetem.

105
00:05:05,460 --> 00:05:09,410
És fogunk tárolni
egy sor mutató

106
00:05:09,410 --> 00:05:12,190
más csomópontokhoz az azonos típusú.

107
00:05:12,190 --> 00:05:14,780
Szóval, megint ez az a fajta
A koncepció mindenhol

108
00:05:14,780 --> 00:05:18,567
vagyunk, mi a 10 lehetséges
helyek mehetünk.

109
00:05:18,567 --> 00:05:20,150
Ha látunk egy 0, megyünk le az ág.

110
00:05:20,150 --> 00:05:22,690
Ha látunk egy 1, ez az ág,
és így tovább, és így tovább, és így tovább.

111
00:05:22,690 --> 00:05:25,160
Ha azt mondjuk, 9, megyünk le az ág.

112
00:05:25,160 --> 00:05:28,220
Tehát minden csomópontjában,
mehetünk 10 lehetséges helyeket.

113
00:05:28,220 --> 00:05:35,740
Tehát minden csomópont tartalmaznia 10 mutató
más csomópontokhoz, hogy 10 másik csomópont.

114
00:05:35,740 --> 00:05:39,810
>> És az adatokat mi tárolására is
csak a neve az egyetem.

115
00:05:39,810 --> 00:05:41,060
Így építsük fel a Trie.

116
00:05:41,060 --> 00:05:44,860
Nézzük be egy pár
A tételek a mi Trie.

117
00:05:44,860 --> 00:05:46,740
Tehát az egyik legfontosabb,
ez a mi gyökér csomópont.

118
00:05:46,740 --> 00:05:49,740
Ez valószínűleg lesz valami
fogsz globálisan hirdetjük.

119
00:05:49,740 --> 00:05:53,450
És te fogsz globálisan fenntartása
egy mutató, ez a csomópont mindig.

120
00:05:53,450 --> 00:05:55,360
>> Meg fogsz mondani,
gyökér egyenlő, és te

121
00:05:55,360 --> 00:05:57,580
fog malloc magát Trie csomópontot.

122
00:05:57,580 --> 00:05:59,850
És te soha nem fog
megérinteni újra gyökeret eresszen.

123
00:05:59,850 --> 00:06:02,300
Minden alkalommal, amikor akar
a navigáció elindítása révén,

124
00:06:02,300 --> 00:06:05,802
beállított egy másik mutatót
egyenlő gyökér, mint a trav,

125
00:06:05,802 --> 00:06:07,760
amely a példában azt
Használja sok videóm

126
00:06:07,760 --> 00:06:11,090
itt a halmok és a sorban állás
és linklisták és így tovább.

127
00:06:11,090 --> 00:06:13,320
>> Te meg egy másik mutatót
nevű trav a bejárás.

128
00:06:13,320 --> 00:06:15,890
És akkor használja trav navigálni
keresztül az adatszerkezet.

129
00:06:15,890 --> 00:06:17,500
Nézzük, hogyan nézhet ki.

130
00:06:17,500 --> 00:06:19,880
Tehát most, hogy mi
nem egy csomópont kinézni?

131
00:06:19,880 --> 00:06:22,920
Nos, épp úgy, ahogy adatok
szerkezete megjelölt nyilatkozatban,

132
00:06:22,920 --> 00:06:26,906
van egy szöveg, amely
ebben az esetben üres.

133
00:06:26,906 --> 00:06:27,780
Nincs itt semmi.

134
00:06:27,780 --> 00:06:29,550
>> És egy sor 10 mutató.

135
00:06:29,550 --> 00:06:31,790
És most, mi csak
Van 1 csomópont ebben Trie.

136
00:06:31,790 --> 00:06:33,110
Semmi mást benne.

137
00:06:33,110 --> 00:06:36,020
Tehát mind a 10 ilyen
mutatók pont null.

138
00:06:36,020 --> 00:06:38,090
Ez az, amit a piros jelzi.

139
00:06:38,090 --> 00:06:39,500
>> Nézzük helyezze a húr Harvard.

140
00:06:39,500 --> 00:06:41,999
Helyezzük az Egyetem
Harvard ebbe Trie, amely

141
00:06:41,999 --> 00:06:43,940
-ben alakult a 1636.

142
00:06:43,940 --> 00:06:48,220
Azt szeretnénk használni a kulcsot,
1636, mondja el nekünk, hol vagyunk

143
00:06:48,220 --> 00:06:50,140
fog tárolni Harvard a Trie.

144
00:06:50,140 --> 00:06:51,470
Most, hogy hogyan lehet ezt tesszük?

145
00:06:51,470 --> 00:06:52,886
>> Lehet, hogy valahogy így néz ki.

146
00:06:52,886 --> 00:06:54,160
Kezdjük a gyökér.

147
00:06:54,160 --> 00:06:56,920
És mi van a 10 helyekre mehetünk.

148
00:06:56,920 --> 00:06:59,900
A gyökér van, mint bármely
másik csomópont a Trie.

149
00:06:59,900 --> 00:07:02,850
Jelenleg 10 helyen tudunk menni innen.

150
00:07:02,850 --> 00:07:07,215
>> Hogyan képzeljük érdemes
menni, ha a kulcs 1636?

151
00:07:07,215 --> 00:07:08,340
Ott tényleg két lehetősége van.

152
00:07:08,340 --> 00:07:08,450
Jobb.

153
00:07:08,450 --> 00:07:10,825
Mi lehet építeni a kulcsot
jobbról balra, és kezdje 6.

154
00:07:10,825 --> 00:07:14,000
Vagy tudtuk építeni a kulcsot
balról jobbra, és kezdődik 1.

155
00:07:14,000 --> 00:07:16,140
>> Ez valószínűleg több
intuitív, mint egy emberi lény

156
00:07:16,140 --> 00:07:18,110
megérteni mi
Csak megy balról jobbra.

157
00:07:18,110 --> 00:07:21,140
És így ha szeretné szúrni
Harvard ebbe Trie,

158
00:07:21,140 --> 00:07:23,560
Azt érdemes kezdeni
kiindulva a gyökér,

159
00:07:23,560 --> 00:07:25,720
néztem én 10 opciók
előttem, és azt mondja:

160
00:07:25,720 --> 00:07:28,700
Azt akarom, hogy menjen le a 1 útját.

161
00:07:28,700 --> 00:07:29,700
OKÉ.

162
00:07:29,700 --> 00:07:31,810
>> Most, 1 ág jelenleg üres.

163
00:07:31,810 --> 00:07:35,920
Tehát, ha azt akarom, hogy folytassa ezen az úton
beilleszteni ezt az elemet a Trie,

164
00:07:35,920 --> 00:07:42,040
Van malloc egy új csomópont, van 1
pont ott, és akkor én vagyok jó menni.

165
00:07:42,040 --> 00:07:46,460
>> Szóval én alapvetően vagyok egy
pont, ahol állok

166
00:07:46,460 --> 00:07:50,270
a gyökér a fa vagy a
Trie és van 10 ág.

167
00:07:50,270 --> 00:07:52,260
De minden ága van
kapu előtt azt.

168
00:07:52,260 --> 00:07:53,060
Jobb.

169
00:07:53,060 --> 00:07:54,850
Mert nincs más van.

170
00:07:54,850 --> 00:07:56,522
Nem biztonságos áthaladását.

171
00:07:56,522 --> 00:07:58,980
Ez azt jelenti, hogy nincs semmi
le bármely olyan ágakat.

172
00:07:58,980 --> 00:08:02,532
Ha azt szeretnénk, hogy kezdjék építeni
valamit, azt akarom, hogy távolítsa el a kaput.

173
00:08:02,532 --> 00:08:04,490
Azt akarom, hogy távolítsa el a kaput
előtt az 1. számú.

174
00:08:04,490 --> 00:08:05,698
És azt akarom, hogy sétálni, hogy.

175
00:08:05,698 --> 00:08:08,060
És szeretnék építeni
Egy másik helyen, hogy menjek.

176
00:08:08,060 --> 00:08:09,470
>> És ez az, amit én csináltam itt.

177
00:08:09,470 --> 00:08:11,430
Tehát 1 már nem mutat null.

178
00:08:11,430 --> 00:08:13,830
Azt mondtam, nyugodtan menjen le itt.

179
00:08:13,830 --> 00:08:15,789
Építettem egy másik csomópont.

180
00:08:15,789 --> 00:08:18,330
És mikor jut el, hogy node, én
Van egy másik döntés.

181
00:08:18,330 --> 00:08:20,890
Hol fogok menni innen?

182
00:08:20,890 --> 00:08:22,700
>> Nos, én már lement a 1.

183
00:08:22,700 --> 00:08:24,470
Szóval most érdemes lemenni a 6.

184
00:08:24,470 --> 00:08:24,970
Jobb.

185
00:08:24,970 --> 00:08:27,100
Ismét van 10 helyszínen tudok választani.

186
00:08:27,100 --> 00:08:30,060
Úgyhogy most megy le a 6.

187
00:08:30,060 --> 00:08:32,280
Szóval egyértelmű a kaput
előtte 6-os szám.

188
00:08:32,280 --> 00:08:33,250
És sétálok oda.

189
00:08:33,250 --> 00:08:34,580
És építek egy másik csomópont.

190
00:08:34,580 --> 00:08:37,630
És elértem egy másik kapcsolódási pont.

191
00:08:37,630 --> 00:08:40,289
>> Ismét én 10 választási
hol tudok menni.

192
00:08:40,289 --> 00:08:42,799
Már költözött 1-6.

193
00:08:42,799 --> 00:08:44,215
Szóval most érdemes menni 3.

194
00:08:44,215 --> 00:08:45,381
3, nincs hová megyek.

195
00:08:45,381 --> 00:08:48,980
Szóval van, hogy egyértelmű az utat
és építeni magamnak egy új helyet.

196
00:08:48,980 --> 00:08:50,870
És akkor a 3, hol akarok menni?

197
00:08:50,870 --> 00:08:52,450
Azt akarom, hogy menjen le 6.

198
00:08:52,450 --> 00:08:54,770
>> És újra meg kellett
egyértelmű az utat megtenni.

199
00:08:54,770 --> 00:08:59,179
Szóval most én is használtam a kulcsot, hogy helyezze létre
csomópontok és elkezdi építeni ezt a Trie.

200
00:08:59,179 --> 00:09:00,220
Elkezdtem a gyökere.

201
00:09:00,220 --> 00:09:03,666
Már lement 1636.

202
00:09:03,666 --> 00:09:05,540
És most én vagyok az alján
ott azon a csomóponton.

203
00:09:05,540 --> 00:09:06,610
És akkor lehet, hogy
látni a képernyőn.

204
00:09:06,610 --> 00:09:07,735
>> Ez sárgával.

205
00:09:07,735 --> 00:09:10,020
Ez az, ahol én vagyok jelenleg.

206
00:09:10,020 --> 00:09:11,300
Saját kulcs történik.

207
00:09:11,300 --> 00:09:13,030
Én már kimerítette minden helyzetben a kulcsot.

208
00:09:13,030 --> 00:09:15,040
Így nem tudok tovább menni.

209
00:09:15,040 --> 00:09:17,720
Tehát ezen a ponton, minden, amit
Tényleg kell tennie, hogy azt mondják, OK.

210
00:09:17,720 --> 00:09:18,990
Ez olyan, mint keres
le a földre,

211
00:09:18,990 --> 00:09:21,115
ha derített fényt
egyedül ez a fajta utat

212
00:09:21,115 --> 00:09:22,350
a különböző kapcsolatokat.

213
00:09:22,350 --> 00:09:25,800
Valahogy úgy nézett le, és egyfajta
festékszóró Harvard a földön.

214
00:09:25,800 --> 00:09:26,800
Ez a neve ennek.

215
00:09:26,800 --> 00:09:28,300
Tudd meg, hogy az, ami ezen a helyen.

216
00:09:28,300 --> 00:09:31,870
Ha elkezdjük a gyökere, és lemegyünk
1, majd 6, majd 3, majd 6,

217
00:09:31,870 --> 00:09:32,780
hol vagyunk?

218
00:09:32,780 --> 00:09:35,640
Nos, ha megnézzük le
és látjuk, Harvard, majd

219
00:09:35,640 --> 00:09:38,960
Tudjuk, hogy a Harvard volt
alapította 1636-ban, annak alapján, ahogy

220
00:09:38,960 --> 00:09:41,400
mi végrehajtási adatstruktúrát.

221
00:09:41,400 --> 00:09:43,177
Szóval ez volt remélhetőleg egyértelmű.

222
00:09:43,177 --> 00:09:44,760
Fogunk csinálni két betoldások.

223
00:09:44,760 --> 00:09:50,060
És remélhetőleg ez segíteni fog, hogy
lásd ezt el még kétszer.

224
00:09:50,060 --> 00:09:52,210
>> Most pedig nézzük helyezzen be egy másik egyetemen.

225
00:09:52,210 --> 00:09:54,630
Nézzük helyezze Yale ebbe Trie.

226
00:09:54,630 --> 00:09:57,037
Yale-ben alakult 1701-ben.

227
00:09:57,037 --> 00:09:58,870
Tehát kezdjük meg a
gyökér, mint mi mindig.

228
00:09:58,870 --> 00:09:59,890
És mi meg bejárás mutatót.

229
00:09:59,890 --> 00:10:01,624
Fogunk használni, hogy mozoghat.

230
00:10:01,624 --> 00:10:03,790
Az első dolog, amit szeretnénk
tennie, hogy menjen le az 1 útját.

231
00:10:03,790 --> 00:10:05,830
Ez az első számjegy a mi gombot.

232
00:10:05,830 --> 00:10:08,420
Szerencsére azonban, mi nem
van, hogy csináljanak valamit ebben az időben.

233
00:10:08,420 --> 00:10:09,919
Az 1 útját már törölték.

234
00:10:09,919 --> 00:10:13,520
Én tisztázta korábban, amikor
volt behelyezése Harvard meg 1636.

235
00:10:13,520 --> 00:10:18,090
Szóval lehet biztonságosan mozog
csökkentés 1, és csak ott.

236
00:10:18,090 --> 00:10:20,150
Ha lefelé mozdul az 1.

237
00:10:20,150 --> 00:10:22,930
>> Most azonban szeretnék menni 7.

238
00:10:22,930 --> 00:10:24,280
Azt az utat a 6.

239
00:10:24,280 --> 00:10:27,050
Tudom, hogy nyugodtan
folytassa le a 6 utat.

240
00:10:27,050 --> 00:10:29,220
De azt kell, hogy járjon el a 7 útját.

241
00:10:29,220 --> 00:10:30,580
Szóval mit kell tennem?

242
00:10:30,580 --> 00:10:35,070
Nos, csak úgy, mint korábban, csak kell
törölje a kapu, kap az útból,

243
00:10:35,070 --> 00:10:38,740
és épít egy új csomópont a 7. utat.

244
00:10:38,740 --> 00:10:40,250
Mint ez.

245
00:10:40,250 --> 00:10:42,930
>> Szóval most már átkerült 1, majd 7.

246
00:10:42,930 --> 00:10:45,550
És most észre, én vagyok a fajta
Az ezen az új alcsoport.

247
00:10:45,550 --> 00:10:46,050
Jobb.

248
00:10:46,050 --> 00:10:49,260
Minden más 16
a, Nem érdekel.

249
00:10:49,260 --> 00:10:50,720
Nem csinálok semmit 16.

250
00:10:50,720 --> 00:10:51,750
Csinálok 17 cucc.

251
00:10:51,750 --> 00:10:58,380
>> Tehát most 17, azt kell
fajta lángok új pályák itt.

252
00:10:58,380 --> 00:11:00,462
A következő számjegy a kulcsot 0.

253
00:11:00,462 --> 00:11:01,670
Én nyilvánvalóan nem kap sehol.

254
00:11:01,670 --> 00:11:02,628
Csak építette ezt a csomópontot.

255
00:11:02,628 --> 00:11:04,550
Szóval tudom, hogy nincs
utak előre innen.

256
00:11:04,550 --> 00:11:06,370
Tehát azt kell, hogy egy magam.

257
00:11:06,370 --> 00:11:09,360
>> Szóval malloc egy új csomópont
és 0 pont ott.

258
00:11:09,360 --> 00:11:12,770
És akkor még egyszer, én egy malloc
új csomópont és egy ponton van.

259
00:11:12,770 --> 00:11:15,870
Megint kimerítette a kulcsom, 1701.

260
00:11:15,870 --> 00:11:18,472
Így nézek le, és én festék spray Yale.

261
00:11:18,472 --> 00:11:19,680
Ez a neve ennek a csomópontot.

262
00:11:19,680 --> 00:11:24,660
>> És így most ha én valaha is kell látni, ha Yale
Ebben Trie, elkezdem a gyökér,

263
00:11:24,660 --> 00:11:27,060
Lemegyek 1701, és nézz le.

264
00:11:27,060 --> 00:11:30,030
És ha látom Yale permetező
festett a földre, majd

265
00:11:30,030 --> 00:11:32,200
Tudom Yale létezik ezen Trie.

266
00:11:32,200 --> 00:11:32,950
Csináljunk még egy.

267
00:11:32,950 --> 00:11:36,430
Nézzük helyezze Dartmouth ebbe
Trie-ben alapított 1769-ben.

268
00:11:36,430 --> 00:11:37,750
>> Kezdjük a gyökér újra.

269
00:11:37,750 --> 00:11:39,445
Az első számjegy az én kulcs 1.

270
00:11:39,445 --> 00:11:40,820
Én nyugodtan mozog ezen az úton.

271
00:11:40,820 --> 00:11:42,400
Amely már létezik.

272
00:11:42,400 --> 00:11:44,040
A következő számjegy az én kulcs 7.

273
00:11:44,040 --> 00:11:45,890
Én nyugodtan mozog ezen az úton.

274
00:11:45,890 --> 00:11:47,540
Ez létezik.

275
00:11:47,540 --> 00:11:49,000
>> A következő 6.

276
00:11:49,000 --> 00:11:52,860
Innen, ahol jelenleg vagyok
sárga ott, abban a középső csomópont,

277
00:11:52,860 --> 00:11:56,060
6 jelenleg zárolva van kapcsolva.

278
00:11:56,060 --> 00:11:58,830
Ha akarok menni ezen az úton,
Meg kell építeni magam.

279
00:11:58,830 --> 00:12:02,250
Úgyhogy malloc egy új csomópont
és 6 pont ott.

280
00:12:02,250 --> 00:12:04,250
És akkor megint én vagyok
ragyogó új pályák itt.

281
00:12:04,250 --> 00:12:10,750
>> Szóval malloc egy új csomópont, hogy honnan
hogy node-- Menetvonalszám 9-- majd most

282
00:12:10,750 --> 00:12:13,584
Ha utazom 1769, és nézek le.

283
00:12:13,584 --> 00:12:15,500
Nincs semmi jelenleg
spray-festett ott.

284
00:12:15,500 --> 00:12:16,930
Tudok Dartmouth.

285
00:12:16,930 --> 00:12:20,710
És én már be
Dartmouth a Trie.

286
00:12:20,710 --> 00:12:23,450
>> Szóval ez behelyezése
dolgokat a Trie.

287
00:12:23,450 --> 00:12:25,384
Most szeretnénk keresni dolgokat.

288
00:12:25,384 --> 00:12:27,050
Hogyan keresni dolgokat a Trie?

289
00:12:27,050 --> 00:12:29,170
Nos, ez nagyjából ugyanaz a gondolat.

290
00:12:29,170 --> 00:12:33,620
Most már csak használja a számjegyek a kulcs
hogy hátha tudunk navigálni a gyökér

291
00:12:33,620 --> 00:12:37,170
hogy hová akarunk menni a Trie.

292
00:12:37,170 --> 00:12:41,620
>> Ha zsákutcába bármely pontján, majd
tudjuk, hogy ez az elem nem létezik

293
00:12:41,620 --> 00:12:44,500
vagy pedig, hogy pályától
már kitisztult.

294
00:12:44,500 --> 00:12:45,930
Ha mi készítjük egészen
A végén, csak annyit kell tennie

295
00:12:45,930 --> 00:12:48,471
az lenézni és látni, ha ez
Az elem keresünk.

296
00:12:48,471 --> 00:12:49,335
Ha igen, akkor a siker.

297
00:12:49,335 --> 00:12:52,610
Ha nem, nem.

298
00:12:52,610 --> 00:12:54,940
>> Úgyhogy keresni
Harvard ebben Trie.

299
00:12:54,940 --> 00:12:56,020
Kezdjük a gyökér.

300
00:12:56,020 --> 00:12:58,228
És megint megyünk
hozzon létre egy bejárás mutatót

301
00:12:58,228 --> 00:12:59,390
hogy nem a mi mozog a számunkra.

302
00:12:59,390 --> 00:13:02,080
A gyökér tudjuk, hogy a
Először is meg kell, hogy menjen az 1,

303
00:13:02,080 --> 00:13:03,390
tehetünk, hogy?

304
00:13:03,390 --> 00:13:03,982
Igen.

305
00:13:03,982 --> 00:13:04,690
Ha biztonságosan létezik.

306
00:13:04,690 --> 00:13:06,660
Mi lehet ott.

307
00:13:06,660 --> 00:13:08,440
>> Most, a következő helyen kell mennünk 6.

308
00:13:08,440 --> 00:13:10,557
Vajon a 6 utat léteznek innen?

309
00:13:10,557 --> 00:13:11,140
Ja, igen.

310
00:13:11,140 --> 00:13:12,690
Mi lehet lemenni a 6 utat.

311
00:13:12,690 --> 00:13:13,905
És mi kerül ide.

312
00:13:13,905 --> 00:13:16,130
>> Mehetünk le a 3 utat innen?

313
00:13:16,130 --> 00:13:18,450
Nos, mint kiderült,
igen, ez létezik is.

314
00:13:18,450 --> 00:13:20,790
És tudjuk, hogy a 6 utat innen?

315
00:13:20,790 --> 00:13:21,982
Igen.

316
00:13:21,982 --> 00:13:24,002
>> Már nem is válaszol
A kérdés még.

317
00:13:24,002 --> 00:13:25,710
Van még egy további
lépés, amely most

318
00:13:25,710 --> 00:13:28,520
meg kell nézni le, és
hátha ez actually--

319
00:13:28,520 --> 00:13:32,660
ha keresünk Harvard, hogy
mit találunk miután kimeríti a kulcs?

320
00:13:32,660 --> 00:13:35,430
A példában mi használ itt,
Az év mindig négy számjegy.

321
00:13:35,430 --> 00:13:40,280
De lehet, hogy példáján, ahol
akkor tárolja a szótárban a szavak.

322
00:13:40,280 --> 00:13:44,060
>> És így ahelyett, hogy 10 mutató
hol vagyok, lehet, hogy 26.

323
00:13:44,060 --> 00:13:46,040
Egy minden egyes betűt az ábécé.

324
00:13:46,040 --> 00:13:50,350
És van néhány szó, mint a denevér,
amely egy részhalmaza szakaszos, például.

325
00:13:50,350 --> 00:13:53,511
És így még ha nem kap a
a kulcs vége, és úgy nézel le,

326
00:13:53,511 --> 00:13:55,260
lehet, hogy nem látni, mi
keres.

327
00:13:55,260 --> 00:13:58,500
>> Így mindig van, hogy áthalad
A teljes elérési utat, majd

328
00:13:58,500 --> 00:14:01,540
ha sikeresen tudja
bejárására a teljes elérési utat,

329
00:14:01,540 --> 00:14:03,440
lenéznek, és tegye végleges megerősítése.

330
00:14:03,440 --> 00:14:05,120
Ez az, amit én keresek?

331
00:14:05,120 --> 00:14:07,740
Nos, lenézek megkezdése után
a tetején, és megy 1636.

332
00:14:07,740 --> 00:14:08,240
Nézek le.

333
00:14:08,240 --> 00:14:09,400
Látom Harvard.

334
00:14:09,400 --> 00:14:11,689
Szóval, igen, sikerült.

335
00:14:11,689 --> 00:14:13,980
Mi van, ha az, amit keresek a
nem a Trie, mégis.

336
00:14:13,980 --> 00:14:17,200
Mi van, ha én keresek Princeton,
ben alapított 1746-ban.

337
00:14:17,200 --> 00:14:20,875
És így 1746 lesz a kulcsom
eligazodni a Trie.

338
00:14:20,875 --> 00:14:22,040
Nos, elkezdem a gyökere.

339
00:14:22,040 --> 00:14:24,760
És az első helyen akarok
hogy lemegy a 1 útját.

340
00:14:24,760 --> 00:14:25,590
Tudok csinálni?

341
00:14:25,590 --> 00:14:26,490
Igen tudok.

342
00:14:26,490 --> 00:14:28,730
>> Mehetek le a 7 utat onnan?

343
00:14:28,730 --> 00:14:29,230
Igen, én is.

344
00:14:29,230 --> 00:14:30,750
Hogy létezik is.

345
00:14:30,750 --> 00:14:32,460
De tudok lemenni a 4 utat innen?

346
00:14:32,460 --> 00:14:35,550
Ez olyan, mintha azt kérdezi a kérdést, lehet
Én jár le, hogy a kis négyzet

347
00:14:35,550 --> 00:14:37,114
hogy már sárga színnel?

348
00:14:37,114 --> 00:14:38,030
Nincs ott semmi.

349
00:14:38,030 --> 00:14:38,610
Jobb.

350
00:14:38,610 --> 00:14:41,310
>> Kizárt, hogy előre le 4 útját.

351
00:14:41,310 --> 00:14:46,480
Ha Princeton volt ebben Trie, hogy 4
azt nem törlik a számunkra már.

352
00:14:46,480 --> 00:14:49,130
És így ezen a ponton
elértük zsákutca.

353
00:14:49,130 --> 00:14:50,250
Nem tudunk tovább menni.

354
00:14:50,250 --> 00:14:53,440
És így azt mondhatjuk, véglegesen, nem.

355
00:14:53,440 --> 00:14:56,760
Princeton nem létezik ebben a Trie.

356
00:14:56,760 --> 00:14:58,860
>> Szóval mit is jelent ez?

357
00:14:58,860 --> 00:14:59,360
Jobb.

358
00:14:59,360 --> 00:15:01,000
Van egy csomó folyik itt.

359
00:15:01,000 --> 00:15:02,500
Van mutatókat az egész hely.

360
00:15:02,500 --> 00:15:04,249
És, mint látod
Csak a rajz,

361
00:15:04,249 --> 00:15:07,010
van egy csomó csomópontok
van egyfajta repülő körül.

362
00:15:07,010 --> 00:15:13,480
De észre minden alkalommal akartuk
ellenőrizni, hogy valami volt a Trie,

363
00:15:13,480 --> 00:15:15,000
már csak az, hogy a 4. mozog.

364
00:15:15,000 --> 00:15:17,208
>> Minden alkalommal, amikor meg akartuk
helyezze valamit a Trie,

365
00:15:17,208 --> 00:15:20,440
van, hogy a 4 mozog, esetleg
mallocing néhány dolgot az út mentén.

366
00:15:20,440 --> 00:15:23,482
De mint láttuk, amikor be
Dartmouth a Trie,

367
00:15:23,482 --> 00:15:25,940
néha néhány utat
Lehet, hogy már kitisztult számunkra.

368
00:15:25,940 --> 00:15:30,520
És így, mint a mi Trie egyre nagyobb és
nagyobb, már kevesebb munka minden alkalommal

369
00:15:30,520 --> 00:15:32,270
helyezzen be új dolgokat
hiszen már

370
00:15:32,270 --> 00:15:35,746
épített egy csomó köztes
ágak az út mentén.

371
00:15:35,746 --> 00:15:38,370
Ha mindig csak meg kell nézni
4 dolog, 4 egy konstans.

372
00:15:38,370 --> 00:15:41,750
Tényleg van ilyen közeleg
konstans időt behelyezés

373
00:15:41,750 --> 00:15:44,501
és állandó idő keresést.

374
00:15:44,501 --> 00:15:47,500
A kompromisszum, természetesen, az, hogy
ez Trie, ahogy talán mondani,

375
00:15:47,500 --> 00:15:49,030
hatalmas.

376
00:15:49,030 --> 00:15:51,040
Mindegyik csomópontok
vesz fel egy csomó helyet.

377
00:15:51,040 --> 00:15:52,090
>> De ez a kompromisszum.

378
00:15:52,090 --> 00:15:55,260
Ha azt akarjuk, nagyon gyors
beillesztés, nagyon gyors törlés,

379
00:15:55,260 --> 00:15:59,630
és nagyon gyors kereséssel, meg kell
Van egy csomó adat repülő körül.

380
00:15:59,630 --> 00:16:03,590
Meg kell félretenni egy csomó hely
és a memória az adott adatstruktúra

381
00:16:03,590 --> 00:16:04,290
létezni.

382
00:16:04,290 --> 00:16:05,415
>> És ez az a kompromisszum.

383
00:16:05,415 --> 00:16:07,310
De úgy néz ki, mint mi
Lehet, hogy megtalálta.

384
00:16:07,310 --> 00:16:09,560
Talán azt találták, hogy
szent grál adatstruktúrák

385
00:16:09,560 --> 00:16:12,264
gyors feltöltés,
törlés, és elemzéssel.

386
00:16:12,264 --> 00:16:14,430
És talán ez lesz
megfelelő adatok szerkezete

387
00:16:14,430 --> 00:16:18,890
használható bármilyen információ
próbálunk boltban.

388
00:16:18,890 --> 00:16:21,860
Én Doug Lloyd, ez CS50.

389
00:16:21,860 --> 00:16:23,433