1
00:00:00,000 --> 00:00:02,994
>> [MUSIC nagpe-play]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Kaya namin na-inching mas malapit
at mas malapit na banal na Kopita ng data

4
00:00:08,550 --> 00:00:13,050
kaayusan, isa na maaari naming ipasok
sa, tanggalin mula sa, at maghanap ng

5
00:00:13,050 --> 00:00:15,440
nasa tapat na oras.

6
00:00:15,440 --> 00:00:16,270
Right.

7
00:00:16,270 --> 00:00:17,280
Iyan ay ang uri ng layunin.

8
00:00:17,280 --> 00:00:19,720
Gusto naming magawa
mga bagay na tunay, tunay mabilis.

9
00:00:19,720 --> 00:00:22,580
>> May natagpuan namin ito dito kapag
pinag-uusapan natin ang tungkol sa mga sumusubok?

10
00:00:22,580 --> 00:00:23,670
Well, sabihin kumuha ng isang hitsura.

11
00:00:23,670 --> 00:00:25,628
Kaya nakita namin ang ilang mga
iba't ibang kayarian ng data

12
00:00:25,628 --> 00:00:28,680
na panghawakan ang mga pagmamapa ng
tinatawag na mga pares ng key-value,

13
00:00:28,680 --> 00:00:32,080
paggawa ng mga mapa sa ilang piraso ng data
sa ilang iba pang mga piraso ng data

14
00:00:32,080 --> 00:00:36,020
upang malaman namin kung saan makikita ang
impormasyon sa istraktura.

15
00:00:36,020 --> 00:00:40,060
>> Kaya para sa array, halimbawa, ang
key ay ang index elemento o array

16
00:00:40,060 --> 00:00:42,600
lokasyon 0 o array 1 at iba pa.

17
00:00:42,600 --> 00:00:46,140
At ang halaga ay ang data
na umiiral sa lokasyon na iyon.

18
00:00:46,140 --> 00:00:48,550
Kaya kung ano ang naka-imbak sa array 0?

19
00:00:48,550 --> 00:00:54,290
Ano ay naka-imbak sa array 1 laban lamang
0 at 1, na kung saan ay ang susi.

20
00:00:54,290 --> 00:00:56,360
>> Sa pamamagitan ng isang hash table ito ay
uri ng parehong ideya.

21
00:00:56,360 --> 00:01:00,690
Sa pamamagitan ng isang hash table, taglay namin ang hash
function na bumubuo hash code.

22
00:01:00,690 --> 00:01:03,670
Kaya ang susi ay ang hash code ng data.

23
00:01:03,670 --> 00:01:06,530
At ang halaga, lalo na
usapan natin ang tungkol pagdudugtong

24
00:01:06,530 --> 00:01:10,590
sa video sa hash talahanayan,
ay na-link na listahan ng data

25
00:01:10,590 --> 00:01:12,550
na hash sa na hashcode.

26
00:01:12,550 --> 00:01:14,050
Right.

27
00:01:14,050 --> 00:01:16,050
Paano ang tungkol sa iba pang diskarte
ang paraan na ito, kahit na?

28
00:01:16,050 --> 00:01:21,000
Ano ang tungkol sa isang paraan kung saan ang
key ay garantisadong maging natatangi,

29
00:01:21,000 --> 00:01:25,410
hindi katulad ng isang hash table, kung saan maaari namin
end up sa dalawang piraso ng data

30
00:01:25,410 --> 00:01:27,200
pagkakaroon ng parehong hashcode.

31
00:01:27,200 --> 00:01:30,020
At pagkatapos kami ay may sa pakikitungo sa
na sa pamamagitan ng alinman sa probing o higit pa

32
00:01:30,020 --> 00:01:33,340
mas mabuti ang pagdudugtong upang ayusin ang problema.

33
00:01:33,340 --> 00:01:37,520
>> Kaya ngayon maaari naming garantiya
na ang aming mga key ay kakaiba.

34
00:01:37,520 --> 00:01:39,690
At paano kung ang aming halaga ay
isang bagay na tulad ng madaling

35
00:01:39,690 --> 00:01:44,080
bilang tunay at huwad na nagsasabi sa amin kung
o hindi na piraso ng impormasyon

36
00:01:44,080 --> 00:01:45,610
umiiral sa istraktura?

37
00:01:45,610 --> 00:01:48,180
Ang isang Boolean maaaring maging kasing simple ng isang bit.

38
00:01:48,180 --> 00:01:52,660
Realistically ito ay maaring isang
byte mas malamang kaysa sa isang bit.

39
00:01:52,660 --> 00:01:55,410
Ngunit iyon lamang ang isang pulutong na mas maliit sa
pagtatabi marahil ng isang 50-character string,

40
00:01:55,410 --> 00:01:57,360
Halimbawa.

41
00:01:57,360 --> 00:02:02,210
>> Kaya sumusubok, katulad ng hash talahanayan,
na kung saan pinagsama array at naka-link na listahan,

42
00:02:02,210 --> 00:02:05,790
pagsamahin ang mga pagsusubok na array,
istruktura, at mga payo

43
00:02:05,790 --> 00:02:08,509
sama-sama upang mag-imbak ng data sa
isang kawili-wiling paraan na

44
00:02:08,509 --> 00:02:11,550
medyo iba mula sa
anumang bagay na nakita namin sa ngayon.

45
00:02:11,550 --> 00:02:16,750
Ngayon kami ay gumagamit ng data bilang isang roadmap
upang mag-navigate ito istraktura ng data.

46
00:02:16,750 --> 00:02:18,710
At kung maaari naming sundin
ang roadmap, kung maaari naming

47
00:02:18,710 --> 00:02:22,390
sundin ang mga data mula sa
simula sa dulo, bibigyan namin ng

48
00:02:22,390 --> 00:02:24,945
alam kung na data
umiiral sa trie.

49
00:02:24,945 --> 00:02:28,310
>> At kapag hindi namin na sundin ang mga mapa
mula sa ibig sabihin sa mga end sa lahat,

50
00:02:28,310 --> 00:02:30,600
hindi maaaring umiiral ang data.

51
00:02:30,600 --> 00:02:32,890
Muli, ang mga susi dito ay
garantisadong maging kakaiba.

52
00:02:32,890 --> 00:02:36,020
At kaya hindi katulad ng isang hash table, bibigyan namin ng hindi kailanman
kailangang harapin ang mga banggaan dito.

53
00:02:36,020 --> 00:02:39,090
At walang dalawang piraso ng data
may eksakto ang parehong roadmap

54
00:02:39,090 --> 00:02:40,530
maliban na data ay magkapareho.

55
00:02:40,530 --> 00:02:44,580
>> Kung ipasok namin John, pagkatapos
paghahanap para sa John.

56
00:02:44,580 --> 00:02:47,430
Iyon ang dalawang magkatulad na mga piraso ng
data, right, naghahanap kami sa pamamagitan ng.

57
00:02:47,430 --> 00:02:49,880
Ngunit sa kabilang banda, ang anumang
dalawang piraso ng data ay

58
00:02:49,880 --> 00:02:52,750
garantisadong na magkaroon ng natatanging roadmaps
sa pamamagitan na ito istraktura ng data.

59
00:02:52,750 --> 00:02:56,210
At kami ay pagpunta sa tumagal ng isang pagtingin sa
isang visual ng mga ito sa ilang sandali lamang.

60
00:02:56,210 --> 00:02:58,810
>> Gagawin namin ito sa pamamagitan ng pagsubok sa
lumikha ng isang bagong istraktura ng data,

61
00:02:58,810 --> 00:03:00,564
paggawa ng mga mapa ang mga sumusunod na mga pangunahing mga pares ng halaga.

62
00:03:00,564 --> 00:03:03,480
Sa kasong ito, hindi namin pagpunta upang gamitin ang
kasing simple ng isang Boolean isang bagay.

63
00:03:03,480 --> 00:03:06,200
Kami ay talagang mag-iimbak ang string.

64
00:03:06,200 --> 00:03:08,690
At na string ay pagpunta sa
ang pangalan ng isang unibersidad.

65
00:03:08,690 --> 00:03:12,140
>> At ang susi ay magiging taon
kapag na unibersidad ay itinatag.

66
00:03:12,140 --> 00:03:15,380
Lahat ng mga taon para sa mga unibersidad
ay magiging apat na digit.

67
00:03:15,380 --> 00:03:19,840
At kaya gagamitin namin ang mga apat na digit
navigate sa pamamagitan ng mga istraktura ng data.

68
00:03:19,840 --> 00:03:22,270
At kami makita, muli, kung paano
gagawin namin na sa isang segundo lang.

69
00:03:22,270 --> 00:03:25,110
>> Sa dulo ng landas,
ipapakita namin makita ang pangalan

70
00:03:25,110 --> 00:03:30,250
ng unibersidad na tumutugma
sa na key, ang mga apat na digit.

71
00:03:30,250 --> 00:03:34,390
Ang pangunahing ideya sa likod ng isang trie
ay kami ay may isang sentral na ruta.

72
00:03:34,390 --> 00:03:35,640
Kaya mag-isip tungkol sa mga ito tulad ng isang puno.

73
00:03:35,640 --> 00:03:39,211
At ito ay katulad sa spelling
at sa konsepto sa isang puno.

74
00:03:39,211 --> 00:03:41,460
Karaniwan kapag sa tingin namin tungkol
puno sa tunay na mundo,

75
00:03:41,460 --> 00:03:44,090
mayroon sila ng isang ugat na ang sa
lupa at maging sila ay paitaas

76
00:03:44,090 --> 00:03:46,830
at sila ay may sanga
at sila ay may mga dahon.

77
00:03:46,830 --> 00:03:49,450
At isa lamang ang mga ideya ng
isang trie ay eksaktong kapareho,

78
00:03:49,450 --> 00:03:51,755
maliban ugat na anchor
lugar sa kalangitan.

79
00:03:51,755 --> 00:03:53,130
At ang mga dahon ay sa ilalim.

80
00:03:53,130 --> 00:03:55,750
>> Kaya ito ay uri ng tulad ng pagkuha ng isang puno
at lamang flipping ito baligtad.

81
00:03:55,750 --> 00:03:56,880
Ngunit may mga sanga pa rin.

82
00:03:56,880 --> 00:03:59,463
At yaong kaya ang ating daanan,
mga ito ay ang aming mga koneksyon

83
00:03:59,463 --> 00:04:02,220
mula sa mga ugat ng mga dahon.

84
00:04:02,220 --> 00:04:04,200
Sa kasong ito, ang mga
mga landas, mga sanga

85
00:04:04,200 --> 00:04:08,490
ay may label na may mga digit na sabihin sa amin
kung aling mga paraan upang pumunta mula sa kung saan kami.

86
00:04:08,490 --> 00:04:11,800
>> Kapag nakita namin ang isang 0, pumunta kami pababa sangay na ito,
kung makita natin ang isang 1, pumunta kami pababa sangay na ito,

87
00:04:11,800 --> 00:04:12,900
at iba at iba pa.

88
00:04:12,900 --> 00:04:14,060
Well, kung ano ang ibig sabihin nito?

89
00:04:14,060 --> 00:04:16,519
Well, na nangangahulugan na ang
sa bawat kantong point

90
00:04:16,519 --> 00:04:19,260
at ang bawat node sa
gitna at ang bawat sanga,

91
00:04:19,260 --> 00:04:23,020
may mga 10 na posible
lugar na maaari naming pumunta.

92
00:04:23,020 --> 00:04:27,690
Kaya may mga 10 mga payo
mula sa bawat lokasyon.

93
00:04:27,690 --> 00:04:30,610
>> At ito ay kung saan sinusubukan ng maaaring makakuha ng isang
Medyo pananakot para sa isang tao

94
00:04:30,610 --> 00:04:34,460
sino ang hindi magkaroon ng isang pulutong ng mga
karanasan sa computer science bago.

95
00:04:34,460 --> 00:04:35,960
Ngunit pagsusubok ay talagang medyo kasindak-sindak.

96
00:04:35,960 --> 00:04:37,793
At kung mayroon kang mga
pagkakataon upang gumana sa mga ito

97
00:04:37,793 --> 00:04:40,420
at ikaw ay handa na maghukay-in
at mag-eksperimento sa mga ito,

98
00:04:40,420 --> 00:04:44,234
ang mga ito ay talagang lubos na interesante
istruktura ng data upang gumana sa.

99
00:04:44,234 --> 00:04:46,900
Kung nais namin na ipasok ang isang elemento
sa trie, ang lahat ng kailangan naming gawin

100
00:04:46,900 --> 00:04:51,360
ay bumuo ng ang tamang landas
mula sa mga ugat sa dahon.

101
00:04:51,360 --> 00:04:55,390
Narito kung ano ang bawat hakbang na kasama
maaaring magmukhang ang paraan.

102
00:04:55,390 --> 00:04:59,660
Kami ay pagpunta upang tukuyin ang isang bagong data
istraktura para sa isang bagong node tinatawag na isang trie.

103
00:04:59,660 --> 00:05:02,560
>> At sa loob ng na data
istraktura ay may dalawang piraso.

104
00:05:02,560 --> 00:05:05,460
Kami ay pagpunta sa tindahan ng
pangalan ng isang unibersidad.

105
00:05:05,460 --> 00:05:09,410
At kami ay pagpunta sa mga tindahan ng
isang array ng payo

106
00:05:09,410 --> 00:05:12,190
sa iba pang mga nodes ng parehong uri.

107
00:05:12,190 --> 00:05:14,780
Kaya, muli, ito ay na-uri-uriin
ng konsepto ng lahat ng dako

108
00:05:14,780 --> 00:05:18,567
tayo, kami sa 10 posibleng
lugar na maaari naming pumunta.

109
00:05:18,567 --> 00:05:20,150
Kapag nakita namin ang isang 0, pumunta kami pababa sangay na ito.

110
00:05:20,150 --> 00:05:22,690
Kapag nakita namin ang isang 1, sangay na ito,
at iba pa at iba pa at iba pa.

111
00:05:22,690 --> 00:05:25,160
Kung sinasabi nating 9, pumunta kami pababa sangay na ito.

112
00:05:25,160 --> 00:05:28,220
Kaya sa bawat kantong point,
kami ay maaaring pumunta 10 posibleng mga lugar.

113
00:05:28,220 --> 00:05:35,740
Kaya ang bawat node ay naglalaman ng 10 mga payo
sa iba pang mga nodes, 10 iba pang mga node.

114
00:05:35,740 --> 00:05:39,810
>> At ang data namin ang pag-iimbak ay
lamang ang pangalan ng unibersidad.

115
00:05:39,810 --> 00:05:41,060
Kaya ipaalam sa bumuo ng isang trie.

116
00:05:41,060 --> 00:05:44,860
Ipasok ang isang pares Ipaalam
ng mga item sa aming trie.

117
00:05:44,860 --> 00:05:46,740
Kaya sa pinakatuktok,
ito ay ang aming root node.

118
00:05:46,740 --> 00:05:49,740
Ito ay marahil pagpunta sa maging isang bagay
ikaw ay pagpunta sa globally claim.

119
00:05:49,740 --> 00:05:53,450
At ikaw ay pagpunta sa globally mapanatili
isang pointer sa node na ito palagi.

120
00:05:53,450 --> 00:05:55,360
>> Ikaw ay pagpunta sa sabihin,
ugat ay katumbas ng, at ikaw ay

121
00:05:55,360 --> 00:05:57,580
pagpunta sa malloc iyong sarili trie node.

122
00:05:57,580 --> 00:05:59,850
At hindi ka na pagpunta
pindutin muli root.

123
00:05:59,850 --> 00:06:02,300
Sa bawat oras na nais mong
magsimulang mag-navigate sa pamamagitan ng,

124
00:06:02,300 --> 00:06:05,802
set ka ng isa pang pointer
pantay-pantay sa root, tulad ng mga trav,

125
00:06:05,802 --> 00:06:07,760
na kung saan ay ang mga halimbawa ko
gamitin sa maraming ng aking mga video

126
00:06:07,760 --> 00:06:11,090
dito sa stack at queues
at mga listahan ng mga link at iba pa.

127
00:06:11,090 --> 00:06:13,320
>> Itakda mo ang isa pang pointer
tinatawag trav para traversal.

128
00:06:13,320 --> 00:06:15,890
And mong gamitin trav upang mag-navigate
sa pamamagitan ng mga istraktura ng data.

129
00:06:15,890 --> 00:06:17,500
Kaya sabihin makita kung paano maaaring tumingin ito.

130
00:06:17,500 --> 00:06:19,880
Kaya ngayon, kung ano
ang hitsura ng isang node tulad?

131
00:06:19,880 --> 00:06:22,920
Well, tulad ng aming data
istraktura deklarasyon ipinahiwatig,

132
00:06:22,920 --> 00:06:26,906
kami ay may isang string, na kung saan
sa kasong ito ay walang laman.

133
00:06:26,906 --> 00:06:27,780
Mayroong wala dito ang.

134
00:06:27,780 --> 00:06:29,550
>> At isang array ng 10 mga payo.

135
00:06:29,550 --> 00:06:31,790
At ngayon, kami lamang
may 1 node sa trie.

136
00:06:31,790 --> 00:06:33,110
May wala pa sa ito ay.

137
00:06:33,110 --> 00:06:36,020
Kaya lahat ng 10 ng mga
payo point sa null.

138
00:06:36,020 --> 00:06:38,090
Iyon ay kung ano ay nagpapahiwatig ng pula.

139
00:06:38,090 --> 00:06:39,500
>> Ipasok sa string Harvard Hayaan.

140
00:06:39,500 --> 00:06:41,999
Ni ipasok ang University of Hayaan
Harvard sa ito trie, na

141
00:06:41,999 --> 00:06:43,940
ay itinatag noong taong 1636.

142
00:06:43,940 --> 00:06:48,220
Gusto naming gamitin ang susi,
1636, upang sabihin sa amin kung saan hindi namin

143
00:06:48,220 --> 00:06:50,140
pagpunta sa tindahan ng Harvard sa trie.

144
00:06:50,140 --> 00:06:51,470
Ngayon, paano namin gawin iyon?

145
00:06:51,470 --> 00:06:52,886
>> Maaaring tumingin Ito ang isang bagay na tulad nito.

146
00:06:52,886 --> 00:06:54,160
Simulan namin sa root.

147
00:06:54,160 --> 00:06:56,920
At kami ay may mga 10 lugar na maaari naming pumunta.

148
00:06:56,920 --> 00:06:59,900
Ang ugat ay tulad ng anumang
iba pang mga node ng trie.

149
00:06:59,900 --> 00:07:02,850
May mga 10 mga lugar na maaari naming pumunta mula dito.

150
00:07:02,850 --> 00:07:07,215
>> Saan ang marahil kami gusto
upang pumunta kung ang susi ay 1636?

151
00:07:07,215 --> 00:07:08,340
Mayroon talagang dalawang mga pagpipilian.

152
00:07:08,340 --> 00:07:08,450
Right.

153
00:07:08,450 --> 00:07:10,825
Maaari naming bumuo ng ang key mula sa
karapatan sa kaliwa at simulan na may 6.

154
00:07:10,825 --> 00:07:14,000
O maaari kaming bumuo ng mga susi mula sa
kaliwa papunta sa kanan at magsimula sa 1.

155
00:07:14,000 --> 00:07:16,140
>> Ito ay marahil mas
intuitive bilang isang tao

156
00:07:16,140 --> 00:07:18,110
upang maunawaan namin makikita
lang pumunta sa kaliwa papuntang kanan.

157
00:07:18,110 --> 00:07:21,140
At kaya kung gusto kong ipasok
Harvard sa ito trie,

158
00:07:21,140 --> 00:07:23,560
Malamang na gusto kong simulan
sa pamamagitan ng pagsisimula sa root,

159
00:07:23,560 --> 00:07:25,720
naghahanap sa aking 10 mga pagpipilian
sa harap ko, at sinasabi

160
00:07:25,720 --> 00:07:28,700
Gusto kong pumunta down ang 1 path.

161
00:07:28,700 --> 00:07:29,700
SIGE.

162
00:07:29,700 --> 00:07:31,810
>> Ngayon, 1 landas ay kasalukuyang null.

163
00:07:31,810 --> 00:07:35,920
Kaya kung nais kong magpatuloy down na landas
upang ipasok ang elementong ito sa trie,

164
00:07:35,920 --> 00:07:42,040
Mayroon akong mag-malloc isang bagong node, may 1
point doon, at pagkatapos ay ako ay magandang pumunta.

165
00:07:42,040 --> 00:07:46,460
>> Kaya talaga ako sa isang
kung saan punto ako nakatayo

166
00:07:46,460 --> 00:07:50,270
sa ugat ng puno o ang
trie at may 10 sanga.

167
00:07:50,270 --> 00:07:52,260
Subalit ang bawat sangay ay may
gate sa harap nito.

168
00:07:52,260 --> 00:07:53,060
Right.

169
00:07:53,060 --> 00:07:54,850
Dahil mayroong wala pa ang mayroong.

170
00:07:54,850 --> 00:07:56,522
Hindi ligtas na daanan.

171
00:07:56,522 --> 00:07:58,980
Iyon ay nangangahulugan na wala doon
down ng anuman sa mga sanga.

172
00:07:58,980 --> 00:08:02,532
Kung gusto ko upang simulan ang gusali
isang bagay, gusto kong tanggalin ang gate.

173
00:08:02,532 --> 00:08:04,490
Gusto kong alisin ang gate
sa harap ng number 1.

174
00:08:04,490 --> 00:08:05,698
At gusto kong maglakad pababa na.

175
00:08:05,698 --> 00:08:08,060
At gusto ko na bumuo ng
isa pang lugar para sa akin upang pumunta.

176
00:08:08,060 --> 00:08:09,470
>> At na kung ano ang aking nagawa dito.

177
00:08:09,470 --> 00:08:11,430
Kaya 1 ay hindi na tumuturo sa null.

178
00:08:11,430 --> 00:08:13,830
Sinabi ko na ito ay ligtas na bumaba dito ngayon.

179
00:08:13,830 --> 00:08:15,789
Ako na binuo ng isa pang node.

180
00:08:15,789 --> 00:08:18,330
At kapag nakakuha ako sa na node, ako
magkaroon ng isa pang desisyon na gumawa.

181
00:08:18,330 --> 00:08:20,890
Saan ako pagpunta upang pumunta mula dito?

182
00:08:20,890 --> 00:08:22,700
>> Well, na wala na akong pababa ang 1.

183
00:08:22,700 --> 00:08:24,470
Kaya ngayon ay malamang na gusto kong pumunta down ang 6.

184
00:08:24,470 --> 00:08:24,970
Right.

185
00:08:24,970 --> 00:08:27,100
Muli, ako ay may 10 mga lokasyon maaari kong piliin.

186
00:08:27,100 --> 00:08:30,060
Kaya hana ngayon down number 6.

187
00:08:30,060 --> 00:08:32,280
Kaya i-clear ko ang gate
sa harap ng number 6.

188
00:08:32,280 --> 00:08:33,250
At lumakad ako doon.

189
00:08:33,250 --> 00:08:34,580
At bumuo ako ng isa pang node.

190
00:08:34,580 --> 00:08:37,630
At naabot ko na ang isa pang kantong point.

191
00:08:37,630 --> 00:08:40,289
>> Muli, ako ay may 10 mga pagpipilian
para sa kung saan ang maaari kong pumunta.

192
00:08:40,289 --> 00:08:42,799
Ko na inilipat mula 1 hanggang 6.

193
00:08:42,799 --> 00:08:44,215
Kaya ngayon ay malamang na gusto kong pumunta sa 3.

194
00:08:44,215 --> 00:08:45,381
3, mayroong wala kahit saan ang maaari kong pumunta.

195
00:08:45,381 --> 00:08:48,980
Kaya ko bang i-clear ang paraan
at bumuo ng aking sarili ng isang bagong space.

196
00:08:48,980 --> 00:08:50,870
At pagkatapos ay mula sa 3, kung saan ang gusto kong pumunta?

197
00:08:50,870 --> 00:08:52,450
Gusto kong pumunta down 6.

198
00:08:52,450 --> 00:08:54,770
>> At, muli, ako ay upang
malinaw na ang paraan upang gawin ito.

199
00:08:54,770 --> 00:08:59,179
Kaya ngayon na ginagamit ko na ang aking mga susi sa ipasok lumikha
nodes at magsimula na magtayo ito trie.

200
00:08:59,179 --> 00:09:00,220
Sinimulan ko sa root.

201
00:09:00,220 --> 00:09:03,666
Ako ay wala na down na 1636.

202
00:09:03,666 --> 00:09:05,540
At ngayon ako sa ibaba
doon sa na node.

203
00:09:05,540 --> 00:09:06,610
At maaari mo na
makita ang mga ito sa iyong screen.

204
00:09:06,610 --> 00:09:07,735
>> Ito ay naka-highlight sa dilaw.

205
00:09:07,735 --> 00:09:10,020
Iyon ay kung saan ako kasalukuyang am.

206
00:09:10,020 --> 00:09:11,300
Aking key ay tapos na.

207
00:09:11,300 --> 00:09:13,030
Naubos ko na ang bawat posisyon sa aking key.

208
00:09:13,030 --> 00:09:15,040
Kaya hindi ako maaaring pumunta sa anumang karagdagang.

209
00:09:15,040 --> 00:09:17,720
Kaya sa puntong ito, ang lahat ng ko
talagang kailangan mong gawin ay sabihin, OK.

210
00:09:17,720 --> 00:09:18,990
Ito ay uri ng tulad ng pagtingin
down sa lupa,

211
00:09:18,990 --> 00:09:21,115
kung ikaw ay envisioning
ang iyong sarili bilang ang uri ng mga landas

212
00:09:21,115 --> 00:09:22,350
na may iba't ibang mga koneksyon.

213
00:09:22,350 --> 00:09:25,800
Pagsunud-sunurin ng naghahanap down at uri ng
spray pagpipinta Harvard sa lupa.

214
00:09:25,800 --> 00:09:26,800
Iyan ang pangalan ng mga ito.

215
00:09:26,800 --> 00:09:28,300
Malaman na kung ano ang sa lokasyong ito.

216
00:09:28,300 --> 00:09:31,870
Kung magsisimula kami sa root at pumunta kami pababa
1 at pagkatapos ay 6 at pagkatapos ay 3 at pagkatapos ay 6,

217
00:09:31,870 --> 00:09:32,780
Nasaan ba tayo?

218
00:09:32,780 --> 00:09:35,640
Well kung titingnan namin down na
at nakita namin Harvard, pagkatapos

219
00:09:35,640 --> 00:09:38,960
alam namin na Harvard ay
itinatag sa 1636 batay sa mga paraan

220
00:09:38,960 --> 00:09:41,400
kami ay pagpapatupad na ito istraktura ng data.

221
00:09:41,400 --> 00:09:43,177
Kaya na ay inaasahan namin na tapat.

222
00:09:43,177 --> 00:09:44,760
Kami ay pagpunta sa gawin ang dalawang higit pang mga pagpapasok.

223
00:09:44,760 --> 00:09:50,060
At sana ito ay makatulong sa
makikita ito gawin ng dalawang beses pa.

224
00:09:50,060 --> 00:09:52,210
>> Ngayon, ipasok ang isa pang university ipaalam.

225
00:09:52,210 --> 00:09:54,630
Ni ipasok Yale na ito sa trie Hayaan.

226
00:09:54,630 --> 00:09:57,037
Yale ay itinatag sa 1701.

227
00:09:57,037 --> 00:09:58,870
Kaya makikita namin magsimula sa
root, gaya ng lagi naming gawin.

228
00:09:58,870 --> 00:09:59,890
At kami ay itakda ang isang traversal pointer.

229
00:09:59,890 --> 00:10:01,624
Kami ay pagpunta sa paggamit na upang ilipat sa pamamagitan ng.

230
00:10:01,624 --> 00:10:03,790
Ang unang bagay na gusto naming
gawin ay pumunta down ang 1 path.

231
00:10:03,790 --> 00:10:05,830
Iyan ang unang titik ng aming mga key.

232
00:10:05,830 --> 00:10:08,420
Sa kabutihang palad, bagaman, ay hindi kami
kailangang gawin ang anumang trabaho sa oras na ito.

233
00:10:08,420 --> 00:10:09,919
Ang 1 na landas ang nai-clear.

234
00:10:09,919 --> 00:10:13,520
Nabura ko ito dati noong ako
ay pagpasok ng Harvard sa 1,636.

235
00:10:13,520 --> 00:10:18,090
Kaya ko ligtas na ilipat
down 1 at pumunta lamang doon.

236
00:10:18,090 --> 00:10:20,150
Kung maaari ilipat pababa ang 1.

237
00:10:20,150 --> 00:10:22,930
>> Ngayon, bagaman, nais kong pumunta sa 7.

238
00:10:22,930 --> 00:10:24,280
Nabura ko ang paraan sa 6.

239
00:10:24,280 --> 00:10:27,050
Alam ko ligtas na ko
magpatuloy down ang 6 path.

240
00:10:27,050 --> 00:10:29,220
Ngunit kailangan kong magpatuloy sa 7 path.

241
00:10:29,220 --> 00:10:30,580
Kaya kung ano ang kailangan kong gawin?

242
00:10:30,580 --> 00:10:35,070
Well, tulad lamang ng dati, kailangan ko lang
upang i-clear ang gate, lumabas ng daan,

243
00:10:35,070 --> 00:10:38,740
at bumuo ng isang bagong node mula sa 7 path.

244
00:10:38,740 --> 00:10:40,250
Tulad na lamang ng mga ito.

245
00:10:40,250 --> 00:10:42,930
>> Kaya ngayon ay inilipat ko na 1 at pagkatapos ay 7.

246
00:10:42,930 --> 00:10:45,550
At ngayon paunawa, sort ako
ng sa bagong subbranch.

247
00:10:45,550 --> 00:10:46,050
Right.

248
00:10:46,050 --> 00:10:49,260
Lahat ng iba pa mula sa 16
on, Wala akong pakialam tungkol sa.

249
00:10:49,260 --> 00:10:50,720
Hindi ako gumagawa ng 16 kahit ano.

250
00:10:50,720 --> 00:10:51,750
Ako ginagawa 17 mga bagay-bagay.

251
00:10:51,750 --> 00:10:58,380
>> Kaya ngayon mula sa 17 on, kailangan kong
uri ng alab bagong trails dito.

252
00:10:58,380 --> 00:11:00,462
Ang susunod na digit aking key ay 0.

253
00:11:00,462 --> 00:11:01,670
Ako malinaw na hindi maaaring makakuha ng kahit saan.

254
00:11:01,670 --> 00:11:02,628
Ko lamang binuo ito node.

255
00:11:02,628 --> 00:11:04,550
Kaya alam ko walang
mga landas pasulong mula dito.

256
00:11:04,550 --> 00:11:06,370
Kaya kailangan kong gumawa ng isa sa aking sarili.

257
00:11:06,370 --> 00:11:09,360
>> Kaya malloc ko ang isang bagong node
at magkaroon ng 0 point doon.

258
00:11:09,360 --> 00:11:12,770
At pagkatapos ng isa pang oras, malloc ko ang isang
bagong node at magkaroon ng isang punto doon.

259
00:11:12,770 --> 00:11:15,870
Muli, naubos ko na ang aking mga susi, 1701.

260
00:11:15,870 --> 00:11:18,472
Kaya tumingin ako at ko spray pintura Yale.

261
00:11:18,472 --> 00:11:19,680
Iyan ang pangalan ng mga ito node.

262
00:11:19,680 --> 00:11:24,660
>> At kaya ngayon kung kailangan ko ba upang makita kung Yale
ay sa ito trie, sisimulan ko sa root,

263
00:11:24,660 --> 00:11:27,060
Bababa ako 1701, at tumingin pababa.

264
00:11:27,060 --> 00:11:30,030
At kung makikita ko ang spray Yale
pininturahan papunta sa lupa, at pagkatapos ay

265
00:11:30,030 --> 00:11:32,200
Alam ko Yale umiiral sa trie.

266
00:11:32,200 --> 00:11:32,950
Ni gawin ang isa pang Hayaan.

267
00:11:32,950 --> 00:11:36,430
Ni ipasok Dartmouth sa ito Hayaan
trie, na kung saan ay itinatag sa 1769.

268
00:11:36,430 --> 00:11:37,750
>> Simulan muli sa root.

269
00:11:37,750 --> 00:11:39,445
Aking unang digit ng aking mga susi ay 1.

270
00:11:39,445 --> 00:11:40,820
Maaari ko ligtas na ilipat pababa na path.

271
00:11:40,820 --> 00:11:42,400
Umiiral Na.

272
00:11:42,400 --> 00:11:44,040
Ang susunod na digit ng aking mga susi ay 7.

273
00:11:44,040 --> 00:11:45,890
Maaari ko ligtas na ilipat pababa na path.

274
00:11:45,890 --> 00:11:47,540
Umiiral na ito pati na rin.

275
00:11:47,540 --> 00:11:49,000
>> Ang aking susunod ay 6.

276
00:11:49,000 --> 00:11:52,860
Mula dito, mula sa kung saan ako kasalukuyang am
sa dilaw doon sa gitna na node,

277
00:11:52,860 --> 00:11:56,060
6 ay kasalukuyang naka-lock off.

278
00:11:56,060 --> 00:11:58,830
Kung gusto kong pumunta down na landas,
Mayroon akong upang bumuo ng ito sa aking sarili.

279
00:11:58,830 --> 00:12:02,250
Kaya kailangan ko malloc isang bagong node
at may 6 point doon.

280
00:12:02,250 --> 00:12:04,250
At pagkatapos ay, muli, ako ay
nagliliyab bagong trails dito.

281
00:12:04,250 --> 00:12:10,750
>> Kaya malloc ko ang isang bagong node sa gayon ay mula
na node-- path numero 9-- at pagkatapos ay ngayon

282
00:12:10,750 --> 00:12:13,584
kung maglakbay ako 1769, at tumingin ako pababa.

283
00:12:13,584 --> 00:12:15,500
May walang kasalukuyang
spray pininturahan doon.

284
00:12:15,500 --> 00:12:16,930
Maaari kong isulat Dartmouth.

285
00:12:16,930 --> 00:12:20,710
At ako nakapasok
Dartmouth sa trie.

286
00:12:20,710 --> 00:12:23,450
>> Kaya na pagpasok
mga bagay-bagay sa trie.

287
00:12:23,450 --> 00:12:25,384
Ngayon gusto naming upang maghanap para sa mga bagay-bagay.

288
00:12:25,384 --> 00:12:27,050
Paano namin maghanap para sa mga bagay-bagay sa trie?

289
00:12:27,050 --> 00:12:29,170
Well, ito ay medyo marami ang parehong ideya.

290
00:12:29,170 --> 00:12:33,620
Ngayon, gamitin lamang namin ang mga digit ng key
upang makita kung kami ay maaaring mag-navigate mula sa mga ugat

291
00:12:33,620 --> 00:12:37,170
na kung saan namin gustong pumunta sa trie.

292
00:12:37,170 --> 00:12:41,620
>> Kung ang hit namin ang isang patay na dulo sa anumang punto, at pagkatapos ay
alam natin na hindi maaaring umiiral na elemento

293
00:12:41,620 --> 00:12:44,500
o ibang tao na ang path ng gagawin
may na-clear.

294
00:12:44,500 --> 00:12:45,930
Kung gawin namin ito sa lahat ng mga paraan upang
Sa katapusan, ang lahat ng kailangan naming gawin

295
00:12:45,930 --> 00:12:48,471
ay tumingin down at makita kung na
ang elemento kaming naghahanap para sa.

296
00:12:48,471 --> 00:12:49,335
Kung ito ay, sa tagumpay.

297
00:12:49,335 --> 00:12:52,610
Kung ito ay hindi, mabibigo.

298
00:12:52,610 --> 00:12:54,940
>> Kaya sabihin sa paghahanap para sa
Harvard sa trie.

299
00:12:54,940 --> 00:12:56,020
Simulan namin sa root.

300
00:12:56,020 --> 00:12:58,228
At, muli, kami ay pagpunta sa
lumikha ng isang traversal pointer

301
00:12:58,228 --> 00:12:59,390
na gawin ang aming mga galaw para sa amin.

302
00:12:59,390 --> 00:13:02,080
Mula sa root alam namin na ang
unang lugar na kailangan namin upang pumunta ay 1,

303
00:13:02,080 --> 00:13:03,390
maaari naming gawin iyon?

304
00:13:03,390 --> 00:13:03,982
Oo kaya natin.

305
00:13:03,982 --> 00:13:04,690
Kung ligtas na umiiral na.

306
00:13:04,690 --> 00:13:06,660
Maaari naming pumunta doon.

307
00:13:06,660 --> 00:13:08,440
>> Ngayon, sa susunod na lugar kailangan namin upang pumunta ay 6.

308
00:13:08,440 --> 00:13:10,557
Umiiral ba ang 6 na landas mula dito?

309
00:13:10,557 --> 00:13:11,140
Oo, ito ay.

310
00:13:11,140 --> 00:13:12,690
Maaari naming pumunta down ang 6 path.

311
00:13:12,690 --> 00:13:13,905
At kami end up dito.

312
00:13:13,905 --> 00:13:16,130
>> Puwede ba kaming pumunta down ang 3 landas mula dito?

313
00:13:16,130 --> 00:13:18,450
Well, dahil ito ay lumiliko out,
yes, na umiiral masyadong.

314
00:13:18,450 --> 00:13:20,790
At maaari naming makakuha ng sa 6 na landas mula dito?

315
00:13:20,790 --> 00:13:21,982
Oo kaya natin.

316
00:13:21,982 --> 00:13:24,002
>> Hindi namin lubos na nasagot
ang pa pinag-uusapan.

317
00:13:24,002 --> 00:13:25,710
Mayroong isa pang pa rin
hakbang, na ngayon

318
00:13:25,710 --> 00:13:28,520
kailangan namin upang tumingin down at
makita kung na actually--

319
00:13:28,520 --> 00:13:32,660
kung kami ay naghahanap para sa Harvard, ay na
ano ang nakita namin matapos naming maubos ang key?

320
00:13:32,660 --> 00:13:35,430
Sa halimbawa na aming ginagamit dito,
ang taong palaging apat na digit.

321
00:13:35,430 --> 00:13:40,280
Ngunit maaaring gumagamit ka ng mga halimbawa kung saan ang
ikaw ay naglalagay ng isang diksyunaryo ng mga salita.

322
00:13:40,280 --> 00:13:44,060
>> At kaya sa halip ng pagkakaroon ng 10 mga payo
para sa aking mga lokasyon, maaari kang magkaroon ng 26.

323
00:13:44,060 --> 00:13:46,040
Isa para sa bawat titik ng alpabeto.

324
00:13:46,040 --> 00:13:50,350
At may ilang mga salita tulad ng paniki,
kung saan ay isang subset ng mga batch, halimbawa.

325
00:13:50,350 --> 00:13:53,511
At kaya kahit na ikaw ay makakuha sa
dulo ng key at tumingin ka down,

326
00:13:53,511 --> 00:13:55,260
maaaring hindi mo makita kung ano ang
ikaw ay naghahanap para sa.

327
00:13:55,260 --> 00:13:58,500
>> Kaya palagi kang magkaroon sa pagtawid
ang buong landas at pagkatapos ay

328
00:13:58,500 --> 00:14:01,540
kung kayo ay matagumpay na ma
upang tumawid ang buong path,

329
00:14:01,540 --> 00:14:03,440
tumingin down at gawin ang isa huling confirmation.

330
00:14:03,440 --> 00:14:05,120
Ay na kung ano Naghahanap ako?

331
00:14:05,120 --> 00:14:07,740
Well, tumungo ako pagkatapos ng simula
sa tuktok at pagpunta 1636.

332
00:14:07,740 --> 00:14:08,240
Tumingin ako pababa.

333
00:14:08,240 --> 00:14:09,400
Nakakakita ako ng Harvard.

334
00:14:09,400 --> 00:14:11,689
Kaya, oo, nagtagumpay ako.

335
00:14:11,689 --> 00:14:13,980
Paano kung ano ako ay naghahanap para sa
ay wala sa trie, bagaman.

336
00:14:13,980 --> 00:14:17,200
Paano kung Naghahanap ako ng Princeton,
na kung saan ay itinatag sa 1746.

337
00:14:17,200 --> 00:14:20,875
At kaya 1746 ay magiging aking mga susi
upang mag-navigate sa pamamagitan ng trie.

338
00:14:20,875 --> 00:14:22,040
Well, sisimulan ko sa root.

339
00:14:22,040 --> 00:14:24,760
At ang unang lugar na gusto ko
upang pupunta pababa sa 1 path.

340
00:14:24,760 --> 00:14:25,590
Maaari ko bang gawin ito?

341
00:14:25,590 --> 00:14:26,490
Oo, kaya ko.

342
00:14:26,490 --> 00:14:28,730
>> Puwede ba akong mag down ang 7 landas mula doon?

343
00:14:28,730 --> 00:14:29,230
Oo, maaari ko.

344
00:14:29,230 --> 00:14:30,750
Iyon ay umiiral din.

345
00:14:30,750 --> 00:14:32,460
Ngunit ako maaaring pumunta down ang 4 na landas mula dito?

346
00:14:32,460 --> 00:14:35,550
Iyan ay tulad ng pagtatanong ng mga tanong, maaari
Magpatuloy ko down na maliit na parisukat

347
00:14:35,550 --> 00:14:37,114
na ko na naka-highlight sa dilaw?

348
00:14:37,114 --> 00:14:38,030
May walang may.

349
00:14:38,030 --> 00:14:38,610
Right.

350
00:14:38,610 --> 00:14:41,310
>> Walang paraan forward down ang 4 path.

351
00:14:41,310 --> 00:14:46,480
Kung Princeton ay sa ito trie, na ang 4
sana ay na-clear para sa amin na.

352
00:14:46,480 --> 00:14:49,130
At kaya sa puntong ito
naabot na namin ang isang patay na dulo.

353
00:14:49,130 --> 00:14:50,250
Hindi namin maaaring pumunta anumang karagdagang.

354
00:14:50,250 --> 00:14:53,440
At upang maaari naming sabihin, definitively, hindi.

355
00:14:53,440 --> 00:14:56,760
Princeton ay hindi umiiral sa trie.

356
00:14:56,760 --> 00:14:58,860
>> Kaya kung ano ang ibig sabihin ng lahat?

357
00:14:58,860 --> 00:14:59,360
Right.

358
00:14:59,360 --> 00:15:01,000
Mayroong maraming nagaganap dito.

359
00:15:01,000 --> 00:15:02,500
May mga payo sa lahat ng dako ng lugar.

360
00:15:02,500 --> 00:15:04,249
At, tulad ng makikita mo
lamang mula sa diagram,

361
00:15:04,249 --> 00:15:07,010
may isang pulutong ng mga node na
ang mga uri ng lumilipad sa paligid.

362
00:15:07,010 --> 00:15:13,480
Ngunit paunawa sa bawat oras na namin nais na
suriin kung ang isang bagay ay sa trie,

363
00:15:13,480 --> 00:15:15,000
lamang kami ay upang gumawa ng 4 na gumagalaw.

364
00:15:15,000 --> 00:15:17,208
>> Sa bawat oras na namin nais na
ipasok ang isang bagay sa trie,

365
00:15:17,208 --> 00:15:20,440
mayroon kaming gumawa ng 4 na gumagalaw, marahil ay
mallocing ilang mga bagay-bagay kasama ang paraan.

366
00:15:20,440 --> 00:15:23,482
Ngunit tulad ng nakita natin kapag ipinasok namin
Dartmouth sa trie,

367
00:15:23,482 --> 00:15:25,940
minsan ang ilan sa mga landas
maaaring ma-clear para sa amin.

368
00:15:25,940 --> 00:15:30,520
At sa gayon ay ang aming trie ay makakakuha ng mas malaki at
mas malaki, mayroon kaming gawin mas mababa sa trabaho sa bawat oras

369
00:15:30,520 --> 00:15:32,270
upang magpasok ng mga bagong bagay
dahil hindi namin nai

370
00:15:32,270 --> 00:15:35,746
na binuo ng isang pulutong ng mga intermediate
sanga kasama ang paraan.

371
00:15:35,746 --> 00:15:38,370
Kung sakaling lamang namin upang tumingin sa
4 mga bagay-bagay, 4 ay ang tapat lamang.

372
00:15:38,370 --> 00:15:41,750
Kami ay talagang uri ng papalapit
constant insertion oras

373
00:15:41,750 --> 00:15:44,501
at pare-pareho ang oras lookup.

374
00:15:44,501 --> 00:15:47,500
Tradeoff, siyempre, na na
ito trie, tulad ng maaari mong marahil sabihin,

375
00:15:47,500 --> 00:15:49,030
ay malaking.

376
00:15:49,030 --> 00:15:51,040
Ang bawat isa sa mga ito nodes
tumatagal ng hanggang isang pulutong ng mga puwang.

377
00:15:51,040 --> 00:15:52,090
>> Ngunit iyon ang tradeoff.

378
00:15:52,090 --> 00:15:55,260
Kung gusto namin talagang mabilis
insertion, talagang mabilis na pagbura,

379
00:15:55,260 --> 00:15:59,630
at talagang mabilis na paghahanap, kami ay may sa
magkaroon ng isang pulutong ng mga data na lumilipad sa paligid.

380
00:15:59,630 --> 00:16:03,590
Mayroon kaming upang magtabi ng isang pulutong ng mga puwang
at memory para sa na istraktura ng data

381
00:16:03,590 --> 00:16:04,290
para mabuhay.

382
00:16:04,290 --> 00:16:05,415
>> At kaya na ang tradeoff.

383
00:16:05,415 --> 00:16:07,310
Ngunit mukhang namin
maaaring may natagpuan ito.

384
00:16:07,310 --> 00:16:09,560
Maaaring Nakakita kami na
banal na Kopita ng mga istraktura ng data

385
00:16:09,560 --> 00:16:12,264
may mabilis na paglalagyan,
pagtanggal, at lookup.

386
00:16:12,264 --> 00:16:14,430
At marahil ito ay magiging isang
naaangkop na istraktura ng data

387
00:16:14,430 --> 00:16:18,890
upang gamitin para sa kahit anong impormasyon
kami ay nagsisikap na store.

388
00:16:18,890 --> 00:16:21,860
Ako Doug Lloyd, ito ay cs50.

389
00:16:21,860 --> 00:16:23,433