1
00:00:00,000 --> 00:00:02,994
>> [MUZIKO Ludante]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Do ni estis inching proksime
kaj pli proksimen, ke sankta grail de datumoj

4
00:00:08,550 --> 00:00:13,050
strukturoj, unu kiu ni povas enmeti
en, forigi el, kaj rigardi supren

5
00:00:13,050 --> 00:00:15,440
en konstanta tempo.

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

7
00:00:16,270 --> 00:00:17,280
Tio estas speco de la golo.

8
00:00:17,280 --> 00:00:19,720
Ni volas povi fari
aferojn tre, tre rapide.

9
00:00:19,720 --> 00:00:22,580
>> Tion ni trovis ŝin tie kiam
ni parolas pri klopodoj?

10
00:00:22,580 --> 00:00:23,670
Nu, ni rigardu.

11
00:00:23,670 --> 00:00:25,628
Do ni vidis plurajn
malsamaj datumstrukturoj

12
00:00:25,628 --> 00:00:28,680
tenantaj la surĵeto de
tn ŝlosilo-valoro paroj,

13
00:00:28,680 --> 00:00:32,080
surĵeto iu peco de datumoj
al alia peco de datumoj

14
00:00:32,080 --> 00:00:36,020
tial ni scias kie trovi
informo en la strukturo.

15
00:00:36,020 --> 00:00:40,060
>> Do por tabelo, ekzemple, la
ŝlosilo estas la elemento indekso aŭ tabelo

16
00:00:40,060 --> 00:00:42,600
ĉelo 0 aŭ tabelo 1 kaj tiel plu.

17
00:00:42,600 --> 00:00:46,140
Kaj la valoro estas la datumoj
kiu ekzistas ĉe tiu loko.

18
00:00:46,140 --> 00:00:48,550
Do kio estas stokita en tabelo 0?

19
00:00:48,550 --> 00:00:54,290
Kio estas stokita en tabelo 1 kontre nur
0 kaj 1, kiuj estus la ŝlosilojn.

20
00:00:54,290 --> 00:00:56,360
>> Kun hash tablo estas
ia la sama ideo.

21
00:00:56,360 --> 00:01:00,690
Kun hash tablo, ni havas ĉi hash
funkcion kiu generas hash kodojn.

22
00:01:00,690 --> 00:01:03,670
Do la ŝlosilo estas la hash kodon de la datumoj.

23
00:01:03,670 --> 00:01:06,530
Kaj la valoro, aparte
ni parolis pri ĉenante

24
00:01:06,530 --> 00:01:10,590
en la video sur hash tabloj,
estas ke ligillisto de datumoj

25
00:01:10,590 --> 00:01:12,550
ke hashes al tiu hashcode.

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

27
00:01:14,050 --> 00:01:16,050
Kio pri alian alproksimiĝon
tiu metodo, kvankam?

28
00:01:16,050 --> 00:01:21,000
Kio pri metodo kie la
ŝlosilo estas garantiita esti unika,

29
00:01:21,000 --> 00:01:25,410
kontraste hash tablo, kie ni povis
finos kun du pecoj de datumoj

30
00:01:25,410 --> 00:01:27,200
havantaj la saman hashcode.

31
00:01:27,200 --> 00:01:30,020
Kaj tiam ni devas trakti
ke per ĉu tuŝoprobado aŭ pli

32
00:01:30,020 --> 00:01:33,340
prefere ĉenante ripari tiun problemon.

33
00:01:33,340 --> 00:01:37,520
>> Do nun ni povas garantii
ke nia ŝlosilo estos unika.

34
00:01:37,520 --> 00:01:39,690
Kaj kio se nia valoro estis
nur io tiel facila

35
00:01:39,690 --> 00:01:44,080
kiel vera kaj falsa kiu diras al ni, cxu
aŭ ne ke peco de informo

36
00:01:44,080 --> 00:01:45,610
ekzistas en la strukturo?

37
00:01:45,610 --> 00:01:48,180
Al Bulea povus esti kiel simpla kiel iom.

38
00:01:48,180 --> 00:01:52,660
Realisme estas probable
Bajto pli verŝajna ol iom.

39
00:01:52,660 --> 00:01:55,410
Sed tio estas multe pli malgranda ol
stokante eble 50-signoĉenon,

40
00:01:55,410 --> 00:01:57,360
ekzemple.

41
00:01:57,360 --> 00:02:02,210
>> Do provas, simila al hash tabloj,
kiu kombinas arrays kaj ligillisto,

42
00:02:02,210 --> 00:02:05,790
tries kombini arrays,
strukturoj, kaj punteros

43
00:02:05,790 --> 00:02:08,509
kune por stoki datumoj en
interesa maniero kiu estas

44
00:02:08,509 --> 00:02:11,550
bela malsama
ion ni vidis ĝis nun.

45
00:02:11,550 --> 00:02:16,750
Nun ni uzas la datumojn kiel vojmapon
navigi tiu datumstrukturo.

46
00:02:16,750 --> 00:02:18,710
Kaj se ni povas sekvi
la vojmapon, se ni povas

47
00:02:18,710 --> 00:02:22,390
sekvi la datenoj de
komencanta fini, ni

48
00:02:22,390 --> 00:02:24,945
scias ĉu tiu datumo
ekzistas en la trie.

49
00:02:24,945 --> 00:02:28,310
>> Kaj se ni ne povas sekvi la mapo
el signifanta finiĝu ĉiuj,

50
00:02:28,310 --> 00:02:30,600
la datumoj povas ne ekzisti.

51
00:02:30,600 --> 00:02:32,890
Denove, la klavoj jen
garantiita esti unika.

52
00:02:32,890 --> 00:02:36,020
Kaj tiel kontraste hash tablo, ni neniam
devos pritrakti koliziojn tie.

53
00:02:36,020 --> 00:02:39,090
Kaj ne du pecoj de datumoj
havas ekzakte la saman vojmapon

54
00:02:39,090 --> 00:02:40,530
se tio datumoj estas identaj.

55
00:02:40,530 --> 00:02:44,580
>> Se ni enmeti Johanon, tiam
Ni serĉu por John.

56
00:02:44,580 --> 00:02:47,430
Jen du identaj pecoj de
datumoj, ĝuste, ni serĉas tra.

57
00:02:47,430 --> 00:02:49,880
Sed alie, iu
du pecoj de datumoj estas

58
00:02:49,880 --> 00:02:52,750
garantiita havi unikan roadmaps
tra ĉi datumstrukturo.

59
00:02:52,750 --> 00:02:56,210
Kaj ni tuj rigardu
vida de tiu en nur momento.

60
00:02:56,210 --> 00:02:58,810
>> Ni faros tion per provo
krei novan datumstrukturo,

61
00:02:58,810 --> 00:03:00,564
surĵeto la jenaj ŝlosilaj valoro paroj.

62
00:03:00,564 --> 00:03:03,480
En tiu kazo, ni ne tuj uzi
iu tiel simpla kiel Bulea.

63
00:03:03,480 --> 00:03:06,200
Ni efektive konservos la kordo.

64
00:03:06,200 --> 00:03:08,690
Kaj ke kordoj tuj
esti la nomo de universitato.

65
00:03:08,690 --> 00:03:12,140
>> Kaj la ŝlosilo tuj estos la jaro
kiam tiu universitato estis fondita.

66
00:03:12,140 --> 00:03:15,380
Ĉiuj jaroj por universitatoj
tuj estos kvar ciferoj.

67
00:03:15,380 --> 00:03:19,840
Kaj tial ni uzas tiujn kvar ciferoj por
navigi tra tiu datumstrukturo.

68
00:03:19,840 --> 00:03:22,270
Kaj ni vidos, denove, kiom
ni faru tion en nur dua.

69
00:03:22,270 --> 00:03:25,110
>> Fine de la pado,
ni vidos la nomo

70
00:03:25,110 --> 00:03:30,250
de la universitato kiu respondas
al tiu klavo, tiuj kvar ciferoj.

71
00:03:30,250 --> 00:03:34,390
La baza ideo malantaŭ trie
Estas ni havas centran itineron.

72
00:03:34,390 --> 00:03:35,640
Do pensu pri ĝi kiel arbon.

73
00:03:35,640 --> 00:03:39,211
Kaj tiu estas simila en ortografio
kaj en koncepto al arbo.

74
00:03:39,211 --> 00:03:41,460
Ĝenerale, kiam ni pensas pri
arboj en la reala mondo,

75
00:03:41,460 --> 00:03:44,090
ili havas radikon kiu estas en la
teron kaj kreskas supren

76
00:03:44,090 --> 00:03:46,830
kaj ili havas branĉojn
kaj ili havas foliojn.

77
00:03:46,830 --> 00:03:49,450
Kaj esence la ideo de
trie estas ekzakte la sama,

78
00:03:49,450 --> 00:03:51,755
krom ke radiko estas ankrumita
ie en la ĉielo.

79
00:03:51,755 --> 00:03:53,130
Kaj la folioj estas en la fundo.

80
00:03:53,130 --> 00:03:55,750
>> Do ĝi estas speco de kiel preni arbo
kaj ĝuste klakanta renversos.

81
00:03:55,750 --> 00:03:56,880
Sed estas ankoraŭ branĉoj.

82
00:03:56,880 --> 00:03:59,463
Kaj tiuj estus niaj vojoj,
tiuj estos nia rilatoj

83
00:03:59,463 --> 00:04:02,220
de la radiko al la folioj.

84
00:04:02,220 --> 00:04:04,200
En tiu kazo, tiuj
vojetoj, tiuj branĉoj

85
00:04:04,200 --> 00:04:08,490
estas etikedita kun ciferoj, kiuj montras
kiun vojo iri de kie ni estas.

86
00:04:08,490 --> 00:04:11,800
>> Se ni vidas ĉirkaŭ 0, ni iras, ĉi tiu branĉo,
se ni vidas 1, ni iras, ĉi tiu branĉo,

87
00:04:11,800 --> 00:04:12,900
kaj tiel kaj tiel plu.

88
00:04:12,900 --> 00:04:14,060
Nu, kion tio signifu?

89
00:04:14,060 --> 00:04:16,519
Nu, tio signifas ke
ĉe ĉiu krucvojo punkto

90
00:04:16,519 --> 00:04:19,260
kaj ĉiu nodo en la
mezo kaj ĉiu branĉo,

91
00:04:19,260 --> 00:04:23,020
ekzistas 10 eblaj
lokoj kiujn ni povas iri.

92
00:04:23,020 --> 00:04:27,690
Do estas 10 punteros
de ĉiu loko.

93
00:04:27,690 --> 00:04:30,610
>> Kaj tiu estas kie tries povas akiri
iomete timiga por iu

94
00:04:30,610 --> 00:04:34,460
kiuj estas ne havas multajn
sperto en komputiko antaŭe.

95
00:04:34,460 --> 00:04:35,960
Sed provoj estas vere bela awesome.

96
00:04:35,960 --> 00:04:37,793
Kaj se vi havas la
eblecon labori kun ili

97
00:04:37,793 --> 00:04:40,420
kaj vi pretas fosi -in
kaj sperti kun ili,

98
00:04:40,420 --> 00:04:44,234
ili estas vere sufiĉe interesa
datumstrukturoj labori kun.

99
00:04:44,234 --> 00:04:46,900
Se ni volas enmeti ero
en la trie, ĉiuj ni devas fari

100
00:04:46,900 --> 00:04:51,360
estas konstrui la ĝustan padon
de la radiko al la folio.

101
00:04:51,360 --> 00:04:55,390
Jen kion ĉiupaŝe kune
la vojo povus aspekti.

102
00:04:55,390 --> 00:04:59,660
Ni tuj difini novajn datumojn
strukturon por nova nodo nomata trie.

103
00:04:59,660 --> 00:05:02,560
>> Kaj ene de tiu datumoj
strukturo estas du pecoj.

104
00:05:02,560 --> 00:05:05,460
Ni tuj stoki la
nomo de universitato.

105
00:05:05,460 --> 00:05:09,410
Kaj ni tuj stoki
tabelo de punteros

106
00:05:09,410 --> 00:05:12,190
al aliaj nodoj de la sama tipo.

107
00:05:12,190 --> 00:05:14,780
Do, denove, ĉi tiu estas tia
de koncepto de ĉie

108
00:05:14,780 --> 00:05:18,567
ni estas, ni ĉe 10 eblaj
lokoj oni povas iri.

109
00:05:18,567 --> 00:05:20,150
Se ni vidas ĉirkaŭ 0, ni iras, tiu branĉo.

110
00:05:20,150 --> 00:05:22,690
Se ni vidas 1, ĉi tiu branĉo,
kaj tiel plu kaj tiel plu kaj tiel plu.

111
00:05:22,690 --> 00:05:25,160
Se ni diras 9, ni iras malsupren tiu branĉo.

112
00:05:25,160 --> 00:05:28,220
Do je ĉiu punkto junton,
ni povas iri 10 eblaj lokoj.

113
00:05:28,220 --> 00:05:35,740
Do ĉiu nodo havas enhavi 10 punteros
al aliaj nodoj, al 10 aliaj nodoj.

114
00:05:35,740 --> 00:05:39,810
>> Kaj la datumoj ni stokante estas
nur la nomo de la universitato.

115
00:05:39,810 --> 00:05:41,060
Do ni konstruu trie.

116
00:05:41,060 --> 00:05:44,860
Ni enmeti paron
de erojn en nia trie.

117
00:05:44,860 --> 00:05:46,740
Do ĉe la plejsupro,
jen nia radika nodo.

118
00:05:46,740 --> 00:05:49,740
Tio sendube estas tuj estos iu
vi tuj tutmonde deklaras.

119
00:05:49,740 --> 00:05:53,450
Kaj vi tuj tutmonde subteni
puntero al tiu nodo ĉiam.

120
00:05:53,450 --> 00:05:55,360
>> Vi tuj diros,
radiko egalas, kaj vi estas

121
00:05:55,360 --> 00:05:57,580
tuj malloc mem trie nodo.

122
00:05:57,580 --> 00:05:59,850
Kaj vi neniam iras
tuŝi radiko denove.

123
00:05:59,850 --> 00:06:02,300
Ĉiufoje vi volas
komenci navigi tra,

124
00:06:02,300 --> 00:06:05,802
vi fiksis alian montrilon
egala al radiko, kiel trav,

125
00:06:05,802 --> 00:06:07,760
kiu estas la ekzemplo mi
uzi en multaj de miaj filmetoj

126
00:06:07,760 --> 00:06:11,090
tie sur stakoj kaj atendovicoj
kaj karmo lertaj kaj tiel plu.

127
00:06:11,090 --> 00:06:13,320
>> Vi starigis alian montrilon
nomata trav por trairado.

128
00:06:13,320 --> 00:06:15,890
Kaj vi uzas trav navigi
tra la datumstrukturo.

129
00:06:15,890 --> 00:06:17,500
Do ni vidu kiel ĉi povus rigardi.

130
00:06:17,500 --> 00:06:19,880
Do nun, kio
does nodo aspektas?

131
00:06:19,880 --> 00:06:22,920
Nu, ĝuste kiel nia datumoj
strukturo deklaro indikis,

132
00:06:22,920 --> 00:06:26,906
ni havas ĉenon, kiu
en tiu kazo estas malplena.

133
00:06:26,906 --> 00:06:27,780
Nenio ĉi tie.

134
00:06:27,780 --> 00:06:29,550
>> Kaj tabelo de 10 punteros.

135
00:06:29,550 --> 00:06:31,790
Kaj nun, ni nur
havas 1 nodo en ĉi trie.

136
00:06:31,790 --> 00:06:33,110
Ekzistas nenio en ĝi.

137
00:06:33,110 --> 00:06:36,020
Do ĉiuj 10 el tiuj
punteros punkto al nula.

138
00:06:36,020 --> 00:06:38,090
Tion la ruĝa indikas.

139
00:06:38,090 --> 00:06:39,500
>> Ni enŝovu la kordo Harvard.

140
00:06:39,500 --> 00:06:41,999
Ni enŝovu la Universitato de
Harvard en ĉi trie, kiu

141
00:06:41,999 --> 00:06:43,940
estis fondita en la jaro 1636.

142
00:06:43,940 --> 00:06:48,220
Ni volas uzi la ŝlosilon,
1636, por diri al ni kie ni estas

143
00:06:48,220 --> 00:06:50,140
tuj stoki Harvard en la trie.

144
00:06:50,140 --> 00:06:51,470
Nun, kio povus ni faru tion?

145
00:06:51,470 --> 00:06:52,886
>> Eble aspektas tiel.

146
00:06:52,886 --> 00:06:54,160
Ni starti je la radiko.

147
00:06:54,160 --> 00:06:56,920
Kaj ni havas tiujn 10 lokoj oni povas iri.

148
00:06:56,920 --> 00:06:59,900
La radiko estas nur kiel ajna
alia nodo de la trie.

149
00:06:59,900 --> 00:07:02,850
Ekzistas 10 lokoj ni povas iri de tie.

150
00:07:02,850 --> 00:07:07,215
>> Kie ni probable volas
iri se la ŝlosilo estas 1636?

151
00:07:07,215 --> 00:07:08,340
Ekzistas vere du ebloj.

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

153
00:07:08,450 --> 00:07:10,825
Ni povas konstrui la ŝlosilo de
dekstra al maldekstra kaj komenci kun 6.

154
00:07:10,825 --> 00:07:14,000
Aŭ ni povus konstrui la ŝlosilo de
maldekstre dekstren kaj komenci kun 1.

155
00:07:14,000 --> 00:07:16,140
>> Estas probable pli
intuicia kiel homo

156
00:07:16,140 --> 00:07:18,110
kompreni ni
Nur iru maldekstre dekstren.

157
00:07:18,110 --> 00:07:21,140
Kaj do se mi volas enmeti
Harvard en ĉi trie,

158
00:07:21,140 --> 00:07:23,560
Mi verŝajne volas komenci
komencante ĉe la radiko,

159
00:07:23,560 --> 00:07:25,720
rigardante mian 10 ebloj
antaŭ mi, kaj dirante

160
00:07:25,720 --> 00:07:28,700
Mi volas iri malsupren la 1 pado.

161
00:07:28,700 --> 00:07:29,700
BONE.

162
00:07:29,700 --> 00:07:31,810
>> Nun, 1 vojo estas nuntempe nula.

163
00:07:31,810 --> 00:07:35,920
Do, se mi volas daŭrigi laŭ tiu vojo
enigi tiun elementon en la trie,

164
00:07:35,920 --> 00:07:42,040
Mi havas malloc novan nodon, havas 1
atentigi tie, kaj tiam mi estas bona iri.

165
00:07:42,040 --> 00:07:46,460
>> Do mi esence estas je
punkto kie mi staris

166
00:07:46,460 --> 00:07:50,270
ĉe la radiko de la arbo aŭ la
trie kaj ekzistas 10 branĉoj.

167
00:07:50,270 --> 00:07:52,260
Sed ĉiu branĉo havas
pordego antaŭ ĝi.

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

169
00:07:53,060 --> 00:07:54,850
Ĉar estas nenio alia ekzistas.

170
00:07:54,850 --> 00:07:56,522
Neniu sekura trairejo.

171
00:07:56,522 --> 00:07:58,980
Tio signifas ke nenio estas
malsupren iu el tiuj branĉoj.

172
00:07:58,980 --> 00:08:02,532
Se mi volas komenci konstruaĵo
ion, mi volas forigi la pordego.

173
00:08:02,532 --> 00:08:04,490
Mi volas forigi la pordego
antaŭ numeron 1.

174
00:08:04,490 --> 00:08:05,698
Kaj mi volas promeni malsupren tio.

175
00:08:05,698 --> 00:08:08,060
Kaj mi volas konstrui
alia loko por mi iri.

176
00:08:08,060 --> 00:08:09,470
>> Kaj tio estas kion mi faris tie.

177
00:08:09,470 --> 00:08:11,430
Do 1 ne plu notas al nula.

178
00:08:11,430 --> 00:08:13,830
Mi jam diris ke estas sekure iri malsupren tien nun.

179
00:08:13,830 --> 00:08:15,789
Mi konstruis alia nodo.

180
00:08:15,789 --> 00:08:18,330
Kiam mi alvenas al tiu nodo, Mi
havas alian decidon fari.

181
00:08:18,330 --> 00:08:20,890
Kie mi tuj iros de tie ĉi?

182
00:08:20,890 --> 00:08:22,700
>> Nu, mi jam subiris la 1.

183
00:08:22,700 --> 00:08:24,470
Do nun mi probable volas iri malsupren la 6an.

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

185
00:08:24,970 --> 00:08:27,100
Denove, mi havas 10 lokojn mi povas elekti.

186
00:08:27,100 --> 00:08:30,060
Do ni nun iru malsupren numero 6.

187
00:08:30,060 --> 00:08:32,280
Do mi malbari la pordego
antaŭ numero 6.

188
00:08:32,280 --> 00:08:33,250
Kaj mi iras tien.

189
00:08:33,250 --> 00:08:34,580
Kaj Mi konstruos al alia nodo.

190
00:08:34,580 --> 00:08:37,630
Kaj mi atingis alian junton punkto.

191
00:08:37,630 --> 00:08:40,289
>> Denove, mi havas 10 elektoj
cxar kie mi povas iri.

192
00:08:40,289 --> 00:08:42,799
Mi kopiis de 1 ĝis 6.

193
00:08:42,799 --> 00:08:44,215
Do nun mi probable volas iri al 3.

194
00:08:44,215 --> 00:08:45,381
3, ekzistas nenie mi povas iri.

195
00:08:45,381 --> 00:08:48,980
Do mi devas liberigi la vojon
kaj konstruos al mi novan spacon.

196
00:08:48,980 --> 00:08:50,870
Kaj tiam de 3, kie mi volas iri?

197
00:08:50,870 --> 00:08:52,450
Mi volas iri malsupren 6.

198
00:08:52,450 --> 00:08:54,770
>> Kaj, denove, mi devis
liberigi la vojon por fari ĝin.

199
00:08:54,770 --> 00:08:59,179
Do nun mi uzis mian ŝlosilon enigi krei
nodoj kaj komenci konstrui ĉi trie.

200
00:08:59,179 --> 00:09:00,220
Mi komencis ĉe la radiko.

201
00:09:00,220 --> 00:09:03,666
Mi iris malsupren 1636.

202
00:09:03,666 --> 00:09:05,540
Kaj nun mi estas ĉe la fundo
tie en tiu nodo.

203
00:09:05,540 --> 00:09:06,610
Kaj vi eble povus
vidi ĝin sur via ekrano.

204
00:09:06,610 --> 00:09:07,735
>> Ĝi estas elstarigita en flava.

205
00:09:07,735 --> 00:09:10,020
Tie estas kie mi nuntempe estas.

206
00:09:10,020 --> 00:09:11,300
Mia ŝlosilo estas farita.

207
00:09:11,300 --> 00:09:13,030
Mi jam elĉerpita ĉiu pozicio en mia ŝlosilo.

208
00:09:13,030 --> 00:09:15,040
Do mi ne povas iri plu.

209
00:09:15,040 --> 00:09:17,720
Do en ĉi tiu punkto, ĉiuj mi
vere devas fari estas diri, OK.

210
00:09:17,720 --> 00:09:18,990
Estas ia ŝatas rigardanta
malsupren al la planko,

211
00:09:18,990 --> 00:09:21,115
se vi antaŭvidante
mem kiel tian vojon

212
00:09:21,115 --> 00:09:22,350
kun malsamaj rilatoj.

213
00:09:22,350 --> 00:09:25,800
Ia rigardante malsupren kaj ia
ŝprucigi pentranta Harvard surgrunde.

214
00:09:25,800 --> 00:09:26,800
Tio estas la nomo de tiu.

215
00:09:26,800 --> 00:09:28,300
Sciu ke estas kio estas ĉe tiu loko.

216
00:09:28,300 --> 00:09:31,870
Se ni komencas je la radiko kaj ni iru malsupren
1 kaj poste 6 kaj tiam 3 kaj poste 6

217
00:09:31,870 --> 00:09:32,780
kie ni estas?

218
00:09:32,780 --> 00:09:35,640
Nu, se ni rigardas malsupren
kaj ni vidos Harvard, tiam

219
00:09:35,640 --> 00:09:38,960
ni scias ke Harvard estis
fondita en 1636 surbaze de la maniero

220
00:09:38,960 --> 00:09:41,400
ni implementando ĉi datumstrukturo.

221
00:09:41,400 --> 00:09:43,177
Tiel estis espereble simpla.

222
00:09:43,177 --> 00:09:44,760
Ni tuj fari du pli inserciones.

223
00:09:44,760 --> 00:09:50,060
Kaj espereble tio helpos al
vidu ĉi farita dufoje pli.

224
00:09:50,060 --> 00:09:52,210
>> Nun, ni enŝovu alia universitato.

225
00:09:52,210 --> 00:09:54,630
Ni enigi Yale en ĉi trie.

226
00:09:54,630 --> 00:09:57,037
Yale fondiĝis en 1701.

227
00:09:57,037 --> 00:09:58,870
Do ni komencu ĉe la
radiko, kiel ni ĉiam faras.

228
00:09:58,870 --> 00:09:59,890
Kaj ni starigis al trairado montrilo.

229
00:09:59,890 --> 00:10:01,624
Ni tuj uzos tiun por movi tra.

230
00:10:01,624 --> 00:10:03,790
La unua afero ni volas
fari estas iri malsupren la 1 pado.

231
00:10:03,790 --> 00:10:05,830
Tio estas la unua cifero de nia ŝlosilo.

232
00:10:05,830 --> 00:10:08,420
Feliĉe, tamen, ni ne
devi fari ian laboron ĉi tempon.

233
00:10:08,420 --> 00:10:09,919
La 1 vojo jam estis malbarita.

234
00:10:09,919 --> 00:10:13,520
Mi malbaris lin antaŭe kiam mi
estis enmeto Harvard je 1636.

235
00:10:13,520 --> 00:10:18,090
Do mi povas sekure movi
malsupren 1 kaj simple iri tien.

236
00:10:18,090 --> 00:10:20,150
Se povas movi malsupren la 1.

237
00:10:20,150 --> 00:10:22,930
>> Nun, tamen, mi volas iri al 7.

238
00:10:22,930 --> 00:10:24,280
Mi malbaris la vojon ĉe 6.

239
00:10:24,280 --> 00:10:27,050
Mi scias mi povas sekure
procedi malsupren la 6an pado.

240
00:10:27,050 --> 00:10:29,220
Sed mi devas iri sur la 7 pado.

241
00:10:29,220 --> 00:10:30,580
Do kion mi devas fari?

242
00:10:30,580 --> 00:10:35,070
Nu, samkiel antaŭe, mi nur bezonas
malbari la pordego, liberigu la vojon,

243
00:10:35,070 --> 00:10:38,740
kaj konstruu novan nodon de la 7 pado.

244
00:10:38,740 --> 00:10:40,250
Ĝuste kiel ĉi.

245
00:10:40,250 --> 00:10:42,930
>> Do nun mi kopiis 1 kaj tiam 7.

246
00:10:42,930 --> 00:10:45,550
Kaj nun rimarkas, mi estas ia
de sur tiu nova subramal.

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

248
00:10:46,050 --> 00:10:49,260
Ĉio alia el 16
on, mi ne zorgas pri.

249
00:10:49,260 --> 00:10:50,720
Mi ne faras 16 nenion.

250
00:10:50,720 --> 00:10:51,750
Mi faras 17 stuff.

251
00:10:51,750 --> 00:10:58,380
>> Do nun el 17 sur, mi devas
ia Blaze novaj migrovojoj tie.

252
00:10:58,380 --> 00:11:00,462
La sekva cifero mia ŝlosilo estas 0.

253
00:11:00,462 --> 00:11:01,670
Mi klare ne povas ie.

254
00:11:01,670 --> 00:11:02,628
Mi nur konstruis ĉi nodo.

255
00:11:02,628 --> 00:11:04,550
Do mi scias ne estas
padojn antaŭen de tie.

256
00:11:04,550 --> 00:11:06,370
Do mi devas fari unu mem.

257
00:11:06,370 --> 00:11:09,360
>> Do mi malloc nova nodo
kaj havas 0 punkto tie.

258
00:11:09,360 --> 00:11:12,770
Kaj tiam unu pli tempon, mi malloc a
nova nodo kaj havas unu punkto.

259
00:11:12,770 --> 00:11:15,870
Denove, mi elĉerpis mian ŝlosilon, 1701.

260
00:11:15,870 --> 00:11:18,472
Do mi rigardas malsupren kaj mi spray pentras Yale.

261
00:11:18,472 --> 00:11:19,680
Tio estas la nomo de tiu nodo.

262
00:11:19,680 --> 00:11:24,660
>> Kaj tial nun, se mi iam bezonas vidi se Yale
Estas en ĉi trie, mi komencas je la radika,

263
00:11:24,660 --> 00:11:27,060
Mi iras malsupren 1701, kaj subrigardi.

264
00:11:27,060 --> 00:11:30,030
Kaj se mi vidas Yale spray
pentrita sur la tero, tiam

265
00:11:30,030 --> 00:11:32,200
Mi scias Yale ekzistas en ĉi trie.

266
00:11:32,200 --> 00:11:32,950
Ni faru pli.

267
00:11:32,950 --> 00:11:36,430
Ni enigi Dartmouth en tiun
trie, kiu estis fondita en 1769.

268
00:11:36,430 --> 00:11:37,750
>> Komencu ĉe la radiko denove.

269
00:11:37,750 --> 00:11:39,445
Mia unua cifero de mia ŝlosilo estas 1.

270
00:11:39,445 --> 00:11:40,820
Mi povas sekure movi malsupren ke vojo.

271
00:11:40,820 --> 00:11:42,400
Kiu jam ekzistas.

272
00:11:42,400 --> 00:11:44,040
La sekva cifero de mia ŝlosilo estas 7.

273
00:11:44,040 --> 00:11:45,890
Mi povas sekure movi malsupren ke vojo.

274
00:11:45,890 --> 00:11:47,540
Ekzistas ankaŭ.

275
00:11:47,540 --> 00:11:49,000
>> Mia sekvanta estas 6.

276
00:11:49,000 --> 00:11:52,860
De tie, de kie mi nuntempe estas
en flava tie en tiu meza nodo,

277
00:11:52,860 --> 00:11:56,060
6 estas nun ŝlosita for.

278
00:11:56,060 --> 00:11:58,830
Se mi volas iri malsupren tiu vojo,
Mi devas konstrui mem.

279
00:11:58,830 --> 00:12:02,250
Do mi malloc nova nodo
kaj havas 6 punkto tie.

280
00:12:02,250 --> 00:12:04,250
Kaj tiam, denove, mi estas
flamadanta novaj migrovojoj tie.

281
00:12:04,250 --> 00:12:10,750
>> Do mi malloc nova nodo tiel ke de
ke node-- padon nombro 9-- kaj tiam nun

282
00:12:10,750 --> 00:12:13,584
se mi vojaĝas 1769, kaj mi rigardas suben.

283
00:12:13,584 --> 00:12:15,500
Nenio aktuale
ŝprucigi pentris tie.

284
00:12:15,500 --> 00:12:16,930
Mi povas skribi Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Kaj mi insertita
Dartmouth en la trie.

286
00:12:20,710 --> 00:12:23,450
>> Do jen enmeto
aferojn en la trie.

287
00:12:23,450 --> 00:12:25,384
Nun ni volas serĉi aĵojn.

288
00:12:25,384 --> 00:12:27,050
Kiel ni serĉu por aĵoj en la trie?

289
00:12:27,050 --> 00:12:29,170
Nu, estas preskaux la sama ideo.

290
00:12:29,170 --> 00:12:33,620
Nun ni nur uzu la ciferojn de la klavon
al vidi se ni povas navigi de la radiko

291
00:12:33,620 --> 00:12:37,170
al kie volas iri en la trie.

292
00:12:37,170 --> 00:12:41,620
>> Se ni batis sakstrato ĉe ajna punkto, tiam
ni scias, ke tiu elemento ne ekzistas povas

293
00:12:41,620 --> 00:12:44,500
aŭ alia ke pado
jam estis malbarita.

294
00:12:44,500 --> 00:12:45,930
Se ni faras ĝin la tutan vojon al
Fine, ĉiuj ni devas fari

295
00:12:45,930 --> 00:12:48,471
estas malsupren rigardi kaj vidi se tio estas
la elemento ni serĉas.

296
00:12:48,471 --> 00:12:49,335
Se jes, sukceso.

297
00:12:49,335 --> 00:12:52,610
Se ĝi ne estas, malsukcesi.

298
00:12:52,610 --> 00:12:54,940
>> Do ni serĉi
Harvard en ĉi trie.

299
00:12:54,940 --> 00:12:56,020
Ni starti je la radiko.

300
00:12:56,020 --> 00:12:58,228
Kaj, denove, ni tuj
krei trairado montrilon

301
00:12:58,228 --> 00:12:59,390
fari nian movoj por ni.

302
00:12:59,390 --> 00:13:02,080
El la radiko ni scias ke la
Unue ni devas iri estas 1,

303
00:13:02,080 --> 00:13:03,390
ni faru tion?

304
00:13:03,390 --> 00:13:03,982
Jes ni povas.

305
00:13:03,982 --> 00:13:04,690
Se sekure ekzistas.

306
00:13:04,690 --> 00:13:06,660
Ni povas iri tie.

307
00:13:06,660 --> 00:13:08,440
>> Nun, la sekvanta loko ni devas iri estas 6.

308
00:13:08,440 --> 00:13:10,557
Ĉu la 6 padon ekzistas de ĉi tie?

309
00:13:10,557 --> 00:13:11,140
Jes, ĝi faras.

310
00:13:11,140 --> 00:13:12,690
Ni povas iri malsupren la 6an pado.

311
00:13:12,690 --> 00:13:13,905
Kaj ni finas tie.

312
00:13:13,905 --> 00:13:16,130
>> Ĉu ni povas iri malsupren la 3an padon de ĉi tie?

313
00:13:16,130 --> 00:13:18,450
Nu, kiel ĝi rezultas,
jes, ke ekzistas ankaŭ.

314
00:13:18,450 --> 00:13:20,790
Kaj ni povas akiri sur la 6 padon de ĉi tie?

315
00:13:20,790 --> 00:13:21,982
Jes ni povas.

316
00:13:21,982 --> 00:13:24,002
>> Ni ne tute respondis
la demandon ankoraŭ.

317
00:13:24,002 --> 00:13:25,710
Ekzistas ankoraŭ unu pli
paŝo, kio estas nun

318
00:13:25,710 --> 00:13:28,520
ni devas rigardi malsupren kaj
vidu se tio actually--

319
00:13:28,520 --> 00:13:32,660
se ni serĉas Harvard, estas ke
kion ni trovos post ni elĉerpas la klavo?

320
00:13:32,660 --> 00:13:35,430
En la ekzemplo ni uzas ĉi tie,
la jaroj estas ĉiam kvar ciferoj.

321
00:13:35,430 --> 00:13:40,280
Sed vi povus esti uzante la ekzemplon kie
vi amasigas vortaron de vortoj.

322
00:13:40,280 --> 00:13:44,060
>> Do anstataŭ havi 10 punteros
cxar mia loko, vi eble havas 26.

323
00:13:44,060 --> 00:13:46,040
Unu por ĉiu litero de la alfabeto.

324
00:13:46,040 --> 00:13:50,350
Kaj estas kelkaj vortoj kiel vesperton,
kiu estas subaro de aro, ekzemple.

325
00:13:50,350 --> 00:13:53,511
Kaj tiel eĉ se vi atingos la
fino de la ŝlosilo kaj vi ekrigardos

326
00:13:53,511 --> 00:13:55,260
vi eble ne vidos kion
vi serĉas.

327
00:13:55,260 --> 00:13:58,500
>> Do vi ĉiam devas _traverse_
la tutan vojon kaj tiam

328
00:13:58,500 --> 00:14:01,540
se vi estis sukcese povis
kruci la tutan vojon,

329
00:14:01,540 --> 00:14:03,440
subrigardi kaj fari unu finan konfirmon.

330
00:14:03,440 --> 00:14:05,120
Ĉu tio kion mi serĉas?

331
00:14:05,120 --> 00:14:07,740
Nu, mi rigardas malsupren post komencado
ĉe la supro kaj irante 1636.

332
00:14:07,740 --> 00:14:08,240
Mi rigardas malsupren.

333
00:14:08,240 --> 00:14:09,400
Mi vidas Harvard.

334
00:14:09,400 --> 00:14:11,689
Do, jes, mi sukcesis.

335
00:14:11,689 --> 00:14:13,980
Kio se kion mi serĉas
ne estas en la trie, kvankam.

336
00:14:13,980 --> 00:14:17,200
Kio se mi serĉas Princeton,
kiu estis fondita en 1746.

337
00:14:17,200 --> 00:14:20,875
Kaj do 1746 iĝas mian ŝlosilon
navigi tra la trie.

338
00:14:20,875 --> 00:14:22,040
Nu, mi komencas je la radika.

339
00:14:22,040 --> 00:14:24,760
Kaj la unua loko kiun mi volas
al iras malsupren la 1 pado.

340
00:14:24,760 --> 00:14:25,590
Ĉu mi povas fari ĝin?

341
00:14:25,590 --> 00:14:26,490
Jes mi povas.

342
00:14:26,490 --> 00:14:28,730
>> Ĉu mi povas iri malsupren la 7an vojon de tie?

343
00:14:28,730 --> 00:14:29,230
Jes, mi povas.

344
00:14:29,230 --> 00:14:30,750
Ke ekzistas tro.

345
00:14:30,750 --> 00:14:32,460
Sed mi povas iri malsupren la 4 vojo de tie ĉi?

346
00:14:32,460 --> 00:14:35,550
Tio estas kiel demandanta la demandon, ĉu
Mi procedi malsupren ke kvadrateto

347
00:14:35,550 --> 00:14:37,114
ke mi reliefigis en flava?

348
00:14:37,114 --> 00:14:38,030
Nenio tie.

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

350
00:14:38,610 --> 00:14:41,310
>> Ne estas maniero antaŭen malsupren la 4 pado.

351
00:14:41,310 --> 00:14:46,480
Se Princeton estis en ĉi trie, ke 4
estus malbarita por ni jam.

352
00:14:46,480 --> 00:14:49,130
Kaj tiel ĉe tiu punkto
ni atingis sakstraton.

353
00:14:49,130 --> 00:14:50,250
Ni ne povas iri plu.

354
00:14:50,250 --> 00:14:53,440
Kaj tial ni povas diri, definitive, ne.

355
00:14:53,440 --> 00:14:56,760
Princeton ne ekzistas en ĉi trie.

356
00:14:56,760 --> 00:14:58,860
>> Do kion signifas ĉi ĉiuj signifas?

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

358
00:14:59,360 --> 00:15:01,000
Estas multe okazas tie.

359
00:15:01,000 --> 00:15:02,500
Ekzistas indikoj tuta loko.

360
00:15:02,500 --> 00:15:04,249
Kaj, kiel vi povas vidi
nur de la figuro,

361
00:15:04,249 --> 00:15:07,010
ekzistas multe de nodoj kiuj
estas tiaj promenadoj ĉirkaŭ.

362
00:15:07,010 --> 00:15:13,480
Sed rimarki ĉiufoje ni volis
kontroli ĉu io en la trie,

363
00:15:13,480 --> 00:15:15,000
ni nur devis fari 4 movojn.

364
00:15:15,000 --> 00:15:17,208
>> Ĉiufoje ni volis
enmeti ion en la trie,

365
00:15:17,208 --> 00:15:20,440
ni devos fari 4 movojn, eventuale
mallocing iuj aĵoj survoje.

366
00:15:20,440 --> 00:15:23,482
Sed kiel ni vidis kiam ni insertita
Dartmouth en la trie,

367
00:15:23,482 --> 00:15:25,940
kelkfoje iuj de la vojo
jam povus esti malbarita por ni.

368
00:15:25,940 --> 00:15:30,520
Kaj tiel kiel nia trie akiras pli grandan kaj
pli granda, ni havas ion malgrandan laboron ĉiufoje

369
00:15:30,520 --> 00:15:32,270
enmeti novajn aferojn
ĉar ni jam

370
00:15:32,270 --> 00:15:35,746
konstruis multajn mezajn
branĉoj survoje.

371
00:15:35,746 --> 00:15:38,370
Se ni nur iam devas rigardi
4 aferoj, 4 estas nur konstanta.

372
00:15:38,370 --> 00:15:41,750
Ni vere estas speco de alproksimiĝanta
konstanta tempo inserción

373
00:15:41,750 --> 00:15:44,501
kaj konstantan tempo lookup.

374
00:15:44,501 --> 00:15:47,500
La tradeoff, kompreneble, estante tiu
ĉi trie, kiel vi versxajne povas diri,

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

376
00:15:49,030 --> 00:15:51,040
Ĉiu de ĉi tiuj nodoj
okupas multe da spaco.

377
00:15:51,040 --> 00:15:52,090
>> Sed tio estas la tradeoff.

378
00:15:52,090 --> 00:15:55,260
Se ni volas vere rapida
inserción, vere rapida forigo,

379
00:15:55,260 --> 00:15:59,630
kaj vere rapida lookup, ni devas
havas multajn datumojn fluganta ĉirkaŭe.

380
00:15:59,630 --> 00:16:03,590
Ni devas flankenmetis multajn spaco
kaj memoro por tiu datumstrukturo

381
00:16:03,590 --> 00:16:04,290
ekzisti.

382
00:16:04,290 --> 00:16:05,415
>> Kaj tiel tio estas la tradeoff.

383
00:16:05,415 --> 00:16:07,310
Sed ĝi aspektas kiel ni
eble trovis gxin.

384
00:16:07,310 --> 00:16:09,560
Ni eble trovis ke
sankta gralo de datumstrukturoj

385
00:16:09,560 --> 00:16:12,264
per rapidaj inserción,
forigo, kaj lookup.

386
00:16:12,264 --> 00:16:14,430
Kaj eble tiu estos
taŭga datumstrukturo

387
00:16:14,430 --> 00:16:18,890
uzi por kiaj informo
ni provas vendejo.

388
00:16:18,890 --> 00:16:21,860
Mi Doug Lloyd, tiu estas CS50.

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