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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Soms, wanneer die bou van 'n
program, kan jy wil gebruik om 'n

3
00:00:10,890 --> 00:00:13,190
data struktuur bekend as 'n woordeboek.

4
00:00:13,190 --> 00:00:17,960
'N Woordeboek kaarte sleutels, wat
gewoonlik snare, met waardes, ints,

5
00:00:17,960 --> 00:00:21,900
karakters, 'n verwysing na 'n voorwerp,
wat ons wil.

6
00:00:21,900 --> 00:00:26,510
Dit is net soos gewone woordeboeke
die kaart woorde deur definisies.

7
00:00:26,510 --> 00:00:29,440
>> Woordeboeke voorsien ons met die
vermoë om inligting te stoor

8
00:00:29,440 --> 00:00:32,750
verband hou met iets
en kyk dit later.

9
00:00:32,750 --> 00:00:36,620
So hoe ons eintlik implementeer nie 'n
woordeboek in, sê, C-kode wat ons kan

10
00:00:36,620 --> 00:00:38,460
gebruik in een van ons programme?

11
00:00:38,460 --> 00:00:41,790
Wel, daar is 'n baie maniere wat
Ons kan 'n woordeboek te implementeer.

12
00:00:41,790 --> 00:00:45,930
>> Vir een, kan ons 'n skikking te gebruik dat ons
dinamiese re-grootte of ons kan gebruik om 'n

13
00:00:45,930 --> 00:00:49,150
gekoppel lys hutstabel
of 'n binêre boom.

14
00:00:49,150 --> 00:00:52,250
Maar wat ons ook al kies, moet ons
wees bewus van die doeltreffendheid en

15
00:00:52,250 --> 00:00:54,300
prestasie van die implementering.

16
00:00:54,300 --> 00:00:57,930
Ons moet dink oor die algoritme gebruik
in te voeg en kyk op items in

17
00:00:57,930 --> 00:00:59,120
ons data struktuur.

18
00:00:59,120 --> 00:01:03,060
>> Vir nou, laat ons aanvaar dat ons
wil snare te gebruik as sleutels.

19
00:01:03,060 --> 00:01:07,290
Kom ons praat oor 'n moontlikheid,
'n data struktuur genaamd 'n Trie.

20
00:01:07,290 --> 00:01:11,210
So hier is 'n visuele voorstelling
van 'n Trie.

21
00:01:11,210 --> 00:01:14,590
>> As die prentjie stel, 'n tydstip waarop
is 'n boom data struktuur met

22
00:01:14,590 --> 00:01:16,050
nodes met mekaar verbind.

23
00:01:16,050 --> 00:01:19,420
Ons sien dat daar is duidelik 'n wortel
knoop met 'n paar skakels uit te brei na

24
00:01:19,420 --> 00:01:20,500
ander nodes.

25
00:01:20,500 --> 00:01:23,040
Maar wat beteken elke knoop bestaan ​​uit?

26
00:01:23,040 --> 00:01:26,700
As ons aanvaar dat ons stoor sleutels
met net letters en

27
00:01:26,700 --> 00:01:30,150
Ons gee nie om oor kapitalisasie,
hier is 'n definisie van 'n knoop wat

28
00:01:30,150 --> 00:01:31,100
sal voldoende wees.

29
00:01:31,100 --> 00:01:34,130
>> 'N voorwerp waarvan die tipe is struct
node bestaan ​​uit twee dele

30
00:01:34,130 --> 00:01:35,740
data en kinders genoem.

31
00:01:35,740 --> 00:01:39,200
Ons het die data deel gelaat as 'n opmerking
vervang word deur 'n komponent

32
00:01:39,200 --> 00:01:43,190
verklaring wanneer struct knoop is
opgeneem in 'n C program.

33
00:01:43,190 --> 00:01:47,040
Die data deel van 'n knoop kan wees om 'n
Boolese waarde aan te dui of

34
00:01:47,040 --> 00:01:51,160
nie die knoop verteenwoordig die voltooiing
van 'n woordeboek sleutel of dit kan wees om 'n

35
00:01:51,160 --> 00:01:54,240
string die definisie wat
van 'n woord in die woordeboek.

36
00:01:54,240 --> 00:01:58,870
>> Ons sal 'n smiley face gebruik om aan te dui
wanneer data teenwoordig is in 'n knoop.

37
00:01:58,870 --> 00:02:02,310
Daar is 26 elemente in ons
kinders skikking, een-indeks

38
00:02:02,310 --> 00:02:03,690
per alfabetletter begin.

39
00:02:03,690 --> 00:02:06,570
Ons sal die betekenis sien
van hierdie gou.

40
00:02:06,570 --> 00:02:10,759
>> Kom ons kry 'n nader kyk van die wortel node
in ons diagram, wat geen data

41
00:02:10,759 --> 00:02:14,740
verband hou met dit, soos aangedui deur die
afwesigheid van die smiley gesig in die

42
00:02:14,740 --> 00:02:16,110
data gedeelte.

43
00:02:16,110 --> 00:02:19,910
Die pyle wat strek van die dele van
die kinders skikking verteenwoordig nie-knoop

44
00:02:19,910 --> 00:02:21,640
verwysings na ander nodes.

45
00:02:21,640 --> 00:02:25,500
Byvoorbeeld, die pyl wat strek vanaf
die tweede element van kinders

46
00:02:25,500 --> 00:02:28,400
verteenwoordig die letter B
in 'n woordeboek sleutel.

47
00:02:28,400 --> 00:02:31,920
En in die groter diagram
ons benoem dit met 'n B.

48
00:02:31,920 --> 00:02:35,810
>> Let daarop dat in die groter diagram, wanneer ons
trek 'n verwysing na 'n ander knoop, dit

49
00:02:35,810 --> 00:02:39,100
maak nie saak waar die pylpunt
voldoen aan die ander knoop.

50
00:02:39,100 --> 00:02:43,850
Ons voorbeeld woordeboek Trie bevat
twee woorde, wat en zoom.

51
00:02:43,850 --> 00:02:47,040
Kom ons loop deur 'n voorbeeld van
kyk op data vir 'n sleutel.

52
00:02:47,040 --> 00:02:50,800
>> Gestel ons wil om te kyk die
ooreenstemmende waarde vir die sleutel bad.

53
00:02:50,800 --> 00:02:53,610
Ons sal begin om ons kyk op
aan die wortel node.

54
00:02:53,610 --> 00:02:57,870
Dan sal ons die eerste letter van ons neem
sleutel, B, en vind die ooreenstemmende

55
00:02:57,870 --> 00:03:00,020
plek in ons kinders skikking.

56
00:03:00,020 --> 00:03:04,490
Let daarop dat daar presies 26 plekke
in die skikking, een vir elke letter van

57
00:03:04,490 --> 00:03:05,330
die alfabet.

58
00:03:05,330 --> 00:03:08,800
En ons sal die kolle verteenwoordig die
letters van die alfabet in orde is.

59
00:03:08,800 --> 00:03:13,960
>> Ons sal kyk na die tweede indeks dan
indeks een, vir B. In die algemeen, as ons

60
00:03:13,960 --> 00:03:17,990
het 'n paar alfabetletter C ons
kon die ooreenstemmende plek bepaal

61
00:03:17,990 --> 00:03:21,520
in die kinders skikking gebruik
'n berekening soos hierdie.

62
00:03:21,520 --> 00:03:25,140
Ons kan 'n groter kinders gebruik het
verskeidenheid as ons wou kyk uit aan te bied

63
00:03:25,140 --> 00:03:28,380
sleutels met 'n groter verskeidenheid van die karakters,
soos die hele

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

65
00:03:29,880 --> 00:03:32,630
>> In hierdie geval, die wyser
in ons kinders opgestel by

66
00:03:32,630 --> 00:03:34,320
indeks een is nie null.

67
00:03:34,320 --> 00:03:36,600
So ons sal voortgaan om te kyk
die sleutel bad.

68
00:03:36,600 --> 00:03:40,130
As ons ooit 'n nul pointer teëgekom
op die regte plek in die kinders

69
00:03:40,130 --> 00:03:43,230
skikking terwyl ons deurkruis die nodes,
dan sal ons moet sê dat ons

70
00:03:43,230 --> 00:03:45,630
kon nie iets kry vir die sleutel.

71
00:03:45,630 --> 00:03:49,370
>> Nou, sal ons die tweede brief van neem
ons sleutel, A, en gaan voort om volgende

72
00:03:49,370 --> 00:03:52,400
wysers op hierdie manier, totdat ons
bereik die einde van ons sleutel.

73
00:03:52,400 --> 00:03:56,530
As ons die einde van die sleutel bereik sonder
slaan enige dood eindig, null wysers,

74
00:03:56,530 --> 00:03:59,730
soos in die geval hier nie, dan net ons
het een ding om te kyk.

75
00:03:59,730 --> 00:04:02,110
Is dit die sleutel eintlik
in die woordeboek?

76
00:04:02,110 --> 00:04:07,660
>> As dit so is, moet ons 'n waarde vind, goed 'n
smiley face ikoon in ons diagram waar

77
00:04:07,660 --> 00:04:08,750
die woord eindig.

78
00:04:08,750 --> 00:04:12,270
As daar is iets anders gestoor met
die data, dan kan ons dit terug.

79
00:04:12,270 --> 00:04:16,500
Byvoorbeeld, die sleutel dieretuin is nie in die
woordeboek, selfs al het ons kan hê

80
00:04:16,500 --> 00:04:19,810
aan die einde van hierdie sleutel sonder om ooit
slaan 'n nul pointer, terwyl ons

81
00:04:19,810 --> 00:04:21,089
Itereer deur die Trie.

82
00:04:21,089 --> 00:04:25,436
>> As ons probeer om op te kyk die sleutel bad, die
tweede laaste knoop se skikking indeks,

83
00:04:25,436 --> 00:04:28,750
ooreenstem met die letter H, sou
het gehou 'n nul wyser.

84
00:04:28,750 --> 00:04:31,120
So bad is nie in die woordeboek.

85
00:04:31,120 --> 00:04:34,800
En so 'n tydstip waarop is uniek in die sin dat die sleutels
nooit uitdruklik in gestoor

86
00:04:34,800 --> 00:04:36,650
die data struktuur.

87
00:04:36,650 --> 00:04:38,810
So hoe iets voeg ons
in 'n Trie?

88
00:04:38,810 --> 00:04:41,780
>> Kom ons plaas die sleutel
dieretuin in ons Trie.

89
00:04:41,780 --> 00:04:46,120
Onthou dat 'n smiley face op 'n knoop
kon ooreenstem in die kode op 'n eenvoudige

90
00:04:46,120 --> 00:04:50,170
Boolean waarde wat dieretuin aan te dui
is in die woordeboek of dit kan

91
00:04:50,170 --> 00:04:53,710
ooreenstem met meer inligting wat ons
wil assosieer met die sleutel dieretuin,

92
00:04:53,710 --> 00:04:56,860
soos die definisie van die
woord of iets anders.

93
00:04:56,860 --> 00:05:00,350
In sommige maniere, om die proses te voeg
iets in 'n Trie is soortgelyk aan

94
00:05:00,350 --> 00:05:02,060
soek iets in 'n Trie.

95
00:05:02,060 --> 00:05:05,720
>> Ons begin met die wortel node weer
volgende wenke wat ooreenstem met

96
00:05:05,720 --> 00:05:07,990
die letters van ons sleutel.

97
00:05:07,990 --> 00:05:11,310
Gelukkig het ons in staat was om riglyne te volg
al die pad totdat ons bereik

98
00:05:11,310 --> 00:05:12,770
die einde van die sleutel.

99
00:05:12,770 --> 00:05:16,480
Sedert dieretuin is 'n voorvoegsel van die woord
Klik op die, wat 'n lid van die

100
00:05:16,480 --> 00:05:19,440
woordeboek, het ons nie nodig het om te
ken enige nuwe nodes.

101
00:05:19,440 --> 00:05:23,140
>> Ons kan die knoop verander om aan te dui dat
die pad van die karakters wat lei tot

102
00:05:23,140 --> 00:05:25,360
dit verteenwoordig 'n belangrike in ons woordeboek.

103
00:05:25,360 --> 00:05:28,630
Nou, laat ons probeer om die plaas van die
sleutel BATH in die Trie.

104
00:05:28,630 --> 00:05:32,260
Ons begin by die wortel node
en volg aanwysings weer.

105
00:05:32,260 --> 00:05:35,620
Maar in hierdie situasie, ons 'n dooie getref
eindig voordat ons in staat is om te kry om die

106
00:05:35,620 --> 00:05:36,940
einde van die sleutel.

107
00:05:36,940 --> 00:05:40,980
Nou, moet ons 'n paar nuwe te ken
nodes sal moet een nuwe te ken

108
00:05:40,980 --> 00:05:43,660
knoop vir elke oorblywende
letter van die sleutel.

109
00:05:43,660 --> 00:05:46,740
>> In hierdie geval, ons moet net
een nuwe knoop toe te ken.

110
00:05:46,740 --> 00:05:50,590
Dan sal ons die H-indeks te maak
verwys hierdie nuwe knoop.

111
00:05:50,590 --> 00:05:54,070
Weereens, kan ons die knoop verander na
dui daarop dat die pad van die karakters

112
00:05:54,070 --> 00:05:57,120
wat lei tot dit 'n
sleutel in ons woordeboek.

113
00:05:57,120 --> 00:06:00,730
Kom ons redeneer oor die asimptotiese
kompleksiteit van ons prosedures vir hierdie

114
00:06:00,730 --> 00:06:02,110
twee operasies.

115
00:06:02,110 --> 00:06:06,420
>> Ons sien dat in beide gevalle die aantal
stappe ons algoritme geneem het, was

116
00:06:06,420 --> 00:06:09,470
eweredig aan die aantal
letters in die navraag.

117
00:06:09,470 --> 00:06:10,220
Dit is reg.

118
00:06:10,220 --> 00:06:13,470
As jy wil om te kyk op 'n woord in 'n
Trie jy hoef net te Itereer deur

119
00:06:13,470 --> 00:06:17,100
die letters een vir een totdat jy óf
bereik die einde van die woord of

120
00:06:17,100 --> 00:06:19,060
getref 'n doodloopstraat in die Trie.

121
00:06:19,060 --> 00:06:22,470
>> En as jy 'n sleutel in te voeg
waarde paar in 'n tydstip waarop die gebruik van die

122
00:06:22,470 --> 00:06:26,250
proses wat ons bespreek het, die ergste geval
sal jy die toekenning van 'n nuwe node

123
00:06:26,250 --> 00:06:27,550
vir elke brief.

124
00:06:27,550 --> 00:06:31,290
En ons sal daardie toewysing aanvaar
is 'n konstante werking.

125
00:06:31,290 --> 00:06:35,850
So as ons aanvaar dat die sleutel lengte
begrens deur 'n vaste konstante, beide

126
00:06:35,850 --> 00:06:39,400
inplanting en kyk konstant
tyd bedrywighede vir 'n Trie.

127
00:06:39,400 --> 00:06:42,930
>> As ons maak nie hierdie aanname dat
die sleutel lengte begrens deur 'n vaste

128
00:06:42,930 --> 00:06:46,650
konstante, dan inplanting en kyk,
In die ergste geval, is lineêr in die

129
00:06:46,650 --> 00:06:48,240
lengte van die sleutel.

130
00:06:48,240 --> 00:06:51,800
Let daarop dat die aantal items gestoor
in die Trie raak nie die blik op

131
00:06:51,800 --> 00:06:52,820
of voeg die tyd.

132
00:06:52,820 --> 00:06:55,360
Dit is net beïnvloed deur die
lengte van die sleutel.

133
00:06:55,360 --> 00:06:59,300
>> In teenstelling hiermee, voeg inskrywings aan, sê,
'n hutstabel geneig is om te maak

134
00:06:59,300 --> 00:07:01,250
toekoms kyk stadiger.

135
00:07:01,250 --> 00:07:04,520
Hoewel dit mag klink aantreklik op die eerste,
Ons moet in gedagte hou dat 'n

136
00:07:04,520 --> 00:07:08,740
gunstige asimptotiese kompleksiteit nie
beteken dat in die praktyk die data

137
00:07:08,740 --> 00:07:11,410
struktuur is noodwendig
bo verdenking.

138
00:07:11,410 --> 00:07:15,860
Ons moet ook in ag neem dat die stoor 'n
woord in 'n tydstip waarop ons nodig het, in die ergste

139
00:07:15,860 --> 00:07:19,700
geval, 'n aantal nodes proporsionele
die lengte van die woord self.

140
00:07:19,700 --> 00:07:21,880
>> Drieë is geneig om 'n baie ruimte om te gebruik.

141
00:07:21,880 --> 00:07:25,620
Dit is in teenstelling met 'n hash tafel,
waar ons moet net een nuwe node te

142
00:07:25,620 --> 00:07:27,940
slaan 'n paar belangrike waarde paar.

143
00:07:27,940 --> 00:07:31,370
Nou, weer in teorie, 'n groot ruimte
verbruik lyk nie soos 'n groot

144
00:07:31,370 --> 00:07:34,620
hanteer, veral gegewe dat die moderne
rekenaars GB en

145
00:07:34,620 --> 00:07:36,180
GB van die geheue.

146
00:07:36,180 --> 00:07:39,200
Maar dit blyk dat ons nog
bekommerd te wees oor die geheue gebruik en

147
00:07:39,200 --> 00:07:42,540
organisasie ter wille van die
prestasie, aangesien die moderne rekenaars

148
00:07:42,540 --> 00:07:46,960
meganismes in plek onder die
kap te bespoedig geheue toegang.

149
00:07:46,960 --> 00:07:51,180
>> Maar hierdie meganismes werk die beste wanneer
geheue besoeke is gemaak in kompakte

150
00:07:51,180 --> 00:07:52,810
streke of gebiede.

151
00:07:52,810 --> 00:07:55,910
En die knope van 'n Trie kon woon
enige plek in die hoop.

152
00:07:55,910 --> 00:07:58,390
Maar dit is trade-offs
dat ons moet in ag neem.

153
00:07:58,390 --> 00:08:01,440
>> Onthou dat, wanneer jy 'n data
struktuur vir 'n spesifieke taak, ons

154
00:08:01,440 --> 00:08:04,420
moet dink oor watter soort
bedrywighede die data struktuur moet

155
00:08:04,420 --> 00:08:07,140
ondersteuning en hoeveel van die prestasie
van elk van dié

156
00:08:07,140 --> 00:08:09,080
bedrywighede sake vir ons.

157
00:08:09,080 --> 00:08:11,300
Hierdie bedrywighede kan selfs
brei verder as net

158
00:08:11,300 --> 00:08:13,430
basiese voorkoms en inplanting.

159
00:08:13,430 --> 00:08:17,010
Gestel ons wil 'n soort te implementeer
van die motor-volledige funksie, baie

160
00:08:17,010 --> 00:08:18,890
soos Google soektog doen.

161
00:08:18,890 --> 00:08:22,210
Dit is, terug al die sleutels en
potensieel waardes wat

162
00:08:22,210 --> 00:08:24,130
'n gegewe voorvoegsel.

163
00:08:24,130 --> 00:08:27,050
>> 'N Trie is uniek nuttig
vir hierdie operasie.

164
00:08:27,050 --> 00:08:29,890
Dit is maklik om te Itereer deur
die tydstip waarop vir elke karakter

165
00:08:29,890 --> 00:08:30,950
die voorvoegsel.

166
00:08:30,950 --> 00:08:33,559
Net soos 'n kyk op die operasie,
ons wenke kan volg

167
00:08:33,559 --> 00:08:35,400
karakter deur karakter.

168
00:08:35,400 --> 00:08:38,659
Dan, wanneer ons by die einde van die
voorvoegsel, kan ons Itereer deur die

169
00:08:38,659 --> 00:08:42,049
oorblywende gedeelte van die data struktuur
aangesien enige van die sleutels buite

170
00:08:42,049 --> 00:08:43,980
hierdie punt het die prefix.

171
00:08:43,980 --> 00:08:47,670
>> Dit is ook maklik om hierdie lys te kry
in alfabetiese volgorde, aangesien die

172
00:08:47,670 --> 00:08:50,970
elemente van die kinders skikking
word alfabeties gerangskik nie.

173
00:08:50,970 --> 00:08:54,420
So hopelik sal jy dit oorweeg
gee probeer om 'n drie te druk.

174
00:08:54,420 --> 00:08:56,085
Ek is Kevin Schmid, en dit is CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ag, dit is die begin
van die afname.

177
00:09:00,790 --> 00:09:01,350
Ek is jammer.

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

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

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

181
00:09:03,130 --> 00:09:03,950
>> Staak vier.

182
00:09:03,950 --> 00:09:04,360
Ek is uit.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Jammer vir die maak van die persoon wat
te wysig hierdie gaan mal.

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

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

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

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

191
00:09:15,680 --> 00:09:16,280
>> Spreker 1: Wel gedaan.

192
00:09:16,280 --> 00:09:17,530
Dit is baie goed gedoen.

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