1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> Kevin Schmid: Kelkfoje, kiam la konstruado de
programon, eble vi volas uzi unu

3
00:00:10,890 --> 00:00:13,190
datumstrukturo konata kiel vortaro.

4
00:00:13,190 --> 00:00:17,960
A vortaro mapoj klavoj, kiuj estas
kutime kordoj, al valoroj, ints,

5
00:00:17,960 --> 00:00:21,900
signoj, puntero por iu celo,
kion ajn ni volas.

6
00:00:21,900 --> 00:00:26,510
Estas nur kiel ordinaraj vortaroj
ke mapo vortojn per difinoj.

7
00:00:26,510 --> 00:00:29,440
>> Vortaroj provizi nin per la
kapablon konservi informojn

8
00:00:29,440 --> 00:00:32,750
asociita kun iu
kaj rigardi ĝin poste.

9
00:00:32,750 --> 00:00:36,620
Do kiel fari ni reale efektivigi
vortaro en, ekzemple, C kodo kiun ni povas

10
00:00:36,620 --> 00:00:38,460
uzi en unu el niaj programoj?

11
00:00:38,460 --> 00:00:41,790
Nu, tie estas multaj vojoj kiujn
ni povus efektivigi vortaro.

12
00:00:41,790 --> 00:00:45,930
>> Por unu, ni povus uzi tabelo, ke ni
dinamike re-grandeco aŭ ni povus uzi

13
00:00:45,930 --> 00:00:49,150
ligillisto, hash tablo
aŭ duuma arbo.

14
00:00:49,150 --> 00:00:52,250
Sed kion ajn ni elektos, ni devus
ke vi memoru la efikeco kaj

15
00:00:52,250 --> 00:00:54,300
agado de la efektivigo.

16
00:00:54,300 --> 00:00:57,930
Ni devas pensi pri la algoritmo uzita
enmeti kaj rigardi supren erojn en

17
00:00:57,930 --> 00:00:59,120
nia datumstrukturo.

18
00:00:59,120 --> 00:01:03,060
>> Por nun, ni supozu, ke ni
volas uzi kordoj kiel ŝlosilojn.

19
00:01:03,060 --> 00:01:07,290
Ni parolu pri unu eblo,
datumstrukturo nomata trie.

20
00:01:07,290 --> 00:01:11,210
Do jen vida reprezento
de trie.

21
00:01:11,210 --> 00:01:14,590
>> Kiel la bildo sugestas, a trie
estas arbo datumstrukturo kun

22
00:01:14,590 --> 00:01:16,050
nodoj kunligitaj.

23
00:01:16,050 --> 00:01:19,420
Ni vidas, ke tie estas klare radiko
nodo kun kelkaj ligiloj plilongigante

24
00:01:19,420 --> 00:01:20,500
aliaj nodoj.

25
00:01:20,500 --> 00:01:23,040
Sed kion signifas ĉiu nodo konsistos?

26
00:01:23,040 --> 00:01:26,700
Se ni supozas ke ni stokante ŝlosilojn
kun nur alfabetaj signoj, kaj

27
00:01:26,700 --> 00:01:30,150
ni ne zorgas pri majuskloj,
jen difino de nodo ke

28
00:01:30,150 --> 00:01:31,100
sufiĉos.

29
00:01:31,100 --> 00:01:34,130
>> Objekto kies tipo estas struct
nodo havas du partojn

30
00:01:34,130 --> 00:01:35,740
vokis datumoj kaj infanoj.

31
00:01:35,740 --> 00:01:39,200
Ni forlasis la datumoj parto kiel komento
esti anstataŭita de komponanto

32
00:01:39,200 --> 00:01:43,190
deklaro kiam struct nodo estas
korpigis en C-programo.

33
00:01:43,190 --> 00:01:47,040
La datumoj parto de nodo povus esti
Bulea valoro por indiki ĉu aŭ

34
00:01:47,040 --> 00:01:51,160
ne la nodo reprezentas la finaĵon
de vortaro ŝlosilo aŭ povus esti

35
00:01:51,160 --> 00:01:54,240
kordo reprezentanta la difino
de iu vorto en la vortaro.

36
00:01:54,240 --> 00:01:58,870
>> Ni uzu smiley vizaĝon indiki
Kiam datumoj estas ĉeestanta en nodo.

37
00:01:58,870 --> 00:02:02,310
Estas 26 eroj en nia
infanoj tabelo, unu indekso

38
00:02:02,310 --> 00:02:03,690
po alfabeta karaktero.

39
00:02:03,690 --> 00:02:06,570
Ni vidos la signifon
de tiu baldaŭ.

40
00:02:06,570 --> 00:02:10,759
>> Ni ricevas pli proksima rigardo de la radika nodo
en la diagramo, kiu ne havas datumoj

41
00:02:10,759 --> 00:02:14,740
asociita kun ĝi, kiel indikita de la
foresto de la ridetanta vizaĝo en la

42
00:02:14,740 --> 00:02:16,110
datumoj porcion.

43
00:02:16,110 --> 00:02:19,910
La sagoj etendanta de la partoj de
la idoj tabelo reprezentas ne-nodon

44
00:02:19,910 --> 00:02:21,640
montriloj al aliaj nodoj.

45
00:02:21,640 --> 00:02:25,500
Ekzemple, la sago etendanta de
la dua elemento de infanoj

46
00:02:25,500 --> 00:02:28,400
reprezentas la litero B
en vortaro ŝlosilo.

47
00:02:28,400 --> 00:02:31,920
Kaj en la pli granda diagramo
ni marko ĝin per B.

48
00:02:31,920 --> 00:02:35,810
>> Notu ke en la granda figuro, kiam ni
desegni montrilon al alia vertico, ĝi

49
00:02:35,810 --> 00:02:39,100
Ne gravas, kie la Arrowhead
renkontas tiu alia nodo.

50
00:02:39,100 --> 00:02:43,850
Nia specimeno vortaro trie enhavas
du vortoj, kiuj kaj zoom.

51
00:02:43,850 --> 00:02:47,040
Ni marŝas tra ekzemplo de
suprenrigardinte datumoj por ŝlosilo.

52
00:02:47,040 --> 00:02:50,800
>> Supozi ni volis rigardi la
responda valoro por la klavo bano.

53
00:02:50,800 --> 00:02:53,610
Ni komencu nian rigardon supren
ĉe la radika nodo.

54
00:02:53,610 --> 00:02:57,870
Tiam ni prenos la unua litero de nia
klavo, B, kaj trovi la respondajn

55
00:02:57,870 --> 00:03:00,020
spot en niaj infanoj tabelo.

56
00:03:00,020 --> 00:03:04,490
Rimarku, ke estas precize 26 makuloj
en la tabelo, unu por ĉiu litero de

57
00:03:04,490 --> 00:03:05,330
la alfabeto.

58
00:03:05,330 --> 00:03:08,800
Kaj ni havos la makuloj reprezentas la
literojn de la alfabeto en ordo.

59
00:03:08,800 --> 00:03:13,960
>> Ni rigardu la duan indekso tiam,
indekso unu pro B. En ĝenerala, se ni

60
00:03:13,960 --> 00:03:17,990
havi iu alfabeta karaktero C ni
povis determini la responda loko

61
00:03:17,990 --> 00:03:21,520
en la infanoj tabelo uzante
kalkulo kiel ĉi tio.

62
00:03:21,520 --> 00:03:25,140
Ni povus esti uzata pli grandan infanoj
tabelo, se ni volas proponi rigardon supren de

63
00:03:25,140 --> 00:03:28,380
ŝlosilojn kun ampleksa gamo de karakteroj,
kiel en la tuta

64
00:03:28,380 --> 00:03:29,880
ASCII-signaro.

65
00:03:29,880 --> 00:03:32,630
>> En ĉi tiu kazo, la montrilo
en niaj infanoj tabelo cxe

66
00:03:32,630 --> 00:03:34,320
indekso oni ne estas nula.

67
00:03:34,320 --> 00:03:36,600
Do ni daŭre serĉas
ĝis la ŝlosilo bano.

68
00:03:36,600 --> 00:03:40,130
Se ni iam renkontis nula montrilo
ĉe la taŭgan lokon en la infanoj

69
00:03:40,130 --> 00:03:43,230
tabelo dum ni trairis la nodoj,
tiam ni devos diri ke ni

70
00:03:43,230 --> 00:03:45,630
ne povis trovi ion ajn por tiu klavo.

71
00:03:45,630 --> 00:03:49,370
>> Nu, ni prenu la duan leteron de
nia ŝlosilo, A, kaj daŭrigi jenaj

72
00:03:49,370 --> 00:03:52,400
montriloj en tiu vojo ĝis ni
atingi la finon de nia ŝlosilo.

73
00:03:52,400 --> 00:03:56,530
Se ni atingas la finon de la ŝlosilo sen
bati neniu mortinto pintojn, nula montriloj,

74
00:03:56,530 --> 00:03:59,730
kiel estas la kazo tie, do ni nur
devas kontroli alia afero.

75
00:03:59,730 --> 00:04:02,110
Ĉu ĉi tiu ŝlosilo reale
en la vortaro?

76
00:04:02,110 --> 00:04:07,660
>> Se jes, ni devus trovi valoron, puto
smiley vizaĝon piktogramon en nia diagramo kie

77
00:04:07,660 --> 00:04:08,750
la vorto finiĝas.

78
00:04:08,750 --> 00:04:12,270
Se estas io alia stokita per
la datumojn, tiam ni povas reveni al ĝi.

79
00:04:12,270 --> 00:04:16,500
Ekzemple, la ŝlosilo bestoĝardeno ne estas en la
vortaro, eĉ se ni povus havi

80
00:04:16,500 --> 00:04:19,810
atingis la finon de ĉi tiu ŝlosilo sen iam ajn
bati nula montrilon, dum ni

81
00:04:19,810 --> 00:04:21,089
persisti tra la trie.

82
00:04:21,089 --> 00:04:25,436
>> Se ni provis serĉi la ŝlosilon bano, la
dua ĝis lasta nodo tabelo indekso,

83
00:04:25,436 --> 00:04:28,750
responda al la literon H, estus
tenis nula montrilo.

84
00:04:28,750 --> 00:04:31,120
Do bano ne estas en la vortaro.

85
00:04:31,120 --> 00:04:34,800
Kaj tiel oni trie estas unika en kiuj la ŝlosilojn
neniam estas eksplicite stokitaj en

86
00:04:34,800 --> 00:04:36,650
la datumstrukturo.

87
00:04:36,650 --> 00:04:38,810
Do kiel fari ni enmetas ion
enen trie?

88
00:04:38,810 --> 00:04:41,780
>> Ni enmeti la ŝlosilon
zoo en nian trie.

89
00:04:41,780 --> 00:04:46,120
Memoru ke smiley vizagxon cxe nodon
povus respondi en kodon por simpla

90
00:04:46,120 --> 00:04:50,170
Bulea valoro por indiki ke bestoĝardeno
estas en la vortaro aŭ ĝi povis

91
00:04:50,170 --> 00:04:53,710
respondas al pli da informoj, ke ni
volas asocii kun la klavo zoo,

92
00:04:53,710 --> 00:04:56,860
same kiel la difino de la
vorto aŭ ion alian.

93
00:04:56,860 --> 00:05:00,350
En iuj manieroj, la procezo por enmeti
io en trie estas simila al

94
00:05:00,350 --> 00:05:02,060
suprenrigardinte io en trie.

95
00:05:02,060 --> 00:05:05,720
>> Ni komencu per la nodo radiko denove,
jenaj pointers responda al

96
00:05:05,720 --> 00:05:07,990
la leterojn de niaj ŝlosilo.

97
00:05:07,990 --> 00:05:11,310
Bonŝance, ni povis sekvi pointers
tuta vojo ĝis ni atingis

98
00:05:11,310 --> 00:05:12,770
la finon de la ŝlosilo.

99
00:05:12,770 --> 00:05:16,480
Ekde bestoĝardeno estas prefikso de la vorto
zomo, kiu estas membro de la

100
00:05:16,480 --> 00:05:19,440
vortaro, oni ne bezonas
atribui al si novajn nodojn.

101
00:05:19,440 --> 00:05:23,140
>> Ni povas modifi la nodo por indiki ke
la vojo de la karakteroj kondukante al

102
00:05:23,140 --> 00:05:25,360
ĝi reprezentas klavo en nia vortaro.

103
00:05:25,360 --> 00:05:28,630
Nun, ni provu la enmeto de la
ŝlosilo bano en la trie.

104
00:05:28,630 --> 00:05:32,260
Ni komencos je la radika nodo
kaj sekvi pointers denove.

105
00:05:32,260 --> 00:05:35,620
Sed en ĉi tiu situacio, ni trafis morta
fini antaux ni povis atingi la

106
00:05:35,620 --> 00:05:36,940
fino de la ŝlosilo.

107
00:05:36,940 --> 00:05:40,980
Nun, ni bezonos por atribui iun novan
nodojn bezonos atribui unu nova

108
00:05:40,980 --> 00:05:43,660
nodo por ĉiu restanta
letero de nia ŝlosilo.

109
00:05:43,660 --> 00:05:46,740
>> En ĉi tiu kazo, ni nur bezonas
atribui unu nova nodo.

110
00:05:46,740 --> 00:05:50,590
Tiam ni bezonos por fari la H indekso
referenci tiun ĉi novan nodon.

111
00:05:50,590 --> 00:05:54,070
Denove, ni povas modifi la nodo
indikas ke la vojo de la karakteroj

112
00:05:54,070 --> 00:05:57,120
kondukante al ĝi reprezentas
klavo en nia vortaro.

113
00:05:57,120 --> 00:06:00,730
Ni rezoni pri la asimptota
komplekseco de niaj proceduroj por tiuj

114
00:06:00,730 --> 00:06:02,110
du operacioj.

115
00:06:02,110 --> 00:06:06,420
>> Ni rimarkas, ke en ambaŭ kazoj la nombro
de paŝas nia algoritmo prenis estis

116
00:06:06,420 --> 00:06:09,470
proporcie kun la nombro de
literojn en la ŝlosilvorto.

117
00:06:09,470 --> 00:06:10,220
Tio estas prava.

118
00:06:10,220 --> 00:06:13,470
Kiam vi volas rigardi supren vorto en
trie, vi nur devas persisti tra

119
00:06:13,470 --> 00:06:17,100
la literojn unu post alia, ĝis vi ĉu
atingi la finon de la vorto aŭ

120
00:06:17,100 --> 00:06:19,060
batis senelirejo en la trie.

121
00:06:19,060 --> 00:06:22,470
>> Kaj kiam vi volas enmeti ŝlosilon
valoro paro en trie uzante la

122
00:06:22,470 --> 00:06:26,250
proceduro ni diskutis, la plej malbona kazo
havos vi atribuante nova nodo

123
00:06:26,250 --> 00:06:27,550
por ĉiu litero.

124
00:06:27,550 --> 00:06:31,290
Kaj ni vidos supozi ke atribuo
Estas konstanta tempo operacio.

125
00:06:31,290 --> 00:06:35,850
Do, se ni supozas ke la ŝlosila longo estas
barita per fiksita konstanto, ambaŭ

126
00:06:35,850 --> 00:06:39,400
inserción kaj rigardi supren estas konstanta
tempo operacioj por trie.

127
00:06:39,400 --> 00:06:42,930
>> Se ni ne faras ĉi supozo ke
la ŝlosilo longeco estas barita per fiksa

128
00:06:42,930 --> 00:06:46,650
konstanta, do Insertion kaj rigardi supren,
en la plej malbona kazo, estas lineara en la

129
00:06:46,650 --> 00:06:48,240
longeco de la ŝlosilo.

130
00:06:48,240 --> 00:06:51,800
Rimarku ke la nombro de eroj stokitaj
en la trie ne tuŝas la rigardon supren

131
00:06:51,800 --> 00:06:52,820
aŭ inserción tempo.

132
00:06:52,820 --> 00:06:55,360
Ĝi estas nur efikis per la
longeco de la ŝlosilo.

133
00:06:55,360 --> 00:06:59,300
>> Kontraste, aldonante Aktualaĵoj al, ni diru,
kradon tablo inklinas fari

134
00:06:59,300 --> 00:07:01,250
estonteco rigardi supren malrapida.

135
00:07:01,250 --> 00:07:04,520
Dum tio povas soni apelacianta al la komenco,
ni devas memori tion, ke oni

136
00:07:04,520 --> 00:07:08,740
favoraj asimptota komplekseco ne
signifas, ke en la praktiko la datumoj

137
00:07:08,740 --> 00:07:11,410
strukturo estas bezone
preter riproĉo.

138
00:07:11,410 --> 00:07:15,860
Ni devas ankaŭ konsideri ke stoki
vorto en trie ni bezonas, en la plej malbona

139
00:07:15,860 --> 00:07:19,700
kazo, nombro de nodoj proporcia
al la longeco de la vorto mem.

140
00:07:19,700 --> 00:07:21,880
>> Tries emas uzi multe da spaco.

141
00:07:21,880 --> 00:07:25,620
Tio estas en kontrasto al hash tablo
kie oni nur bezonas unu nova nodo

142
00:07:25,620 --> 00:07:27,940
stoki iuj ŝlosilaj valoro paron.

143
00:07:27,940 --> 00:07:31,370
Nun, denove en teorio, granda spaco
konsumado ne ŝajnas kiel granda

144
00:07:31,370 --> 00:07:34,620
trakti, precipe pro tio ke la moderna
komputiloj havas gigabajtoj kaj

145
00:07:34,620 --> 00:07:36,180
gigabajtoj da memoro.

146
00:07:36,180 --> 00:07:39,200
Sed tio rezultas ke ni ankoraŭ havas
maltrankviligi memoro uzado kaj

147
00:07:39,200 --> 00:07:42,540
organizon por la bono de
agado, ekde modernaj komputiloj

148
00:07:42,540 --> 00:07:46,960
havi mekanismojn en loko sub la
kapuĉo rapidigi memoro aliron.

149
00:07:46,960 --> 00:07:51,180
>> Sed tiuj ĉi mekanismoj funkcias plej bone kiam
memoro aliroj estas faritaj en kompakta

150
00:07:51,180 --> 00:07:52,810
regionoj aŭ zonoj.

151
00:07:52,810 --> 00:07:55,910
Kaj la nodoj de trie povus loĝi
ie ajn en tiu amaso.

152
00:07:55,910 --> 00:07:58,390
Sed jen estas la komerco maldungitaj
ke ni devas konsideri.

153
00:07:58,390 --> 00:08:01,440
>> Memoru ke, elektinte datumoj
strukturon por certa tasko, ni

154
00:08:01,440 --> 00:08:04,420
devas pensi pri kio specoj de
operacioj la datumstrukturo bezonu

155
00:08:04,420 --> 00:08:07,140
apogon kaj kiom la agado
de ĉiu el tiuj

156
00:08:07,140 --> 00:08:09,080
operacioj aferojn al ni.

157
00:08:09,080 --> 00:08:11,300
Ĉi tiuj operacioj povas eĉ
etendi preter nur

158
00:08:11,300 --> 00:08:13,430
bazaj rigardon supren kaj inserción.

159
00:08:13,430 --> 00:08:17,010
Supozi ni volis efektivigi ian
de auto-kompletaj funkcioj, multe

160
00:08:17,010 --> 00:08:18,890
kiel Google serĉilon faras.

161
00:08:18,890 --> 00:08:22,210
Tio estas, revenu ĉiuj klavoj kaj
potenciale valoroj kiujn

162
00:08:22,210 --> 00:08:24,130
havi donita prefikson.

163
00:08:24,130 --> 00:08:27,050
>> A trie estas unike utilan
por tiu ĉi operacio.

164
00:08:27,050 --> 00:08:29,890
Ĝi estas simpla al persisti tra
la trie por ĉiu karaktero de

165
00:08:29,890 --> 00:08:30,950
la prefikso.

166
00:08:30,950 --> 00:08:33,559
Ĝuste kiel aspektas supren operacio,
ni povis sekvi pointers

167
00:08:33,559 --> 00:08:35,400
karaktero de karaktero.

168
00:08:35,400 --> 00:08:38,659
Tiam, kiam ni alvenos al la fino de la
prefikso, ni povus persisti tra la

169
00:08:38,659 --> 00:08:42,049
cetera parto de la datumstrukturo
ĉar neniu el la klavoj trans

170
00:08:42,049 --> 00:08:43,980
ĉi punkton havas la prefikson.

171
00:08:43,980 --> 00:08:47,670
>> Ĝi estas ankaŭ facila por akiri ĉi tiun liston
en alfabeta ordo ekde la

172
00:08:47,670 --> 00:08:50,970
elementoj de la infanoj tabelo
estas ordigita alfabete.

173
00:08:50,970 --> 00:08:54,420
Do espereble vi devos konsideri
almozo provas provi.

174
00:08:54,420 --> 00:08:56,085
Mi estas Kevin Schmid, kaj ĉi tiu estas CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ha, ĉi tiu estas la komenco
de la dekadenco.

177
00:09:00,790 --> 00:09:01,350
Mi bedaŭras.

178
00:09:01,350 --> 00:09:01,870
Pardonon.

179
00:09:01,870 --> 00:09:02,480
Pardonon.

180
00:09:02,480 --> 00:09:03,130
Pardonon.

181
00:09:03,130 --> 00:09:03,950
>> Frapu kvar.

182
00:09:03,950 --> 00:09:04,360
Mi estas ekstere.

183
00:09:04,360 --> 00:09:05,280
Pardonon.

184
00:09:05,280 --> 00:09:06,500
Pardonon.

185
00:09:06,500 --> 00:09:07,490
Pardonon.

186
00:09:07,490 --> 00:09:12,352
Pardonu por fari la persono kiu
havas redakti ĉi freneziĝos.

187
00:09:12,352 --> 00:09:13,280
>> Pardonon.

188
00:09:13,280 --> 00:09:13,880
Pardonon.

189
00:09:13,880 --> 00:09:15,080
Pardonon.

190
00:09:15,080 --> 00:09:15,680
Pardonon.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Bonege.

192
00:09:16,280 --> 00:09:17,530
Tio estis vere bone farita.

193
00:09:17,530 --> 00:09:18,430