1
00:00:00,000 --> 00:00:02,994
>> [Daqq tal-mużika]

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

3
00:00:05,426 --> 00:00:08,550
Doug LLOYD: Allura aħna kont qed inching eqreb
u eqreb li Grail qaddis ta 'data

4
00:00:08,550 --> 00:00:13,050
strutturi, wieħed li nistgħu daħħal
fis, iħassru minn, u jfittxu up

5
00:00:13,050 --> 00:00:15,440
fi żmien kostanti.

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

7
00:00:16,270 --> 00:00:17,280
Dik hija tip ta 'l-għan.

8
00:00:17,280 --> 00:00:19,720
Aħna rridu li tkun tista 'tagħmel
affarijiet ħafna, malajr ħafna.

9
00:00:19,720 --> 00:00:22,580
>> Have we sabuha hawn meta
aħna qed jitkellem dwar jipprova?

10
00:00:22,580 --> 00:00:23,670
Well, ejja tagħti ħarsa.

11
00:00:23,670 --> 00:00:25,628
Allura aħna stajt tidher diversi
strutturi differenti ta 'data

12
00:00:25,628 --> 00:00:28,680
li jimmaniġġjaw l-immappjar ta '
hekk imsejħa pari b'valur ewlenin,

13
00:00:28,680 --> 00:00:32,080
immappjar xi biċċa ta 'data
għal xi biċċa oħra ta 'data

14
00:00:32,080 --> 00:00:36,020
hekk nafu fejn issib
informazzjoni fl-istruttura.

15
00:00:36,020 --> 00:00:40,060
>> Allura għal firxa, per eżempju, il-
muftieħ huwa l-indiċi element jew firxa

16
00:00:40,060 --> 00:00:42,600
lokazzjoni 0 jew firxa 1 u l-bqija.

17
00:00:42,600 --> 00:00:46,140
U il-valur huwa d-data
li teżisti f'dak il-post.

18
00:00:46,140 --> 00:00:48,550
Allura dak li hija maħżuna fil-firxa ta '0?

19
00:00:48,550 --> 00:00:54,290
Dak hija maħżuna fil-firxa 1 versus biss
0 u 1, li tkun l-keys.

20
00:00:54,290 --> 00:00:56,360
>> Ma 'tabella hash huwa
tip ta 'l-istess idea.

21
00:00:56,360 --> 00:01:00,690
Ma 'tabella hash, aħna għandna dan hash
funzjoni li jiġġenera kodiċijiet hash.

22
00:01:00,690 --> 00:01:03,670
Allura l-muftieħ huwa l-kodiċi hash tad-data.

23
00:01:03,670 --> 00:01:06,530
U l-valur, partikolarment
tkellimna dwar ikkatenar

24
00:01:06,530 --> 00:01:10,590
fil-video fuq tabelli hash,
huwa dik il-lista marbuta tad-data

25
00:01:10,590 --> 00:01:12,550
li hashes għal dak hashcode.

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

27
00:01:14,050 --> 00:01:16,050
Xi ngħidu dwar approċċ ieħor
dan il-metodu, għalkemm?

28
00:01:16,050 --> 00:01:21,000
What about metodu fejn il-
muftieħ huwa garantit li tkun unika,

29
00:01:21,000 --> 00:01:25,410
b'differenza tabella hash, fejn nistgħu
jispiċċaw ma 'żewġ biċċiet ta' data

30
00:01:25,410 --> 00:01:27,200
jkollhom l-istess hashcode.

31
00:01:27,200 --> 00:01:30,020
U allura għandna biex jittrattaw ma '
li minn xi waħda mill probing jew aktar

32
00:01:30,020 --> 00:01:33,340
preferibbilment ikkatenar li tiffissa din il-problema.

33
00:01:33,340 --> 00:01:37,520
>> Allura issa nistgħu garanzija
li ewlieni tagħna se jkun uniku.

34
00:01:37,520 --> 00:01:39,690
U jekk dak il-valur tagħna kien
biss xi ħaġa faċli

35
00:01:39,690 --> 00:01:44,080
kif vera u falza li tgħidilna jekk
jew le li l-biċċa ta 'informazzjoni

36
00:01:44,080 --> 00:01:45,610
teżisti fl-istruttura?

37
00:01:45,610 --> 00:01:48,180
A Boolean tista 'tkun sempliċi bħala daqsxejn.

38
00:01:48,180 --> 00:01:52,660
Realistikament huwa probabbilment
Byte aktar probabbli minn daqsxejn.

39
00:01:52,660 --> 00:01:55,410
Imma dak li ħafna iżgħar minn
ħażna forsi string 50-karattru,

40
00:01:55,410 --> 00:01:57,360
pereżempju.

41
00:01:57,360 --> 00:02:02,210
>> Allura tentattivi, simili għal hash tabelli,
li jikkombinaw arrays u lista marbuta,

42
00:02:02,210 --> 00:02:05,790
jipprova jikkombinaw arrays,
istrutturi, u indikaturi

43
00:02:05,790 --> 00:02:08,509
flimkien biex taħżen data
mod interessanti li l-

44
00:02:08,509 --> 00:02:11,550
pretty differenti minn
xejn Rajna s'issa.

45
00:02:11,550 --> 00:02:16,750
Issa aħna nużaw l-informazzjoni bħala pjan direzzjonali
biex jinnaviga din l-istruttura tad-data.

46
00:02:16,750 --> 00:02:18,710
U jekk aħna tista 'ssegwi
il-pjan direzzjonali, jekk nistgħu

47
00:02:18,710 --> 00:02:22,390
isegwu d-data mill
bidu sat-tmiem, aħna ser

48
00:02:22,390 --> 00:02:24,945
taf jekk dik id-data
jeżistu fil-trie.

49
00:02:24,945 --> 00:02:28,310
>> U jekk aħna ma jistgħux isegwu l-mappa
minn tifsira sat-tmiem fil-livelli kollha,

50
00:02:28,310 --> 00:02:30,600
ma jistax jeżisti d-data.

51
00:02:30,600 --> 00:02:32,890
Għal darb'oħra, il-keys hawn huma
garantit li jkun uniku.

52
00:02:32,890 --> 00:02:36,020
U hekk b'differenza tabella hash, aħna ser qatt
ikollhom jittrattaw mal kolliżjonijiet hawn.

53
00:02:36,020 --> 00:02:39,090
U l-ebda żewġ biċċiet ta 'data
għandhom eżattament l-istess pjan direzzjonali

54
00:02:39,090 --> 00:02:40,530
sakemm dik id-data hija identika.

55
00:02:40,530 --> 00:02:44,580
>> Jekk aħna daħħal John, allura
aħna tfittxija għall John.

56
00:02:44,580 --> 00:02:47,430
C'est żewġ biċċiet identiċi ta '
data, id-dritt, aħna qed tfittex permezz.

57
00:02:47,430 --> 00:02:49,880
Iżda mod ieħor, kull
żewġ biċċiet ta 'data huma

58
00:02:49,880 --> 00:02:52,750
garantit li jkollhom pjanijiet direzzjonali uniku
permezz ta 'dan struttura tad-data.

59
00:02:52,750 --> 00:02:56,210
U aħna qed tmur biex tagħti ħarsa lejn
viżwali ta 'dan fi ftit mument.

60
00:02:56,210 --> 00:02:58,810
>> Aħna ser tagħmel dan billi tipprova
tinħoloq struttura ġdida tad-data,

61
00:02:58,810 --> 00:03:00,564
immappjar il-pari b'valur ewlenin li ġejjin.

62
00:03:00,564 --> 00:03:03,480
F'dan il-każ, aħna mhux ser tuża
xi ħaġa sempliċi bħala Boolean.

63
00:03:03,480 --> 00:03:06,200
Aħna fil-fatt se taħżen l-sekwenza.

64
00:03:06,200 --> 00:03:08,690
U li string se
jkun l-isem ta 'università.

65
00:03:08,690 --> 00:03:12,140
>> U l-muftieħ se tkun is-sena
meta din l-Università twaqqfet.

66
00:03:12,140 --> 00:03:15,380
Snin kollha għall-universitajiet
ser ikunu erba 'numri.

67
00:03:15,380 --> 00:03:19,840
U hekk aħna ser tuża dawn l-erba ċifri
jinnavigaw fil din l-istruttura tad-data.

68
00:03:19,840 --> 00:03:22,270
U aħna ser tara, għal darb'oħra, kif
nagħmlu li fi ftit tieni.

69
00:03:22,270 --> 00:03:25,110
>> Fl-aħħar tal-passaġġ,
Ser naraw l-isem

70
00:03:25,110 --> 00:03:30,250
tal-università li jikkorrispondi
għal dak ewlieni, dawn l-erba 'ċifri.

71
00:03:30,250 --> 00:03:34,390
L-idea bażika wara trie
hija li għandna rotta ċentrali.

72
00:03:34,390 --> 00:03:35,640
Allura taħseb dwarha bħal siġra.

73
00:03:35,640 --> 00:03:39,211
U dan huwa simili fl-ortografija
u fil-kunċett ma 'siġra.

74
00:03:39,211 --> 00:03:41,460
Ġeneralment meta naħsbu dwar
siġar fid-dinja reali,

75
00:03:41,460 --> 00:03:44,090
dawn ikollhom għeruq li fil-
art u huma u jikbru l fuq

76
00:03:44,090 --> 00:03:46,830
u dawn għandhom fergħat
u dawn ikollha l-weraq.

77
00:03:46,830 --> 00:03:49,450
U bażikament l-idea ta
a trie huwa eżattament l-istess,

78
00:03:49,450 --> 00:03:51,755
ħlief li għeruq huwa ankrat
x'imkien fis-sema.

79
00:03:51,755 --> 00:03:53,130
U l-weraq huma fil-qiegħ.

80
00:03:53,130 --> 00:03:55,750
>> Allura huwa tip simili tieħu siġra
u biss flipping rasu 'l isfel.

81
00:03:55,750 --> 00:03:56,880
Iżda għad hemm fergħat.

82
00:03:56,880 --> 00:03:59,463
U dawk ikun mogħdijiet tagħna,
dawn se jkunu konnessjonijiet tagħna

83
00:03:59,463 --> 00:04:02,220
mill-għeruq li l-weraq.

84
00:04:02,220 --> 00:04:04,200
F'dan il-każ, dawk
mogħdijiet, dawn il-friegħi

85
00:04:04,200 --> 00:04:08,490
jkollhom it-tikketta ċifri li jgħidulna
liema mod biex imorru minn fejn ninsabu.

86
00:04:08,490 --> 00:04:11,800
>> Jekk naraw 0, aħna jinżlu din il-fergħa,
jekk naraw 1, we jinżlu din il-fergħa,

87
00:04:11,800 --> 00:04:12,900
u hekk u hekk.

88
00:04:12,900 --> 00:04:14,060
Ukoll, dak li jfisser dan?

89
00:04:14,060 --> 00:04:16,519
Ukoll, dan ifisser li
f'kull punt junction

90
00:04:16,519 --> 00:04:19,260
u kull node fil-
nofs u kull fergħa,

91
00:04:19,260 --> 00:04:23,020
hemm 10 possibbli
postijiet li nistgħu mmorru.

92
00:04:23,020 --> 00:04:27,690
Allura hemm 10 pointers
minn kull post.

93
00:04:27,690 --> 00:04:30,610
>> U dan huwa fejn jipprova tista 'tikseb
ftit intimidanti għal xi ħadd

94
00:04:30,610 --> 00:04:34,460
Min hu ma għandhom ħafna ta '
esperjenza fix-xjenza tal-kompjuter qabel.

95
00:04:34,460 --> 00:04:35,960
Imma jipprova huma verament pjuttost tal-biża.

96
00:04:35,960 --> 00:04:37,793
U jekk inti għandek l-
opportunità li jaħdmu magħhom

97
00:04:37,793 --> 00:04:40,420
u int lest biex ħaffer fil
u esperiment magħhom,

98
00:04:40,420 --> 00:04:44,234
dawn qed verament pjuttost interessanti
strutturi tad-dejta li jaħdmu magħhom.

99
00:04:44,234 --> 00:04:46,900
Jekk irridu li daħħal element
fil-trie, kollha għandna bżonn tagħmel

100
00:04:46,900 --> 00:04:51,360
tinbena l-mogħdija korretta
mill-għeruq għall-weraq.

101
00:04:51,360 --> 00:04:55,390
Hawn dak li kull pass tul
il-mod jista 'dehra.

102
00:04:55,390 --> 00:04:59,660
Aħna qed tmur biex jiddefinixxu data ġdida
struttura għal node ġdid jissejjaħ trie.

103
00:04:59,660 --> 00:05:02,560
>> U ġewwa ta 'dik id-data
istruttura hemm żewġ biċċiet.

104
00:05:02,560 --> 00:05:05,460
Aħna qed tmur biex jaħżnu l-
isem ta 'università.

105
00:05:05,460 --> 00:05:09,410
U aħna qed tmur biex jaħżnu
firxa ta 'indikaturi

106
00:05:09,410 --> 00:05:12,190
fin-nodi oħra tal-istess tip.

107
00:05:12,190 --> 00:05:14,780
Allura, għal darb'oħra, dan huwa li tip ta
tal-kunċett ta 'kullimkien

108
00:05:14,780 --> 00:05:18,567
aħna, aħna fil-10 possibbli
postijiet nistgħu mmorru.

109
00:05:18,567 --> 00:05:20,150
Jekk naraw 0, aħna jinżlu din il-fergħa.

110
00:05:20,150 --> 00:05:22,690
Jekk naraw 1, din il-fergħa,
u hekk u hekk u hekk.

111
00:05:22,690 --> 00:05:25,160
Jekk aħna ngħidu 9, aħna jinżlu din il-fergħa.

112
00:05:25,160 --> 00:05:28,220
Allura f'kull punt junction,
nistgħu mmorru 10 postijiet possibbli.

113
00:05:28,220 --> 00:05:35,740
Allura kull node għandu jkun fiha 10 pointers
fin-nodi oħra, għal 10 punti strateġiċi oħrajn.

114
00:05:35,740 --> 00:05:39,810
>> U d-data aħna qed ħażna hija
biss l-isem tal-università.

115
00:05:39,810 --> 00:05:41,060
Mela ejja jibnu trie.

116
00:05:41,060 --> 00:05:44,860
Ejja daħħal koppja
ta 'oġġetti fis-trie tagħna.

117
00:05:44,860 --> 00:05:46,740
Allura fil-quċċata ħafna,
dan huwa node għerq tagħna.

118
00:05:46,740 --> 00:05:49,740
Dan huwa probabbilment se tkun xi ħaġa
int ser globalment jiddikjaraw.

119
00:05:49,740 --> 00:05:53,450
U int ser globalment jżommu
a pointer għal dan node dejjem.

120
00:05:53,450 --> 00:05:55,360
>> Int ser ngħid,
għeruq ugwali, u int

121
00:05:55,360 --> 00:05:57,580
ser malloc yourself node trie.

122
00:05:57,580 --> 00:05:59,850
U int qatt ser
tmissx għerq ġdid.

123
00:05:59,850 --> 00:06:02,300
Kull darba li inti tixtieq li
tibda navigazzjoni permezz,

124
00:06:02,300 --> 00:06:05,802
tissettja pointer ieħor
daqs għerq, bħal trav,

125
00:06:05,802 --> 00:06:07,760
li huwa l-eżempju I
użu f'ħafna videos tiegħi

126
00:06:07,760 --> 00:06:11,090
hawn fuq stacks u kjuwijiet
u listi rabta u l-bqija.

127
00:06:11,090 --> 00:06:13,320
>> Tissettja pointer ieħor
sejjaħ trav għall traversal.

128
00:06:13,320 --> 00:06:15,890
U inti tuża trav biex jinnaviga
permezz tal-istruttura tad-data.

129
00:06:15,890 --> 00:06:17,500
Mela ejja ara kif dan tista 'tidher.

130
00:06:17,500 --> 00:06:19,880
Allura issa dritt, liema
ma node look like?

131
00:06:19,880 --> 00:06:22,920
Ukoll, biss bħala data tagħna
dikjarazzjoni istruttura indikat,

132
00:06:22,920 --> 00:06:26,906
għandna string, li
f'dan il-każ ikun vojt.

133
00:06:26,906 --> 00:06:27,780
M'hemm xejn hawn.

134
00:06:27,780 --> 00:06:29,550
>> U l-firxa ta '10 pointers.

135
00:06:29,550 --> 00:06:31,790
U d-dritt issa, aħna biss
ikollha 1 node f'dan trie.

136
00:06:31,790 --> 00:06:33,110
M'hemm xejn fiha.

137
00:06:33,110 --> 00:06:36,020
Allura kollha 10 ta 'dawk
pointers minn punt tkun tista null.

138
00:06:36,020 --> 00:06:38,090
Dak hu l-aħmar jindika.

139
00:06:38,090 --> 00:06:39,500
>> Ejja daħħal l-sekwenza Harvard.

140
00:06:39,500 --> 00:06:41,999
Ejja daħħal l-Università ta '
Harvard fis dan trie, li

141
00:06:41,999 --> 00:06:43,940
twaqqfet fis-sena 1636.

142
00:06:43,940 --> 00:06:48,220
Aħna rridu li jużaw l-ewlenin,
1636, biex tgħidilna fejn aħna qed

143
00:06:48,220 --> 00:06:50,140
ser taħżen Harvard fil-trie.

144
00:06:50,140 --> 00:06:51,470
Issa, kif jista 'nagħmlu dan?

145
00:06:51,470 --> 00:06:52,886
>> Hija tista 'tidher xi ħaġa bħal din.

146
00:06:52,886 --> 00:06:54,160
Nibdew fl-għeruq.

147
00:06:54,160 --> 00:06:56,920
U aħna għandna dawn l-10 postijiet nistgħu mmorru.

148
00:06:56,920 --> 00:06:59,900
L-għerq huwa biss bħal kull
node oħra tal-trie.

149
00:06:59,900 --> 00:07:02,850
Hemm 10 postijiet nistgħu mmorru minn hawn.

150
00:07:02,850 --> 00:07:07,215
>> Fejn do we probabilment tixtieq
biex imorru jekk il-muftieħ huwa 1636?

151
00:07:07,215 --> 00:07:08,340
Hemm verament żewġ għażliet.

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

153
00:07:08,450 --> 00:07:10,825
Nistgħu nibnu ċ-ċavetta minn
lemin għax-xellug u tibda bl 6.

154
00:07:10,825 --> 00:07:14,000
Jew nistgħu nibnu l-muftieħ mill
xellug għal-lemin u tibda bil 1.

155
00:07:14,000 --> 00:07:16,140
>> Huwa probabbilment aktar
intuwittivi bħala bniedem

156
00:07:16,140 --> 00:07:18,110
biex jifhmu aħna ser
Just go xellug għal-lemin.

157
00:07:18,110 --> 00:07:21,140
U hekk jekk irrid li daħħal
Harvard fis dan trie,

158
00:07:21,140 --> 00:07:23,560
I probabbilment jridu jibdew
billi jibda mid-għeruq,

159
00:07:23,560 --> 00:07:25,720
tħares lejn 10 għażliet tiegħi
quddiem lili, u qal

160
00:07:25,720 --> 00:07:28,700
Irrid immur fit-triq 1.

161
00:07:28,700 --> 00:07:29,700
KOLLOX SEW.

162
00:07:29,700 --> 00:07:31,810
>> Issa, 1 passaġġ bħalissa null.

163
00:07:31,810 --> 00:07:35,920
Mela jekk jien tixtieq li tipproċedi isfel f'din it-triq
li daħħal dan l-element fil-trie,

164
00:07:35,920 --> 00:07:42,040
I għandhom malloc node ġdid, għandhom 1
punt hemmhekk, u mbagħad jien tajba biex tmur.

165
00:07:42,040 --> 00:07:46,460
>> So I bażikament am fi
punt fejn jien wieqfa

166
00:07:46,460 --> 00:07:50,270
l-għerq tal-siġra jew l
trie u hemm 10 fergħat.

167
00:07:50,270 --> 00:07:52,260
Iżda kull fergħa għandha
xatba quddiem ta 'dan.

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

169
00:07:53,060 --> 00:07:54,850
Għaliex hemm xejn hemmhekk. L

170
00:07:54,850 --> 00:07:56,522
Nru passaġġ mingħajr periklu.

171
00:07:56,522 --> 00:07:58,980
Dan ifisser li hemm xejn
l-ebda minn dawk il-friegħi.

172
00:07:58,980 --> 00:08:02,532
Jekk nixtieq li jibdew bini
xi ħaġa, I tixtieq li tneħħi l-bieb.

173
00:08:02,532 --> 00:08:04,490
I tixtieq li tneħħi l-bieb
quddiem numru 1.

174
00:08:04,490 --> 00:08:05,698
U nixtieq li jimxu dan.

175
00:08:05,698 --> 00:08:08,060
U nixtieq li jibnu
post ieħor għalija li jmorru.

176
00:08:08,060 --> 00:08:09,470
>> U dan huwa dak I ghamilt hawn.

177
00:08:09,470 --> 00:08:11,430
Allura 1 ma jipponta lejn null.

178
00:08:11,430 --> 00:08:13,830
Stajt qal li huwa tajjeb li jinżlu hawn issa.

179
00:08:13,830 --> 00:08:15,789
I mibnija node ieħor.

180
00:08:15,789 --> 00:08:18,330
U meta niġi biex dik node, I
jkollhom deċiżjoni oħra li jagħmlu.

181
00:08:18,330 --> 00:08:20,890
Fejn am I se jmorru minn hawn?

182
00:08:20,890 --> 00:08:22,700
>> Well, stajt diġà niżlu 1.

183
00:08:22,700 --> 00:08:24,470
Allura issa I probabilment tixtieq li jinżlu 6.

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

185
00:08:24,970 --> 00:08:27,100
Għal darb'oħra, I jkollhom 10 postijiet I tista 'tagħżel.

186
00:08:27,100 --> 00:08:30,060
Mela ejja issa jinżlu numru 6.

187
00:08:30,060 --> 00:08:32,280
So I ċar l-gate
quddiem numru 6.

188
00:08:32,280 --> 00:08:33,250
U I walk stabbiliti hemmhekk.

189
00:08:33,250 --> 00:08:34,580
U jien jibnu node ieħor.

190
00:08:34,580 --> 00:08:37,630
U stajt laħqu punt junction ieħor.

191
00:08:37,630 --> 00:08:40,289
>> Għal darb'oħra, I jkollhom 10 għażliet
għall fejn I tista 'tmur.

192
00:08:40,289 --> 00:08:42,799
Stajt mċaqalqa 1-6.

193
00:08:42,799 --> 00:08:44,215
Allura issa I probabilment tixtieq li tmur sa 3.

194
00:08:44,215 --> 00:08:45,381
3, hemm imkien I tista 'tmur.

195
00:08:45,381 --> 00:08:48,980
So I jkollhom ċar li l-mod
u jibnu myself spazju ġdid.

196
00:08:48,980 --> 00:08:50,870
U mbagħad minn 3, fejn ma nixtieq li jmorru?

197
00:08:50,870 --> 00:08:52,450
Irrid li jinżlu 6.

198
00:08:52,450 --> 00:08:54,770
>> U, għal darb'oħra, I kellhom
ċar il-mod kif tagħmel dan.

199
00:08:54,770 --> 00:08:59,179
Allura issa stajt użati ewlieni tiegħi biex tiddaħħal joħolqu
lymph u jibdew jibnu dan trie.

200
00:08:59,179 --> 00:09:00,220
Stajt beda fl-għeruq.

201
00:09:00,220 --> 00:09:03,666
Stajt marret isfel 1636.

202
00:09:03,666 --> 00:09:05,540
U issa jien fil-qiegħ
hemm fuq dik node.

203
00:09:05,540 --> 00:09:06,610
U inti tista 'tkun kapaċi
tara fuq l-iskrin tiegħek.

204
00:09:06,610 --> 00:09:07,735
>> Huwa enfasizzat bl-isfar.

205
00:09:07,735 --> 00:09:10,020
Li meta I bħalissa am.

206
00:09:10,020 --> 00:09:11,300
Muftieħ My isir.

207
00:09:11,300 --> 00:09:13,030
Stajt eżawriti kull pożizzjoni fl-iskema tiegħi.

208
00:09:13,030 --> 00:09:15,040
So I ma tistax tmur aktar.

209
00:09:15,040 --> 00:09:17,720
Allura f'dan il-punt, I kollha
verament bżonn tagħmel hu li jgħidu, OK.

210
00:09:17,720 --> 00:09:18,990
Huwa tip ta 'bħal tfittex
stabbiliti fuq l-art,

211
00:09:18,990 --> 00:09:21,115
jekk int jaħseb
lilek innifsek bħala dan it-tip ta 'triq

212
00:09:21,115 --> 00:09:22,350
b'konnessjonijiet differenti.

213
00:09:22,350 --> 00:09:25,800
Tip ta 'tfittex l isfel u tip ta'
sprej pittura Harvard fuq l-art.

214
00:09:25,800 --> 00:09:26,800
Dik hija l-isem ta 'dan.

215
00:09:26,800 --> 00:09:28,300
Kun af dak hu l fuq dan il-post.

216
00:09:28,300 --> 00:09:31,870
Jekk nibdew fil-għerq u aħna jinżlu
1 u mbagħad 6 u mbagħad 3 u mbagħad 6,

217
00:09:31,870 --> 00:09:32,780
fejn ninsabu?

218
00:09:32,780 --> 00:09:35,640
Ukoll jekk inħarsu l isfel
u naraw Harvard, allura

219
00:09:35,640 --> 00:09:38,960
nafu li Harvard kien
imwaqqfa fl 1636 ibbażata fuq il-mod

220
00:09:38,960 --> 00:09:41,400
aħna qed timplimenta din l-istruttura tad-data.

221
00:09:41,400 --> 00:09:43,177
Allura li kien nisperaw sempliċi.

222
00:09:43,177 --> 00:09:44,760
Aħna qed tmur biex tagħmel żewġ inserzjonijiet aktar.

223
00:09:44,760 --> 00:09:50,060
U wieħed jittama li ser tgħin biex
tara dan isir darbtejn aktar.

224
00:09:50,060 --> 00:09:52,210
>> Issa, ejja daħħal università oħra.

225
00:09:52,210 --> 00:09:54,630
Ejja daħħal Yale fis dan trie.

226
00:09:54,630 --> 00:09:57,037
Yale twaqqfet fl 1701.

227
00:09:57,037 --> 00:09:58,870
Allura aħna ser tibda fil-
għerq, kif aħna dejjem do.

228
00:09:58,870 --> 00:09:59,890
U waqqafna pointer traversal.

229
00:09:59,890 --> 00:10:01,624
Aħna qed tmur għall-użu li jimxu permezz.

230
00:10:01,624 --> 00:10:03,790
L-ewwel ħaġa li rridu
tagħmel hu li tmur fit-triq 1.

231
00:10:03,790 --> 00:10:05,830
Dik hija l-ewwel numru ta 'ċavetta tagħna.

232
00:10:05,830 --> 00:10:08,420
Fortunatament, għalkemm, aħna ma
għandek tagħmel xi xogħol f'dan il-ħin.

233
00:10:08,420 --> 00:10:09,919
Il-passaġġ 1 tkun diġà ġiet ikklerjata.

234
00:10:09,919 --> 00:10:13,520
I approvat it preċedentement meta I
kien ddaħħal Harvard fl 1636.

235
00:10:13,520 --> 00:10:18,090
So I jistgħu b'sigurtà jiċċaqalqu
down 1 u biss jmorru hemm.

236
00:10:18,090 --> 00:10:20,150
Jekk tista 'timxi l-1.

237
00:10:20,150 --> 00:10:22,930
>> Issa, għalkemm, nixtieq li jmorru sa 7.

238
00:10:22,930 --> 00:10:24,280
I kklerjat l-mod ta '6.

239
00:10:24,280 --> 00:10:27,050
I know I jistgħu b'sigurtà
jipproċedi fit-triq 6.

240
00:10:27,050 --> 00:10:29,220
Imma I bżonn li tipproċedi fuq il-passaġġ 7.

241
00:10:29,220 --> 00:10:30,580
Mela xi do I bżonn tagħmel?

242
00:10:30,580 --> 00:10:35,070
Ukoll, bħad qabel, I biss bżonn
ċar li l-gate, toħroġ il-mod,

243
00:10:35,070 --> 00:10:38,740
u jibnu node ġdid mill-mogħdija 7.

244
00:10:38,740 --> 00:10:40,250
Eżatt bħal din.

245
00:10:40,250 --> 00:10:42,930
>> Allura issa stajt mċaqalqa 1 u mbagħad 7.

246
00:10:42,930 --> 00:10:45,550
U issa avviż, jien sort
ta 'fuq din Subbranch ġdid.

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

248
00:10:46,050 --> 00:10:49,260
Kollox mill-16 ta '
fuq, jien ma care about.

249
00:10:49,260 --> 00:10:50,720
Jien ma tagħmel 16 xejn.

250
00:10:50,720 --> 00:10:51,750
Li qed nagħmel 17 Jittieħed.

251
00:10:51,750 --> 00:10:58,380
>> Allura issa minn 17 dwar, I għandhom
tip ta 'blaze trails ġodda hawn.

252
00:10:58,380 --> 00:11:00,462
Il ċifri jmiss muftieħ tiegħi huwa ta '0.

253
00:11:00,462 --> 00:11:01,670
I ċertament ma tistax tikseb kullimkien.

254
00:11:01,670 --> 00:11:02,628
I biss mibnija din node.

255
00:11:02,628 --> 00:11:04,550
So I know hemm l-ebda
mogħdijiet quddiem minn hawn.

256
00:11:04,550 --> 00:11:06,370
So I għandhom jagħmlu waħda myself.

257
00:11:06,370 --> 00:11:09,360
>> So I malloc a node ġdid
u jkollhom 0 punt hemmhekk.

258
00:11:09,360 --> 00:11:12,770
U mbagħad waħda aktar ħin, I malloc a
node ġdid u jkollu punt wieħed hemmhekk.

259
00:11:12,770 --> 00:11:15,870
Għal darb'oħra, stajt eżawriti ewlieni tiegħi, 1701.

260
00:11:15,870 --> 00:11:18,472
So I tfittex l isfel u I isprej taż-żebgħa Yale.

261
00:11:18,472 --> 00:11:19,680
Dik hija l-isem ta 'dan node.

262
00:11:19,680 --> 00:11:24,660
>> U hekk issa jekk I qatt bżonn biex tara jekk Yale
huwa f'dan trie, I tibda fil-għeruq,

263
00:11:24,660 --> 00:11:27,060
I jinżlu 1701, u tfittex l isfel.

264
00:11:27,060 --> 00:11:30,030
U jekk nara isprej Yale
miżbugħa fuq l-art, imbagħad

265
00:11:30,030 --> 00:11:32,200
Naf Yale teżisti f'dan trie.

266
00:11:32,200 --> 00:11:32,950
Ejja nagħmlu waħda aktar.

267
00:11:32,950 --> 00:11:36,430
Ejja daħħal Dartmouth fis dan
trie, li twaqqfet fl-1769.

268
00:11:36,430 --> 00:11:37,750
>> Ibda fl-għerq ġdid.

269
00:11:37,750 --> 00:11:39,445
Ewwel ċifra tiegħi ta 'ċavetta tiegħi huwa 1.

270
00:11:39,445 --> 00:11:40,820
I jistgħu b'sigurtà jinżel f'din it-triq.

271
00:11:40,820 --> 00:11:42,400
Li diġà teżisti.

272
00:11:42,400 --> 00:11:44,040
Il ċifri jmiss tal ċavetta tiegħi hija ta '7.

273
00:11:44,040 --> 00:11:45,890
I jistgħu b'sigurtà jinżel f'din it-triq.

274
00:11:45,890 --> 00:11:47,540
Jeżisti wkoll.

275
00:11:47,540 --> 00:11:49,000
>> My jmiss huwa 6.

276
00:11:49,000 --> 00:11:52,860
Minn hawn, minn fejn I am bħalissa
bl-isfar hemm f'dak node tan-nofs,

277
00:11:52,860 --> 00:11:56,060
6 bħalissa huwa maqful off.

278
00:11:56,060 --> 00:11:58,830
Jekk irrid li jinżlu f'din it-triq,
Għandi biex tinbena myself.

279
00:11:58,830 --> 00:12:02,250
So I ser malloc a node ġdid
u jkollhom 6. punt hemmhekk.

280
00:12:02,250 --> 00:12:04,250
U mbagħad, għal darb'oħra, jien
tisreġ trails ġodda hawn.

281
00:12:04,250 --> 00:12:10,750
>> So I malloc node ġdid sabiex min
dak in-numru passaġġ node-- 9-- u mbagħad issa

282
00:12:10,750 --> 00:12:13,584
jekk I-ivvjaġġar 1769, u I tfittex l isfel.

283
00:12:13,584 --> 00:12:15,500
M'hemm xejn bħalissa
sprej miżbugħa hemm.

284
00:12:15,500 --> 00:12:16,930
Kapaċi nikteb Dartmouth.

285
00:12:16,930 --> 00:12:20,710
U stajt jiddaħħal
Dartmouth fil-trie.

286
00:12:20,710 --> 00:12:23,450
>> Allura dak li ddaħħal
affarijiet fil-trie.

287
00:12:23,450 --> 00:12:25,384
Issa rridu li tfittxija għal affarijiet.

288
00:12:25,384 --> 00:12:27,050
Kif nistgħu tfittxija għal affarijiet fil-trie?

289
00:12:27,050 --> 00:12:29,170
Ukoll, huwa pjuttost l-istess idea.

290
00:12:29,170 --> 00:12:33,620
Issa aħna biss jużaw l-ċifri tal-ċavetta
biex tara jekk nistgħu jinnavigaw mill-għeruq

291
00:12:33,620 --> 00:12:37,170
fejn irridu imorru fil-trie.

292
00:12:37,170 --> 00:12:41,620
>> Jekk aħna hit tmiem mejta fi kwalunkwe punt, imbagħad
nafu li dan l-element ma jistax jeżisti

293
00:12:41,620 --> 00:12:44,500
jew inkella dik it-triq se
diġà ġew approvati.

294
00:12:44,500 --> 00:12:45,930
Jekk nagħmlu dan il-mod kollu li
l-aħħar, kollha għandna bżonn tagħmel

295
00:12:45,930 --> 00:12:48,471
huwa tfittex l isfel u tara jekk dan huwa
l-element aħna qed tfittex.

296
00:12:48,471 --> 00:12:49,335
Jekk huwa, suċċess.

297
00:12:49,335 --> 00:12:52,610
Jekk mhuwiex, jonqsu.

298
00:12:52,610 --> 00:12:54,940
>> Mela ejja tfittxija għal
Harvard f'dan trie.

299
00:12:54,940 --> 00:12:56,020
Nibdew fl-għeruq.

300
00:12:56,020 --> 00:12:58,228
U, għal darb'oħra, aħna qed tmur biex
joħolqu pointer traversal

301
00:12:58,228 --> 00:12:59,390
tagħmel jiċċaqlaq tagħna għalina.

302
00:12:59,390 --> 00:13:02,080
Mill-għeruq nafu li l-
ewwel post għandna bżonn immorru huwa 1,

303
00:13:02,080 --> 00:13:03,390
nistgħu nagħmlu dan?

304
00:13:03,390 --> 00:13:03,982
Iva, nistgħu.

305
00:13:03,982 --> 00:13:04,690
Jekk teżisti mingħajr periklu.

306
00:13:04,690 --> 00:13:06,660
Aħna tista 'tmur hemm.

307
00:13:06,660 --> 00:13:08,440
>> Issa, il-post li jmiss għandna bżonn immorru huwa 6.

308
00:13:08,440 --> 00:13:10,557
Il-passaġġ 6 jeżistu minn hawn?

309
00:13:10,557 --> 00:13:11,140
Yeah, ma.

310
00:13:11,140 --> 00:13:12,690
Aħna tista 'tmur fit-triq 6.

311
00:13:12,690 --> 00:13:13,905
U aħna jispiċċaw hawn.

312
00:13:13,905 --> 00:13:16,130
>> Nistgħu jinżlu 3 passaġġ minn hawn?

313
00:13:16,130 --> 00:13:18,450
Ukoll, kif jirriżulta,
iva, li teżisti wisq.

314
00:13:18,450 --> 00:13:20,790
U nistgħu tikseb fuq il-6 passaġġ minn hawn?

315
00:13:20,790 --> 00:13:21,982
Iva, nistgħu.

316
00:13:21,982 --> 00:13:24,002
>> Aħna ma pjuttost imwieġba
il-kwistjoni għadu.

317
00:13:24,002 --> 00:13:25,710
Hemm għadu wieħed aktar
pass, li issa huwa

318
00:13:25,710 --> 00:13:28,520
għandna bżonn li tfittex l isfel u
tara jekk dan huwa actually--

319
00:13:28,520 --> 00:13:32,660
jekk aħna qed infittxu Harvard, huwa li
dak li nsibu wara we jeżawrixxi d ċavetta?

320
00:13:32,660 --> 00:13:35,430
Fl-eżempju aħna qed jużaw hawn,
is-snin huma dejjem erba 'numri.

321
00:13:35,430 --> 00:13:40,280
Iżda int tista 'tuża l-eżempju fejn
inti qed jaħżnu dizzjunarju ta 'kliem.

322
00:13:40,280 --> 00:13:44,060
>> U għalhekk minflok li 10 pointers
għall-lokazzjoni tiegħi, inti jista 'jkollok 26.

323
00:13:44,060 --> 00:13:46,040
Wieħed għal kull ittra tal-alfabett.

324
00:13:46,040 --> 00:13:50,350
U hemm xi kliem bħal BAT,
li hu subsett ta 'lott, per eżempju.

325
00:13:50,350 --> 00:13:53,511
U hekk anke jekk ikollok il-
aħħar tas-ċavetta u inti tfittex l isfel,

326
00:13:53,511 --> 00:13:55,260
inti tista 'ma tara dak
inti qed tfittex.

327
00:13:55,260 --> 00:13:58,500
>> Allura inti dejjem ikollhom biex travers
il-passaġġ kollu u mbagħad

328
00:13:58,500 --> 00:14:01,540
jekk inti kienu kapaċi b'suċċess
travers il-passaġġ kollu,

329
00:14:01,540 --> 00:14:03,440
tfittex l isfel u jagħmlu konferma finali wieħed.

330
00:14:03,440 --> 00:14:05,120
Hija li dak li jien tfittex?

331
00:14:05,120 --> 00:14:07,740
Well, I tfittex l isfel wara li tibda
fil-quċċata u jmorru 1636.

332
00:14:07,740 --> 00:14:08,240
I tfittex l isfel.

333
00:14:08,240 --> 00:14:09,400
Nara Harvard.

334
00:14:09,400 --> 00:14:11,689
Allura, iva, I irnexxielu.

335
00:14:11,689 --> 00:14:13,980
X'jiġri jekk dak I infittex
mhuwiex fil-trie, għalkemm.

336
00:14:13,980 --> 00:14:17,200
X'jiġri jekk I infittex Princeton,
li twaqqfet fl 1746.

337
00:14:17,200 --> 00:14:20,875
U hekk 1746 isir ewlenin tiegħi
li jinnavigaw fil-trie.

338
00:14:20,875 --> 00:14:22,040
Well, I tibda fil-għerq.

339
00:14:22,040 --> 00:14:24,760
U l-ewwel post nixtieq
li tmur fit-triq 1.

340
00:14:24,760 --> 00:14:25,590
Nista 'nagħmel dan?

341
00:14:25,590 --> 00:14:26,490
Iva, nista '.

342
00:14:26,490 --> 00:14:28,730
>> Nista jinżlu 7 triq minn hemm?

343
00:14:28,730 --> 00:14:29,230
Yeah, I jistgħu.

344
00:14:29,230 --> 00:14:30,750
Li teżisti wisq.

345
00:14:30,750 --> 00:14:32,460
Imma nista 'mmur l-4 triq minn hawn?

346
00:14:32,460 --> 00:14:35,550
Dik hija simili tistaqsi l-mistoqsija, jista
I jipproċedi isfel li ftit kwadru

347
00:14:35,550 --> 00:14:37,114
li stajt enfasizzat bl-isfar?

348
00:14:37,114 --> 00:14:38,030
M'hemm xejn hemmhekk.

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

350
00:14:38,610 --> 00:14:41,310
>> M'hemm l-ebda triq 'il quddiem fit-triq 4.

351
00:14:41,310 --> 00:14:46,480
Jekk Princeton kien f'dan trie, li 4
kien ikun approvat għalina diġà.

352
00:14:46,480 --> 00:14:49,130
U hekk f'dan il-punt
konna laħaq tmiem mejta.

353
00:14:49,130 --> 00:14:50,250
Aħna ma tistax tmur aktar.

354
00:14:50,250 --> 00:14:53,440
U hekk nistgħu ngħidu, b'mod definittiv, ebda.

355
00:14:53,440 --> 00:14:56,760
Princeton ma jeżistix f'dan il-trie.

356
00:14:56,760 --> 00:14:58,860
>> Allura dak li jfisser dan kollu jfisser?

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

358
00:14:59,360 --> 00:15:01,000
Hemm ħafna jiġri hawn fuq.

359
00:15:01,000 --> 00:15:02,500
Hemm indikaturi kollha fuq il-post.

360
00:15:02,500 --> 00:15:04,249
U, kif tistgħu taraw
biss mid-dijagramma,

361
00:15:04,249 --> 00:15:07,010
hemm ħafna ta 'punti ta' konġunzjoni li
huma tip ta 'jtajru madwar.

362
00:15:07,010 --> 00:15:13,480
Iżda avviż kull darba li ridna
tivverifika jekk xi ħaġa kienet fil-trie,

363
00:15:13,480 --> 00:15:15,000
aħna biss kellhom jagħmlu 4 jiċċaqlaq.

364
00:15:15,000 --> 00:15:17,208
>> Kull darba ridna
daħħal xi ħaġa fil-trie,

365
00:15:17,208 --> 00:15:20,440
irridu nkunu 4 jiċċaqlaq, possibilment
mallocing xi għalf matul it-triq.

366
00:15:20,440 --> 00:15:23,482
Imma kif rajna meta aħna inserit
Dartmouth fil-trie,

367
00:15:23,482 --> 00:15:25,940
kultant xi wħud mill-passaġġ
Wieħed diġà jista kklerjati għalina.

368
00:15:25,940 --> 00:15:30,520
U hekk kif trie tagħna tkompli tikber u
akbar, għandna nagħmlu inqas xogħol kull darba

369
00:15:30,520 --> 00:15:32,270
li daħħal affarijiet ġodda
għaliex aħna ħadthom diġà

370
00:15:32,270 --> 00:15:35,746
mibnija ħafna tas-sustanza intermedja
fergħat tul it-triq.

371
00:15:35,746 --> 00:15:38,370
Jekk aħna biss qatt tħares lejn
4 affarijiet, 4 huwa biss kostanti.

372
00:15:38,370 --> 00:15:41,750
Aħna verament huma tip ta 'toqrob
inserzjoni ħin kostanti

373
00:15:41,750 --> 00:15:44,501
u lookup ħin kostanti.

374
00:15:44,501 --> 00:15:47,500
Il tradeoff, naturalment, hija li
dan trie, kif inti tista 'probabbilment tgħid,

375
00:15:47,500 --> 00:15:49,030
huwa enormi.

376
00:15:49,030 --> 00:15:51,040
Kull waħda minn dawn in-nodi
jieħu ħafna spazju.

377
00:15:51,040 --> 00:15:52,090
>> Imma dak li l-tradeoff.

378
00:15:52,090 --> 00:15:55,260
Jekk irridu tassew mgħaġġla
inserzjoni, tħassir tassew mgħaġġla,

379
00:15:55,260 --> 00:15:59,630
u lookup tassew mgħaġġla, irridu
għandhom ħafna ta 'data jtajru madwar.

380
00:15:59,630 --> 00:16:03,590
Irridu twarrab ħafna spazju
u l-memorja għal dik l-istruttura tad-data

381
00:16:03,590 --> 00:16:04,290
jeżistu.

382
00:16:04,290 --> 00:16:05,415
>> U għalhekk dak l-tradeoff.

383
00:16:05,415 --> 00:16:07,310
Iżda jidher qisu aħna
jista sabuha.

384
00:16:07,310 --> 00:16:09,560
Aħna jista sabu li
Grail qaddis ta 'strutturi ta' dejta

385
00:16:09,560 --> 00:16:12,264
ma inserzjoni malajr,
tħassir, u Lookup.

386
00:16:12,264 --> 00:16:14,430
U forsi dan se jkun
istruttura xierqa data

387
00:16:14,430 --> 00:16:18,890
għall-użu għal kwalunkwe informazzjoni
aħna qed jippruvaw biex jaħżnu.

388
00:16:18,890 --> 00:16:21,860
Jien Doug Lloyd, dan huwa CS50.

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