1
00:00:00,000 --> 00:00:02,994
>> [Muzika]

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

3
00:00:05,426 --> 00:00:08,550
DOUG Lloyd: Pra, ne kemi qenë të afrohet
dhe më afër se Grail shenjtë e të dhënave

4
00:00:08,550 --> 00:00:13,050
struktura, ai që ne mund të futni
në, fshini nga, dhe të kërkoni

5
00:00:13,050 --> 00:00:15,440
në kohë të vazhdueshme.

6
00:00:15,440 --> 00:00:16,270
E drejtë.

7
00:00:16,270 --> 00:00:17,280
Kjo është lloj i qëllimit.

8
00:00:17,280 --> 00:00:19,720
Ne duam që të jenë në gjendje për të bërë
gjëra shumë, shumë shpejt.

9
00:00:19,720 --> 00:00:22,580
>> Kemi gjetur këtu kur
ne jemi duke folur për përpiqet?

10
00:00:22,580 --> 00:00:23,670
E pra, le të marrin një sy.

11
00:00:23,670 --> 00:00:25,628
Pra, ne kemi parë disa
strukturat e ndryshme të të dhënave

12
00:00:25,628 --> 00:00:28,680
që merret me pasqyrimin e
ashtuquajtura çifte kyç vlerë,

13
00:00:28,680 --> 00:00:32,080
hartë disa pjesë të të dhënave
në disa pjesë të tjera të të dhënave

14
00:00:32,080 --> 00:00:36,020
kështu që ne e dimë se ku për të gjetur
informacioni në strukturën.

15
00:00:36,020 --> 00:00:40,060
>> Pra për grup, për shembull,
Çelësi është indeksi ose elementi grup

16
00:00:40,060 --> 00:00:42,600
Vendndodhja 0 ose 1 grup dhe kështu me radhë.

17
00:00:42,600 --> 00:00:46,140
Dhe vlera janë të dhënat
që ekziston në atë vend.

18
00:00:46,140 --> 00:00:48,550
Pra, çfarë është ruajtur në rrjet 0?

19
00:00:48,550 --> 00:00:54,290
Çfarë është ruajtur në rrjet 1 kundrejt vetëm
0 dhe 1, e cila do të jetë çelësat.

20
00:00:54,290 --> 00:00:56,360
>> Me një tabelë hash është
lloj të njëjtën ide.

21
00:00:56,360 --> 00:01:00,690
Me një tabelë hash, ne kemi këtë hash
funksion që gjeneron kodet hash.

22
00:01:00,690 --> 00:01:03,670
Pra, çelësi është kodi hash e të dhënave.

23
00:01:03,670 --> 00:01:06,530
Dhe vlera, veçanërisht
kemi biseduar për chaining

24
00:01:06,530 --> 00:01:10,590
në video në tabelat hash,
është se lista e lidhur e të dhënave

25
00:01:10,590 --> 00:01:12,550
se hashes për atë hashcode.

26
00:01:12,550 --> 00:01:14,050
E drejtë.

27
00:01:14,050 --> 00:01:16,050
Po në lidhje me një tjetër përqasje
kjo metodë, edhe pse?

28
00:01:16,050 --> 00:01:21,000
Po në lidhje me një metodë ku
Çelësi është e garantuar të jetë unike,

29
00:01:21,000 --> 00:01:25,410
ndryshe nga një tabelë hash, ku ne mund të
përfundojnë me dy pjesë të të dhënave

30
00:01:25,410 --> 00:01:27,200
që ka të njëjtin hashcode.

31
00:01:27,200 --> 00:01:30,020
Dhe pastaj ne duhet të merren me
që nga ose probing ose më shumë

32
00:01:30,020 --> 00:01:33,340
mundësisht chaining për të rregulluar këtë problem.

33
00:01:33,340 --> 00:01:37,520
>> Deri tani ne mund të garantojë
se çelësi jonë do të jetë unik.

34
00:01:37,520 --> 00:01:39,690
Dhe çfarë nëse vlera jonë ishte
vetëm diçka aq e lehtë

35
00:01:39,690 --> 00:01:44,080
si vërteta dhe të rreme që na tregon nëse
apo jo ajo pjesë e informacionit

36
00:01:44,080 --> 00:01:45,610
ekziston në strukturën?

37
00:01:45,610 --> 00:01:48,180
Një Boolean mund të jetë aq e thjeshtë sa një grimë.

38
00:01:48,180 --> 00:01:52,660
Realisht kjo është ndoshta një
byte më shumë gjasa se një grimë.

39
00:01:52,660 --> 00:01:55,410
Por kjo është shumë më e vogël se
ruajtjen ndoshta një varg 50-karakter,

40
00:01:55,410 --> 00:01:57,360
për shembull.

41
00:01:57,360 --> 00:02:02,210
>> Pra përpiqet, të ngjashme me hash tavolina,
të cilat kombinojnë vargjeve dhe listë e lidhur,

42
00:02:02,210 --> 00:02:05,790
përpiqet të kombinuar vargjeve,
strukturat, dhe pointers

43
00:02:05,790 --> 00:02:08,509
së bashku për të ruajtur të dhënat në
një mënyrë interesante që është

44
00:02:08,509 --> 00:02:11,550
mjaft i ndryshëm nga
çdo gjë që kemi parë deri tani.

45
00:02:11,550 --> 00:02:16,750
Tani ne përdorim të dhënat si një udhërrëfyes
për të lundruar këtë strukturë të dhënave.

46
00:02:16,750 --> 00:02:18,710
Dhe në qoftë se ne mund të ndiqni
udhërrëfyesi, në qoftë se ne mund të

47
00:02:18,710 --> 00:02:22,390
ndjekin të dhënat nga
fillimi në fund, ne do të

48
00:02:22,390 --> 00:02:24,945
e di nëse këto të dhëna
ekzistojnë në Trie.

49
00:02:24,945 --> 00:02:28,310
>> Dhe në qoftë se ne nuk mund të ndiqni hartën
nga do të thotë në fund fare,

50
00:02:28,310 --> 00:02:30,600
të dhënat nuk mund të ekzistojë.

51
00:02:30,600 --> 00:02:32,890
Përsëri, çelësat këtu janë
garantuar të jetë unike.

52
00:02:32,890 --> 00:02:36,020
Dhe kështu ndryshe nga një tabelë hash, ne kurrë nuk do të
duhet të merren me goditjet këtu.

53
00:02:36,020 --> 00:02:39,090
Dhe nuk ka dy pjesë të të dhënave
kanë saktësisht të njëjtën udhërrëfyesin e

54
00:02:39,090 --> 00:02:40,530
përveç nëse që të dhënat është identike.

55
00:02:40,530 --> 00:02:44,580
>> Nëse ne të futur Gjoni, atëherë
ne kërko për Gjonit.

56
00:02:44,580 --> 00:02:47,430
Kjo është dy copa identike të
të dhënave, e drejtë, ne jemi duke kërkuar përmes.

57
00:02:47,430 --> 00:02:49,880
Por ndryshe, çdo
dy copa të të dhënave janë

58
00:02:49,880 --> 00:02:52,750
garantuara që të ketë plane unike
përmes kësaj strukture të dhënave.

59
00:02:52,750 --> 00:02:56,210
Dhe ne jemi duke shkuar për të marrë një vështrim në
një vizuale të këtë në një moment të vetëm.

60
00:02:56,210 --> 00:02:58,810
>> Ne do të bëjmë këtë duke u përpjekur për të
të krijojë një strukturë të re të të dhënave,

61
00:02:58,810 --> 00:03:00,564
hartës palë kyçe vlerë.

62
00:03:00,564 --> 00:03:03,480
Në këtë rast, ne nuk jemi duke shkuar për të përdorur
diçka e thjeshtë si një Boolean.

63
00:03:03,480 --> 00:03:06,200
Ne fakt do të ruajtur string.

64
00:03:06,200 --> 00:03:08,690
Dhe kjo varg do të
të jetë emri i një universiteti.

65
00:03:08,690 --> 00:03:12,140
>> Dhe çelësi do të jetë viti
kur se universiteti u themelua.

66
00:03:12,140 --> 00:03:15,380
Të gjitha vjet për universitetet
do të jenë katër shifra.

67
00:03:15,380 --> 00:03:19,840
Dhe kështu që ne do të përdorim këto katër shifra të
lundruar nëpër këtë strukturë të dhënave.

68
00:03:19,840 --> 00:03:22,270
Dhe ne do të shohim, përsëri, si
ne bëjmë atë në vetëm një të dytë.

69
00:03:22,270 --> 00:03:25,110
>> Në fund të rrugës,
ne do të shohim emrin

70
00:03:25,110 --> 00:03:30,250
e universitetit që korrespondon
në atë kyç, këto katër shifra.

71
00:03:30,250 --> 00:03:34,390
Ideja themelore prapa një Trie
është që ne kemi një rrugë qendrore.

72
00:03:34,390 --> 00:03:35,640
Pra, mendoni për atë si një pemë.

73
00:03:35,640 --> 00:03:39,211
Dhe kjo është e ngjashme në drejtshkrim
dhe në konceptin për një pemë.

74
00:03:39,211 --> 00:03:41,460
Në përgjithësi kur mendojmë për
pemë në botën e vërtetë,

75
00:03:41,460 --> 00:03:44,090
ata kanë një rrënjë që është në
terren dhe ata rriten lart

76
00:03:44,090 --> 00:03:46,830
dhe ata kanë degë
dhe ata kanë gjethe.

77
00:03:46,830 --> 00:03:49,450
Dhe në thelb ideja e
një Trie është saktësisht e njëjtë,

78
00:03:49,450 --> 00:03:51,755
përveç se rrënjë është ankoruar
diku në qiell.

79
00:03:51,755 --> 00:03:53,130
Dhe gjethet janë në fund.

80
00:03:53,130 --> 00:03:55,750
>> Pra, kjo është lloj i marrë si një pemë
dhe vetëm Flipping atë me kokë poshtë.

81
00:03:55,750 --> 00:03:56,880
Por ka ende degë.

82
00:03:56,880 --> 00:03:59,463
Dhe ata do të ishin rrugët tona,
ata do të jenë lidhjet tona

83
00:03:59,463 --> 00:04:02,220
nga rrënja në gjethe.

84
00:04:02,220 --> 00:04:04,200
Në këtë rast, ata
shtigjet, ato degë

85
00:04:04,200 --> 00:04:08,490
janë emërtuar me shifra që na tregojnë
cila rrugë për të shkuar nga aty ku jemi.

86
00:04:08,490 --> 00:04:11,800
>> Nëse ne shohim një 0, ne do të shkojmë poshtë këtë degë,
në qoftë se ne shohim një 1, ne do të shkojmë poshtë këtë degë,

87
00:04:11,800 --> 00:04:12,900
dhe kështu dhe kështu me radhë.

88
00:04:12,900 --> 00:04:14,060
E pra, çfarë do të thotë kjo?

89
00:04:14,060 --> 00:04:16,519
E pra, kjo do të thotë se
në çdo pikë kryqëzim

90
00:04:16,519 --> 00:04:19,260
dhe çdo nyje në
e mesme dhe çdo degë,

91
00:04:19,260 --> 00:04:23,020
ka 10 të mundshme
vende që ne mund të shkojnë.

92
00:04:23,020 --> 00:04:27,690
Pra, ka 10 pointers
nga çdo vend.

93
00:04:27,690 --> 00:04:30,610
>> Dhe ky është vendi ku mundohet mund të merrni
pak frikësuese për dikë

94
00:04:30,610 --> 00:04:34,460
i cili nuk ka shumë
Përvoja në shkenca kompjuterike para.

95
00:04:34,460 --> 00:04:35,960
Por mundohet janë me të vërtetë shumë e awesome.

96
00:04:35,960 --> 00:04:37,793
Dhe në qoftë se ju keni
shans për të punuar me ta

97
00:04:37,793 --> 00:04:40,420
dhe ju jeni të gatshëm për të gërmoj-në
dhe të eksperimentojnë me ta,

98
00:04:40,420 --> 00:04:44,234
ata janë me të vërtetë mjaft interesante
strukturat e të dhënave për të punuar me të.

99
00:04:44,234 --> 00:04:46,900
Në qoftë se ne duam të futur një element
në Trie, të gjithë ne duhet të bëjmë

100
00:04:46,900 --> 00:04:51,360
është ndërtuar rrugën e drejtë
nga rrënja deri në fletë.

101
00:04:51,360 --> 00:04:55,390
Ja se çfarë çdo hap përgjatë
mënyra mund të duket si.

102
00:04:55,390 --> 00:04:59,660
Ne jemi duke shkuar për të përcaktuar një të dhënave të re
Struktura për një nyje të re të quajtur një Trie.

103
00:04:59,660 --> 00:05:02,560
>> Dhe brenda kësaj dhënave
Struktura ka dy pjesë.

104
00:05:02,560 --> 00:05:05,460
Ne jemi duke shkuar për të ruajtur
emri i një universiteti.

105
00:05:05,460 --> 00:05:09,410
Dhe ne jemi duke shkuar për të ruajtur
një grup i pointers

106
00:05:09,410 --> 00:05:12,190
të nyjeve të tjera të tipit të njëjtë.

107
00:05:12,190 --> 00:05:14,780
Pra, përsëri, kjo është se lloj
e konceptit të kudo

108
00:05:14,780 --> 00:05:18,567
ne jemi, ne në 10 të mundshme
vende ne mund të shkojnë.

109
00:05:18,567 --> 00:05:20,150
Nëse ne shohim një 0, ne do të shkojmë poshtë këtë degë.

110
00:05:20,150 --> 00:05:22,690
Nëse ne shohim një 1, kjo degë,
dhe kështu me radhë e kështu me radhë e kështu me radhë.

111
00:05:22,690 --> 00:05:25,160
Nëse themi 9, ne do të shkojmë poshtë këtë degë.

112
00:05:25,160 --> 00:05:28,220
Pra, në çdo pikë kryqëzim,
ne mund të shkojnë 10 vende të mundshme.

113
00:05:28,220 --> 00:05:35,740
Pra, çdo nyje duhet të përmbajë 10 pointers
për nyjet e tjera, deri në 10 nyjet e tjera.

114
00:05:35,740 --> 00:05:39,810
>> Dhe të dhënat që ne jemi ruajtjen është
vetëm emri i universitetit.

115
00:05:39,810 --> 00:05:41,060
Pra, le të ndërtojmë një Trie.

116
00:05:41,060 --> 00:05:44,860
Le të futur një çift
e artikujve në Trie tonë.

117
00:05:44,860 --> 00:05:46,740
Pra, në shumë të lartë,
kjo është nyja jonë rrënjë.

118
00:05:46,740 --> 00:05:49,740
Kjo është ndoshta do të jetë diçka
ju jeni do të shpallim globalisht.

119
00:05:49,740 --> 00:05:53,450
Dhe ju do të jeni për të ruajtur globalisht
një tregues për këtë nyje gjithmonë.

120
00:05:53,450 --> 00:05:55,360
>> Ju jeni duke shkuar për të thënë,
rrënjë barabartë, dhe ju jeni

121
00:05:55,360 --> 00:05:57,580
do të malloc veten nyje Trie.

122
00:05:57,580 --> 00:05:59,850
Dhe ju kurrë nuk do të jeni
për të prekur rrënjë përsëri.

123
00:05:59,850 --> 00:06:02,300
Çdo herë që dëshironi të
të fillojë lundrimit nëpër,

124
00:06:02,300 --> 00:06:05,802
keni vendosur një akrep
barabartë me rrënjës, të tilla si trav,

125
00:06:05,802 --> 00:06:07,760
i cili është shembulli i
përdorim në shumë prej videot e mia

126
00:06:07,760 --> 00:06:11,090
këtu në oxhaqet dhe radhët e gjata
dhe listat Link dhe kështu me radhë.

127
00:06:11,090 --> 00:06:13,320
>> Ju vendosur një akrep
thirrje Trav për traversal.

128
00:06:13,320 --> 00:06:15,890
Dhe ju përdorni për të lundruar trav
nëpërmjet strukturës së të dhënave.

129
00:06:15,890 --> 00:06:17,500
Pra, le të shohim se si kjo mund të duket.

130
00:06:17,500 --> 00:06:19,880
Deri tani, çfarë
nuk duket si një nyje?

131
00:06:19,880 --> 00:06:22,920
E pra, ashtu si të dhëna tona
Deklarata Struktura e treguar,

132
00:06:22,920 --> 00:06:26,906
ne kemi një varg, i cili
në këtë rast është bosh.

133
00:06:26,906 --> 00:06:27,780
Nuk ka asgjë këtu.

134
00:06:27,780 --> 00:06:29,550
>> Dhe një grup prej 10 pointers.

135
00:06:29,550 --> 00:06:31,790
Dhe tani, ne vetëm
1 nyje në këtë Trie.

136
00:06:31,790 --> 00:06:33,110
Nuk ka asgjë tjetër në të.

137
00:06:33,110 --> 00:06:36,020
Pra, të gjithë 10 e atyre
pointers pikë të null.

138
00:06:36,020 --> 00:06:38,090
Kjo është ajo që e kuqe tregon.

139
00:06:38,090 --> 00:06:39,500
>> Le të futur vargun Harvardit.

140
00:06:39,500 --> 00:06:41,999
Le të futur në Universitetin e
Harvard në këtë Trie, i cili

141
00:06:41,999 --> 00:06:43,940
u themelua në vitin 1636.

142
00:06:43,940 --> 00:06:48,220
Ne duam që të përdorni tastin,
1636, për të na tregoni se ku ne jemi

143
00:06:48,220 --> 00:06:50,140
duke shkuar për të ruajtur Harvardit në Trie.

144
00:06:50,140 --> 00:06:51,470
Tani, si mund ta bëjmë këtë?

145
00:06:51,470 --> 00:06:52,886
>> Kjo mund të duket diçka si kjo.

146
00:06:52,886 --> 00:06:54,160
Ne të fillojë në rrënjë.

147
00:06:54,160 --> 00:06:56,920
Dhe ne kemi këto 10 vende ne mund të shkojnë.

148
00:06:56,920 --> 00:06:59,900
Rrënja është vetëm si çdo
nyje të tjera të Trie.

149
00:06:59,900 --> 00:07:02,850
Ka 10 vende ne mund të shkojë nga këtu.

150
00:07:02,850 --> 00:07:07,215
>> Ku ne ndoshta duam
për të shkuar në qoftë se çelësi është 1636?

151
00:07:07,215 --> 00:07:08,340
Ka me të vërtetë dy opsione.

152
00:07:08,340 --> 00:07:08,450
E drejtë.

153
00:07:08,450 --> 00:07:10,825
Ne mund të ndërtojmë kyç nga
djathta në të majtë dhe të fillojnë me 6.

154
00:07:10,825 --> 00:07:14,000
Ose ne mund të ndërtojmë kyç nga
majta në të djathtë dhe të fillojnë me 1.

155
00:07:14,000 --> 00:07:16,140
>> Kjo është ndoshta më shumë
intuitive si një qenie njerëzore

156
00:07:16,140 --> 00:07:18,110
për të kuptuar ne do të
Vetëm të shkojnë majta në të djathtë.

157
00:07:18,110 --> 00:07:21,140
Dhe kështu që në qoftë se unë dua të futur
Harvard në këtë Trie,

158
00:07:21,140 --> 00:07:23,560
Unë ndoshta duan të fillojnë
duke filluar në rrënjë,

159
00:07:23,560 --> 00:07:25,720
duke kërkuar në 10 opsionet e mia
para meje, dhe duke thënë

160
00:07:25,720 --> 00:07:28,700
Unë dua të shkoj poshtë 1 rrugën.

161
00:07:28,700 --> 00:07:29,700
NE RREGULL.

162
00:07:29,700 --> 00:07:31,810
>> Tani, 1 rruga është aktualisht null.

163
00:07:31,810 --> 00:07:35,920
Pra, nëse unë dua të vazhdoj poshtë këtë rrugë
për të futur këtë element në Trie,

164
00:07:35,920 --> 00:07:42,040
Unë kam për të malloc një nyje të re, kanë 1
pikë atje, dhe pastaj unë jam i mirë për të shkuar.

165
00:07:42,040 --> 00:07:46,460
>> Kështu që unë jam në thelb një
pikë ku unë jam duke qëndruar

166
00:07:46,460 --> 00:07:50,270
në rrënjët e pemës apo në
Trie dhe ka 10 degë.

167
00:07:50,270 --> 00:07:52,260
Por secila degë ka një
porta në frontin e tij.

168
00:07:52,260 --> 00:07:53,060
E drejtë.

169
00:07:53,060 --> 00:07:54,850
Sepse nuk ka asgjë tjetër nuk ka.

170
00:07:54,850 --> 00:07:56,522
Nuk ka kalim të sigurt.

171
00:07:56,522 --> 00:07:58,980
Kjo do të thotë se nuk ka asgjë
poshtë ndonjë prej këtyre degëve.

172
00:07:58,980 --> 00:08:02,532
Nëse unë dua të fillojë ndërtimin
diçka, unë dua për të hequr portën.

173
00:08:02,532 --> 00:08:04,490
Unë dua për të hequr portën
në frontin e numrit 1.

174
00:08:04,490 --> 00:08:05,698
Dhe unë dua të ecin poshtë atë.

175
00:08:05,698 --> 00:08:08,060
Dhe unë dua të ndërtoj
Një tjetër vend për mua për të shkuar.

176
00:08:08,060 --> 00:08:09,470
>> Dhe kjo është ajo që unë kam bërë këtu.

177
00:08:09,470 --> 00:08:11,430
Pra, 1 nuk tregon null.

178
00:08:11,430 --> 00:08:13,830
Unë e kam thënë se është e sigurt për të shkuar poshtë këtu tani.

179
00:08:13,830 --> 00:08:15,789
I ndërtuar një nyje.

180
00:08:15,789 --> 00:08:18,330
Dhe kur të shkoj në atë nyje, unë
kanë një tjetër vendim për të bërë.

181
00:08:18,330 --> 00:08:20,890
Ku jam duke shkuar për të shkuar nga këtu?

182
00:08:20,890 --> 00:08:22,700
>> E pra, unë kam shkuar tashmë poshtë 1.

183
00:08:22,700 --> 00:08:24,470
Kështu që tani unë ndoshta dua të shkoj poshtë 6.

184
00:08:24,470 --> 00:08:24,970
E drejtë.

185
00:08:24,970 --> 00:08:27,100
Përsëri, unë kam 10 vende unë mund të zgjidhni.

186
00:08:27,100 --> 00:08:30,060
Pra, tani le të zbresin numrin 6.

187
00:08:30,060 --> 00:08:32,280
Kështu që unë të qartë portën
në frontin e numrit 6.

188
00:08:32,280 --> 00:08:33,250
Dhe unë eci atje poshtë.

189
00:08:33,250 --> 00:08:34,580
Dhe unë ndërtoj një tjetër nyje.

190
00:08:34,580 --> 00:08:37,630
Dhe unë kam arritur në një pikë tjetër kryqëzim.

191
00:08:37,630 --> 00:08:40,289
>> Përsëri, unë kam 10 zgjedhje
për ku unë mund të shkoj.

192
00:08:40,289 --> 00:08:42,799
Kam lëvizur nga 1 deri në 6.

193
00:08:42,799 --> 00:08:44,215
Kështu që tani unë ndoshta dëshironi të shkoni në 3.

194
00:08:44,215 --> 00:08:45,381
3, nuk ka ku unë mund të shkoj.

195
00:08:45,381 --> 00:08:48,980
Kështu që unë kam për të pastruar rrugën
dhe të ndërtoj një hapësirë ​​të re.

196
00:08:48,980 --> 00:08:50,870
Dhe pastaj nga 3, ku dua të shkoj?

197
00:08:50,870 --> 00:08:52,450
Unë dua të shkoj poshtë 6.

198
00:08:52,450 --> 00:08:54,770
>> Dhe, përsëri, unë kam për të
të pastruar rrugën për të bërë atë.

199
00:08:54,770 --> 00:08:59,179
Deri tani unë kam përdorur çelësin tim për të futur të krijuar
nyjet dhe të fillojnë për të ndërtuar këtë Trie.

200
00:08:59,179 --> 00:09:00,220
Unë kam filluar në rrënjë.

201
00:09:00,220 --> 00:09:03,666
Unë kam shkuar poshtë 1636.

202
00:09:03,666 --> 00:09:05,540
Dhe tani unë jam në fund
aty në atë nyje.

203
00:09:05,540 --> 00:09:06,610
Dhe ju mund të jetë në gjendje të
shohin atë në ekranin tuaj.

204
00:09:06,610 --> 00:09:07,735
>> Është theksuar në të verdhë.

205
00:09:07,735 --> 00:09:10,020
Kjo është ajo ku unë aktualisht jam.

206
00:09:10,020 --> 00:09:11,300
Çelësi im është bërë.

207
00:09:11,300 --> 00:09:13,030
Unë e kam shteruar çdo pozicion në Key time.

208
00:09:13,030 --> 00:09:15,040
Kështu që unë nuk mund të shkojmë më tutje.

209
00:09:15,040 --> 00:09:17,720
Pra, në këtë pikë, të gjithë i
me të vërtetë duhet të bëni është të thënë, në rregull.

210
00:09:17,720 --> 00:09:18,990
Kjo është lloj i pëlqen kërkim
poshtë në tokë,

211
00:09:18,990 --> 00:09:21,115
në qoftë se ju jeni duke parashikuar
veten si këtë lloj të rrugës

212
00:09:21,115 --> 00:09:22,350
me lidhje të ndryshme.

213
00:09:22,350 --> 00:09:25,800
Lloj të shikuar poshtë dhe lloj
llak pikturë Harvard në terren.

214
00:09:25,800 --> 00:09:26,800
Ky është emri i kësaj.

215
00:09:26,800 --> 00:09:28,300
E di se kjo është ajo që është në këtë vend.

216
00:09:28,300 --> 00:09:31,870
Në qoftë se ne të fillojë në rrënjë dhe ne do të shkojmë poshtë
1 dhe pastaj 6 dhe pastaj 3 dhe pastaj 6,

217
00:09:31,870 --> 00:09:32,780
ku jemi ne?

218
00:09:32,780 --> 00:09:35,640
E pra, nëse ne shikojmë poshtë
dhe ne shohim Harvard, pastaj

219
00:09:35,640 --> 00:09:38,960
ne e dimë se Harvardit ishte
themeluar në vitin 1636 në bazë të rrugës

220
00:09:38,960 --> 00:09:41,400
ne jemi duke zbatuar këtë strukturën e të dhënave.

221
00:09:41,400 --> 00:09:43,177
Kështu që ishte shpresë e thjeshtë.

222
00:09:43,177 --> 00:09:44,760
Ne jemi duke shkuar për të bërë dy insertions më shumë.

223
00:09:44,760 --> 00:09:50,060
Dhe shpresojmë se ajo do të ndihmojë për të
shih kjo bëhet dy herë më shumë.

224
00:09:50,060 --> 00:09:52,210
>> Tani, le të futur një tjetër universitet.

225
00:09:52,210 --> 00:09:54,630
Le të futur Yale në këtë Trie.

226
00:09:54,630 --> 00:09:57,037
Yale u themelua në 1701.

227
00:09:57,037 --> 00:09:58,870
Pra, ne do të fillojë në nivel
rrënjë, si ne gjithmonë të bëjë.

228
00:09:58,870 --> 00:09:59,890
Dhe ne kemi vendosur një tregues traversal.

229
00:09:59,890 --> 00:10:01,624
Ne jemi duke shkuar për të përdorur atë për të lëvizur nëpër.

230
00:10:01,624 --> 00:10:03,790
Gjëja e parë që ne duam të
bëni është të shkoni poshtë 1 rrugën.

231
00:10:03,790 --> 00:10:05,830
Kjo është shifra e parë e kyç tonë.

232
00:10:05,830 --> 00:10:08,420
Për fat të mirë, edhe pse, ne nuk e bëjmë
keni për të bërë ndonjë punë këtë herë.

233
00:10:08,420 --> 00:10:09,919
Në 1 rruga tashmë është pastruar.

234
00:10:09,919 --> 00:10:13,520
I pastruar atë më parë kur unë
ishte futur në Harvard në 1636.

235
00:10:13,520 --> 00:10:18,090
Kështu që unë mund të sigurtë të lëvizin
poshtë 1 dhe thjesht shkoni atje.

236
00:10:18,090 --> 00:10:20,150
Nëse mund të lëvizin poshtë 1.

237
00:10:20,150 --> 00:10:22,930
>> Tani, edhe pse, unë dua të shkoj në 7.

238
00:10:22,930 --> 00:10:24,280
I hapi rrugën në 6.

239
00:10:24,280 --> 00:10:27,050
Unë e di unë mund të sigurtë
të vazhdojë në rrugën 6.

240
00:10:27,050 --> 00:10:29,220
Por kam nevojë për të vazhduar në rrugën 7.

241
00:10:29,220 --> 00:10:30,580
Pra, çfarë duhet të bëj?

242
00:10:30,580 --> 00:10:35,070
E pra, ashtu si më parë, unë vetëm nevojë
për të pastruar portën, të marrë nga rruga,

243
00:10:35,070 --> 00:10:38,740
dhe për të ndërtuar një nyje të re nga rruga 7.

244
00:10:38,740 --> 00:10:40,250
Ashtu si kjo.

245
00:10:40,250 --> 00:10:42,930
>> Deri tani unë kam lëvizur 1 dhe pastaj 7.

246
00:10:42,930 --> 00:10:45,550
Dhe tani vini re, unë jam lloj
e në këtë Subbranch ri.

247
00:10:45,550 --> 00:10:46,050
E drejtë.

248
00:10:46,050 --> 00:10:49,260
Çdo gjë tjetër nga 16
në, unë nuk e kujdesit në lidhje me.

249
00:10:49,260 --> 00:10:50,720
Unë nuk jam duke bërë 16 asgjë.

250
00:10:50,720 --> 00:10:51,750
Unë jam duke bërë 17 gjëra.

251
00:10:51,750 --> 00:10:58,380
>> Deri tani nga 17 e tutje, unë kam për të
lloj i flakët shtigje të reja këtu.

252
00:10:58,380 --> 00:11:00,462
Shifra tjetër Çelësi im është 0.

253
00:11:00,462 --> 00:11:01,670
Unë në mënyrë të qartë nuk mund të merrni kudo.

254
00:11:01,670 --> 00:11:02,628
Unë vetëm ndërtuar këtë nyje.

255
00:11:02,628 --> 00:11:04,550
Kështu që unë e di se nuk ka asnjë
Shtigjet përpara nga këtu.

256
00:11:04,550 --> 00:11:06,370
Pra, unë kam për të bërë një veten.

257
00:11:06,370 --> 00:11:09,360
>> Kështu që unë malloc një nyje të re
dhe kanë 0 pikë atje.

258
00:11:09,360 --> 00:11:12,770
Dhe pastaj një herë më shumë, unë malloc një
nyje të reja dhe kanë një pikë atje.

259
00:11:12,770 --> 00:11:15,870
Përsëri, unë e kam lodhur çelësin tim, 1701.

260
00:11:15,870 --> 00:11:18,472
Kështu që unë shikoj poshtë dhe unë llak bojë Yale.

261
00:11:18,472 --> 00:11:19,680
Ky është emri i këtij nyje.

262
00:11:19,680 --> 00:11:24,660
>> Dhe kështu që tani, nëse unë ndonjëherë nevojë për të parë nëse Yale
është në këtë Trie, unë të fillojë në rrënjë,

263
00:11:24,660 --> 00:11:27,060
Unë shkoj poshtë 1701, dhe shikoni poshtë.

264
00:11:27,060 --> 00:11:30,030
Dhe në qoftë se unë shoh Yale llak
pikturuar mbi tokë, atëherë

265
00:11:30,030 --> 00:11:32,200
Unë e di Yale ekziston në këtë Trie.

266
00:11:32,200 --> 00:11:32,950
Le të bëjmë një më shumë.

267
00:11:32,950 --> 00:11:36,430
Le të futur Dartmouth në këtë
Trie, e cila u themelua në 1769.

268
00:11:36,430 --> 00:11:37,750
>> Të fillojë në rrënjë përsëri.

269
00:11:37,750 --> 00:11:39,445
Shifra ime e parë e çelësit tim është 1.

270
00:11:39,445 --> 00:11:40,820
Unë mund të sigurtë të lëvizin poshtë këtë rrugë.

271
00:11:40,820 --> 00:11:42,400
Që tashmë ekziston.

272
00:11:42,400 --> 00:11:44,040
Shifra tjetër e çelësit tim është 7.

273
00:11:44,040 --> 00:11:45,890
Unë mund të sigurtë të lëvizin poshtë këtë rrugë.

274
00:11:45,890 --> 00:11:47,540
Ajo ekziston si.

275
00:11:47,540 --> 00:11:49,000
>> Im i ardhshëm është 6.

276
00:11:49,000 --> 00:11:52,860
Prej këtu, nga ku unë aktualisht jam
në të verdhë atje në atë nyje e mesme,

277
00:11:52,860 --> 00:11:56,060
6 është momentalisht E Mbyllur off.

278
00:11:56,060 --> 00:11:58,830
Nëse unë dua të shkoj poshtë këtë rrugë,
Unë kam për të ndërtuar atë vetë.

279
00:11:58,830 --> 00:12:02,250
Kështu që unë do malloc një nyje të re
dhe kanë 6 pikë atje.

280
00:12:02,250 --> 00:12:04,250
Dhe pastaj, përsëri, unë jam
flakëron shtigje të reja këtu.

281
00:12:04,250 --> 00:12:10,750
>> Kështu që unë malloc një nyje të re në mënyrë që nga
se numri rrugë node-- 9-- dhe pastaj tani

282
00:12:10,750 --> 00:12:13,584
në qoftë se unë e udhëtimit vitin 1769, dhe unë shikoj poshtë.

283
00:12:13,584 --> 00:12:15,500
Nuk ka asgjë për momentin
llak pikturuar atje.

284
00:12:15,500 --> 00:12:16,930
Unë mund të shkruaj Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Dhe unë e kam futur
Dartmouth në Trie.

286
00:12:20,710 --> 00:12:23,450
>> Pra, kjo është futur
gjërat në të Trie.

287
00:12:23,450 --> 00:12:25,384
Tani ne duam të kërkoni për gjëra.

288
00:12:25,384 --> 00:12:27,050
Si mund të kërkoni për gjërat në Trie?

289
00:12:27,050 --> 00:12:29,170
E pra, kjo është shumë e shumë të njëjtën ide.

290
00:12:29,170 --> 00:12:33,620
Tani ne vetëm përdorni shifrat e kyç
për të parë nëse ne mund të lundruar nga rrënja

291
00:12:33,620 --> 00:12:37,170
ku duam të shkojmë në Trie.

292
00:12:37,170 --> 00:12:41,620
>> Nëse ne goditi një fund të vdekur në çdo pikë, atëherë
ne e dimë se se elementi nuk mund të ekziston

293
00:12:41,620 --> 00:12:44,500
ose tjetër se rruga do të
tashmë janë pastruar.

294
00:12:44,500 --> 00:12:45,930
Nëse bëjmë atë gjatë gjithë rrugës për
në fund, të gjithë ne duhet të bëjmë

295
00:12:45,930 --> 00:12:48,471
është të shikoni poshtë dhe të shohim nëse kjo është
elementi ne jemi duke kërkuar për të.

296
00:12:48,471 --> 00:12:49,335
Nëse kjo është, suksesi.

297
00:12:49,335 --> 00:12:52,610
Nëse nuk është, dështojnë.

298
00:12:52,610 --> 00:12:54,940
>> Pra, le të kërkoni për
Harvard në këtë Trie.

299
00:12:54,940 --> 00:12:56,020
Ne të fillojë në rrënjë.

300
00:12:56,020 --> 00:12:58,228
Dhe, përsëri, ne jemi duke shkuar për
të krijojë një akrep traversal

301
00:12:58,228 --> 00:12:59,390
për të bërë lëvizje tonën.

302
00:12:59,390 --> 00:13:02,080
Nga rrënja ne e dimë se
Vendin e parë ne kemi nevojë për të shkuar është 1,

303
00:13:02,080 --> 00:13:03,390
mund ta bëjmë këtë?

304
00:13:03,390 --> 00:13:03,982
Po ne mundemi.

305
00:13:03,982 --> 00:13:04,690
Nëse në mënyrë të sigurtë ekziston.

306
00:13:04,690 --> 00:13:06,660
Ne mund të shkojnë atje.

307
00:13:06,660 --> 00:13:08,440
>> Tani, vendi tjetër ne kemi nevojë për të shkuar është 6.

308
00:13:08,440 --> 00:13:10,557
A ekziston rruga 6 nga këtu?

309
00:13:10,557 --> 00:13:11,140
Po, ajo bën.

310
00:13:11,140 --> 00:13:12,690
Ne mund të shkojnë në rrugën 6.

311
00:13:12,690 --> 00:13:13,905
Dhe ne fund deri këtu.

312
00:13:13,905 --> 00:13:16,130
>> A mund të shkojmë poshtë në 3 rrugën nga këtu?

313
00:13:16,130 --> 00:13:18,450
E pra, siç rezulton,
po, që ekziston edhe.

314
00:13:18,450 --> 00:13:20,790
Dhe mund të marrim në 6 rrugën nga këtu?

315
00:13:20,790 --> 00:13:21,982
Po ne mundemi.

316
00:13:21,982 --> 00:13:24,002
>> Ne nuk janë përgjigjur fare
pyetja akoma.

317
00:13:24,002 --> 00:13:25,710
Ka ende një më shumë
hap, e cila tani është

318
00:13:25,710 --> 00:13:28,520
ne duhet të shikoni poshtë dhe
të shohim nëse kjo është actually--

319
00:13:28,520 --> 00:13:32,660
në qoftë se ne jemi duke kërkuar për Harvardit, është se
Çfarë ne gjejmë pasi ne shter çelësin?

320
00:13:32,660 --> 00:13:35,430
Në shembullin ne jemi duke përdorur këtu,
vite janë gjithmonë katër shifra.

321
00:13:35,430 --> 00:13:40,280
Por ju mund të jeni duke përdorur shembullin ku
po mbledh një fjalor të fjalëve.

322
00:13:40,280 --> 00:13:44,060
>> Dhe kështu në vend që 10 pointers
për vendndodhjen time, ju mund të keni 26.

323
00:13:44,060 --> 00:13:46,040
Një për çdo letër e alfabetit.

324
00:13:46,040 --> 00:13:50,350
Dhe ka disa fjalë si bat,
i cili është një mesin e batch, per shembull.

325
00:13:50,350 --> 00:13:53,511
Dhe kështu që edhe në qoftë se ju merrni të
Fundi i kyç dhe ju shikoni poshtë,

326
00:13:53,511 --> 00:13:55,260
ju nuk mund të shihni se çfarë
ju jeni duke kërkuar për.

327
00:13:55,260 --> 00:13:58,500
>> Kështu që ju gjithmonë duhet të kaloj
tërë rruga dhe pastaj

328
00:13:58,500 --> 00:14:01,540
qoftë se keni qenë në gjendje me sukses
të kaloj nëpër të gjithë rrugën,

329
00:14:01,540 --> 00:14:03,440
shikoni poshtë dhe të bëjë një konfirmim përfundimtar.

330
00:14:03,440 --> 00:14:05,120
A është kjo ajo që unë jam duke kërkuar për?

331
00:14:05,120 --> 00:14:07,740
E pra, unë shikoj poshtë pas fillimit
në krye dhe të shkojnë 1636.

332
00:14:07,740 --> 00:14:08,240
Unë shoh poshtë.

333
00:14:08,240 --> 00:14:09,400
Unë shoh në Harvard.

334
00:14:09,400 --> 00:14:11,689
Pra, po, kam pasur sukses.

335
00:14:11,689 --> 00:14:13,980
Çka nëse ajo që unë jam duke kërkuar për
nuk është në Trie, edhe pse.

336
00:14:13,980 --> 00:14:17,200
Çka nëse unë jam duke kërkuar për Princeton,
e cila u themelua në 1746.

337
00:14:17,200 --> 00:14:20,875
Dhe kështu 1746 bëhet çelësi im
për të lundruar nëpër Trie.

338
00:14:20,875 --> 00:14:22,040
E pra, unë të fillojë në rrënjë.

339
00:14:22,040 --> 00:14:24,760
Dhe vendi i parë që unë dua
të shkon poshtë 1 rrugën.

340
00:14:24,760 --> 00:14:25,590
A mund ta bëjë këtë?

341
00:14:25,590 --> 00:14:26,490
Po, unë mund të.

342
00:14:26,490 --> 00:14:28,730
>> A mund të shkoj poshtë në 7 rrugën nga atje?

343
00:14:28,730 --> 00:14:29,230
Po, unë mund të.

344
00:14:29,230 --> 00:14:30,750
Që ekziston shumë.

345
00:14:30,750 --> 00:14:32,460
Por mund të shkoj poshtë në 4 rrugën nga këtu?

346
00:14:32,460 --> 00:14:35,550
Kjo është si të pyesësh pyetje, mund
Unë vazhdoj poshtë që pak katrore

347
00:14:35,550 --> 00:14:37,114
që unë e kam theksuar në të verdhë?

348
00:14:37,114 --> 00:14:38,030
Nuk ka asgjë atje.

349
00:14:38,030 --> 00:14:38,610
E drejtë.

350
00:14:38,610 --> 00:14:41,310
>> Nuk ka asnjë mënyrë përpara poshtë në rrugën 4.

351
00:14:41,310 --> 00:14:46,480
Nëse Princeton ishte në këtë Trie, se 4
do të kishte qenë pastruar për ne tashmë.

352
00:14:46,480 --> 00:14:49,130
Dhe kështu në këtë pikë
ne kemi arritur në një qorrsokak.

353
00:14:49,130 --> 00:14:50,250
Ne nuk mund të shkojmë më tutje.

354
00:14:50,250 --> 00:14:53,440
Dhe kështu që ne mund të themi, përfundimisht, nr.

355
00:14:53,440 --> 00:14:56,760
Princeton nuk ekziston në këtë Trie.

356
00:14:56,760 --> 00:14:58,860
>> Pra, çfarë do thotë e gjithë kjo?

357
00:14:58,860 --> 00:14:59,360
E drejtë.

358
00:14:59,360 --> 00:15:01,000
Ka shumë ndodh këtu.

359
00:15:01,000 --> 00:15:02,500
Ka pointers të gjithë vendin.

360
00:15:02,500 --> 00:15:04,249
Dhe, si ju mund të shihni
vetëm nga diagrami,

361
00:15:04,249 --> 00:15:07,010
ka shumë të nyjeve që
janë lloj i fluturon rreth.

362
00:15:07,010 --> 00:15:13,480
Por vini re çdo herë që ne të kërkuar për të
kontrolloni nëse diçka ishte në Trie,

363
00:15:13,480 --> 00:15:15,000
ne vetëm kishte për të bërë 4 lëvizje.

364
00:15:15,000 --> 00:15:17,208
>> Çdo herë që ne të kërkuar për
futur diçka në Trie,

365
00:15:17,208 --> 00:15:20,440
ne duhet të bëjmë 4 lëvizje, ndoshta
mallocing disa gjëra gjatë rrugës.

366
00:15:20,440 --> 00:15:23,482
Por, siç e pamë kur kemi futur
Dartmouth në Trie,

367
00:15:23,482 --> 00:15:25,940
nganjëherë disa të rrugës
tashmë mund të pastruar për ne.

368
00:15:25,940 --> 00:15:30,520
Dhe kështu si Trie ynë merr më të mëdha dhe
më e madhe, ne kemi bërë pak punë çdo kohë

369
00:15:30,520 --> 00:15:32,270
për të futur gjëra të reja
sepse ne kemi tashmë

370
00:15:32,270 --> 00:15:35,746
ndërtuar një shumë të ndërmjetme
Degët gjatë rrugës.

371
00:15:35,746 --> 00:15:38,370
Në qoftë se ne vetëm ndonjëherë duhet të shikoni në
4 gjëra, 4 është vetëm një konstante.

372
00:15:38,370 --> 00:15:41,750
Ne me të vërtetë jemi lloj i afrohet
futje kohë konstante

373
00:15:41,750 --> 00:15:44,501
dhe koha lookup konstante.

374
00:15:44,501 --> 00:15:47,500
Kompromisit, natyrisht, duke qenë se
kjo Trie, si ju ndoshta mund të them,

375
00:15:47,500 --> 00:15:49,030
është i madh.

376
00:15:49,030 --> 00:15:51,040
Secili prej këtyre nyjeve
merr një shumë hapësirë.

377
00:15:51,040 --> 00:15:52,090
>> Por kjo është kompromis.

378
00:15:52,090 --> 00:15:55,260
Në qoftë se ne duam me të vërtetë të shpejtë
futje, fshirje të vërtetë të shpejtë,

379
00:15:55,260 --> 00:15:59,630
dhe lookup të vërtetë të shpejtë, ne duhet të
kanë shumë të dhëna fluturon rreth.

380
00:15:59,630 --> 00:16:03,590
Ne duhet të vënë mënjanë një shumë hapësirë
dhe kujtesës për këtë strukturë e të dhënave

381
00:16:03,590 --> 00:16:04,290
të ekzistojnë.

382
00:16:04,290 --> 00:16:05,415
>> Dhe kështu kjo është kompromis.

383
00:16:05,415 --> 00:16:07,310
Por kjo duket si ne
mund të keni gjetur atë.

384
00:16:07,310 --> 00:16:09,560
Ne mund të kemi gjetur se
shenjtë Gral e strukturat e të dhënave

385
00:16:09,560 --> 00:16:12,264
me futje të shpejtë,
fshirje, dhe lookup.

386
00:16:12,264 --> 00:16:14,430
Dhe ndoshta kjo do të jetë një
strukturë e përshtatshme e të dhënave

387
00:16:14,430 --> 00:16:18,890
për t'u përdorur për çfarëdo informata
ne jemi duke u përpjekur për të ruajtur.

388
00:16:18,890 --> 00:16:21,860
Unë jam Doug Lloyd, kjo është CS50.

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