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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Noen ganger, når du bygger en
program, kan det være lurt å bruke en

3
00:00:10,890 --> 00:00:13,190
datastruktur som kalles en ordbok.

4
00:00:13,190 --> 00:00:17,960
En ordbok kart nøkler, som er
vanligvis strenger, til verdier, ints,

5
00:00:17,960 --> 00:00:21,900
tegn, en peker til et objekt,
hva vi ønsker.

6
00:00:21,900 --> 00:00:26,510
Det er akkurat som vanlige ordbøker
som kart ord gjennom definisjoner.

7
00:00:26,510 --> 00:00:29,440
>> Ordbøker gi oss den
Muligheten til å lagre informasjon

8
00:00:29,440 --> 00:00:32,750
assosiert med noe
og slå det opp senere.

9
00:00:32,750 --> 00:00:36,620
Så hvordan skal vi faktisk gjennomføre en
ordbok i for eksempel C-kode som vi kan

10
00:00:36,620 --> 00:00:38,460
bruke i et av våre programmer?

11
00:00:38,460 --> 00:00:41,790
Vel, det er mange måter som
vi kunne implementere en ordbok.

12
00:00:41,790 --> 00:00:45,930
>> For én, kan vi bruke en matrise som vi
dynamisk re-størrelse eller vi kunne bruke en

13
00:00:45,930 --> 00:00:49,150
lenket liste, hash table
eller et binært tre.

14
00:00:49,150 --> 00:00:52,250
Men uansett hva vi velger, bør vi
være oppmerksom på effektivitet og

15
00:00:52,250 --> 00:00:54,300
utførelse av gjennomføringen.

16
00:00:54,300 --> 00:00:57,930
Vi bør tenke på algoritmen som brukes
å sette inn og se opp elementer inn

17
00:00:57,930 --> 00:00:59,120
vår datastruktur.

18
00:00:59,120 --> 00:01:03,060
>> For nå, la oss anta at vi
ønsker å bruke strenger som nøkler.

19
00:01:03,060 --> 00:01:07,290
La oss snakke om én mulighet,
en datastruktur som kalles en trie.

20
00:01:07,290 --> 00:01:11,210
Så her er en visuell representasjon
av en trie.

21
00:01:11,210 --> 00:01:14,590
>> Som bildet antyder, en trie
er et tre datastruktur med

22
00:01:14,590 --> 00:01:16,050
noder koblet sammen.

23
00:01:16,050 --> 00:01:19,420
Vi ser at det er helt klart en rot
node med noen linker som strekker seg til

24
00:01:19,420 --> 00:01:20,500
andre noder.

25
00:01:20,500 --> 00:01:23,040
Men hva betyr hver node består av?

26
00:01:23,040 --> 00:01:26,700
Hvis vi antar at vi lagrer nøkler
med bare alfabetiske tegn, og

27
00:01:26,700 --> 00:01:30,150
vi bryr oss ikke om kapitalisering,
her er en definisjon av en node som

28
00:01:30,150 --> 00:01:31,100
vil være nok.

29
00:01:31,100 --> 00:01:34,130
>> Et objekt som type er struct
node har to deler

30
00:01:34,130 --> 00:01:35,740
kalt data og barn.

31
00:01:35,740 --> 00:01:39,200
Vi har forlatt data del som en kommentar
for å bli erstattet av en-komponent

32
00:01:39,200 --> 00:01:43,190
erklæring når struct node er
innarbeidet i en C-program.

33
00:01:43,190 --> 00:01:47,040
Dataene del av en node kan være en
Boolsk verdi for å indikere hvorvidt

34
00:01:47,040 --> 00:01:51,160
ikke noden betegner fullføringen
av en ordbok nøkkel eller det kan være en

35
00:01:51,160 --> 00:01:54,240
streng som representerer definisjonen
av et ord i ordlisten.

36
00:01:54,240 --> 00:01:58,870
>> Vi vil bruke en smiley face å indikere
når data er tilstede i en node.

37
00:01:58,870 --> 00:02:02,310
Det er 26 elementer i vår
barn array, en indeks

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

39
00:02:03,690 --> 00:02:06,570
Vi får se betydningen
av dette snart.

40
00:02:06,570 --> 00:02:10,759
>> La oss ta en nærmere titt på rotnoden
i vårt diagram, som ikke har noen data

41
00:02:10,759 --> 00:02:14,740
forbundet med den, som antydet med den
fravær av smilefjes i

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

43
00:02:16,110 --> 00:02:19,910
De piler som strekker seg fra de delene av
barna matrise representerer ikke-node

44
00:02:19,910 --> 00:02:21,640
pekere til andre noder.

45
00:02:21,640 --> 00:02:25,500
For eksempel, med pilen som strekker seg fra
det andre elementet i barn

46
00:02:25,500 --> 00:02:28,400
representerer bokstaven B
i en ordbok nøkkel.

47
00:02:28,400 --> 00:02:31,920
Og i større diagram
vi merke det med en B.

48
00:02:31,920 --> 00:02:35,810
>> Legg merke til at i den større diagrammet, når vi
tegner en peker til en annen node, det

49
00:02:35,810 --> 00:02:39,100
spiller ingen rolle hvor pilspissen
møter den andre noden.

50
00:02:39,100 --> 00:02:43,850
Vår eksempel ordbok trie inneholder
to ord, som og zoom.

51
00:02:43,850 --> 00:02:47,040
La oss gå gjennom et eksempel på
leter opp data for en nøkkel.

52
00:02:47,040 --> 00:02:50,800
>> Anta at vi ønsket å slå opp
Tilsvarende verdi for nøkkel-bad.

53
00:02:50,800 --> 00:02:53,610
Vi begynner vår titt opp
ved roten node.

54
00:02:53,610 --> 00:02:57,870
Så får vi ta den første bokstaven i vår
nøkkel, B, og finne tilsvarende

55
00:02:57,870 --> 00:03:00,020
få øye på i vår barn array.

56
00:03:00,020 --> 00:03:04,490
Legg merke til at det er nøyaktig 26 spots
i matrisen, ett for hver bokstav i

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

58
00:03:05,330 --> 00:03:08,800
Og vi vil ha flekkene representerer
bokstavene i alfabetet i rekkefølge.

59
00:03:08,800 --> 00:03:13,960
>> Vi skal se på den andre indeksen da,
index en, for B. Generelt, hvis vi

60
00:03:13,960 --> 00:03:17,990
har noen bokstav C vi
kunne finne den tilsvarende sted

61
00:03:17,990 --> 00:03:21,520
i barn array ved hjelp
en beregning som dette.

62
00:03:21,520 --> 00:03:25,140
Vi kunne ha brukt større barn
matrise hvis vi ønsket å tilby titt opp av

63
00:03:25,140 --> 00:03:28,380
taster med et bredere spekter av karakterer,
for eksempel hele

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

65
00:03:29,880 --> 00:03:32,630
>> I dette tilfelle pekeren
i våre barn matrise på

66
00:03:32,630 --> 00:03:34,320
index man ikke er null.

67
00:03:34,320 --> 00:03:36,600
Så vi vil fortsette å se
opp nøkkelen bad.

68
00:03:36,600 --> 00:03:40,130
Hvis vi noen gang støtt på en nullpeker
på riktig sted i barna

69
00:03:40,130 --> 00:03:43,230
matrise mens vi krysset nodene,
Da må vi si at vi

70
00:03:43,230 --> 00:03:45,630
kunne ikke finne noe for den tasten.

71
00:03:45,630 --> 00:03:49,370
>> Nå vil vi ta den andre bokstaven i
vår nøkkel, A, og fortsett med å følge

72
00:03:49,370 --> 00:03:52,400
pekere på denne måten før vi
kommer til slutten av våre viktigste.

73
00:03:52,400 --> 00:03:56,530
Hvis vi nå enden av nøkkelen uten
treffe noen blindveier, null pekere,

74
00:03:56,530 --> 00:03:59,730
som tilfellet er her, da bare vi
må sjekke en ting til.

75
00:03:59,730 --> 00:04:02,110
Er dette nøkkelen faktisk
i ordlisten?

76
00:04:02,110 --> 00:04:07,660
>> I så fall bør vi finne en verdi, vel en
smilefjes-ikonet i vår diagrammet der

77
00:04:07,660 --> 00:04:08,750
ordet ender.

78
00:04:08,750 --> 00:04:12,270
Hvis det er noe annet som er lagret med
dataene, så vi kan returnere den.

79
00:04:12,270 --> 00:04:16,500
For eksempel, er nøkkelen zoo ikke i
ordbok, selv om vi kunne ha

80
00:04:16,500 --> 00:04:19,810
nådd slutten av denne nøkkelen uten noensinne
treffer en nullpeker, mens vi

81
00:04:19,810 --> 00:04:21,089
iterere gjennom trie.

82
00:04:21,089 --> 00:04:25,436
>> Hvis vi prøvde å slå opp nøkkelen bad,
nest siste node fylking indeks,

83
00:04:25,436 --> 00:04:28,750
svarende til bokstaven H, ville
har hatt en nullpeker.

84
00:04:28,750 --> 00:04:31,120
Så bad er ikke i ordboken.

85
00:04:31,120 --> 00:04:34,800
Og så en trie er unik i at nøklene
aldri er eksplisitt lagret

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

87
00:04:36,650 --> 00:04:38,810
Så hvordan setter vi gjør noe
inn en trie?

88
00:04:38,810 --> 00:04:41,780
>> La oss sette inn nøkkelen
dyrehage i vår trie.

89
00:04:41,780 --> 00:04:46,120
Husk at et smilefjes på en node
kan tilsvare i koden for en enkel

90
00:04:46,120 --> 00:04:50,170
Boolsk verdi for å indikere at zoo
er i ordlisten, eller det kunne

91
00:04:50,170 --> 00:04:53,710
tilsvare mer informasjon som vi
ønsker å assosiere med nøkkelen zoo,

92
00:04:53,710 --> 00:04:56,860
som definisjonen av
ord eller noe annet.

93
00:04:56,860 --> 00:05:00,350
På en måte, til prosessen sette
noe inn en trie ligner

94
00:05:00,350 --> 00:05:02,060
ser opp noe i en trie.

95
00:05:02,060 --> 00:05:05,720
>> Vi begynner med rotnoden igjen,
følgende tips som tilsvarer

96
00:05:05,720 --> 00:05:07,990
bokstavene i vår nøkkel.

97
00:05:07,990 --> 00:05:11,310
Heldigvis var vi i stand til å følge pekere
helt til vi nådde

98
00:05:11,310 --> 00:05:12,770
slutten av nøkkelen.

99
00:05:12,770 --> 00:05:16,480
Siden dyrehagen er et prefiks av ordet
zoom, som er medlem av

100
00:05:16,480 --> 00:05:19,440
ordbok, trenger vi ikke å
tildele eventuelle nye noder.

101
00:05:19,440 --> 00:05:23,140
>> Vi kan modifisere knutepunktet for å indikere at
banen for tegnene som fører til

102
00:05:23,140 --> 00:05:25,360
det representerer en nøkkel i vår ordbok.

103
00:05:25,360 --> 00:05:28,630
Nå, la oss prøve å sette inn
Nøkkelen BATH inn i trie.

104
00:05:28,630 --> 00:05:32,260
Vi begynner ved roten noden
og følg pekere igjen.

105
00:05:32,260 --> 00:05:35,620
Men i denne situasjonen, vi traff en død
slutt før vi er i stand til å komme til

106
00:05:35,620 --> 00:05:36,940
slutten av nøkkelen.

107
00:05:36,940 --> 00:05:40,980
Nå må vi fordele litt nytt
noder må tildele en ny

108
00:05:40,980 --> 00:05:43,660
node for hver gjenværende
brev av våre viktigste.

109
00:05:43,660 --> 00:05:46,740
>> I dette tilfelle vi bare trenger
å tildele en ny node.

110
00:05:46,740 --> 00:05:50,590
Da må vi gjøre H-indeksen
referere til denne nye noden.

111
00:05:50,590 --> 00:05:54,070
Nok en gang, kan vi endre node til
indikerer at banen tegn

112
00:05:54,070 --> 00:05:57,120
fører til det representerer en
nøkkel i vår ordbok.

113
00:05:57,120 --> 00:06:00,730
La oss resonnere om den asymptotiske
kompleksiteten i våre prosedyrer for disse

114
00:06:00,730 --> 00:06:02,110
to operasjoner.

115
00:06:02,110 --> 00:06:06,420
>> Vi legger merke til at i begge tilfeller antallet
av trinn vår algoritme tok ble

116
00:06:06,420 --> 00:06:09,470
proporsjonal med antallet
bokstaver i søkeordet.

117
00:06:09,470 --> 00:06:10,220
Det er riktig.

118
00:06:10,220 --> 00:06:13,470
Når du ønsker å slå opp et ord i en
trie du trenger bare å reagere gjennom

119
00:06:13,470 --> 00:06:17,100
bokstavene en etter en til du enten
kommer til slutten av ordet eller

120
00:06:17,100 --> 00:06:19,060
traff en blindvei i trie.

121
00:06:19,060 --> 00:06:22,470
>> Og når du ønsker å sette inn en nøkkel
verdi-par i en trie bruker

122
00:06:22,470 --> 00:06:26,250
prosedyren vi diskuterte, verste fall
vil ha deg tildeling av en ny node

123
00:06:26,250 --> 00:06:27,550
for hver bokstav.

124
00:06:27,550 --> 00:06:31,290
Og vi vil anta at tildeling
er en konstant tidsoperasjon.

125
00:06:31,290 --> 00:06:35,850
Så hvis vi antar at nøkkellengden er
som er avgrenset av en fast konstant, både

126
00:06:35,850 --> 00:06:39,400
innsetting og ser opp er konstant
gang operasjoner for en trie.

127
00:06:39,400 --> 00:06:42,930
>> Hvis vi ikke gjør denne antakelsen at
nøkkellengden er avgrenset av en fast

128
00:06:42,930 --> 00:06:46,650
konstant, så innsetting og ser opp,
i verste fall, blir lineær i

129
00:06:46,650 --> 00:06:48,240
Lengden av nøkkelen.

130
00:06:48,240 --> 00:06:51,800
Legg merke til at antall elementer som er lagret
i trie påvirker ikke utseendet opp

131
00:06:51,800 --> 00:06:52,820
eller innsetting tid.

132
00:06:52,820 --> 00:06:55,360
Det er bare påvirket av den
Lengden av nøkkelen.

133
00:06:55,360 --> 00:06:59,300
>> Som kontrast, legge til oppføringer til, si,
en hash table tendens til å gjøre

134
00:06:59,300 --> 00:07:01,250
fremtiden ser opp saktere.

135
00:07:01,250 --> 00:07:04,520
Selv om dette kan høres tiltalende i starten,
Vi bør huske på at en

136
00:07:04,520 --> 00:07:08,740
gunstig asymptotiske kompleksitet gjør ikke
betyr i praksis at dataene

137
00:07:08,740 --> 00:07:11,410
Strukturen er nødvendigvis
hinsides kritikk.

138
00:07:11,410 --> 00:07:15,860
Vi må også tenke på at for å lagre en
ord i en trie vi trenger, i verste

139
00:07:15,860 --> 00:07:19,700
tilfelle, et antall noder proporsjonal
til lengden av selve ordet.

140
00:07:19,700 --> 00:07:21,880
>> Prøver en tendens til å bruke mye plass.

141
00:07:21,880 --> 00:07:25,620
Det er i motsetning til en nøkkeltabell,
hvor vi trenger bare en ny node til

142
00:07:25,620 --> 00:07:27,940
lagre noen suse_register_auto.ycp.

143
00:07:27,940 --> 00:07:31,370
Nå, igjen i teorien, stor plass
forbruket ser ikke ut som en stor

144
00:07:31,370 --> 00:07:34,620
håndtere, særlig gitt at moderne
datamaskiner har gigabyte og

145
00:07:34,620 --> 00:07:36,180
gigabyte minne.

146
00:07:36,180 --> 00:07:39,200
Men det viser seg at vi fortsatt har
å bekymre deg for minnebruk og

147
00:07:39,200 --> 00:07:42,540
organisasjon for moro skyld
ytelse, siden moderne datamaskiner

148
00:07:42,540 --> 00:07:46,960
har mekanismer på plass under
hette for å øke hastigheten på minnetilgang.

149
00:07:46,960 --> 00:07:51,180
>> Men disse mekanismene fungerer best når
minneaksesser er laget i kompakt

150
00:07:51,180 --> 00:07:52,810
regioner eller områder.

151
00:07:52,810 --> 00:07:55,910
Og noder av en trie kunne oppholde
hvor som helst i denne haugen.

152
00:07:55,910 --> 00:07:58,390
Men disse er avveininger
at vi må vurdere.

153
00:07:58,390 --> 00:08:01,440
>> Husk at når du velger en data
Strukturen for en viss oppgave, vi

154
00:08:01,440 --> 00:08:04,420
bør tenke på hva slags
operasjoner datastrukturen må

155
00:08:04,420 --> 00:08:07,140
støtte og hvor mye ytelsen
av hver av disse

156
00:08:07,140 --> 00:08:09,080
operasjoner er viktig for oss.

157
00:08:09,080 --> 00:08:11,300
Disse operasjonene kan selv
utvide utover bare

158
00:08:11,300 --> 00:08:13,430
grunnleggende utseende opp og innsetting.

159
00:08:13,430 --> 00:08:17,010
Anta at vi ønsket å gjennomføre en slags
av autofullfør-funksjonalitet, mye

160
00:08:17,010 --> 00:08:18,890
som Google søkemotor gjør.

161
00:08:18,890 --> 00:08:22,210
Det er, returnere alle nøklene og
potensielt verdier som

162
00:08:22,210 --> 00:08:24,130
har en gitt prefiks.

163
00:08:24,130 --> 00:08:27,050
>> En trie er unikt nyttig
for denne operasjonen.

164
00:08:27,050 --> 00:08:29,890
Det er ukomplisert å reagere gjennom
den trie for hvert tegn i

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

166
00:08:30,950 --> 00:08:33,559
Akkurat som en titt opp drift,
vi kunne følge pekere

167
00:08:33,559 --> 00:08:35,400
tegn for tegn.

168
00:08:35,400 --> 00:08:38,659
Deretter, når vi kommer til slutten av
prefiks, kunne vi iterere gjennom

169
00:08:38,659 --> 00:08:42,049
gjenværende del av datastrukturen
ettersom en hvilken som helst av tastene utover

170
00:08:42,049 --> 00:08:43,980
dette punktet har prefikset.

171
00:08:43,980 --> 00:08:47,670
>> Det er også lett å få tak i denne oppføringen
i alfabetisk rekkefølge siden

172
00:08:47,670 --> 00:08:50,970
elementer av barn matrise
er ordnet alfabetisk.

173
00:08:50,970 --> 00:08:54,420
Så forhåpentligvis vil du vurdere
gi forsøker et forsøk.

174
00:08:54,420 --> 00:08:56,085
Jeg er Kevin Schmid, og dette er CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, dette er begynnelsen
av nedgangen.

177
00:09:00,790 --> 00:09:01,350
Jeg beklager.

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

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

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

181
00:09:03,130 --> 00:09:03,950
>> Strike fire.

182
00:09:03,950 --> 00:09:04,360
Jeg er ute.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Sorry for å gjøre den personen som
har til å redigere dette gå gale.

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

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

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

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

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

192
00:09:16,280 --> 00:09:17,530
Det var veldig bra gjort.

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