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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Ibland, när man bygger en
program, kanske du vill använda en

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

4
00:00:13,190 --> 00:00:17,960
En ordbok kartor nycklar, som är
oftast strängar, till värden, Ints,

5
00:00:17,960 --> 00:00:21,900
tecken, en pekare till något objekt,
vad vi vill.

6
00:00:21,900 --> 00:00:26,510
Det är precis som vanliga ordböcker
att kart ord genom definitioner.

7
00:00:26,510 --> 00:00:29,440
>> Ordböcker ger oss
förmåga att lagra information

8
00:00:29,440 --> 00:00:32,750
förknippas med något
och slå upp det senare.

9
00:00:32,750 --> 00:00:36,620
Så hur gör vi faktiskt genomför en
dictionary i, säg, C-kod som vi kan

10
00:00:36,620 --> 00:00:38,460
användning i någon av våra program?

11
00:00:38,460 --> 00:00:41,790
Nåväl, det finns många sätt att
vi skulle kunna genomföra en ordbok.

12
00:00:41,790 --> 00:00:45,930
>> För en, kan vi använda en array som vi
dynamiskt ändra storlek eller vi skulle kunna använda en

13
00:00:45,930 --> 00:00:49,150
länkad lista, hashtabell
eller ett binärt träd.

14
00:00:49,150 --> 00:00:52,250
Men vad vi än väljer, bör vi
vara uppmärksam på effektivitet och

15
00:00:52,250 --> 00:00:54,300
utförandet av implementeringen.

16
00:00:54,300 --> 00:00:57,930
Vi borde tänka på den algoritm som används
att sätta in och leta upp poster i

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

18
00:00:59,120 --> 00:01:03,060
>> För nu, låt oss anta att vi
vill använda strängar som nycklar.

19
00:01:03,060 --> 00:01:07,290
Låt oss tala om en möjlighet,
en datastruktur som kallas en trie.

20
00:01:07,290 --> 00:01:11,210
Så här är en visuell representation
av en trie.

21
00:01:11,210 --> 00:01:14,590
>> Som bilden antyder, en trie
är en träddatastruktur med

22
00:01:14,590 --> 00:01:16,050
noder kopplas samman.

23
00:01:16,050 --> 00:01:19,420
Vi ser att det finns helt klart en rot
nod med några länkar som sträcker sig till

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

25
00:01:20,500 --> 00:01:23,040
Men vad varje nod består av?

26
00:01:23,040 --> 00:01:26,700
Om vi ​​antar att vi lagrar nycklar
med endast alfabetiska tecken, och

27
00:01:26,700 --> 00:01:30,150
Vi bryr oss inte om kapitalisering,
Här är en definition av en nod som

28
00:01:30,150 --> 00:01:31,100
tillräcklig.

29
00:01:31,100 --> 00:01:34,130
>> Ett objekt vars typ är struct
nod har två delar

30
00:01:34,130 --> 00:01:35,740
kallas data och barn.

31
00:01:35,740 --> 00:01:39,200
Vi har lämnat uppgifterna ingår som en kommentar
för att ersättas av en komponent

32
00:01:39,200 --> 00:01:43,190
deklaration när struct nod är
införlivas i ett C-program.

33
00:01:43,190 --> 00:01:47,040
Datadelen hos en nod kan vara en
Booleskt värde som anger om

34
00:01:47,040 --> 00:01:51,160
inte den nod representerar slutför
av en ordbok nyckel eller det kan vara en

35
00:01:51,160 --> 00:01:54,240
sträng som representerar definitionen
av ett ord i ordlistan.

36
00:01:54,240 --> 00:01:58,870
>> Vi kommer att använda en smiley för att ange
när data är närvarande i en nod.

37
00:01:58,870 --> 00:02:02,310
Det finns 26 element i vår
barn array, ett index

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

39
00:02:03,690 --> 00:02:06,570
Vi får se vilken betydelse
av detta kort.

40
00:02:06,570 --> 00:02:10,759
>> Låt oss få en närmare titt på rotnoden
i vårt diagram, som saknar uppgifter

41
00:02:10,759 --> 00:02:14,740
samband med det, vilket framgår av den
avsaknad av smiley i

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

43
00:02:16,110 --> 00:02:19,910
De pilar som sträcker sig från de delar som
barnen array representerar icke-nod

44
00:02:19,910 --> 00:02:21,640
pekare till andra noder.

45
00:02:21,640 --> 00:02:25,500
Exempelvis pilen som sträcker sig från
den andra delen av barn

46
00:02:25,500 --> 00:02:28,400
representerar bokstaven B
i en ordbok nyckel.

47
00:02:28,400 --> 00:02:31,920
Och i den större schema
vi märka den med ett B.

48
00:02:31,920 --> 00:02:35,810
>> Notera att i den större diagrammet, när vi
dra en pekare till en annan nod, det

49
00:02:35,810 --> 00:02:39,100
spelar ingen roll var pilspetsen
uppfyller denna andra nod.

50
00:02:39,100 --> 00:02:43,850
Vår provet ordboks trie innehåller
två ord, det och zooma.

51
00:02:43,850 --> 00:02:47,040
Låt oss gå igenom ett exempel på
leta upp uppgifter för en nyckel.

52
00:02:47,040 --> 00:02:50,800
>> Antag att vi ville slå upp
Motsvarande värde för nyckeln badet.

53
00:02:50,800 --> 00:02:53,610
Vi börjar vår blick upp
vid rotnoden.

54
00:02:53,610 --> 00:02:57,870
Sen tar vi den första bokstaven i vår
nyckel, B, och hittar motsvarande

55
00:02:57,870 --> 00:03:00,020
plats i våra barn array.

56
00:03:00,020 --> 00:03:04,490
Lägg märke till att det är exakt 26 platser
i arrayen, en för varje bokstav i

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

58
00:03:05,330 --> 00:03:08,800
Och vi kommer att ha fläckarna representerar
bokstäverna i alfabetet i ordning.

59
00:03:08,800 --> 00:03:13,960
>> Vi tittar på det andra indexet sedan,
index en, för B. I allmänhet, om vi

60
00:03:13,960 --> 00:03:17,990
har någon bokstav C vi
skulle kunna fastställa den motsvarande plats

61
00:03:17,990 --> 00:03:21,520
i barn array med
en beräkning som denna.

62
00:03:21,520 --> 00:03:25,140
Vi kunde ha använt ett större barn
matris om vi ville erbjuda titta upp på

63
00:03:25,140 --> 00:03:28,380
nycklar med ett bredare utbud av karaktärer,
såsom hela

64
00:03:28,380 --> 00:03:29,880
ASCII-teckenuppsättning.

65
00:03:29,880 --> 00:03:32,630
>> I detta fall pekaren
i våra barn array på

66
00:03:32,630 --> 00:03:34,320
index man inte är null.

67
00:03:34,320 --> 00:03:36,600
Så vi ska fortsätta titta
upp nyckeln badet.

68
00:03:36,600 --> 00:03:40,130
Om vi ​​någonsin stött på en nollpekare
på rätt plats i barnen

69
00:03:40,130 --> 00:03:43,230
matris medan vi korsas noderna,
då vi måste säga att vi

70
00:03:43,230 --> 00:03:45,630
kunde inte hitta något för den tangenten.

71
00:03:45,630 --> 00:03:49,370
>> Nu tar vi den andra bokstaven i
vår nyckel, A, och fortsätter efter

72
00:03:49,370 --> 00:03:52,400
pekare på detta sätt tills vi
når slutet av vår nyckel.

73
00:03:52,400 --> 00:03:56,530
Om vi ​​kommer till slutet av nyckeln utan
träffa några återvändsgränder, null pekare,

74
00:03:56,530 --> 00:03:59,730
vilket är fallet här, då bara vi
måste kolla en sak.

75
00:03:59,730 --> 00:04:02,110
Är det nyckeln faktiskt
i ordlistan?

76
00:04:02,110 --> 00:04:07,660
>> Om så är fallet, skulle vi finna ett värde, väl en
smiley-ikonen i vårt diagram där

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

78
00:04:08,750 --> 00:04:12,270
Om det är något annat som lagras med
data, då kan vi lämna tillbaka den.

79
00:04:12,270 --> 00:04:16,500
Till exempel, är nyckeln zoo inte i
ordbok, även om vi kunde ha

80
00:04:16,500 --> 00:04:19,810
nått slutet av denna nyckel utan att någonsin
slå en null-pekare, medan vi

81
00:04:19,810 --> 00:04:21,089
iterera igenom trie.

82
00:04:21,089 --> 00:04:25,436
>> Om vi ​​försökte leta upp nyckeln bad,
näst sista nods fältindex,

83
00:04:25,436 --> 00:04:28,750
motsvarar bokstaven H, skulle
har haft en null-pekare.

84
00:04:28,750 --> 00:04:31,120
Så bad är inte i ordlistan.

85
00:04:31,120 --> 00:04:34,800
Och så en trie är unik i det att knapparna
är aldrig explicit lagrad i

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

87
00:04:36,650 --> 00:04:38,810
Så hur ska vi sätta in något
in i en trie?

88
00:04:38,810 --> 00:04:41,780
>> Låt oss sätta i nyckeln
zoo i vår trie.

89
00:04:41,780 --> 00:04:46,120
Kom ihåg att en smiley på en nod
skulle motsvara i koden till ett enkelt

90
00:04:46,120 --> 00:04:50,170
Booleskt värde som tyder på att zoo
är i ordboken eller det kan

91
00:04:50,170 --> 00:04:53,710
motsvara mer information som vi
vill associera med nyckel zoo,

92
00:04:53,710 --> 00:04:56,860
liksom definitionen av
ord eller något annat.

93
00:04:56,860 --> 00:05:00,350
På sätt och vis, att processen för in
något i ett trie liknar

94
00:05:00,350 --> 00:05:02,060
tittar upp något i ett trie.

95
00:05:02,060 --> 00:05:05,720
>> Vi börjar med rotnoden igen,
Följande tips motsvarande

96
00:05:05,720 --> 00:05:07,990
bokstäverna i vår nyckel.

97
00:05:07,990 --> 00:05:11,310
Lyckligtvis kunde vi följa pekare
ända tills vi nådde

98
00:05:11,310 --> 00:05:12,770
slutet av nyckeln.

99
00:05:12,770 --> 00:05:16,480
Eftersom djurparken är ett prefix till ordet
zoom, vilket är en medlem av den

100
00:05:16,480 --> 00:05:19,440
ordbok, behöver vi inte
fördela några nya noder.

101
00:05:19,440 --> 00:05:23,140
>> Vi kan modifiera noden för att indikera att
banan av tecken som leder till

102
00:05:23,140 --> 00:05:25,360
det utgör en nyckel i vår ordlista.

103
00:05:25,360 --> 00:05:28,630
Nu ska vi försöka sätta in
nyckel BAD i trie.

104
00:05:28,630 --> 00:05:32,260
Vi börjar på rotnoden
och följ pekare igen.

105
00:05:32,260 --> 00:05:35,620
Men i den här situationen, slog vi en död
slutar innan vi kan komma till

106
00:05:35,620 --> 00:05:36,940
änden av nyckeln.

107
00:05:36,940 --> 00:05:40,980
Nu kommer vi att behöva avsätta en del nya
kontaktpunkter måste tilldela en ny

108
00:05:40,980 --> 00:05:43,660
nod för varje återstående
skrivelse av vår nyckel.

109
00:05:43,660 --> 00:05:46,740
>> I det här fallet behöver vi bara
att tilldela en ny nod.

110
00:05:46,740 --> 00:05:50,590
Då kommer vi att behöva göra H-index
referera till den nya noden.

111
00:05:50,590 --> 00:05:54,070
Återigen kan vi modifiera den nod till
indikera att banan av tecken

112
00:05:54,070 --> 00:05:57,120
som leder till den representerar en
nyckel i vår ordlista.

113
00:05:57,120 --> 00:06:00,730
Låt oss resonera om asymptotiska
komplexiteten i våra rutiner för dessa

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

115
00:06:02,110 --> 00:06:06,420
>> Vi märker att i båda fallen att antalet
för steg vår algoritm tog var

116
00:06:06,420 --> 00:06:09,470
proportionell mot antalet av
bokstäver i sökordet.

117
00:06:09,470 --> 00:06:10,220
Det stämmer.

118
00:06:10,220 --> 00:06:13,470
När du vill slå upp ett ord i en
trie du behöver bara iterera genom

119
00:06:13,470 --> 00:06:17,100
bokstäverna en efter en tills du antingen
når slutet av ordet eller

120
00:06:17,100 --> 00:06:19,060
träffa en återvändsgränd i trie.

121
00:06:19,060 --> 00:06:22,470
>> Och när du vill lägga in en nyckel
värde-par till ett trie med hjälp av

122
00:06:22,470 --> 00:06:26,250
procedur som vi diskuterade, det värsta fallet
kommer att få dig att tilldela en ny nod

123
00:06:26,250 --> 00:06:27,550
för varje bokstav.

124
00:06:27,550 --> 00:06:31,290
Och vi antar att fördelningen
är en konstant tids operation.

125
00:06:31,290 --> 00:06:35,850
Så om vi antar att nyckellängden är
avgränsas av en fast konstant, både

126
00:06:35,850 --> 00:06:39,400
insättning och leta upp är konstanta
tidsverksamhet för en trie.

127
00:06:39,400 --> 00:06:42,930
>> Om vi ​​inte göra detta antagande att
nyckellängden är begränsad av ett fast

128
00:06:42,930 --> 00:06:46,650
konstant, sedan införandet och titta upp,
i värsta fall, är linjär i

129
00:06:46,650 --> 00:06:48,240
längden på nyckeln.

130
00:06:48,240 --> 00:06:51,800
Observera att antalet objekt som lagras
i trie inte påverkar utseendet upp

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

132
00:06:52,820 --> 00:06:55,360
Det har bara påverkats av den
längden på nyckeln.

133
00:06:55,360 --> 00:06:59,300
>> Däremot att lägga till poster i, säg,
en hashtabell tenderar att göra

134
00:06:59,300 --> 00:07:01,250
framtiden ser upp långsammare.

135
00:07:01,250 --> 00:07:04,520
Även om detta kanske låter lockande i början,
Vi bör hålla i minnet att en

136
00:07:04,520 --> 00:07:08,740
gynnsamma asymptotisk komplexitet inte
innebär att i praktiken uppgifter

137
00:07:08,740 --> 00:07:11,410
strukturen är nödvändigtvis
klanderfri.

138
00:07:11,410 --> 00:07:15,860
Vi måste också tänka på att lagra en
ord i ett trie vi behöver, i värsta

139
00:07:15,860 --> 00:07:19,700
fall ett antal noder i proportion
till längden av själva ordet.

140
00:07:19,700 --> 00:07:21,880
>> Försöker tenderar att använda en hel del utrymme.

141
00:07:21,880 --> 00:07:25,620
Det är i motsats till en hash-tabell,
där vi behöver bara en ny nod till

142
00:07:25,620 --> 00:07:27,940
lagra vissa nyckelvärde paret.

143
00:07:27,940 --> 00:07:31,370
Nu, återigen i teorin, stort utrymme
konsumtion verkar inte som en stor

144
00:07:31,370 --> 00:07:34,620
hantera, speciellt med tanke på att modern
datorer har gigabyte och

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

146
00:07:36,180 --> 00:07:39,200
Men det visar sig att vi fortfarande har
att oroa sig för minnesanvändning och

147
00:07:39,200 --> 00:07:42,540
organisation för den skull
prestanda, eftersom moderna datorer

148
00:07:42,540 --> 00:07:46,960
ha mekanismer enligt
huva för att snabba upp minnesåtkomst.

149
00:07:46,960 --> 00:07:51,180
>> Men dessa mekanismer fungerar bäst när
minnesaccesserna är gjorda i kompakt

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

151
00:07:52,810 --> 00:07:55,910
Och noderna i ett trie kunde uppe
någonstans i högen.

152
00:07:55,910 --> 00:07:58,390
Men dessa är avvägningar
att vi måste överväga.

153
00:07:58,390 --> 00:08:01,440
>> Kom ihåg att när du väljer en data
struktur för en viss uppgift, vi

154
00:08:01,440 --> 00:08:04,420
bör tänka på vad slags
operationer datastrukturen behöver

155
00:08:04,420 --> 00:08:07,140
stöd och hur mycket prestandan
av var och en av dem

156
00:08:07,140 --> 00:08:09,080
verksamhet är viktigt för oss.

157
00:08:09,080 --> 00:08:11,300
Dessa verksamheter kan till och med
sträcker sig längre än bara

158
00:08:11,300 --> 00:08:13,430
grundläggande utseende upp och insättning.

159
00:08:13,430 --> 00:08:17,010
Antag att vi ville genomföra en slags
av automatisk komplettering funktionalitet, mycket

160
00:08:17,010 --> 00:08:18,890
som Googles sökmotor fungerar.

161
00:08:18,890 --> 00:08:22,210
Det vill säga, tillbaka alla nycklar och
potentiellt värden som

162
00:08:22,210 --> 00:08:24,130
har ett givet prefix.

163
00:08:24,130 --> 00:08:27,050
>> En trie är unikt användbar
för denna operation.

164
00:08:27,050 --> 00:08:29,890
Det är enkelt att iterera igenom
den trie för varje karaktär

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

166
00:08:30,950 --> 00:08:33,559
Precis som en slå upp operation
Vi kunde följa pekare

167
00:08:33,559 --> 00:08:35,400
tecken för tecken.

168
00:08:35,400 --> 00:08:38,659
Sedan, när vi kommer till slutet av
prefix, kunde vi iterera genom

169
00:08:38,659 --> 00:08:42,049
återstående del av datastrukturen
sedan någon av knapparna bortom

170
00:08:42,049 --> 00:08:43,980
denna punkt har prefixet.

171
00:08:43,980 --> 00:08:47,670
>> Det är också lätt att få den här informationen
i alfabetisk ordning sedan

172
00:08:47,670 --> 00:08:50,970
delar av barn arrayen
är ordnade alfabetiskt.

173
00:08:50,970 --> 00:08:54,420
Så förhoppningsvis kommer du att tänka på
givandet försöker ett försök.

174
00:08:54,420 --> 00:08:56,085
Jag är Kevin Schmid, och detta är CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, det här är början
av nedgången.

177
00:09:00,790 --> 00:09:01,350
Jag är ledsen.

178
00:09:01,350 --> 00:09:01,870
Ursäkta.

179
00:09:01,870 --> 00:09:02,480
Ursäkta.

180
00:09:02,480 --> 00:09:03,130
Ursäkta.

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

182
00:09:03,950 --> 00:09:04,360
Jag är ute.

183
00:09:04,360 --> 00:09:05,280
Ursäkta.

184
00:09:05,280 --> 00:09:06,500
Ursäkta.

185
00:09:06,500 --> 00:09:07,490
Ursäkta.

186
00:09:07,490 --> 00:09:12,352
Ledsen för att den som
måste redigera bli galen.

187
00:09:12,352 --> 00:09:13,280
>> Ursäkta.

188
00:09:13,280 --> 00:09:13,880
Ursäkta.

189
00:09:13,880 --> 00:09:15,080
Ursäkta.

190
00:09:15,080 --> 00:09:15,680
Ursäkta.

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

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

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