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

2
00:00:07,700 --> 00:00:10,890
>> Kevin Schmid: Minsan, kapag pagbuo ng isang
programa, baka gusto mong ayusin ang isang

3
00:00:10,890 --> 00:00:13,190
istraktura ng data na kilala bilang isang diksiyunaryo.

4
00:00:13,190 --> 00:00:17,960
Ang isang diksyunaryo ng mga mapa susi, na mga
karaniwang mga string, sa mga halaga, ints,

5
00:00:17,960 --> 00:00:21,900
char, isang pointer sa ilang mga bagay,
kahit anong gusto namin.

6
00:00:21,900 --> 00:00:26,510
Ito ay tulad lamang ordinaryong mga diksyunaryo
mga salita na mapa sa pamamagitan ng mga kahulugan.

7
00:00:26,510 --> 00:00:29,440
>> Bigyan kami Diksyunaryo sa
kakayahang mag-imbak ng impormasyon

8
00:00:29,440 --> 00:00:32,750
na nauugnay sa isang bagay
at tumingin ito up sa ibang pagkakataon.

9
00:00:32,750 --> 00:00:36,620
Kaya paano ko talaga naming ipatupad ang
diksyunaryo sa, sabihin nating, C code na aming makakaya

10
00:00:36,620 --> 00:00:38,460
gamitin sa isa sa aming mga programa?

11
00:00:38,460 --> 00:00:41,790
Well, may mga maraming paraan na
maaari naming ipatupad ang isang diksiyunaryo.

12
00:00:41,790 --> 00:00:45,930
>> Para sa isa, maaari kaming gumamit ng isang array na namin
pabago-bago muling laki o maaari naming gamitin ang isang

13
00:00:45,930 --> 00:00:49,150
naka-link na listahan, hash talahanayan
o isang binary tree.

14
00:00:49,150 --> 00:00:52,250
Ngunit namin ang kahit anong piliin, dapat namin
maging maingat sa kahusayan at

15
00:00:52,250 --> 00:00:54,300
pagganap ng pagpapatupad.

16
00:00:54,300 --> 00:00:57,930
Dapat nating isipin ang tungkol sa algorithm na ginamit
upang ipasok at maghanap ng mga item sa mga

17
00:00:57,930 --> 00:00:59,120
ang aming istraktura ng data.

18
00:00:59,120 --> 00:01:03,060
>> Para sa ngayon, ipagpalagay na namin sa
nais na gumamit ng mga string bilang susi.

19
00:01:03,060 --> 00:01:07,290
Usapan natin ang tungkol sa isa posibilidad Hayaan,
isang istraktura ng data na tinatawag na isang trie.

20
00:01:07,290 --> 00:01:11,210
Kaya narito ang isang visual na representasyon
ng isang trie.

21
00:01:11,210 --> 00:01:14,590
>> Tulad ng sa larawan nagmumungkahi, isang trie
ay isang puno istraktura ng data sa

22
00:01:14,590 --> 00:01:16,050
node na naka-link nang sama-sama.

23
00:01:16,050 --> 00:01:19,420
Makita naming may malinaw na isang root
node na may ilang mga link pagpapalawig sa

24
00:01:19,420 --> 00:01:20,500
iba pang mga node.

25
00:01:20,500 --> 00:01:23,040
Ngunit ano ang ibig Binubuo ang bawat node ng?

26
00:01:23,040 --> 00:01:26,700
Kung ipinapalagay namin na kami ay nag-iimbak ng mga susi
may lamang pang-abakada character, at

27
00:01:26,700 --> 00:01:30,150
hindi namin pakialam tungkol sa paggamit ng malaking titik,
narito ang isang kahulugan ng isang node na

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

29
00:01:31,100 --> 00:01:34,130
>> Ang isang bagay na kung saan ang uri ay struct
na node ay may dalawang bahagi

30
00:01:34,130 --> 00:01:35,740
tinatawag na data at mga bata.

31
00:01:35,740 --> 00:01:39,200
Iniwan namin na ang mga bahagi ng data bilang isang komento
upang mapalitan sa pamamagitan ng isang component

32
00:01:39,200 --> 00:01:43,190
deklarasyon kapag struct node ay
Pinagsama-sama sa isang program na C.

33
00:01:43,190 --> 00:01:47,040
Ang bahagi ng isang node data ay maaaring maging isang
Boolean halaga upang ipahiwatig kung ang o

34
00:01:47,040 --> 00:01:51,160
hindi ang node ay kumakatawan sa pagkumpleto
sa isang key diksyunaryo o maaari itong maging isang

35
00:01:51,160 --> 00:01:54,240
na kumakatawan sa mga kahulugan string
ng isang salita sa diksyunaryo.

36
00:01:54,240 --> 00:01:58,870
>> Gagamitin namin ang isang SMILEY mukha upang ipahiwatig
kapag data ay naroroon sa isang node.

37
00:01:58,870 --> 00:02:02,310
May mga 26 mga elemento sa aming
mga bata array, isa index

38
00:02:02,310 --> 00:02:03,690
sa bawat pang-abakada character.

39
00:02:03,690 --> 00:02:06,570
Susubukan naming makita ang kabuluhan
ng ito sa lalong madaling panahon.

40
00:02:06,570 --> 00:02:10,759
>> Hayaan ang makakuha ng mas malapitan naming tingnan ng root node
sa aming diagram, na walang data

41
00:02:10,759 --> 00:02:14,740
na nauugnay dito, bilang ipinahiwatig ng
kawalan ng SMILEY mukha sa

42
00:02:14,740 --> 00:02:16,110
bahagi ng data.

43
00:02:16,110 --> 00:02:19,910
Ang mga arrow pagpapalawak ng mula sa mga bahagi ng
ang mga anak ng array ay kumakatawan non-node

44
00:02:19,910 --> 00:02:21,640
pointer sa iba pang mga node.

45
00:02:21,640 --> 00:02:25,500
Halimbawa, ang arrow sa pagpapalawak ng mula sa
ang pangalawang elemento ng mga bata

46
00:02:25,500 --> 00:02:28,400
kumakatawan sa sulat B
sa isang pangunahing diksyunaryo.

47
00:02:28,400 --> 00:02:31,920
At sa mas malaking diagram
lagyan ng label namin ito sa isang B.

48
00:02:31,920 --> 00:02:35,810
>> Tandaan na sa mas malaking diagram, kung kailan namin
gumuhit ng isang pointer sa isa pang node, ito

49
00:02:35,810 --> 00:02:39,100
Hindi mahalaga kung saan ang unahan ng pana
natutugunan na ang ibang node.

50
00:02:39,100 --> 00:02:43,850
Ang aming trie sample diksyunaryo ay naglalaman ng
dalawang salita, iyon at pag-zoom.

51
00:02:43,850 --> 00:02:47,040
Ni maglakad sa pamamagitan ng isang halimbawa ng Hayaan
hinahanap ang data para sa isang key.

52
00:02:47,040 --> 00:02:50,800
>> Ipagpalagay na gusto naming tumingin hanggang ang
kaukulang halaga para sa key bath.

53
00:02:50,800 --> 00:02:53,610
Sisimulan namin ang aming hitsura up
sa root node.

54
00:02:53,610 --> 00:02:57,870
Pagkatapos ay isasaalang-alang namin ang unang titik ng aming
key, B, at hanapin ang mga kaukulang

55
00:02:57,870 --> 00:03:00,020
makita sa ating mga anak ng array.

56
00:03:00,020 --> 00:03:04,490
Pansinin na mayroong eksaktong 26 spot
sa array, isa para sa bawat titik ng

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

58
00:03:05,330 --> 00:03:08,800
At kakailanganin naming ay kumakatawan sa mga spot ang
titik ng alpabeto sa order.

59
00:03:08,800 --> 00:03:13,960
>> Susubukan naming tumingin sa ikalawang index pagkatapos,
index ng isa, para sa B. Sa pangkalahatan, kung namin

60
00:03:13,960 --> 00:03:17,990
kumuha ng pang-abakada ng character C namin
maaaring matukoy ang nararapat na lugar

61
00:03:17,990 --> 00:03:21,520
sa mga bata array gamit
isang kalkulasyon tulad nito.

62
00:03:21,520 --> 00:03:25,140
Maaaring namin ang ginamit ng mas malaking mga bata
array kung gusto naming mag-alok hitsura up ng

63
00:03:25,140 --> 00:03:28,380
mga susi sa isang mas malawak na hanay ng mga character,
gaya ng buong

64
00:03:28,380 --> 00:03:29,880
Itakda ang mga ASCII na character.

65
00:03:29,880 --> 00:03:32,630
>> Sa kasong ito, ang pointer
sa ating mga anak array sa

66
00:03:32,630 --> 00:03:34,320
index isa ay hindi null.

67
00:03:34,320 --> 00:03:36,600
Kaya ipagpapatuloy namin ang pagtingin
up ang key bath.

68
00:03:36,600 --> 00:03:40,130
Kung sakaling aming nakatagpo ng isang null pointer
sa tamang lugar sa mga bata

69
00:03:40,130 --> 00:03:43,230
array habang kami traversed ang nodes,
pagkatapos ay kakailanganin naming sabihin na tayo

70
00:03:43,230 --> 00:03:45,630
Hindi mahanap ang anumang bagay para sa na key.

71
00:03:45,630 --> 00:03:49,370
>> Ngayon, isasaalang-alang namin ang pangalawang titik ng
ang aming key, A, at magpatuloy sumusunod

72
00:03:49,370 --> 00:03:52,400
mga payo sa paraang ito hanggang namin
maabot ang dulo ng aming key.

73
00:03:52,400 --> 00:03:56,530
Kung naabot namin ang dulo ng key nang walang
pagpindot ng anumang patay na magwakas, null pointer,

74
00:03:56,530 --> 00:03:59,730
tulad ng kaso dito, pagkatapos namin lamang
mayroon upang suriin ang isa pang bagay.

75
00:03:59,730 --> 00:04:02,110
Ay ang key na ito talaga
sa diksyunaryo?

76
00:04:02,110 --> 00:04:07,660
>> Kung gayon, dapat naming mahanap ang isang halaga, na rin ng isang
icon SMILEY mukha sa aming mga diagram kung saan

77
00:04:07,660 --> 00:04:08,750
Nagtatapos ang salita.

78
00:04:08,750 --> 00:04:12,270
Kung mayroong isang bagay pa ang naka-imbak sa
ang data, pagkatapos ay maaari naming ibalik ito.

79
00:04:12,270 --> 00:04:16,500
Halimbawa, ang key zoo ay wala sa
diksyonaryo, kahit na maaari kaming magkaroon

80
00:04:16,500 --> 00:04:19,810
Naabot ang dulo ng ang key na ito nang hindi kailanman
pagpindot ng isang null pointer, habang kami

81
00:04:19,810 --> 00:04:21,089
umulit sa pamamagitan ng trie.

82
00:04:21,089 --> 00:04:25,436
>> Kung sinubukan naming upang tumingin up ang key bath, ang
pangalawang sa array index ng huling node ni,

83
00:04:25,436 --> 00:04:28,750
naaayon sa titik H, magiging
na gaganapin isang null pointer.

84
00:04:28,750 --> 00:04:31,120
Kaya bath ay wala sa diksyonaryo.

85
00:04:31,120 --> 00:04:34,800
At kaya isang trie ay natatangi sa na ang mga key
ay hindi kailanman tahasang naka-imbak sa

86
00:04:34,800 --> 00:04:36,650
ang istraktura ng data.

87
00:04:36,650 --> 00:04:38,810
Kaya paano ko isingit kami ng isang bagay
sa isang trie?

88
00:04:38,810 --> 00:04:41,780
>> Magpasok ng key Hayaan
zoo sa aming trie.

89
00:04:41,780 --> 00:04:46,120
Alalahanin na ang isang SMILEY mukha sa isang node
maaaring Tumutugon sa code sa isang simpleng

90
00:04:46,120 --> 00:04:50,170
Boolean halaga upang isaad na zoo
ay nasa diksyunaryo o ng dati

91
00:04:50,170 --> 00:04:53,710
ay tumutugma sa higit pang impormasyon na aming
nais i-uugnay sa mga key zoo,

92
00:04:53,710 --> 00:04:56,860
tulad ng mga kahulugan ng mga
salita o iba pang dahilan.

93
00:04:56,860 --> 00:05:00,350
Sa ilang mga paraan, ang proseso upang ipasok
isang bagay sa isang trie ay katulad ng

94
00:05:00,350 --> 00:05:02,060
hinahanap ang isang bagay sa isang trie.

95
00:05:02,060 --> 00:05:05,720
>> Sisimulan naming muli gamit ang root node,
sumusunod na pointer naaayon sa

96
00:05:05,720 --> 00:05:07,990
ang mga titik sa aming mga key.

97
00:05:07,990 --> 00:05:11,310
Sa kabutihang-palad, hindi namin magagawang sundan pointer
ang lahat ng paraan hanggang naabot namin

98
00:05:11,310 --> 00:05:12,770
sa dulo ng key.

99
00:05:12,770 --> 00:05:16,480
Dahil zoo ay isang unlapi ng salitang
zoom, na kung saan ay isang miyembro ng

100
00:05:16,480 --> 00:05:19,440
diksyonaryo, hindi namin kailangan upang
magtalaga ng anumang bagong mga node.

101
00:05:19,440 --> 00:05:23,140
>> Maaari naming baguhin ang node upang isaad na
ang landas ng mga character na humahantong sa

102
00:05:23,140 --> 00:05:25,360
ito ay kumakatawan sa isang susi sa aming diksiyunaryo.

103
00:05:25,360 --> 00:05:28,630
Ngayon, Subukan nating pagpasok hayaan ang
key bath sa trie.

104
00:05:28,630 --> 00:05:32,260
Sisimulan naming sa root node
at sundin ang mga payo muli.

105
00:05:32,260 --> 00:05:35,620
Ngunit sa sitwasyong ito, pindutin namin ang isang patay
tapusin bago namin magawang upang makakuha ng sa

106
00:05:35,620 --> 00:05:36,940
dulo ng key.

107
00:05:36,940 --> 00:05:40,980
Ngayon, kailangan namin upang maglaan ng ilang bagong
node na kailangang maglaan ng isang bagong

108
00:05:40,980 --> 00:05:43,660
na node para sa bawat natitirang
sulat ng aming key.

109
00:05:43,660 --> 00:05:46,740
>> Sa kasong ito, kailangan namin lamang
upang magtalaga ng isang bagong node.

110
00:05:46,740 --> 00:05:50,590
Pagkatapos ay kakailanganin naming gawin ang index H
isangguni ang bagong node.

111
00:05:50,590 --> 00:05:54,070
Muli, maaari naming baguhin ang node sa
magpahiwatig na ang landas ng mga character

112
00:05:54,070 --> 00:05:57,120
na humahantong sa ito ay kumakatawan sa isang
susi sa aming diksiyunaryo.

113
00:05:57,120 --> 00:06:00,730
Ni Dahilan tungkol sa asymptotic Hayaan
kasalimuotan ng aming mga pamamaraan para sa mga

114
00:06:00,730 --> 00:06:02,110
dalawang mga operasyon.

115
00:06:02,110 --> 00:06:06,420
>> Napansin namin na sa parehong mga sitwasyon ang bilang
ng steps aming algorithm kinuha ay

116
00:06:06,420 --> 00:06:09,470
proporsyonal sa bilang ng mga
mga titik sa keyword.

117
00:06:09,470 --> 00:06:10,220
Tama iyon.

118
00:06:10,220 --> 00:06:13,470
Kapag nais mong maghanap ng isang salita sa isang
trie kailangan mo lamang upang umulit sa pamamagitan ng

119
00:06:13,470 --> 00:06:17,100
ang mga titik ng isa sa pamamagitan ng isa hanggang mong alinman sa
maabot ang dulo ng salita o

120
00:06:17,100 --> 00:06:19,060
hit ang isang patay na dulo sa trie.

121
00:06:19,060 --> 00:06:22,470
>> At kapag nais mo upang magpasok ng isang key
halaga ng pareho sa isang trie gamit ang

122
00:06:22,470 --> 00:06:26,250
pamamaraan namin tinalakay, ang pinakamasama kaso
Magkakaroon ka paglaan ng isang bagong node

123
00:06:26,250 --> 00:06:27,550
para sa bawat titik.

124
00:06:27,550 --> 00:06:31,290
At makikita naming ipagpalagay na laang-gugulin
ay patuloy na operasyon ng panahon.

125
00:06:31,290 --> 00:06:35,850
Kaya kung ipinapalagay namin na ang mga key na haba ay
bounded sa pamamagitan ng isang nakapirming pare-pareho, parehong

126
00:06:35,850 --> 00:06:39,400
pagpapasok at tumingin up ay pare-pareho
mga pagpapatakbo ng oras para sa isang trie.

127
00:06:39,400 --> 00:06:42,930
>> Kung hindi kami gumawa ito palagay na
ang haba ng pindutan ay bounded sa pamamagitan ng isang nakapirming

128
00:06:42,930 --> 00:06:46,650
pare-pareho, pagkatapos ay pagpapasok at tumingin up,
sa pinakamasama kaso, ay linear sa

129
00:06:46,650 --> 00:06:48,240
haba ng key.

130
00:06:48,240 --> 00:06:51,800
Pansinin na ang bilang ng mga item na naka-imbak
sa trie ay hindi nakakaapekto sa hitsura up

131
00:06:51,800 --> 00:06:52,820
o oras pagpapasok.

132
00:06:52,820 --> 00:06:55,360
Ito ay naapektuhan lamang ng
haba ng key.

133
00:06:55,360 --> 00:06:59,300
>> Sa pamamagitan ng kaibahan, ang pagdaragdag ng mga entry sa, sabihin nating,
isang hash talahanayan ay may gawi na gumawa

134
00:06:59,300 --> 00:07:01,250
hinaharap maghanap ng mas mabagal.

135
00:07:01,250 --> 00:07:04,520
Habang ito ay maaaring tunog akit sa una,
dapat naming panatilihin sa isip na ang isang

136
00:07:04,520 --> 00:07:08,740
kanais-nais na asymptotic pagiging kumplikado ay hindi
ibig sabihin na sa pagsasanay ang data

137
00:07:08,740 --> 00:07:11,410
istraktura ay kinakailangang
lampas pagsisi.

138
00:07:11,410 --> 00:07:15,860
Dapat din namin isaalang-alang na mag-imbak ng isang
salita sa isang trie kailangan namin, sa pinakamalala

139
00:07:15,860 --> 00:07:19,700
kaso, ang isang bilang ng mga node proporsyonal
sa haba ng salita mismo.

140
00:07:19,700 --> 00:07:21,880
>> Pagsusubok na may posibilidad na gumamit ng maraming espasyo.

141
00:07:21,880 --> 00:07:25,620
Iyon ay sa kabilang banda sa isang hash talahanayan,
kung saan kailangan lamang namin ang isa bagong node sa

142
00:07:25,620 --> 00:07:27,940
mag-imbak ng ilang mga pangunahing pares halaga.

143
00:07:27,940 --> 00:07:31,370
Ngayon, muli sa teorya, malaking puwang
pagkonsumo ay hindi tila tulad ng isang malaking

144
00:07:31,370 --> 00:07:34,620
harapin, lalo na ibinigay na modernong
mga computer mayroon gigabytes at

145
00:07:34,620 --> 00:07:36,180
gigabytes ng memorya.

146
00:07:36,180 --> 00:07:39,200
Ngunit ito ay lumiliko out na mayroon pa rin namin
upang mag-alala tungkol sa paggamit ng memory at

147
00:07:39,200 --> 00:07:42,540
samahan alang-alang sa
pagganap, dahil ang mga modernong mga computer

148
00:07:42,540 --> 00:07:46,960
mayroon mekanismo sa lugar sa ilalim ng
hood upang mapabilis ang memory access.

149
00:07:46,960 --> 00:07:51,180
>> Ngunit ang mga mekanismo ang pinakamahusay na gumagana kapag
uma-access ng memory ay gawa sa compact

150
00:07:51,180 --> 00:07:52,810
rehiyon o lugar.

151
00:07:52,810 --> 00:07:55,910
At ang mga node ng isang trie maaaring manirahan
kahit saan sa na magbunton.

152
00:07:55,910 --> 00:07:58,390
Ngunit ang mga ito ay mga trade-off
na kailangan naming isaalang-alang.

153
00:07:58,390 --> 00:08:01,440
>> Tandaan na, kapag pumipili ng data
istraktura para sa isang tiyak na gawain, kami

154
00:08:01,440 --> 00:08:04,420
dapat isipin ang tungkol sa kung anong mga uri ng
pagpapatakbo kailangan ng istraktura ng data sa

155
00:08:04,420 --> 00:08:07,140
suporta at kung magkano ang pagganap
ng bawat isa sa mga

156
00:08:07,140 --> 00:08:09,080
mga usapin pagpapatakbo sa amin.

157
00:08:09,080 --> 00:08:11,300
Ang mga pagpapatakbo ay maaaring kahit na
mapalawak nang higit lamang

158
00:08:11,300 --> 00:08:13,430
pangunahing hitsura up at pagpapasok.

159
00:08:13,430 --> 00:08:17,010
Ipagpalagay na gusto naming ipatupad ang uri
ng auto-complete-andar, magkano

160
00:08:17,010 --> 00:08:18,890
tulad ng Google search engine na gumagana.

161
00:08:18,890 --> 00:08:22,210
Iyon ay, bumalik ang lahat ng mga pindutan at mga
potensyal na mga halaga na

162
00:08:22,210 --> 00:08:24,130
magkaroon ng isang naibigay na prefix.

163
00:08:24,130 --> 00:08:27,050
>> Ang isang trie ay katangi-tangi kapaki-pakinabang
para sa operasyong ito.

164
00:08:27,050 --> 00:08:29,890
Ito ay tuwiran upang umulit sa pamamagitan ng
ang trie para sa bawat katangian ng

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

166
00:08:30,950 --> 00:08:33,559
Tulad ng isang tumingin hanggang operasyon,
maaari naming sundin ang mga payo

167
00:08:33,559 --> 00:08:35,400
ng character ng character.

168
00:08:35,400 --> 00:08:38,659
Pagkatapos, kapag dumating kami sa dulo ng
prefix, maaari kaming umulit sa pamamagitan ng

169
00:08:38,659 --> 00:08:42,049
natitirang bahagi ng istraktura ng data
dahil alinman sa ang mga key na lampas

170
00:08:42,049 --> 00:08:43,980
puntong ito ay may prefix.

171
00:08:43,980 --> 00:08:47,670
>> Ito ay madali ring upang makuha ang listahan na ito
sa alpabetong pagkakasunud-sunod mula noong

172
00:08:47,670 --> 00:08:50,970
mga elemento ng mga bata array
ay nakaayos ayon sa alpabeto.

173
00:08:50,970 --> 00:08:54,420
Kaya sana ay makikita mo isaalang-alang
pagbibigay sinusubukan ng isang try.

174
00:08:54,420 --> 00:08:56,085
Ako Kevin Schmid, at ito ay CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, ito ang simula
ng pagtanggi.

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

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 apat.

182
00:09:03,950 --> 00:09:04,360
Ako out.

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
Paumanhin para sa paggawa ng mga taong nag-
May upang i-edit ito mabaliw.

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
>> Tagapagsalita 1: Magaling.

192
00:09:16,280 --> 00:09:17,530
Iyon ay talagang magaling.

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