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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Soms, als het bouwen van een
programma, wilt u misschien gebruik maken van een

3
00:00:10,890 --> 00:00:13,190
gegevensstructuur bekend als een woordenboek.

4
00:00:13,190 --> 00:00:17,960
Een woordenboek kaarten sleutels, die
meestal strings, waarden, ints,

5
00:00:17,960 --> 00:00:21,900
chars, een pointer naar een object,
wat we willen.

6
00:00:21,900 --> 00:00:26,510
Het is net als gewone woordenboeken
die kaart woorden door definities.

7
00:00:26,510 --> 00:00:29,440
>> Woordenboeken geven ons de
vermogen om informatie op te slaan

8
00:00:29,440 --> 00:00:32,750
geassocieerd met iets
en kijk het later.

9
00:00:32,750 --> 00:00:36,620
Dus hoe kunnen we daadwerkelijk implementeren van een
woordenboek in bijvoorbeeld C code die we kunnen

10
00:00:36,620 --> 00:00:38,460
gebruiken in een van onze programma's?

11
00:00:38,460 --> 00:00:41,790
Nou, er zijn een heleboel manieren waarop
konden we een woordenboek te implementeren.

12
00:00:41,790 --> 00:00:45,930
>> Voor een, konden we een array dat we
dynamisch re-size of we konden gebruiken

13
00:00:45,930 --> 00:00:49,150
gelinkte lijst, hash table
of een binaire boom.

14
00:00:49,150 --> 00:00:52,250
Maar wat we ook kiezen, moeten we
rekening te houden met de efficiëntie en

15
00:00:52,250 --> 00:00:54,300
prestaties van de uitvoering.

16
00:00:54,300 --> 00:00:57,930
We moeten nadenken over de gebruikte algoritme
in te voegen en kijk omhoog artikelen in

17
00:00:57,930 --> 00:00:59,120
onze gegevensstructuur.

18
00:00:59,120 --> 00:01:03,060
>> Voor nu, laten we aannemen dat we
willen strings gebruiken als sleutels.

19
00:01:03,060 --> 00:01:07,290
Laten we praten over een mogelijkheid,
een gegevensstructuur genoemd trie.

20
00:01:07,290 --> 00:01:11,210
Dus hier is een visuele weergave
een trie.

21
00:01:11,210 --> 00:01:14,590
>> Zoals de foto doet vermoeden, een Trie
is een boom datastructuur met

22
00:01:14,590 --> 00:01:16,050
knooppunten met elkaar verbonden.

23
00:01:16,050 --> 00:01:19,420
We zien dat er duidelijk een wortel
knooppunt met een aantal links uit te breiden tot

24
00:01:19,420 --> 00:01:20,500
andere knooppunten.

25
00:01:20,500 --> 00:01:23,040
Maar wat betekent elk knooppunt uit?

26
00:01:23,040 --> 00:01:26,700
Als we aannemen dat we het opslaan van sleutels
met alleen letters, en

27
00:01:26,700 --> 00:01:30,150
we geven niet om kapitalisatie,
Hier is een definitie van een knooppunt dat

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

29
00:01:31,100 --> 00:01:34,130
>> Een object waarvan het type struct
knooppunt bestaat uit twee delen

30
00:01:34,130 --> 00:01:35,740
riep gegevens en kinderen.

31
00:01:35,740 --> 00:01:39,200
We hebben de gegevens deel verliet als een commentaar
te vervangen door een component

32
00:01:39,200 --> 00:01:43,190
verklaring als struct knooppunt
opgenomen in een C programma.

33
00:01:43,190 --> 00:01:47,040
De gegevens onderdeel van een knooppunt misschien een
Booleaanse waarde die aangeeft of

34
00:01:47,040 --> 00:01:51,160
niet het knooppunt vertegenwoordigt de voltooiing
van een woordenboek sleutel of het misschien een

35
00:01:51,160 --> 00:01:54,240
tekenreeks die de definitie
van een woord in het woordenboek.

36
00:01:54,240 --> 00:01:58,870
>> We zullen een smiley gebruiken om aan te geven
wanneer gegevens aanwezig is in een knooppunt.

37
00:01:58,870 --> 00:02:02,310
Er zijn 26 elementen in ons
kinderen array, een index

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

39
00:02:03,690 --> 00:02:06,570
We zullen de betekenis te zien
van deze binnenkort.

40
00:02:06,570 --> 00:02:10,759
>> Laten we een kijkje van de wortel
in ons diagram, waarin geen data

41
00:02:10,759 --> 00:02:14,740
gekoppeld, zoals aangegeven door de
afwezigheid van de smiley in de

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

43
00:02:16,110 --> 00:02:19,910
De pijlen uitstrekt uit delen van
de kinderen reeks vertegenwoordigen niet-knooppunt

44
00:02:19,910 --> 00:02:21,640
verwijzingen naar andere knooppunten.

45
00:02:21,640 --> 00:02:25,500
Bijvoorbeeld, de pijl zich vanaf
het tweede element van kinderen

46
00:02:25,500 --> 00:02:28,400
de letter B
in een woordenboek sleutel.

47
00:02:28,400 --> 00:02:31,920
En in de grotere diagram
we bestempelen het met een B.

48
00:02:31,920 --> 00:02:35,810
>> Merk op dat in de grotere diagram, wanneer we
trek een pointer naar een ander knooppunt, het

49
00:02:35,810 --> 00:02:39,100
maakt niet uit waar de pijlpunt
ontmoet dat andere knooppunt.

50
00:02:39,100 --> 00:02:43,850
Onze steekproef woordenboek trie bevat
twee woorden, die en zoom.

51
00:02:43,850 --> 00:02:47,040
Laten we lopen door een voorbeeld van
het opzoeken van gegevens voor een toets.

52
00:02:47,040 --> 00:02:50,800
>> Stel dat we wilden te zoeken van de
overeenkomstige waarde voor de sleutel bad.

53
00:02:50,800 --> 00:02:53,610
We beginnen onze blik omhoog
bij de root node.

54
00:02:53,610 --> 00:02:57,870
Dan zullen we de eerste letter van onze nemen
sleutel, B, en vind het bijbehorende

55
00:02:57,870 --> 00:03:00,020
spot in onze kinderen array.

56
00:03:00,020 --> 00:03:04,490
Merk op dat er precies 26 plekken
in de array, een voor elke letter van

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

58
00:03:05,330 --> 00:03:08,800
En we moeten de plekken vertegenwoordigen de
letters van het alfabet in orde.

59
00:03:08,800 --> 00:03:13,960
>> We kijken naar de tweede index vervolgens,
index een, B. algemeen, als we

60
00:03:13,960 --> 00:03:17,990
hebben een aantal alfabetisch teken C we
zou de corresponderende vlek bepalen

61
00:03:17,990 --> 00:03:21,520
in de kinderen array met behulp van
een berekening als deze.

62
00:03:21,520 --> 00:03:25,140
We konden gebruiken een grotere kinderen
matrix als we wilden kijken uit bieden

63
00:03:25,140 --> 00:03:28,380
sleutels met een bredere reeks tekens
bijvoorbeeld de totale

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

65
00:03:29,880 --> 00:03:32,630
>> In dit geval de aanwijzer
in onze kinderen bij matrix in

66
00:03:32,630 --> 00:03:34,320
index een is niet nul.

67
00:03:34,320 --> 00:03:36,600
Dus we blijven zoeken
de sleutel bad.

68
00:03:36,600 --> 00:03:40,130
Als we ooit een null pointer aangetroffen
op de juiste plek in de kinderen

69
00:03:40,130 --> 00:03:43,230
matrix terwijl we doorkruist de knooppunten,
dan moeten we dat we zeggen

70
00:03:43,230 --> 00:03:45,630
kon niets voor die toets te vinden.

71
00:03:45,630 --> 00:03:49,370
>> Nu gaan we de tweede letter van nemen
onze belangrijkste, A, en volgt u

72
00:03:49,370 --> 00:03:52,400
pointers dit totdat we
tot het einde van onze belangrijkste.

73
00:03:52,400 --> 00:03:56,530
Als we het van de toets bereiken zonder
raken van doodlopende wegen, null pointers,

74
00:03:56,530 --> 00:03:59,730
zoals hier het geval is, dan alleen wij
moeten nog een ding controleren.

75
00:03:59,730 --> 00:04:02,110
Is deze sleutel echt
in het woordenboek?

76
00:04:02,110 --> 00:04:07,660
>> Als dat zo is, moeten we een waarde te vinden, ook een
smiley icoon in ons diagram waar

77
00:04:07,660 --> 00:04:08,750
het woord eindigt.

78
00:04:08,750 --> 00:04:12,270
Als er iets anders opgeslagen met
de gegevens, dan kunnen we het terug.

79
00:04:12,270 --> 00:04:16,500
Bijvoorbeeld, de sleutel dierentuin niet in de
woordenboek, ook al konden we hebben

80
00:04:16,500 --> 00:04:19,810
aan het einde van deze sleutel zonder ooit
raken van een null pointer, terwijl we

81
00:04:19,810 --> 00:04:21,089
doorloopt de Trie.

82
00:04:21,089 --> 00:04:25,436
>> Als we probeerde om de sleutel bad, de
voorlaatste node-array-index,

83
00:04:25,436 --> 00:04:28,750
overeenkomt met de letter H, zouden
een null pointer hebben gehouden.

84
00:04:28,750 --> 00:04:31,120
Dus bad is niet in het woordenboek.

85
00:04:31,120 --> 00:04:34,800
En dus een Trie is uniek omdat de sleutels
worden nooit expliciet opgeslagen in

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

87
00:04:36,650 --> 00:04:38,810
Dus hoe kunnen we iets te voegen
een trie?

88
00:04:38,810 --> 00:04:41,780
>> Laten we steek de sleutel
dierentuin in onze trie.

89
00:04:41,780 --> 00:04:46,120
Vergeet niet dat een smiley op een knooppunt
overeenkomen code in een simpele

90
00:04:46,120 --> 00:04:50,170
Booleaanse waarde aan dat de dierentuin geven
in het woordenboek of het kan

91
00:04:50,170 --> 00:04:53,710
verantwoordelijk voor meer informatie we
willen associëren met de sleutel dierentuin,

92
00:04:53,710 --> 00:04:56,860
zoals de definitie van de
woord of iets anders.

93
00:04:56,860 --> 00:05:00,350
In sommige opzichten, het proces in te voegen
iets in een Trie is vergelijkbaar

94
00:05:00,350 --> 00:05:02,060
het opzoeken van iets in een Trie.

95
00:05:02,060 --> 00:05:05,720
>> We beginnen opnieuw met de wortel,
volgende aanwijzingen gevonden volgens

96
00:05:05,720 --> 00:05:07,990
de letters van onze belangrijkste.

97
00:05:07,990 --> 00:05:11,310
Gelukkig waren we in staat om aanwijzingen te volgen
de hele weg tot we bereikt

98
00:05:11,310 --> 00:05:12,770
het einde van de toets.

99
00:05:12,770 --> 00:05:16,480
Aangezien dierentuin is een voorvoegsel van het woord
zoom, die lid is van de

100
00:05:16,480 --> 00:05:19,440
woordenboek, hoeven we niet te
toewijzen nieuwe knooppunten.

101
00:05:19,440 --> 00:05:23,140
>> We kunnen het knooppunt aanpassen om aan te geven dat
het pad tekens die tot

102
00:05:23,140 --> 00:05:25,360
het vertegenwoordigt een sleutel in ons woordenboek.

103
00:05:25,360 --> 00:05:28,630
Nu, laten we proberen het plaatsen van de
sleutel BATH in de Trie.

104
00:05:28,630 --> 00:05:32,260
We beginnen bij de wortel knooppunt
en volg de aanwijzingen weer.

105
00:05:32,260 --> 00:05:35,620
Maar in deze situatie, we dode raken
eindigen voordat we in staat om het te krijgen

106
00:05:35,620 --> 00:05:36,940
van de toets.

107
00:05:36,940 --> 00:05:40,980
Nu, we moeten een aantal nieuwe toe te wijzen
knooppunten moet een nieuwe toewijzen

108
00:05:40,980 --> 00:05:43,660
knooppunt voor elke resterende
brief van onze belangrijkste.

109
00:05:43,660 --> 00:05:46,740
>> In dit geval, we hoeven alleen maar
op een nieuw knooppunt toe te wijzen.

110
00:05:46,740 --> 00:05:50,590
Dan zullen we nodig hebben om de H-index maken
verwijzen naar deze nieuwe knooppunt.

111
00:05:50,590 --> 00:05:54,070
Nogmaals, we het knooppunt wijzigen om
geven aan dat de pad karakters

112
00:05:54,070 --> 00:05:57,120
waardoor het vertegenwoordigt een
sleutel in ons woordenboek.

113
00:05:57,120 --> 00:06:00,730
Laten we redeneren over de asymptotische
complexiteit van procedures voor deze

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

115
00:06:02,110 --> 00:06:06,420
>> We merken dat in beide gevallen het aantal
van stappen ons algoritme namen was

116
00:06:06,420 --> 00:06:09,470
evenredig aan het aantal
letters in het sleutelwoord.

117
00:06:09,470 --> 00:06:10,220
Dat klopt.

118
00:06:10,220 --> 00:06:13,470
Wanneer u een woord opzoeken in een
trie je hoeft alleen maar om door te herhalen

119
00:06:13,470 --> 00:06:17,100
de letters een voor een, totdat u
bereiken het einde van het woord of

120
00:06:17,100 --> 00:06:19,060
raakte een doodlopende straat in de Trie.

121
00:06:19,060 --> 00:06:22,470
>> En wanneer u een sleutel in te voegen
waarde paar in een trie met behulp van de

122
00:06:22,470 --> 00:06:26,250
procedure hebben we besproken, het ergste geval
zal u toewijzing van een nieuw knooppunt

123
00:06:26,250 --> 00:06:27,550
voor elke letter.

124
00:06:27,550 --> 00:06:31,290
En we zullen dat de toewijzing ervan uitgaan
is een constante tijd operatie.

125
00:06:31,290 --> 00:06:35,850
Als we aannemen dat de sleutellengte
begrensd door een vaste constante, zowel

126
00:06:35,850 --> 00:06:39,400
inbrengen en kijk omhoog constant zijn
tijd gedurende een Trie.

127
00:06:39,400 --> 00:06:42,930
>> Als we niet deze veronderstelling maken dat
de sleutellengte wordt begrensd door een vaste

128
00:06:42,930 --> 00:06:46,650
constant, dan inbrengen en kijk omhoog,
in het ergste geval worden lineair in de

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

130
00:06:48,240 --> 00:06:51,800
Merk op dat het aantal items opgeslagen
in de Trie heeft geen invloed op de look-up

131
00:06:51,800 --> 00:06:52,820
of insertie tijd.

132
00:06:52,820 --> 00:06:55,360
Het is alleen beïnvloed door de
lengte van de sleutel.

133
00:06:55,360 --> 00:06:59,300
>> Daarentegen ingangen toevoegen van bijvoorbeeld
een hash table neiging om

134
00:06:59,300 --> 00:07:01,250
toekomstige opzoeken langzamer.

135
00:07:01,250 --> 00:07:04,520
Hoewel dit klinkt misschien aantrekkelijk op het eerste,
we in gedachten moeten houden dat een

136
00:07:04,520 --> 00:07:08,740
gunstige asymptotische complexiteit niet
betekent dat in de praktijk de data

137
00:07:08,740 --> 00:07:11,410
structuur noodzakelijkerwijs
onbesproken.

138
00:07:11,410 --> 00:07:15,860
We moeten ook van mening dat voor het opslaan van een
woord in een Trie we nodig hebben, in het ergste

139
00:07:15,860 --> 00:07:19,700
geval een aantal knooppunten proportionele
de lengte van het woord zelf.

140
00:07:19,700 --> 00:07:21,880
>> Tries neiging om veel ruimte te gebruiken.

141
00:07:21,880 --> 00:07:25,620
Dat is in tegenstelling tot een hash tabel,
waar we moeten maar een nieuw knooppunt aan

142
00:07:25,620 --> 00:07:27,940
slaan een aantal belangrijke waarde paar.

143
00:07:27,940 --> 00:07:31,370
Nu, opnieuw in theorie, grote ruimte
verbruik lijkt niet als een grote

144
00:07:31,370 --> 00:07:34,620
omgaan, zeker gezien het feit dat de moderne
computers hebben gigabyte en

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

146
00:07:36,180 --> 00:07:39,200
Maar het blijkt dat we nog steeds
zorgen te maken over het geheugengebruik en

147
00:07:39,200 --> 00:07:42,540
organisatie omwille van
prestaties, aangezien moderne computers

148
00:07:42,540 --> 00:07:46,960
over regelingen voor onder de
kap te versnellen toegang tot het geheugen.

149
00:07:46,960 --> 00:07:51,180
>> Maar deze mechanismen werken het beste wanneer
geheugen toegangen worden gemaakt in compact

150
00:07:51,180 --> 00:07:52,810
regio's of gebieden.

151
00:07:52,810 --> 00:07:55,910
En de knooppunten van een Trie kon wonen
overal in die hoop.

152
00:07:55,910 --> 00:07:58,390
Maar dit zijn trade-offs
dat we moeten overwegen.

153
00:07:58,390 --> 00:08:01,440
>> Vergeet niet dat, bij het kiezen van een data
structuur voor een bepaalde taak, we

154
00:08:01,440 --> 00:08:04,420
moeten denken over wat voor soort
de activiteiten van de datastructuur moet

155
00:08:04,420 --> 00:08:07,140
ondersteuning en hoeveel de prestaties
elk van deze

156
00:08:07,140 --> 00:08:09,080
operaties is belangrijk voor ons.

157
00:08:09,080 --> 00:08:11,300
Deze operaties kunnen zelfs
verder reiken dan alleen

158
00:08:11,300 --> 00:08:13,430
basic uitstraling en inbrengen.

159
00:08:13,430 --> 00:08:17,010
Stel dat we wilden implementeren van een soort
van auto-complete functionaliteit, veel

160
00:08:17,010 --> 00:08:18,890
zoals Google zoekmachine doet.

161
00:08:18,890 --> 00:08:22,210
Dat wil zeggen, het geven van de sleutels en
mogelijke waarden

162
00:08:22,210 --> 00:08:24,130
hebben een bepaalde prefix.

163
00:08:24,130 --> 00:08:27,050
>> Een Trie is uitermate handig
voor deze bewerking.

164
00:08:27,050 --> 00:08:29,890
Het is eenvoudig om door te herhalen
de Trie voor elk teken van

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

166
00:08:30,950 --> 00:08:33,559
Net als een opzoeken operatie,
we konden pointers volgen

167
00:08:33,559 --> 00:08:35,400
teken voor teken.

168
00:08:35,400 --> 00:08:38,659
Dan, als we aankomen aan het einde van de
prefix, konden we doorlopen de

169
00:08:38,659 --> 00:08:42,049
resterende deel van de gegevensstructuur
omdat een van de toetsen buiten

170
00:08:42,049 --> 00:08:43,980
dit punt hebben de prefix.

171
00:08:43,980 --> 00:08:47,670
>> Het is ook gemakkelijk om deze lijst te zien
in alfabetische volgorde, omdat de

172
00:08:47,670 --> 00:08:50,970
elementen van de kinderen reeks
staan ​​op alfabetische volgorde.

173
00:08:50,970 --> 00:08:54,420
Dus hopelijk zult overwegen
geven probeert te proberen.

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

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, dit is het begin
van de daling.

177
00:09:00,790 --> 00:09:01,350
Het spijt me.

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

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

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

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

182
00:09:03,950 --> 00:09:04,360
Ik ben weg.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Sorry voor het maken van de persoon die
heeft te bewerken deze gek.

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

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

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

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

191
00:09:15,680 --> 00:09:16,280
>> LUIDSPREKER 1: Goed gedaan.

192
00:09:16,280 --> 00:09:17,530
Dat was echt goed gedaan.

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