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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Niekedy, pri stavbe
Program, možno budete chcieť využiť

3
00:00:10,890 --> 00:00:13,190
dátové štruktúry známe ako slovník.

4
00:00:13,190 --> 00:00:17,960
Slovník kľúče mapy, ktoré sú
zvyčajne reťazca, hodnôt, ints,

5
00:00:17,960 --> 00:00:21,900
znaky, ukazovateľ na nejaký predmet,
čo chceme.

6
00:00:21,900 --> 00:00:26,510
Je to ako obyčajné slovníky
že mapa slová cez definícií.

7
00:00:26,510 --> 00:00:29,440
>> Slovníky nám poskytujú
schopnosť ukladať informácie

8
00:00:29,440 --> 00:00:32,750
spojené s niečím
a pozrieť sa na to neskôr.

9
00:00:32,750 --> 00:00:36,620
Tak ako sme sa vlastne vykonávať
slovník, povedzme, C kódu, ktorý môžeme

10
00:00:36,620 --> 00:00:38,460
použitie v jednom z našich programov?

11
00:00:38,460 --> 00:00:41,790
No, existuje mnoho spôsobov, ako
by sme mohli realizovať slovník.

12
00:00:41,790 --> 00:00:45,930
>> Pre jedného, ​​mohli by sme použiť pole, ktoré sme
dynamicky re-size, alebo môžeme použiť

13
00:00:45,930 --> 00:00:49,150
spájať zoznam, hash tabuľka
alebo binárny strom.

14
00:00:49,150 --> 00:00:52,250
Ale nech si vyberieme, mali by sme
dbať na efektivitu a

15
00:00:52,250 --> 00:00:54,300
výkon implementácie.

16
00:00:54,300 --> 00:00:57,930
Mali by sme premýšľať o použitom algoritme
vložiť a vyhľadať položky do

17
00:00:57,930 --> 00:00:59,120
naše dátová štruktúra.

18
00:00:59,120 --> 00:01:03,060
>> Teraz predpokladajme, že sme
chcete používať reťazca ako kľúče.

19
00:01:03,060 --> 00:01:07,290
Poďme sa baviť o jednej z možností,
dátová štruktúra sa nazýva trie.

20
00:01:07,290 --> 00:01:11,210
Tak tu je vizuálna reprezentácia
z trie.

21
00:01:11,210 --> 00:01:14,590
>> Ako obrázok naznačuje, trie
je dátový stromová štruktúra s

22
00:01:14,590 --> 00:01:16,050
uzly spojené.

23
00:01:16,050 --> 00:01:19,420
Vidíme, že tam je jasne koreň
Uzol sa niektoré odkazy sa rozširuje

24
00:01:19,420 --> 00:01:20,500
ostatné uzly.

25
00:01:20,500 --> 00:01:23,040
Ale to, čo robí každý uzol sa skladá z?

26
00:01:23,040 --> 00:01:26,700
Ak budeme predpokladať, že sme ukladanie kľúčov
s iba abecedné znaky, a

27
00:01:26,700 --> 00:01:30,150
my sa nestaráme o kapitalizácii,
Tu je definícia uzla, ktorý

28
00:01:30,150 --> 00:01:31,100
bude stačiť.

29
00:01:31,100 --> 00:01:34,130
>> Objekt, ktorého typ struct
uzol má dve časti

30
00:01:34,130 --> 00:01:35,740
volal dát a deti.

31
00:01:35,740 --> 00:01:39,200
Nechali sme časť dát ako komentár
byť nahradená zložkou

32
00:01:39,200 --> 00:01:43,190
Vyhlásenie keď struct uzol je
začlenené do programu C.

33
00:01:43,190 --> 00:01:47,040
Dátová časť uzla môže byť
Logická hodnota označujúci, či alebo

34
00:01:47,040 --> 00:01:51,160
Nie je uzol reprezentuje dokončenie
zo slovníka kľúče, alebo by to mohlo byť

35
00:01:51,160 --> 00:01:54,240
Reťazec predstavujúce definíciu
na slová v slovníku.

36
00:01:54,240 --> 00:01:58,870
>> Budeme používať smajlíky ukázať
, Ak je prítomná dát v uzle.

37
00:01:58,870 --> 00:02:02,310
Existuje 26 prvkov v našom
deti poľa, jeden index

38
00:02:02,310 --> 00:02:03,690
podľa abecedy.

39
00:02:03,690 --> 00:02:06,570
Uvidíme význam
z toho čoskoro.

40
00:02:06,570 --> 00:02:10,759
>> Poďme sa bližšie pozrieť na koreňový uzol
v našom diagrame, ktorý nemá žiadne dáta

41
00:02:10,759 --> 00:02:14,740
spojené s tým, ako je uvedené
absencia smajlíka v

42
00:02:14,740 --> 00:02:16,110
Dátová časť.

43
00:02:16,110 --> 00:02:19,910
Šípky vyčnievať z častí
Deti pole reprezentujú non-uzol

44
00:02:19,910 --> 00:02:21,640
odkazy na iné uzly.

45
00:02:21,640 --> 00:02:25,500
Napríklad, šípka siahajúce od
druhý prvok detí

46
00:02:25,500 --> 00:02:28,400
predstavuje písmeno B
v slovníku kľúč.

47
00:02:28,400 --> 00:02:31,920
A vo väčšom diagrame
sme to označenie s B.

48
00:02:31,920 --> 00:02:35,810
>> Všimnite si, že v širšom schéme, kedy sme
nakresliť ukazovateľ do iného uzla, je

49
00:02:35,810 --> 00:02:39,100
Nezáleží na tom, kde sa šípka
odpovedá, že iný uzol.

50
00:02:39,100 --> 00:02:43,850
Náš vzorka slovník trie obsahuje
dve slová, ktorá aj zoom.

51
00:02:43,850 --> 00:02:47,040
Poďme sa prejsť príklad
vyhľadávanie dát na kľúč.

52
00:02:47,040 --> 00:02:50,800
>> Predpokladajme, že sme sa chceli pozrieť do
zodpovedajúcu hodnotu kľúča kúpele.

53
00:02:50,800 --> 00:02:53,610
Začneme náš pohľad hore
na koreňový uzol.

54
00:02:53,610 --> 00:02:57,870
Potom budeme mať prvé písmeno nášho
kľúč, B, a nájsť zodpovedajúce

55
00:02:57,870 --> 00:03:00,020
mieste v našom deti poli.

56
00:03:00,020 --> 00:03:04,490
Všimnite si, že tam je presne 26 miest
v poli, jeden pre každé písmeno

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

58
00:03:05,330 --> 00:03:08,800
A budeme mať škvrny predstavujú
písmená abecedy v poradí.

59
00:03:08,800 --> 00:03:13,960
>> My sa pozrieme na druhý index potom,
index jeden, pre B. Všeobecne platí, že ak by sme

60
00:03:13,960 --> 00:03:17,990
nejaké abecedný znak C my
by mohla stanoviť zodpovedajúce miesto

61
00:03:17,990 --> 00:03:21,520
v detskom poľa pomocou
Výpočet takto.

62
00:03:21,520 --> 00:03:25,140
Mohli sme použiť väčšie deti
pole, ak by sme chceli ponúknuť look up

63
00:03:25,140 --> 00:03:28,380
kľúče s širším rozsahu znakov,
ako je celé

64
00:03:28,380 --> 00:03:29,880
Znaková sada ASCII.

65
00:03:29,880 --> 00:03:32,630
>> V tomto prípade, ukazovateľ
v našom deti poľa v

66
00:03:32,630 --> 00:03:34,320
index jeden nie je null.

67
00:03:34,320 --> 00:03:36,600
Takže budeme naďalej hľadať
up kľúče kúpele.

68
00:03:36,600 --> 00:03:40,130
Ak sa niekedy stretli nulový ukazovateľ
na správnom mieste, u detí

69
00:03:40,130 --> 00:03:43,230
pole, keď sme sa prejsť uzly,
potom budeme musieť povedať, že sme

70
00:03:43,230 --> 00:03:45,630
nemohol nájsť nič pre tento kľúč.

71
00:03:45,630 --> 00:03:49,370
>> Teraz budeme mať druhý list
náš kľúč, a ďalej po

72
00:03:49,370 --> 00:03:52,400
ukazovatele týmto spôsobom, kým sa
dostať sa na koniec nášho kľúče.

73
00:03:52,400 --> 00:03:56,530
Ak sa dostanete na koniec kľúča, bez toho, aby
zasiahla všetky slepej uličky, null ukazovatele,

74
00:03:56,530 --> 00:03:59,730
ako je tomu v tomto prípade, potom iba
je nutné skontrolovať ešte jednu vec.

75
00:03:59,730 --> 00:04:02,110
Je to kľúč skutočne
v slovníku?

76
00:04:02,110 --> 00:04:07,660
>> Ak áno, mali by sme nájsť hodnotu, dobre
smiley ikona tvár v našom diagrame, kde

77
00:04:07,660 --> 00:04:08,750
slovo končí.

78
00:04:08,750 --> 00:04:12,270
Ak tam je niečo iné, ukladajú sa
dáta, potom sa môžeme vrátiť.

79
00:04:12,270 --> 00:04:16,500
Napríklad, kľúč nie je v zoo
slovník, aj keď sme mohli mať

80
00:04:16,500 --> 00:04:19,810
dosiahol na konci tohto kľúča, bez toho, aby
biť nulový ukazovateľ, zatiaľ čo my

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

82
00:04:21,089 --> 00:04:25,436
>> Ak sme sa snažili vyhľadať kľúčové kúpeľ,
Druhý index poľa minulého uzla,

83
00:04:25,436 --> 00:04:28,750
zodpovedajúce písmeno H, by
držali nulový ukazovateľ.

84
00:04:28,750 --> 00:04:31,120
Takže kúpeľ nie je v slovníku.

85
00:04:31,120 --> 00:04:34,800
A tak trie je unikátny v tom, že kľúče
sa nikdy výslovne uložené v

86
00:04:34,800 --> 00:04:36,650
dátová štruktúra.

87
00:04:36,650 --> 00:04:38,810
Tak ako sme sa vložiť niečo
do trie?

88
00:04:38,810 --> 00:04:41,780
>> Poďme vložte kľúč
zoo do nášho trie.

89
00:04:41,780 --> 00:04:46,120
Pamätajte si, že smajlíky v uzle
mohla odpovedať v kóde na jednoduchej

90
00:04:46,120 --> 00:04:50,170
Boolovská hodnota, ktorá naznačujú, že zoo
je v slovníku, alebo by to mohlo

91
00:04:50,170 --> 00:04:53,710
zodpovedajú viac informácií, ktoré sme
chcete spojiť s kľúčovým zoo,

92
00:04:53,710 --> 00:04:56,860
ako vymedzenie
Slovo alebo niečo iné.

93
00:04:56,860 --> 00:05:00,350
V niektorých ohľadoch, proces vložiť
niečo do trie je podobný

94
00:05:00,350 --> 00:05:02,060
hľadá niečo v trie.

95
00:05:02,060 --> 00:05:05,720
>> Začneme s koreňový uzol znovu,
Nasledujúce ukazovatele zodpovedá

96
00:05:05,720 --> 00:05:07,990
listy z našich kľúčových.

97
00:05:07,990 --> 00:05:11,310
Našťastie sme boli schopní sledovať ukazovatele
celú cestu až sme dorazili do

98
00:05:11,310 --> 00:05:12,770
koniec kľúča.

99
00:05:12,770 --> 00:05:16,480
Vzhľadom k tomu, zoo je prefix slová
zoom, ktorý je členom

100
00:05:16,480 --> 00:05:19,440
slovník, nepotrebujeme, aby
prideliť žiadne nové uzly.

101
00:05:19,440 --> 00:05:23,140
>> Môžeme upraviť uzol čo znamená, že
cesta znakov, ktoré vedú k

102
00:05:23,140 --> 00:05:25,360
predstavuje kľúč v našom slovníku.

103
00:05:25,360 --> 00:05:28,630
Teraz skúsme vloženie
Kľúčovým BATH do trie.

104
00:05:28,630 --> 00:05:32,260
Začneme na koreňový uzol
a sledovať ukazovatele znova.

105
00:05:32,260 --> 00:05:35,620
Ale v tejto situácii, zasiahla sme mŕtvy
skončí skôr, než sme schopní sa dostať do

106
00:05:35,620 --> 00:05:36,940
koniec kľúča.

107
00:05:36,940 --> 00:05:40,980
Teraz budeme musieť prideliť niektoré nové
uzly budú musieť prideliť jednu novú

108
00:05:40,980 --> 00:05:43,660
uzol pre každý zostávajúci
List z nášho kľúča.

109
00:05:43,660 --> 00:05:46,740
>> V tomto prípade, my jednoducho potrebujeme
prideliť jeden nový uzol.

110
00:05:46,740 --> 00:05:50,590
Potom budeme potrebovať, aby index H
odkázanie na nový uzol.

111
00:05:50,590 --> 00:05:54,070
Opäť môžeme zmeniť uzol
ukazujú, že cesta znakov

112
00:05:54,070 --> 00:05:57,120
čo vedie k tomu predstavuje
kľúč v našom slovníku.

113
00:05:57,120 --> 00:06:00,730
Poďme uvažovať o asymptotickej
Komplexnosť našich postupov pre tieto

114
00:06:00,730 --> 00:06:02,110
dve operácie.

115
00:06:02,110 --> 00:06:06,420
>> Všimli sme si, že v oboch prípadoch číslo
z krokov náš algoritmus trvalo bola

116
00:06:06,420 --> 00:06:09,470
úmerná počtu
Písmená na kľúčové slovo.

117
00:06:09,470 --> 00:06:10,220
To je pravda.

118
00:06:10,220 --> 00:06:13,470
Ak chcete vyhľadať slovo v
trie stačí iterovat

119
00:06:13,470 --> 00:06:17,100
listy jeden po druhom, kým buď
dostanete na koniec slova, alebo

120
00:06:17,100 --> 00:06:19,060
hit slepej uličky v trie.

121
00:06:19,060 --> 00:06:22,470
>> A keď budete chcieť vložiť kľúč
hodnota dvojice do trie pomocou

122
00:06:22,470 --> 00:06:26,250
Postup sme diskutovali, najhorší prípad
bude vám pridelenie nového uzla

123
00:06:26,250 --> 00:06:27,550
pre každé písmeno.

124
00:06:27,550 --> 00:06:31,290
A budeme predpokladať, že rozdelenie
je konštantný čas prevádzky.

125
00:06:31,290 --> 00:06:35,850
Takže ak budeme predpokladať, že dĺžka kľúča je
ohraničená pevnú konštantou, a to ako

126
00:06:35,850 --> 00:06:39,400
vkladanie a vyhľadať konštantný
časové operácie pre trie.

127
00:06:39,400 --> 00:06:42,930
>> Ak sa nám nepodarí túto domnienku, že
dĺžka kľúča je ohraničená pevnú

128
00:06:42,930 --> 00:06:46,650
konštantný, potom sa po vložení a pozerať sa,
V najhoršom prípade, sú lineárne v

129
00:06:46,650 --> 00:06:48,240
dĺžka kľúča.

130
00:06:48,240 --> 00:06:51,800
Všimnite si, že počet položiek, uložené
v trie nemá vplyv na vzhľad hore

131
00:06:51,800 --> 00:06:52,820
alebo vloženie čas.

132
00:06:52,820 --> 00:06:55,360
Je to len vplyv
dĺžka kľúča.

133
00:06:55,360 --> 00:06:59,300
>> Naopak, pridávanie položiek, povedzme,
hash tabuľky vedie k tomu,

134
00:06:59,300 --> 00:07:01,250
budúcnosť vyzerať pomalšie.

135
00:07:01,250 --> 00:07:04,520
Aj keď to môže znieť ako lákavá na prvý pohľad,
by sme mali mať na pamäti, že

136
00:07:04,520 --> 00:07:08,740
priaznivé Asymptotická zložitosť nie je
znamená, že v praxi sú dáta

137
00:07:08,740 --> 00:07:11,410
štruktúra je nutne
nič vytknúť.

138
00:07:11,410 --> 00:07:15,860
Musíme tiež vziať do úvahy, že na ukladanie
slovo v trie potrebujeme, v najhoršom

139
00:07:15,860 --> 00:07:19,700
prípad, počet uzlov úmerná
k dĺžke slova.

140
00:07:19,700 --> 00:07:21,880
>> Pokúsi majú tendenciu používať veľa priestoru.

141
00:07:21,880 --> 00:07:25,620
To je na rozdiel od hash tabuľky,
kde budeme potrebovať iba jeden nový uzol

142
00:07:25,620 --> 00:07:27,940
uložiť niektoré dvojice kľúč hodnota.

143
00:07:27,940 --> 00:07:31,370
Teraz, opäť teoreticky, veľký priestor
Spotreba nevyzerá ako veľký

144
00:07:31,370 --> 00:07:34,620
riešiť, a to najmä vzhľadom na to, moderné
počítače majú gigabajtov a

145
00:07:34,620 --> 00:07:36,180
GB pamäte.

146
00:07:36,180 --> 00:07:39,200
Ale ukázalo sa, že máme stále
sa starať o využitie pamäte a

147
00:07:39,200 --> 00:07:42,540
organizácie v záujme
výkon, pretože moderné počítače

148
00:07:42,540 --> 00:07:46,960
majú mechanizmy v mieste pod
kapucňa urýchliť prístup do pamäte.

149
00:07:46,960 --> 00:07:51,180
>> Ale tieto mechanizmy fungujú najlepšie, keď
pamäťové prístupy sú v kompaktnom

150
00:07:51,180 --> 00:07:52,810
regióny alebo oblasti.

151
00:07:52,810 --> 00:07:55,910
A uzly trie mohla zdržiavať
kdekoľvek v tejto hromade.

152
00:07:55,910 --> 00:07:58,390
Ale to sú kompromisy
že musíme vziať do úvahy.

153
00:07:58,390 --> 00:08:01,440
>> Pamätajte si, že pri výbere dát
štruktúra pre určitú úlohu, sa

154
00:08:01,440 --> 00:08:04,420
by mal premýšľať o tom, aké druhy
operácie dátová štruktúra musí

155
00:08:04,420 --> 00:08:07,140
Podpora a koľko výkonu
každého z nich

156
00:08:07,140 --> 00:08:09,080
operácie záleží na nás.

157
00:08:09,080 --> 00:08:11,300
Tieto operácie môžu dokonca
presahujú len

158
00:08:11,300 --> 00:08:13,430
Základný vzhľad a vloženie.

159
00:08:13,430 --> 00:08:17,010
Predpokladajme, že by sme chceli zaviesť akúsi
automatického dokončovania funkcií, veľa

160
00:08:17,010 --> 00:08:18,890
ako vyhľadávač Google robí.

161
00:08:18,890 --> 00:08:22,210
To znamená, že vráti všetky kľúče a
potenciálne hodnoty, ktoré

162
00:08:22,210 --> 00:08:24,130
majú danú predponu.

163
00:08:24,130 --> 00:08:27,050
>> Trie je jednoznačne užitočná
pre túto operáciu.

164
00:08:27,050 --> 00:08:29,890
Je to jednoduché iterácii
trie pre každý znak

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

166
00:08:30,950 --> 00:08:33,559
Rovnako ako sa pozrieť do prevádzky,
sme mohli sledovať ukazovatele

167
00:08:33,559 --> 00:08:35,400
znak po znaku.

168
00:08:35,400 --> 00:08:38,659
Potom, keď dorazíme na koniec
prefix, môžeme iterovat

169
00:08:38,659 --> 00:08:42,049
Zostávajúca časť dátovej štruktúry
pretože každá z kľúčov po

170
00:08:42,049 --> 00:08:43,980
Tento bod má predponu.

171
00:08:43,980 --> 00:08:47,670
>> Je tiež ľahké získať tento zápis
v abecednom poradí od

172
00:08:47,670 --> 00:08:50,970
prvky detského pole
sú radené abecedne.

173
00:08:50,970 --> 00:08:54,420
Takže dúfajme, že budete uvažovať
dávanie sa snaží vyskúšať.

174
00:08:54,420 --> 00:08:56,085
Ja som Kevin Schmid, a to je CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ach, to je začiatok
poklesu.

177
00:09:00,790 --> 00:09:01,350
Je mi to ľúto.

178
00:09:01,350 --> 00:09:01,870
Prepáčte.

179
00:09:01,870 --> 00:09:02,480
Prepáčte.

180
00:09:02,480 --> 00:09:03,130
Prepáčte.

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

182
00:09:03,950 --> 00:09:04,360
Som mimo.

183
00:09:04,360 --> 00:09:05,280
Prepáčte.

184
00:09:05,280 --> 00:09:06,500
Prepáčte.

185
00:09:06,500 --> 00:09:07,490
Prepáčte.

186
00:09:07,490 --> 00:09:12,352
Ospravedlňujeme sa za osobu, ktorá
ak má upraviť tento zblázniť.

187
00:09:12,352 --> 00:09:13,280
>> Prepáčte.

188
00:09:13,280 --> 00:09:13,880
Prepáčte.

189
00:09:13,880 --> 00:09:15,080
Prepáčte.

190
00:09:15,080 --> 00:09:15,680
Prepáčte.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Výborne.

192
00:09:16,280 --> 00:09:17,530
To bolo naozaj dobre.

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