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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Nogle gange, når man bygger en
program, kan du ønsker at bruge en

3
00:00:10,890 --> 00:00:13,190
datastruktur kendt som en ordbog.

4
00:00:13,190 --> 00:00:17,960
A Dictionary kort nøgler, som er
regel strygere, til værdier, ints,

5
00:00:17,960 --> 00:00:21,900
tegn, en pointer til en genstand,
hvad vi vil.

6
00:00:21,900 --> 00:00:26,510
Det er bare som almindelige ordbøger
at kort ord gennem definitioner.

7
00:00:26,510 --> 00:00:29,440
>> Ordbøger give os den
evne til at lagre information

8
00:00:29,440 --> 00:00:32,750
forbundet med noget
og slå det op senere.

9
00:00:32,750 --> 00:00:36,620
Så hvordan kan vi faktisk gennemføre en
ordbog i, siger, C-kode, som vi kan

10
00:00:36,620 --> 00:00:38,460
brug i en af ​​vores programmer?

11
00:00:38,460 --> 00:00:41,790
Nå, der er en masse måder,
vi kunne gennemføre en ordbog.

12
00:00:41,790 --> 00:00:45,930
>> For én, kunne vi bruge et array, vi
dynamisk re-størrelse eller vi kunne bruge en

13
00:00:45,930 --> 00:00:49,150
linkede liste, hash tabel
eller et binært træ.

14
00:00:49,150 --> 00:00:52,250
Men uanset hvad vi vælger, bør vi
være opmærksom på effektivitet og

15
00:00:52,250 --> 00:00:54,300
udførelsen af ​​implementeringen.

16
00:00:54,300 --> 00:00:57,930
Vi bør tænke på den algoritme, der anvendes
at indsætte og se op poster i

17
00:00:57,930 --> 00:00:59,120
vores datastruktur.

18
00:00:59,120 --> 00:01:03,060
>> For nu, lad os antage, at vi
ønsker at bruge strenge som nøgler.

19
00:01:03,060 --> 00:01:07,290
Lad os tale om en mulighed,
en datastruktur kaldet en trie.

20
00:01:07,290 --> 00:01:11,210
Så her er en visuel repræsentation
af en trie.

21
00:01:11,210 --> 00:01:14,590
>> Som billedet antyder, en trie
er et træ datastruktur med

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

23
00:01:16,050 --> 00:01:19,420
Vi ser, at der er helt klart en rod
node med nogle links strækker sig

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

25
00:01:20,500 --> 00:01:23,040
Men hvad betyder hver node består af?

26
00:01:23,040 --> 00:01:26,700
Hvis vi antager, at vi opbevare nøgler
med kun alfabetiske tegn, og

27
00:01:26,700 --> 00:01:30,150
vi er ligeglad kapitalisering,
her er en definition af en node, der

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

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

30
00:01:34,130 --> 00:01:35,740
kaldes data og børn.

31
00:01:35,740 --> 00:01:39,200
Vi har forladt data del som en kommentar
at blive erstattet af en komponent

32
00:01:39,200 --> 00:01:43,190
erklæringen når struct node er
inkorporeres i et C-program.

33
00:01:43,190 --> 00:01:47,040
Datadelen af ​​et knudepunkt kan være en
Boolesk værdi for at angive, om

34
00:01:47,040 --> 00:01:51,160
ikke knudepunktet repræsenterer afslutningen
af en ordbog nøgle eller det kan være en

35
00:01:51,160 --> 00:01:54,240
streng, der repræsenterer definitionen
af et ord i ordbogen.

36
00:01:54,240 --> 00:01:58,870
>> Vi vil bruge et smilende ansigt for at angive
når data er til stede i en knude.

37
00:01:58,870 --> 00:02:02,310
Der er 26 elementer i vores
børn array, et indeks

38
00:02:02,310 --> 00:02:03,690
pr bogstav.

39
00:02:03,690 --> 00:02:06,570
Vi vil se betydningen
dette snart.

40
00:02:06,570 --> 00:02:10,759
>> Lad os få et nærmere kig på roden node
i vores diagram, som ikke har nogen data

41
00:02:10,759 --> 00:02:14,740
forbundet med det, som det fremgår af
fravær af det smilende ansigt i

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

43
00:02:16,110 --> 00:02:19,910
Pilene, der strækker sig fra de dele af
børnene Array repræsenterer ikke-node

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

45
00:02:21,640 --> 00:02:25,500
For eksempel pilen der strækker sig fra
det andet element i børn

46
00:02:25,500 --> 00:02:28,400
repræsenterer bogstavet B
i en ordbog nøgle.

47
00:02:28,400 --> 00:02:31,920
Og i større diagram
vi mærke den med en B.

48
00:02:31,920 --> 00:02:35,810
>> Bemærk, at i større diagram, når vi
tegne en pointer til en anden node, det

49
00:02:35,810 --> 00:02:39,100
ligegyldigt hvor pilespidsen
opfylder dette andet knudepunkt.

50
00:02:39,100 --> 00:02:43,850
Vores stikprøve ordbog trie indeholder
to ord, der og zoom.

51
00:02:43,850 --> 00:02:47,040
Lad os gå gennem et eksempel på
ser op data for en nøgle.

52
00:02:47,040 --> 00:02:50,800
>> Antag, at vi ønskede at se op
tilsvarende værdi for nøglen bad.

53
00:02:50,800 --> 00:02:53,610
Vi begynder vores udseende op
ved roden node.

54
00:02:53,610 --> 00:02:57,870
Så tager vi det første bogstav i vores
nøgle, B, og finde den tilsvarende

55
00:02:57,870 --> 00:03:00,020
øje på vores børn array.

56
00:03:00,020 --> 00:03:04,490
Bemærk, at der er nøjagtig 26 spots
i arrayet, en for hvert bogstav i

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

58
00:03:05,330 --> 00:03:08,800
Og vi vil have pletter repræsenterer
bogstaver i alfabetet i orden.

59
00:03:08,800 --> 00:03:13,960
>> Vi ser på det andet indeks da,
indeks et, B. I almindelighed, hvis vi

60
00:03:13,960 --> 00:03:17,990
har nogle bogstav C, vi
kunne bestemme den tilsvarende plet

61
00:03:17,990 --> 00:03:21,520
i børn array ved hjælp af
en beregning som dette.

62
00:03:21,520 --> 00:03:25,140
Vi kunne have brugt en større børn
matrix, hvis vi ønskede at tilbyde udseendet af

63
00:03:25,140 --> 00:03:28,380
nøgler med en bredere vifte af figurer,
såsom hele

64
00:03:28,380 --> 00:03:29,880
ASCII tegnsæt.

65
00:03:29,880 --> 00:03:32,630
>> I dette tilfælde, er pointeren
i vores børn array

66
00:03:32,630 --> 00:03:34,320
indeks man ikke er nul.

67
00:03:34,320 --> 00:03:36,600
Så vi vil fortsætte med at kigge
nøglens bad.

68
00:03:36,600 --> 00:03:40,130
Hvis vi nogensinde mødt en null-pointer
på det rette sted i børnenes

69
00:03:40,130 --> 00:03:43,230
vifte, mens vi gennemkøres knudepunkter,
så vil vi nødt til at sige, at vi

70
00:03:43,230 --> 00:03:45,630
kunne ikke finde noget for denne nøgle.

71
00:03:45,630 --> 00:03:49,370
>> Nu vil vi tage det andet bogstav på
vores nøgle, A, og fortsætte med at følge

72
00:03:49,370 --> 00:03:52,400
pointere i denne måde, indtil vi
nå slutningen af ​​vores nøgle.

73
00:03:52,400 --> 00:03:56,530
Hvis vi når enden af ​​nøgle uden
ramme nogen blindgyder, null pointers,

74
00:03:56,530 --> 00:03:59,730
som det er tilfældet her, så vi kun
nødt til at tjekke en ting mere.

75
00:03:59,730 --> 00:04:02,110
Er denne nøgle faktisk
i ordbogen?

76
00:04:02,110 --> 00:04:07,660
>> Hvis det er tilfældet, bør vi finde en værdi, godt en
smiley ikon ansigt i vores diagram, hvor

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

78
00:04:08,750 --> 00:04:12,270
Hvis der er noget andet gemt med
data, så vi kan returnere den.

79
00:04:12,270 --> 00:04:16,500
For eksempel, nøglen zoo ikke i
ordbog, selv om vi kunne have

80
00:04:16,500 --> 00:04:19,810
nået slutningen af ​​denne nøgle uden nogensinde
rammer en null-pointer, mens vi

81
00:04:19,810 --> 00:04:21,089
gentage gennem trie.

82
00:04:21,089 --> 00:04:25,436
>> Hvis vi prøvede at kigge op nøglen bad,
næstsidste node arrayindeks,

83
00:04:25,436 --> 00:04:28,750
svarer til bogstavet H, ville
har afholdt en null-pointer.

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

85
00:04:31,120 --> 00:04:34,800
Og så en trie er enestående i, at tasterne
aldrig eksplicit lagret i

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

87
00:04:36,650 --> 00:04:38,810
Så hvordan vi indsætter noget
i en trie?

88
00:04:38,810 --> 00:04:41,780
>> Lad os indsætte nøglen
zoo i vores trie.

89
00:04:41,780 --> 00:04:46,120
Husk, at et smilende ansigt på en node
kunne svare i kode til en simpel

90
00:04:46,120 --> 00:04:50,170
Boolesk værdi for at indikere, zoo
findes i ordbogen, eller det kunne

91
00:04:50,170 --> 00:04:53,710
svarer til flere oplysninger, som vi
ønsker at forbinde med nøglen zoo,

92
00:04:53,710 --> 00:04:56,860
som definitionen af
ord eller noget andet.

93
00:04:56,860 --> 00:05:00,350
På nogle måder, at processen indsætte
noget i en trie ligner

94
00:05:00,350 --> 00:05:02,060
kigge op noget i en trie.

95
00:05:02,060 --> 00:05:05,720
>> Vi begynder med rodnoden igen,
følgende pejlemærker, der svarer til

96
00:05:05,720 --> 00:05:07,990
bogstaverne i vores nøgle.

97
00:05:07,990 --> 00:05:11,310
Heldigvis var vi i stand til at følge pointers
hele vejen, indtil vi nåede

98
00:05:11,310 --> 00:05:12,770
udgangen af ​​nøglen.

99
00:05:12,770 --> 00:05:16,480
Da zoo er et præfiks af ordet
zoom, der er medlem af

100
00:05:16,480 --> 00:05:19,440
ordbog, behøver vi ikke at
tildele nye noder.

101
00:05:19,440 --> 00:05:23,140
>> Vi kan ændre den node indikere, at
stien karakterer, der fører til

102
00:05:23,140 --> 00:05:25,360
det repræsenterer en nøgle i vores ordbog.

103
00:05:25,360 --> 00:05:28,630
Nu, lad os prøve at indsætte
nøgle BATH i trie.

104
00:05:28,630 --> 00:05:32,260
Vi starter ved roden node
og følg pointers igen.

105
00:05:32,260 --> 00:05:35,620
Men i denne situation, vi ramte en død
slutter, før vi er i stand til at komme til

106
00:05:35,620 --> 00:05:36,940
spidsen af ​​nøglen.

107
00:05:36,940 --> 00:05:40,980
Nu vil vi nødt til at afsætte nogle nye
knudepunkter bliver nødt til at afsætte en ny

108
00:05:40,980 --> 00:05:43,660
node for hvert resterende
brev af vores nøgle.

109
00:05:43,660 --> 00:05:46,740
>> I dette tilfælde har vi bare brug
at tildele en ny node.

110
00:05:46,740 --> 00:05:50,590
Så vil vi nødt til at gøre H-indeks
henvise til denne nye node.

111
00:05:50,590 --> 00:05:54,070
Igen kan vi ændre den node
indikerer, at stien karakterer

112
00:05:54,070 --> 00:05:57,120
fører til det repræsenterer en
nøglen i vores ordbog.

113
00:05:57,120 --> 00:06:00,730
Lad os ræsonnere om den asymptotiske
kompleksiteten af ​​vores procedurer for disse

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

115
00:06:02,110 --> 00:06:06,420
>> Vi bemærker, at der i begge tilfælde kan antallet
af trin vores algoritme tog blev

116
00:06:06,420 --> 00:06:09,470
proportional med antallet af
bogstaver i søgeordet.

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

118
00:06:10,220 --> 00:06:13,470
Når du ønsker at se et ord op i en
trie du bare nødt til at gentage gennem

119
00:06:13,470 --> 00:06:17,100
bogstaverne én efter én, indtil du enten
nå slutningen af ​​ordet eller

120
00:06:17,100 --> 00:06:19,060
ramte en blindgyde i trie.

121
00:06:19,060 --> 00:06:22,470
>> Og når du ønsker at indsætte en nøgle
værdi par i en trie ved hjælp af

122
00:06:22,470 --> 00:06:26,250
procedure, vi diskuterede, i værste fald
vil få dig til at afsætte en ny knude

123
00:06:26,250 --> 00:06:27,550
for hvert bogstav.

124
00:06:27,550 --> 00:06:31,290
Og vi vil antage, at fordelingen
er en konstant tid operation.

125
00:06:31,290 --> 00:06:35,850
Så hvis vi antager, at nøglelængde er
afgrænset af en fast konstant, både

126
00:06:35,850 --> 00:06:39,400
indsættelse og kigge op er konstante
time operationer for en trie.

127
00:06:39,400 --> 00:06:42,930
>> Hvis vi ikke gør dette antagelse, at
nøglelængden er afgrænset af en fast

128
00:06:42,930 --> 00:06:46,650
konstant, så indsættelse og se op,
i værste tilfælde er lineær i

129
00:06:46,650 --> 00:06:48,240
længden af ​​nøglen.

130
00:06:48,240 --> 00:06:51,800
Bemærk, at antallet af poster er gemt
i trie påvirker ikke udseendet op

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

132
00:06:52,820 --> 00:06:55,360
Det er kun påvirket af
længden af ​​nøglen.

133
00:06:55,360 --> 00:06:59,300
>> Derimod tilføjer indgange til, sige,
en hash tabel tendens til at gøre

134
00:06:59,300 --> 00:07:01,250
fremtiden ser op langsommere.

135
00:07:01,250 --> 00:07:04,520
Selvom det kan lyde tiltalende ved første,
vi skal huske på, at en

136
00:07:04,520 --> 00:07:08,740
gunstige asymptotiske kompleksitet ikke
betyder, at i praksis data

137
00:07:08,740 --> 00:07:11,410
struktur er nødvendigvis
uanfægtelig.

138
00:07:11,410 --> 00:07:15,860
Vi må også overveje, at for at gemme en
ord i en trie vi har brug for, i værste

139
00:07:15,860 --> 00:07:19,700
tilfælde et antal knudepunkter proportional
til længden af ​​ordet selv.

140
00:07:19,700 --> 00:07:21,880
>> Forsøg tendens til at bruge en masse plads.

141
00:07:21,880 --> 00:07:25,620
Det er i modsætning til en hash-tabel,
hvor vi kun har brug for en ny node til

142
00:07:25,620 --> 00:07:27,940
gemme nogle nøgleværdi par.

143
00:07:27,940 --> 00:07:31,370
Nu igen i teorien stort rum
forbrug ikke virke som en stor

144
00:07:31,370 --> 00:07:34,620
håndtere, især i betragtning, at moderne
computere har gigabytes og

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

146
00:07:36,180 --> 00:07:39,200
Men det viser sig, at vi stadig har
at bekymre sig om brug af hukommelse og

147
00:07:39,200 --> 00:07:42,540
organisation af hensyn til
resultater, da moderne computere

148
00:07:42,540 --> 00:07:46,960
har mekanismer under
hætte til at fremskynde hukommelse adgang.

149
00:07:46,960 --> 00:07:51,180
>> Men disse mekanismer fungerer bedst, når
hukommelse adgange er lavet 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 knudepunkter i en trie kunne opholde
overalt i denne bunke.

152
00:07:55,910 --> 00:07:58,390
Men disse er afvejninger
at vi skal overveje.

153
00:07:58,390 --> 00:08:01,440
>> Husk det, når du vælger en data
struktur for en bestemt opgave, vi

154
00:08:01,440 --> 00:08:04,420
bør tænke over, hvilke former for
operationer datastrukturen skal

155
00:08:04,420 --> 00:08:07,140
støtte og hvor meget ydelse
i hver af disse

156
00:08:07,140 --> 00:08:09,080
operationer spørgsmål til os.

157
00:08:09,080 --> 00:08:11,300
Disse operationer kan endda
strække sig ud over bare

158
00:08:11,300 --> 00:08:13,430
grundlæggende kig op og indsættelse.

159
00:08:13,430 --> 00:08:17,010
Antag, at vi ønskede at gennemføre en slags
af auto-komplet funktionalitet, meget

160
00:08:17,010 --> 00:08:18,890
Ligesom Google-søgemaskinen gør.

161
00:08:18,890 --> 00:08:22,210
Det vil sige, returnere alle nøglerne og
potentielt værdier, som

162
00:08:22,210 --> 00:08:24,130
have givet et præfiks.

163
00:08:24,130 --> 00:08:27,050
>> Et trie er entydigt nyttigt
til denne operation.

164
00:08:27,050 --> 00:08:29,890
Det er ligetil at gentage gennem
den trie for hver karakter

165
00:08:29,890 --> 00:08:30,950
præfikset.

166
00:08:30,950 --> 00:08:33,559
Ligesom et kig op operation,
vi kunne følge pointers

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

168
00:08:35,400 --> 00:08:38,659
Derefter, når vi frem til slutningen af
præfiks, kunne vi gentage gennem

169
00:08:38,659 --> 00:08:42,049
resterende del af datastrukturen
idet enhver af nøglerne ud

170
00:08:42,049 --> 00:08:43,980
dette punkt har præfikset.

171
00:08:43,980 --> 00:08:47,670
>> Det er også nemt at få denne liste
i alfabetisk rækkefølge, da

172
00:08:47,670 --> 00:08:50,970
elementer af børn matrix
er ordnet alfabetisk.

173
00:08:50,970 --> 00:08:54,420
Så forhåbentlig du vil overveje
give forsøger en chance.

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

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, det er begyndelsen
af tilbagegangen.

177
00:09:00,790 --> 00:09:01,350
Undskyld.

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

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

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

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

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

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

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

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

186
00:09:07,490 --> 00:09:12,352
Sorry for at gøre den person, der
har til at redigere denne gå amok.

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

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

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

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

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

192
00:09:16,280 --> 00:09:17,530
Det var virkelig godt gået.

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