1
00:00:00,000 --> 00:00:02,994
>> [Muzikos grojimo]

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

3
00:00:05,426 --> 00:00:08,550
Doug LLOYD: Taigi mes jau pamažu virsta arčiau
ir arčiau, kad Gralis duomenų

4
00:00:08,550 --> 00:00:13,050
struktūros, vienas, kad mes galime įterpti
į, ištrinti iš, ir ieškoti

5
00:00:13,050 --> 00:00:15,440
nuolat laiko.

6
00:00:15,440 --> 00:00:16,270
Teisė.

7
00:00:16,270 --> 00:00:17,280
Štai tarsi į vartus.

8
00:00:17,280 --> 00:00:19,720
Mes norime, kad būtų galima daryti
viskas labai, labai greitai.

9
00:00:19,720 --> 00:00:22,580
>> Ar mes ją radau čia, kai
mes kalbame apie bando?

10
00:00:22,580 --> 00:00:23,670
Na, leiskite pažvelgti.

11
00:00:23,670 --> 00:00:25,628
Taigi mes matėme keletą
įvairios duomenų struktūros

12
00:00:25,628 --> 00:00:28,680
kad rankena žemėlapių
taip vadinamas raktas-reikšmės poros,

13
00:00:28,680 --> 00:00:32,080
kartografavimo kai duomenų gabalas
su kitokiu gabalas duomenų

14
00:00:32,080 --> 00:00:36,020
todėl mes žinome, kur rasti
informacija į struktūrą.

15
00:00:36,020 --> 00:00:40,060
>> Taigi, masyvą, pavyzdžiui,
Svarbiausia yra elementas indeksas arba masyvo

16
00:00:40,060 --> 00:00:42,600
vietą 0 arba 1 masyvas ir taip toliau.

17
00:00:42,600 --> 00:00:46,140
Ir yra, vertės nėra duomenų
kad egzistuoja toje vietoje.

18
00:00:46,140 --> 00:00:48,550
Taigi, kas yra saugomi masyve 0?

19
00:00:48,550 --> 00:00:54,290
Kas yra saugomi masyve 1 prieš tiesiog
0, o 1, kuris būtų raktai.

20
00:00:54,290 --> 00:00:56,360
>> Su maišos lentelė tai
Rūšiuoti tos pačios idėjos.

21
00:00:56,360 --> 00:01:00,690
Su maišos lentelė, mes turime šį maišos
funkcija, kuri generuoja maišos kodai.

22
00:01:00,690 --> 00:01:03,670
Taigi raktas yra maišos kodą iš duomenų.

23
00:01:03,670 --> 00:01:06,530
Ir vertę, ypač
mes kalbėjome apie Grupavimo

24
00:01:06,530 --> 00:01:10,590
Kai dėl maišos lentelėmis vaizdo,
yra tai, kad susijęs sąrašą duomenų

25
00:01:10,590 --> 00:01:12,550
kad maišos tos hashCode.

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

27
00:01:14,050 --> 00:01:16,050
Ką apie kitą metodą
šis metodas, nors?

28
00:01:16,050 --> 00:01:21,000
Ką apie metodu, kai
raktas garantuoja, kad bus unikalus,

29
00:01:21,000 --> 00:01:25,410
skirtingai nuo maišos lentelė, kur mes galėtume
galų gale su dviem gabaliukais duomenis

30
00:01:25,410 --> 00:01:27,200
turintys tą patį hashCode.

31
00:01:27,200 --> 00:01:30,020
Ir tada mes turime elgtis su
, kad vienos ar daugiau zondavimo

32
00:01:30,020 --> 00:01:33,340
pageidautina Grupavimo nustatyti šią problemą.

33
00:01:33,340 --> 00:01:37,520
>> Taigi, dabar mes galime garantuoti
kad mūsų raktas bus unikalus.

34
00:01:37,520 --> 00:01:39,690
Ir ką daryti, jei mūsų vertė buvo
tiesiog kažkas taip paprasta,

35
00:01:39,690 --> 00:01:44,080
kaip teisinga ir neteisinga, kad pasakoja, ar
ar ne todėl, kad gabalas informacijos

36
00:01:44,080 --> 00:01:45,610
egzistuoja struktūros?

37
00:01:45,610 --> 00:01:48,180
Loginius operatorius gali būti taip paprasta, kaip šiek tiek.

38
00:01:48,180 --> 00:01:52,660
Realiai tai tikriausiai
BYTE labiau nei truputį.

39
00:01:52,660 --> 00:01:55,410
Bet tai daug mažesnis nei
saugoti gal 50-simbolių,

40
00:01:55,410 --> 00:01:57,360
pavyzdžiui.

41
00:01:57,360 --> 00:02:02,210
>> Taigi bando, panašūs į maišos lenteles,
kuri sujungia matricas ir susiję sąrašas

42
00:02:02,210 --> 00:02:05,790
bando sujungti matricos,
struktūros, o patarimų

43
00:02:05,790 --> 00:02:08,509
kartu saugoti duomenis
įdomus būdas tai

44
00:02:08,509 --> 00:02:11,550
gana skiriasi nuo
ką mes matėme iki šiol.

45
00:02:11,550 --> 00:02:16,750
Dabar mes naudojame informaciją, kaip plano
naršyti šiuos duomenis struktūrą.

46
00:02:16,750 --> 00:02:18,710
Ir jei mes galime stebėti
veiksmų planas, jei mes galime

47
00:02:18,710 --> 00:02:22,390
sekti duomenis iš
pradžios iki pabaigos, mes

48
00:02:22,390 --> 00:02:24,945
žinoti, ar tais duomenimis
egzistuoja TRIE.

49
00:02:24,945 --> 00:02:28,310
>> Ir jei mes negalime sekti žemėlapį
nuo ty baigti ne visi,

50
00:02:28,310 --> 00:02:30,600
duomenys gali neegzistuoja.

51
00:02:30,600 --> 00:02:32,890
Vėlgi, raktai čia yra
garantuoja, kad bus unikalus.

52
00:02:32,890 --> 00:02:36,020
Ir taip skirtingai maišos lentelės, mes niekada
tenka susidurti su susidūrimų čia.

53
00:02:36,020 --> 00:02:39,090
Ir ne du gabalai duomenis
turi lygiai tą patį planą

54
00:02:39,090 --> 00:02:40,530
išskyrus atvejus, kai duomenys yra identiški.

55
00:02:40,530 --> 00:02:44,580
>> Jei mes įterpti Joną, tada
mes ieškome Jono.

56
00:02:44,580 --> 00:02:47,430
Štai du identiški gabalus
duomenys, tiesa, mes ieškome per.

57
00:02:47,430 --> 00:02:49,880
Bet kitaip, bet koks
dviejų dalių duomenys

58
00:02:49,880 --> 00:02:52,750
garantuoja, kad turi unikalią planus
per šios duomenų struktūros.

59
00:02:52,750 --> 00:02:56,210
Ir mes ketiname pažvelgti
vizualiai tai vos akimirką.

60
00:02:56,210 --> 00:02:58,810
>> Mes tai padaryti bando
sukurti naują duomenų struktūrą,

61
00:02:58,810 --> 00:03:00,564
kartografavimo šiuos pagrindinius vertės poras.

62
00:03:00,564 --> 00:03:03,480
Tokiu atveju, mes neketiname naudoti
kažkas taip paprasta, kaip Būlio.

63
00:03:03,480 --> 00:03:06,200
Mes iš tikrųjų bus saugomi eilutę.

64
00:03:06,200 --> 00:03:08,690
Ir tai styginių ketina
būti universiteto pavadinimą.

65
00:03:08,690 --> 00:03:12,140
>> Ir svarbiausia bus metai
kai buvo įkurta, kad universitetų.

66
00:03:12,140 --> 00:03:15,380
Visi universitetams metų
ketina sudaryti keturi skaitmenys.

67
00:03:15,380 --> 00:03:19,840
Ir todėl mes naudosime tuos keturis skaitmenis į
naršyti šios duomenų struktūros.

68
00:03:19,840 --> 00:03:22,270
Ir mes pamatysime, vėlgi, kaip
mes darome, kad vos per sekundę.

69
00:03:22,270 --> 00:03:25,110
>> Tuo kelio pabaigoje,
matysime pavadinimą

70
00:03:25,110 --> 00:03:30,250
Universiteto, kuris atitinka
į šį raktą, šie keturi skaitmenys.

71
00:03:30,250 --> 00:03:34,390
Pagrindinė idėja yra TRIE
yra mes turime pagrindinį maršrutą.

72
00:03:34,390 --> 00:03:35,640
Taigi apie tai galvoti kaip medis.

73
00:03:35,640 --> 00:03:39,211
Ir tai yra panašios rašymo
ir koncepcijos iki medį.

74
00:03:39,211 --> 00:03:41,460
Paprastai, kai mes galvojame apie
medžiai ir realiame pasaulyje,

75
00:03:41,460 --> 00:03:44,090
jie turi šaknį, kad yra į
žemės ir jie auga aukštyn

76
00:03:44,090 --> 00:03:46,830
ir jie turi filialus
ir jie turi lapus.

77
00:03:46,830 --> 00:03:49,450
Ir iš esmės yra idėja
Trie yra lygiai tas pats,

78
00:03:49,450 --> 00:03:51,755
išskyrus tai, kad šaknys yra įtvirtinta
kažkur danguje.

79
00:03:51,755 --> 00:03:53,130
Ir lapai yra apačioje.

80
00:03:53,130 --> 00:03:55,750
>> Taigi, tai lyg atsižvelgiant į medį
ir tiesiog prakeiktas jis aukštyn kojom.

81
00:03:55,750 --> 00:03:56,880
Tačiau vis dar yra filialai.

82
00:03:56,880 --> 00:03:59,463
Ir tie būtų mūsų keliai,
tie bus mūsų jungtys

83
00:03:59,463 --> 00:04:02,220
nuo iki lapų šaknis.

84
00:04:02,220 --> 00:04:04,200
Šiuo atveju, tie,
takai, šie filialai

85
00:04:04,200 --> 00:04:08,490
yra paženklintos skaitmenų kad pasakys mus
kuriuo keliu eiti iš kur mes esame.

86
00:04:08,490 --> 00:04:11,800
>> Jei mes matome 0, mes eiti šio filialo,
jei matome 1, mes eiti šio filialo,

87
00:04:11,800 --> 00:04:12,900
ir taip ir taip toliau.

88
00:04:12,900 --> 00:04:14,060
Na, ką tai reiškia?

89
00:04:14,060 --> 00:04:16,519
Na, tai reiškia, kad
kiekviename sankryžos taško

90
00:04:16,519 --> 00:04:19,260
ir kiekvienas mazgas
viduryje ir kiekvieną filialas,

91
00:04:19,260 --> 00:04:23,020
Yra 10 galima
vietos, kad mes galime eiti.

92
00:04:23,020 --> 00:04:27,690
Taigi yra 10 patarimų
iš kiekvienos vietos.

93
00:04:27,690 --> 00:04:30,610
>> Ir tai, kai bando galite gauti
šiek tiek bauginanti kažkam

94
00:04:30,610 --> 00:04:34,460
kas neturi daug
patirtis kompiuterių mokslo anksčiau.

95
00:04:34,460 --> 00:04:35,960
Bet bando tikrai gana awesome.

96
00:04:35,960 --> 00:04:37,793
Ir jei jūs turite
galimybė dirbti su jais

97
00:04:37,793 --> 00:04:40,420
ir jūs esate pasirengę kasti-in
ir eksperimentuoti su jais,

98
00:04:40,420 --> 00:04:44,234
jie tikrai gana įdomi
duomenų struktūros dirbti.

99
00:04:44,234 --> 00:04:46,900
Jei norime įterpti elementą
į TRIE, visi mes turime daryti

100
00:04:46,900 --> 00:04:51,360
yra sukurti teisingą kelią
iš į lapų šaknų.

101
00:04:51,360 --> 00:04:55,390
Štai ką kiekvienas žingsnis kartu
būdas gali atrodyti.

102
00:04:55,390 --> 00:04:59,660
Mes ketiname nustatyti naują duomenų
struktūra naują mazgo vadinamas TRIE.

103
00:04:59,660 --> 00:05:02,560
>> Ir viduje, kad duomenys
struktūra yra du gabalai.

104
00:05:02,560 --> 00:05:05,460
Mes ketiname saugoti
Pavadinimas universitete.

105
00:05:05,460 --> 00:05:09,410
Ir mes ketiname saugoti
AN nurodymus masyvo

106
00:05:09,410 --> 00:05:12,190
kitų mazgų to paties tipo.

107
00:05:12,190 --> 00:05:14,780
Taigi, vėl, tai yra tai, kad rūšiuoti
nuo koncepcijos visur

108
00:05:14,780 --> 00:05:18,567
mes esame, mes ne 10 galima
vietos, mes galime eiti.

109
00:05:18,567 --> 00:05:20,150
Jei mes matome 0, mes eiti šiuo filialą.

110
00:05:20,150 --> 00:05:22,690
Jei mes matome 1, tai filialas,
ir taip toliau, ir taip toliau, ir taip toliau.

111
00:05:22,690 --> 00:05:25,160
Jei mes sakome, 9, mes eiti šiuo filialą.

112
00:05:25,160 --> 00:05:28,220
Taigi kiekviename sandūros taške,
mes galime eiti 10 galimų vietų.

113
00:05:28,220 --> 00:05:35,740
Taigi kiekvienas mazgas turi būti 10 patarimų
kitų mazgų, daugiau kaip 10 kitų mazgų.

114
00:05:35,740 --> 00:05:39,810
>> Ir duomenys mes saugoti yra
Tiesiog universiteto pavadinimą.

115
00:05:39,810 --> 00:05:41,060
Taigi leiskite statyti TRIE.

116
00:05:41,060 --> 00:05:44,860
Leiskite įdėti pora
daiktų į mūsų TRIE.

117
00:05:44,860 --> 00:05:46,740
Taigi pačiame viršuje,
tai yra mūsų šaknys mazgas.

118
00:05:46,740 --> 00:05:49,740
Tai turbūt bus kažkas
jūs ketinate globaliai skelbiame.

119
00:05:49,740 --> 00:05:53,450
Ir jūs ketinate globaliai išlaikyti
rodyklė į šį mazgą visada.

120
00:05:53,450 --> 00:05:55,360
>> Jūs ketinate pasakyti,
šaknis lygi, ir jūs

121
00:05:55,360 --> 00:05:57,580
ketina malloc sau TRIE mazgas.

122
00:05:57,580 --> 00:05:59,850
Ir jūs niekada
vėl paliesti šaknis.

123
00:05:59,850 --> 00:06:02,300
Kiekvieną kartą, kai norite
pradėti naršyti,

124
00:06:02,300 --> 00:06:05,802
galite nustatyti kitą rodyklę
lygus šaknis, pavyzdžiui, Trav,

125
00:06:05,802 --> 00:06:07,760
kuris yra pavyzdys,
naudoti daugelis mano video

126
00:06:07,760 --> 00:06:11,090
čia kaminai ir eilėse
ir nuoroda sąrašai ir pan.

127
00:06:11,090 --> 00:06:13,320
>> Jūs nustatote vieną žymiklį
vadinamas Trav už Sankryþos.

128
00:06:13,320 --> 00:06:15,890
Ir jūs naudojate Trav naršyti
per duomenų struktūra.

129
00:06:15,890 --> 00:06:17,500
Taigi pažiūrėkime, kaip tai gali atrodyti.

130
00:06:17,500 --> 00:06:19,880
Taigi dabar, ką
Ar mazgas atrodo?

131
00:06:19,880 --> 00:06:22,920
Na, kaip mūsų duomenų
struktūra deklaracija nurodė,

132
00:06:22,920 --> 00:06:26,906
turime eilutę, kuri
šiuo atveju yra tuščias.

133
00:06:26,906 --> 00:06:27,780
Nėra nieko čia.

134
00:06:27,780 --> 00:06:29,550
>> Ir po 10 patarimų masyvo.

135
00:06:29,550 --> 00:06:31,790
Ir dabar, mes tik
Turiu 1 mazgas šiame TRIE.

136
00:06:31,790 --> 00:06:33,110
Nėra nieko dar jame.

137
00:06:33,110 --> 00:06:36,020
Taigi visi tie 10
rodyklės taškas į NULL.

138
00:06:36,020 --> 00:06:38,090
Štai ką raudona rodo.

139
00:06:38,090 --> 00:06:39,500
>> Leiskite įterpti eilutę Harvardo.

140
00:06:39,500 --> 00:06:41,999
Leiskite įrašyti universitetas
Harvardo į šį TRIE, kuris

141
00:06:41,999 --> 00:06:43,940
buvo įkurta metų 1636.

142
00:06:43,940 --> 00:06:48,220
Mes norime naudoti raktą,
1636, pasakyti mums, kur mes

143
00:06:48,220 --> 00:06:50,140
ketina laikyti Harvardo į TRIE.

144
00:06:50,140 --> 00:06:51,470
Dabar, kaip gali mes tai darome?

145
00:06:51,470 --> 00:06:52,886
>> Tai gali atrodyti kažką panašaus į tai.

146
00:06:52,886 --> 00:06:54,160
Mes pradedame šaknis.

147
00:06:54,160 --> 00:06:56,920
Ir mes turime šiuos 10 vietų, mes galime eiti.

148
00:06:56,920 --> 00:06:59,900
Šaknis yra kaip bet kuris
kitas mazgas TRIE.

149
00:06:59,900 --> 00:07:02,850
Yra 10 vietų, mes galime eiti iš čia.

150
00:07:02,850 --> 00:07:07,215
>> Kur mes tikriausiai nori
eiti, jei raktas yra 1636?

151
00:07:07,215 --> 00:07:08,340
Yra tikrai du variantai.

152
00:07:08,340 --> 00:07:08,450
Teisė.

153
00:07:08,450 --> 00:07:10,825
Galime pastatyti nuo raktą
iš dešinės į kairę ir pradėti su 6.

154
00:07:10,825 --> 00:07:14,000
Arba mes galime sukurti iš raktą
į kairę į dešinę ir pradėti 1 d.

155
00:07:14,000 --> 00:07:16,140
>> Tai tikriausiai daugiau
intuityvi kaip žmogus

156
00:07:16,140 --> 00:07:18,110
Mes suprantame, kad bus
Tiesiog eikite į kairę į dešinę.

157
00:07:18,110 --> 00:07:21,140
Ir taip, jei noriu įterpti
Harvardo į šį TRIE,

158
00:07:21,140 --> 00:07:23,560
Aš tikriausiai norite pradėti
pradedant šaknis,

159
00:07:23,560 --> 00:07:25,720
žiūri mano 10 variantų
priešais mane, ir sako:

160
00:07:25,720 --> 00:07:28,700
Noriu eiti į 1 keliu.

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

162
00:07:29,700 --> 00:07:31,810
>> Dabar, 1 kelias šiuo metu yra tuščias.

163
00:07:31,810 --> 00:07:35,920
Taigi, jei aš noriu tęsti šiuo keliu
įterpti šį elementą į TRIE,

164
00:07:35,920 --> 00:07:42,040
Turiu malloc naują mazgas, turime 1
ten rodo, o tada aš gerai eiti.

165
00:07:42,040 --> 00:07:46,460
>> Taigi aš iš esmės esu ne
vieta, kur aš stoviu

166
00:07:46,460 --> 00:07:50,270
tuo medžio arba iš šaknies
Trie ir yra 10 skyriai.

167
00:07:50,270 --> 00:07:52,260
Bet kiekvienas filialas turi
vartai priešais jį.

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

169
00:07:53,060 --> 00:07:54,850
Nes ten nieko nėra.

170
00:07:54,850 --> 00:07:56,522
Nėra saugų.

171
00:07:56,522 --> 00:07:58,980
Tai reiškia, kad ten nieko
žemyn nors iš šių šakų.

172
00:07:58,980 --> 00:08:02,532
Jei aš noriu pradėti statyti
kažkas, aš noriu pašalinti vartai.

173
00:08:02,532 --> 00:08:04,490
Noriu pašalinti vartai
priešais skaičius 1.

174
00:08:04,490 --> 00:08:05,698
Ir aš noriu vaikščioti žemyn, kad.

175
00:08:05,698 --> 00:08:08,060
Ir aš noriu statyti
kita man kur eiti.

176
00:08:08,060 --> 00:08:09,470
>> Ir tai, ką aš padariau čia.

177
00:08:09,470 --> 00:08:11,430
Taigi 1 nebėra nurodo null.

178
00:08:11,430 --> 00:08:13,830
Sakiau tai saugu eiti čia dabar.

179
00:08:13,830 --> 00:08:15,789
Aš pastatyti dar vieną mazgą.

180
00:08:15,789 --> 00:08:18,330
Ir kai aš gauti tą mazgą, aš
turi kitą sprendimą padaryti.

181
00:08:18,330 --> 00:08:20,890
Kur aš ketinu eiti nuo čia?

182
00:08:20,890 --> 00:08:22,700
>> Na, aš jau sumažėjo 1.

183
00:08:22,700 --> 00:08:24,470
Taigi, dabar aš tikriausiai norite eiti į 6 d.

184
00:08:24,470 --> 00:08:24,970
Teisė.

185
00:08:24,970 --> 00:08:27,100
Vėlgi, aš turiu 10 vietas galiu rinktis.

186
00:08:27,100 --> 00:08:30,060
Taigi leiskite dabar eiti numeriu 6.

187
00:08:30,060 --> 00:08:32,280
Taigi aš išvalyti vartai
priešais numeriu 6.

188
00:08:32,280 --> 00:08:33,250
Ir aš vaikščioti ten.

189
00:08:33,250 --> 00:08:34,580
Ir aš statyti dar mazgas.

190
00:08:34,580 --> 00:08:37,630
Ir aš pasiekė kitą sankryžos tašką.

191
00:08:37,630 --> 00:08:40,289
>> Vėlgi, aš turiu 10 pasirinkimus
o kur aš galiu eiti.

192
00:08:40,289 --> 00:08:42,799
Aš persikėlė nuo 1 iki 6.

193
00:08:42,799 --> 00:08:44,215
Taigi, dabar aš tikriausiai norite eiti į 3 dalis.

194
00:08:44,215 --> 00:08:45,381
3, ten kur aš galiu eiti.

195
00:08:45,381 --> 00:08:48,980
Taigi turiu išvalyti kelią
ir kurti sau naują erdvę.

196
00:08:48,980 --> 00:08:50,870
Ir tada iš 3, kur aš noriu eiti?

197
00:08:50,870 --> 00:08:52,450
Noriu eiti 6.

198
00:08:52,450 --> 00:08:54,770
>> Ir vėl, aš turėjau
išvalyti kelią tai padaryti.

199
00:08:54,770 --> 00:08:59,179
Taigi, dabar aš naudojamas mano klavišą įterpti sukurti
mazgai ir pradėti statyti TRIE.

200
00:08:59,179 --> 00:09:00,220
Aš pradėjau šaknis.

201
00:09:00,220 --> 00:09:03,666
Aš sumažėjo 1636.

202
00:09:03,666 --> 00:09:05,540
Ir dabar aš apačioje
ten tą mazgą.

203
00:09:05,540 --> 00:09:06,610
Ir jums gali būti suteikta galimybė
matyti ekrane.

204
00:09:06,610 --> 00:09:07,735
>> Jis pabrėžė, geltonos spalvos.

205
00:09:07,735 --> 00:09:10,020
Štai kur aš šiuo metu esu.

206
00:09:10,020 --> 00:09:11,300
Mano pagrindinė daroma.

207
00:09:11,300 --> 00:09:13,030
Aš išnaudojo kiekvieną poziciją mano raktu.

208
00:09:13,030 --> 00:09:15,040
Taigi aš negaliu eiti toliau.

209
00:09:15,040 --> 00:09:17,720
Taigi šiuo metu, viskas, ką aš
tikrai reikia padaryti, tai pasakyti, Gerai.

210
00:09:17,720 --> 00:09:18,990
Tai lyg ieškote
žemyn į žemę,

211
00:09:18,990 --> 00:09:21,115
jei jūs vizijos
Būk kaip šio kelio rūšiuoti

212
00:09:21,115 --> 00:09:22,350
su skirtingų jungčių.

213
00:09:22,350 --> 00:09:25,800
Rūšiuoti žiūri ir tarsi
Dažymas purkštuvu, Harvardo ant žemės.

214
00:09:25,800 --> 00:09:26,800
Štai šiuo vardu.

215
00:09:26,800 --> 00:09:28,300
Žinokite, kad tai, kas šioje vietoje.

216
00:09:28,300 --> 00:09:31,870
Jei pradėsime šaknis ir mes eiti
1 ir tada 6 ir tada 3 ir tada 6,

217
00:09:31,870 --> 00:09:32,780
Kur mes esame?

218
00:09:32,780 --> 00:09:35,640
Na, jei mes žiūrime žemyn
ir matome Harvardo, tada

219
00:09:35,640 --> 00:09:38,960
mes žinome, kad Harvardo buvo
įkurta 1636 remiasi būdu

220
00:09:38,960 --> 00:09:41,400
mes įgyvendinti šiuos duomenis struktūrą.

221
00:09:41,400 --> 00:09:43,177
Taigi, tai buvo tikiuosi paprasta.

222
00:09:43,177 --> 00:09:44,760
Mes ketiname padaryti du intarpais.

223
00:09:44,760 --> 00:09:50,060
Ir tikiuosi, kad bus padėti
pamatyti tai padaryti du kartus daugiau.

224
00:09:50,060 --> 00:09:52,210
>> Dabar galime įterpti kitą universitetą.

225
00:09:52,210 --> 00:09:54,630
Leiskite įdėti į šį Yale TRIE.

226
00:09:54,630 --> 00:09:57,037
Yale "buvo įkurta 1701 m.

227
00:09:57,037 --> 00:09:58,870
Taigi mes pradėsime ne
šaknis, kaip mes visada darome.

228
00:09:58,870 --> 00:09:59,890
Ir mes nustatyti Sankryþos žymeklį.

229
00:09:59,890 --> 00:10:01,624
Mes ketiname naudoti, kad pereiti per.

230
00:10:01,624 --> 00:10:03,790
Pirmas dalykas, mes norime
padaryti, tai eiti į 1 keliu.

231
00:10:03,790 --> 00:10:05,830
Štai pirmas skaitmuo mūsų raktu.

232
00:10:05,830 --> 00:10:08,420
Laimei, nors mes ne
daryti bet kokį darbą šį kartą.

233
00:10:08,420 --> 00:10:09,919
1 m kelias jau buvo išvalytas.

234
00:10:09,919 --> 00:10:13,520
Aš vartų anksčiau, kai aš
buvo įterpiant Harvardo 1636.

235
00:10:13,520 --> 00:10:18,090
Taigi aš galiu saugiai judėti
žemyn 1 ir tiesiog eiti ten.

236
00:10:18,090 --> 00:10:20,150
Jei gali judėti žemyn 1 d.

237
00:10:20,150 --> 00:10:22,930
>> Dabar, nors, aš noriu eiti į 7.

238
00:10:22,930 --> 00:10:24,280
Aš atvėręs kelią po 6.

239
00:10:24,280 --> 00:10:27,050
Žinau, kad galiu saugiai
pereiti žemyn 6 kelią.

240
00:10:27,050 --> 00:10:29,220
Bet man reikia pradėti nuo 7 keliu.

241
00:10:29,220 --> 00:10:30,580
Taigi, ką man reikia daryti?

242
00:10:30,580 --> 00:10:35,070
Na, kaip ir anksčiau, aš tiesiog reikia
išvalyti vartai, gauti iš kelio,

243
00:10:35,070 --> 00:10:38,740
ir kurti naują mazgą iš 7 keliu.

244
00:10:38,740 --> 00:10:40,250
Tiesiog, kaip šis.

245
00:10:40,250 --> 00:10:42,930
>> Taigi dabar aš persikėlė 1 ir tada 7.

246
00:10:42,930 --> 00:10:45,550
Ir dabar pastebėsite, aš rūšiuoti
dėl šios naujos subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Visa kita nuo 16
, aš nerūpi.

249
00:10:49,260 --> 00:10:50,720
Aš nesu daro 16 nieko.

250
00:10:50,720 --> 00:10:51,750
Darau 17 stuff.

251
00:10:51,750 --> 00:10:58,380
>> Taigi dabar nuo 17, aš turiu
rūšiuoti naujų būdų čia.

252
00:10:58,380 --> 00:11:00,462
Kitas skaitmenų mano raktas yra 0.

253
00:11:00,462 --> 00:11:01,670
Aš aiškiai negali gauti bet kur.

254
00:11:01,670 --> 00:11:02,628
Aš tiesiog pastatė šį mazgą.

255
00:11:02,628 --> 00:11:04,550
Taigi aš žinau, nėra
keliai į priekį nuo čia.

256
00:11:04,550 --> 00:11:06,370
Taigi turiu padaryti vieną save.

257
00:11:06,370 --> 00:11:09,360
>> Taigi aš malloc naują mazgas
ir turi 0 balų ten.

258
00:11:09,360 --> 00:11:12,770
Ir tada dar kartą, aš malloc
Naujas mazgas ir turi vieną tašką ten.

259
00:11:12,770 --> 00:11:15,870
Vėlgi, aš išnaudojo savo raktą, 1701.

260
00:11:15,870 --> 00:11:18,472
Taigi man atrodo, ir aš dažų purkštuvu Yale.

261
00:11:18,472 --> 00:11:19,680
Štai šio mazgo vardas.

262
00:11:19,680 --> 00:11:24,660
>> Ir todėl dabar, jei aš kada nors reikės pamatyti, jei Yale
yra šiame TRIE, aš pradedu tuo šaknis,

263
00:11:24,660 --> 00:11:27,060
Aš eiti 1701 ir žiūrėti žemyn.

264
00:11:27,060 --> 00:11:30,030
Ir jei matau Yale purkštuvą
dažyti ant žemės, tada

265
00:11:30,030 --> 00:11:32,200
Žinau Jeilio egzistuoja šiame TRIE.

266
00:11:32,200 --> 00:11:32,950
Padarykim dar vieną.

267
00:11:32,950 --> 00:11:36,430
Leiskite įdėkite Dartmouth į tai
Trie, kuri buvo įkurta 1769 m.

268
00:11:36,430 --> 00:11:37,750
>> Prasideda šaknies iš naujo.

269
00:11:37,750 --> 00:11:39,445
Mano pirmasis skaitmuo mano raktas yra 1.

270
00:11:39,445 --> 00:11:40,820
Galiu drąsiai judėti šiuo keliu.

271
00:11:40,820 --> 00:11:42,400
Tai jau egzistuoja.

272
00:11:42,400 --> 00:11:44,040
Kitas skaitmuo mano raktas yra 7.

273
00:11:44,040 --> 00:11:45,890
Galiu drąsiai judėti šiuo keliu.

274
00:11:45,890 --> 00:11:47,540
Ji egzistuoja, taip pat.

275
00:11:47,540 --> 00:11:49,000
>> Mano šalia yra 6.

276
00:11:49,000 --> 00:11:52,860
Iš čia, iš kur aš esu šiuo metu
geltonai ten toje vidurinėje mazgas,

277
00:11:52,860 --> 00:11:56,060
6 šiuo metu yra užrakinta išjungtas.

278
00:11:56,060 --> 00:11:58,830
Jei aš noriu eiti šiuo keliu,
Turiu ją kurti save.

279
00:11:58,830 --> 00:12:02,250
Taigi aš malloc naują mazgas
ir turi 6 punktas ten.

280
00:12:02,250 --> 00:12:04,250
Ir tada vėl, aš
Blazing naujų takai čia.

281
00:12:04,250 --> 00:12:10,750
>> Taigi aš malloc naują mazgą taip, kad iš
kad node-- kelio numeris 9-- ir tada dabar

282
00:12:10,750 --> 00:12:13,584
jei aš keliauti 1769 ir žiūriu žemyn.

283
00:12:13,584 --> 00:12:15,500
Nėra nieko šiuo metu
purkšti ten dažytos.

284
00:12:15,500 --> 00:12:16,930
Gebu rašyti Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Ir aš įterpti
Dartmouth į TRIE.

286
00:12:20,710 --> 00:12:23,450
>> Taigi, kad įterpiant
viskas į TRIE.

287
00:12:23,450 --> 00:12:25,384
Dabar mes norime ieškoti dalykų.

288
00:12:25,384 --> 00:12:27,050
Kaip mes ieškoti dalykų TRIE?

289
00:12:27,050 --> 00:12:29,170
Na, tai beveik tas pats idėja.

290
00:12:29,170 --> 00:12:33,620
Dabar mes tiesiog naudoti rakto skaitmenų
pamatyti, jei mes galime naršyti nuo šaknų

291
00:12:33,620 --> 00:12:37,170
kur mes norime eiti į TRIE.

292
00:12:37,170 --> 00:12:41,620
>> Jei mes paspauskite aklavietę bet kuriame taške, tada
mes žinome, kad šis elementas negali egzistuoja

293
00:12:41,620 --> 00:12:44,500
arba kita, kad planas būtų
jau buvo pašalinta.

294
00:12:44,500 --> 00:12:45,930
Jei mes padarysime tai visą kelią į
pabaiga, viskas, ką reikia padaryti,

295
00:12:45,930 --> 00:12:48,471
tai pažvelgti ir pamatyti, jei tai
elementas mes ieškome.

296
00:12:48,471 --> 00:12:49,335
Jei taip, tai sėkmės.

297
00:12:49,335 --> 00:12:52,610
Jei taip nėra, nepavyks.

298
00:12:52,610 --> 00:12:54,940
>> Taigi leiskite ieškoti
Harvardo šiame TRIE.

299
00:12:54,940 --> 00:12:56,020
Mes pradedame šaknis.

300
00:12:56,020 --> 00:12:58,228
Ir, vėlgi, mes ketiname
sukurti Sankryþos žymiklį

301
00:12:58,228 --> 00:12:59,390
padaryti mūsų juda už mus.

302
00:12:59,390 --> 00:13:02,080
Nuo šaknų mes žinome, kad
Pirmoji vieta turime eiti yra 1,

303
00:13:02,080 --> 00:13:03,390
mes galime padaryti, kad?

304
00:13:03,390 --> 00:13:03,982
Taip, mes galime.

305
00:13:03,982 --> 00:13:04,690
Jei saugiai egzistuoja.

306
00:13:04,690 --> 00:13:06,660
Mes galime eiti ten.

307
00:13:06,660 --> 00:13:08,440
>> Dabar, kitą vietą turime eiti yra 6.

308
00:13:08,440 --> 00:13:10,557
Ar 6 kelias egzistuoja iš čia?

309
00:13:10,557 --> 00:13:11,140
Taip, tai daro.

310
00:13:11,140 --> 00:13:12,690
Mes galime eiti į 6 kelią.

311
00:13:12,690 --> 00:13:13,905
Ir mes galų gale čia.

312
00:13:13,905 --> 00:13:16,130
>> Ar mes galime eiti į 3 kelio nuo čia?

313
00:13:16,130 --> 00:13:18,450
Na, kaip it turns out,
Taip, kad egzistuoja per daug.

314
00:13:18,450 --> 00:13:20,790
Ir mes galime gauti apie 6 kelio nuo čia?

315
00:13:20,790 --> 00:13:21,982
Taip, mes galime.

316
00:13:21,982 --> 00:13:24,002
>> Mes ne visai atsakė
klausimas dar.

317
00:13:24,002 --> 00:13:25,710
Yra dar viena daugiau
žingsnis, kuris yra dabar

318
00:13:25,710 --> 00:13:28,520
mes turime pažvelgti žemyn ir
pamatyti, jei tai actually--

319
00:13:28,520 --> 00:13:32,660
jei mes ieškome Harvardo, yra tai, kad
Ką mes randame, kai mes išnaudoti raktą?

320
00:13:32,660 --> 00:13:35,430
Pavyzdyje mes naudojame čia
metams visada keturi skaitmenys.

321
00:13:35,430 --> 00:13:40,280
Tačiau jums gali būti naudojant pavyzdžiui, kai
Jūs saugoti žodžių žodyną.

322
00:13:40,280 --> 00:13:44,060
>> Ir taip užuot 10 patarimų
mano vietą, galite turėti 26.

323
00:13:44,060 --> 00:13:46,040
Vienas kiekvienos abėcėlės raidės.

324
00:13:46,040 --> 00:13:50,350
Ir ten yra keletas, kaip šikšnosparnių žodžiai
kuris yra partijos poaibis, pavyzdžiui.

325
00:13:50,350 --> 00:13:53,511
Ir net jei jūs gaunate į
pabaiga raktą ir jums pažvelgti žemyn,

326
00:13:53,511 --> 00:13:55,260
galbūt nematote, ką
Jūs ieškote.

327
00:13:55,260 --> 00:13:58,500
>> Taigi jūs visada turite feed
visą kelią ir tada

328
00:13:58,500 --> 00:14:01,540
jei buvo sėkmingai galėtų
feed visą kelią,

329
00:14:01,540 --> 00:14:03,440
žiūrėti žemyn ir padaryti vieną galutinį patvirtinimą.

330
00:14:03,440 --> 00:14:05,120
Ar tai, ką aš ieškote?

331
00:14:05,120 --> 00:14:07,740
Na, aš pažvelgti žemyn pradėjus
viršuje ir vyksta 1636.

332
00:14:07,740 --> 00:14:08,240
Žiūriu žemyn.

333
00:14:08,240 --> 00:14:09,400
Matau Harvardo.

334
00:14:09,400 --> 00:14:11,689
Taigi, taip, man pavyko.

335
00:14:11,689 --> 00:14:13,980
Ką daryti, jei aš ko
yra ne TRIE, nors.

336
00:14:13,980 --> 00:14:17,200
Ką daryti, jei aš ieškau Princeton,
kuri buvo įkurta 1746 m.

337
00:14:17,200 --> 00:14:20,875
Ir taip 1746 tampa mano raktas
naršyti TRIE.

338
00:14:20,875 --> 00:14:22,040
Na, aš pradedu tuo šaknis.

339
00:14:22,040 --> 00:14:24,760
Ir pirmoji vieta Noriu
į krinta 1 keliu.

340
00:14:24,760 --> 00:14:25,590
Ar galiu tai padaryti?

341
00:14:25,590 --> 00:14:26,490
Taip, aš galiu.

342
00:14:26,490 --> 00:14:28,730
>> Ar galiu eiti į 7 kelio nuo ten?

343
00:14:28,730 --> 00:14:29,230
Taip, galiu.

344
00:14:29,230 --> 00:14:30,750
Tai egzistuoja per daug.

345
00:14:30,750 --> 00:14:32,460
Bet aš galiu eiti į 4 kelią iš čia?

346
00:14:32,460 --> 00:14:35,550
Štai tarsi klausia klausimą, gali
Aš toliau nustatyta, kad mažai aikštė

347
00:14:35,550 --> 00:14:37,114
kad aš paryškinamas geltonai?

348
00:14:37,114 --> 00:14:38,030
Nėra nieko ten.

349
00:14:38,030 --> 00:14:38,610
Teisė.

350
00:14:38,610 --> 00:14:41,310
>> Nėra žingsnis į priekį žemyn 4 keliu.

351
00:14:41,310 --> 00:14:46,480
Jei Prinstono buvo šiame TRIE, kad 4
būtų buvę prieki mums jau.

352
00:14:46,480 --> 00:14:49,130
Ir kad šiuo metu
mes pasiekė aklavietę.

353
00:14:49,130 --> 00:14:50,250
Mes negalime eiti toliau.

354
00:14:50,250 --> 00:14:53,440
Ir taip, mes galime pasakyti, galutinai, ne.

355
00:14:53,440 --> 00:14:56,760
Prinstono neegzistuoja šiame TRIE.

356
00:14:56,760 --> 00:14:58,860
>> Taigi, ką visa tai reiškia?

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

358
00:14:59,360 --> 00:15:01,000
Yra daug vyksta čia.

359
00:15:01,000 --> 00:15:02,500
Yra patarimų visur.

360
00:15:02,500 --> 00:15:04,249
Ir, kaip jūs galite pamatyti,
tik iš diagramos,

361
00:15:04,249 --> 00:15:07,010
ten mazgų daug, kad
yra rūšies plaukioja aplink.

362
00:15:07,010 --> 00:15:13,480
Tačiau pastebėti kiekvieną kartą norėjome
patikrinti, ar kažkas buvo į TRIE,

363
00:15:13,480 --> 00:15:15,000
mes tik turėjo padaryti 4 žingsnius.

364
00:15:15,000 --> 00:15:17,208
>> Kiekvieną kartą, kai mes norėjome
įterpti kažką TRIE,

365
00:15:17,208 --> 00:15:20,440
mes turime padaryti 4 žingsnius, galbūt
mallocing kai pakeliui stuff.

366
00:15:20,440 --> 00:15:23,482
Bet, kaip matėme, kai mes įdėta
Dartmouth į TRIE,

367
00:15:23,482 --> 00:15:25,940
kartais kai kurie iš kelio
gali būti jau prieki už mus.

368
00:15:25,940 --> 00:15:30,520
Ir taip mūsų Trie gauna didesni ir
didesni, mes turime padaryti mažiau darbo kiekvieną kartą

369
00:15:30,520 --> 00:15:32,270
įterpti naujus dalykus
nes mes jau ve

370
00:15:32,270 --> 00:15:35,746
pastatė tarpinis daug
filialai pakeliui.

371
00:15:35,746 --> 00:15:38,370
Jei mes tik kada nors pažvelgti į
4 dalykai, 4 yra tik konstanta.

372
00:15:38,370 --> 00:15:41,750
Mes tikrai yra natūra artėja
pastovus laikas įterpimo

373
00:15:41,750 --> 00:15:44,501
ir nuolatinis laiko peržvalgos.

374
00:15:44,501 --> 00:15:47,500
Kompromisas, žinoma, yra ta, kad
tai Trie, kaip jūs galite galbūt pasakys,

375
00:15:47,500 --> 00:15:49,030
yra didžiulis.

376
00:15:49,030 --> 00:15:51,040
Kiekvienas iš šių mazgų
užima daug vietos.

377
00:15:51,040 --> 00:15:52,090
>> Bet tai kompromisas.

378
00:15:52,090 --> 00:15:55,260
Jei norime tikrai greitai
įterpimo, tikrai greitai išbraukta,

379
00:15:55,260 --> 00:15:59,630
ir tikrai greitai peržvalgos, turime
turi daug duomenų plaukioja aplink.

380
00:15:59,630 --> 00:16:03,590
Mes turime atidėti daug vietos
ir atminties už tą duomenų struktūros

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

382
00:16:04,290 --> 00:16:05,415
>> Ir taip tai kompromisas.

383
00:16:05,415 --> 00:16:07,310
Tačiau atrodo, kad mes
galėjo ją radau.

384
00:16:07,310 --> 00:16:09,560
Mes nustatėme, kad gali
Gralis duomenų struktūrų

385
00:16:09,560 --> 00:16:12,264
su greito įkišimo
išbraukta ir peržvalgos.

386
00:16:12,264 --> 00:16:14,430
O gal tai bus
tinkamų duomenų struktūra

387
00:16:14,430 --> 00:16:18,890
naudoti dėl kokios nors informacijos
mes bandome parduotuvėje.

388
00:16:18,890 --> 00:16:21,860
Aš Doug Lloyd, tai CS50.

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