1
00:00:00,000 --> 00:00:02,994
>> [Mūzikas atskaņošanai]

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

3
00:00:05,426 --> 00:00:08,550
Doug LLOYD: Tātad mēs esam inching tuvāk
un tuvāk ka Svētais Grāls datu

4
00:00:08,550 --> 00:00:13,050
struktūras, viens, ka mēs varam ievietot
vērā, dzēst no, un meklēt

5
00:00:13,050 --> 00:00:15,440
pastāvīgā laikā.

6
00:00:15,440 --> 00:00:16,270
Tiesības.

7
00:00:16,270 --> 00:00:17,280
Tas ir sava veida vārtiem.

8
00:00:17,280 --> 00:00:19,720
Mēs vēlamies, lai varētu to izdarīt
lietas ļoti, ļoti ātri.

9
00:00:19,720 --> 00:00:22,580
>> Vai mēs atradām to šeit, kad
mēs runājam par mēģinājumiem?

10
00:00:22,580 --> 00:00:23,670
Nu, pieņemsim to apskatīt.

11
00:00:23,670 --> 00:00:25,628
Tāpēc mēs esam redzējuši vairākas
dažādas datu struktūras

12
00:00:25,628 --> 00:00:28,680
ka rokturis kartēšanu
tā saukto atslēgu vērtību pārus,

13
00:00:28,680 --> 00:00:32,080
kartēšanas kādu gabals datu
uz kādu citu gabals datu

14
00:00:32,080 --> 00:00:36,020
tāpēc mēs zinām, kur atrast
informācija struktūrā.

15
00:00:36,020 --> 00:00:40,060
>> Tā, lai masīvs, piemēram,
Galvenais ir elements indekss vai masīvs

16
00:00:40,060 --> 00:00:42,600
vieta 0 vai masīvs 1 un tā tālāk.

17
00:00:42,600 --> 00:00:46,140
Un vērtība ir datu
kas pastāv šajā vietā.

18
00:00:46,140 --> 00:00:48,550
Tātad, kas ir glabāti masīvā 0?

19
00:00:48,550 --> 00:00:54,290
Kas tiek glabāti masīvā 1 pret tikko
0 un 1, kas būtu atslēgas.

20
00:00:54,290 --> 00:00:56,360
>> Ar hash tabulā tas ir
kārtot to pašu ideju.

21
00:00:56,360 --> 00:01:00,690
Ar hash tabulu, mums ir šī hash
funkcija, kas ģenerē hash kodus.

22
00:01:00,690 --> 00:01:03,670
Tātad galvenais ir hash kodu no datiem.

23
00:01:03,670 --> 00:01:06,530
Un vērtība, it īpaši
mēs runājām par Ķēžu

24
00:01:06,530 --> 00:01:10,590
šajā video hash tabulas,
ir tas, ka saistīts saraksts datu

25
00:01:10,590 --> 00:01:12,550
ka hashes šai hashcode.

26
00:01:12,550 --> 00:01:14,050
Tiesības.

27
00:01:14,050 --> 00:01:16,050
Kas par citu pieeju
Šī metode, lai gan?

28
00:01:16,050 --> 00:01:21,000
Kas par metodi, kurā
atslēga ir garantēta unikāls,

29
00:01:21,000 --> 00:01:25,410
atšķirībā no hash tabulu, kur mēs varētu
galu galā ar diviem gabaliem datu

30
00:01:25,410 --> 00:01:27,200
ar tādu pašu hashcode.

31
00:01:27,200 --> 00:01:30,020
Un tad mums ir tikt galā ar
ka vai nu zondēšana vai vairāk

32
00:01:30,020 --> 00:01:33,340
vēlams Ķēžu noteikt šo problēmu.

33
00:01:33,340 --> 00:01:37,520
>> Tāpēc tagad mēs varam garantēt
ka mūsu galvenais būs unikāls.

34
00:01:37,520 --> 00:01:39,690
Un ko tad, ja mūsu vērtība bija
tikai kaut kā viegli

35
00:01:39,690 --> 00:01:44,080
kā patiess un nepatiess, kas stāsta mums, vai
vai ne, ka informācijas vienību

36
00:01:44,080 --> 00:01:45,610
pastāv struktūrā?

37
00:01:45,610 --> 00:01:48,180
Būla varētu būt tikpat vienkārša kā mazliet.

38
00:01:48,180 --> 00:01:52,660
Reāli tas ir iespējams,
baitu biežāk nekā mazliet.

39
00:01:52,660 --> 00:01:55,410
Bet tas ir daudz mazāks nekā
uzglabājot varbūt 50 rakstzīmju virkne,

40
00:01:55,410 --> 00:01:57,360
piemēram.

41
00:01:57,360 --> 00:02:02,210
>> Tātad mēģina, līdzīgi hash tabulas,
kas apvieno bloki un saistīts saraksts,

42
00:02:02,210 --> 00:02:05,790
mēģina apvienot bloki,
konstrukcijas, un norādes

43
00:02:05,790 --> 00:02:08,509
kopā uzglabāt datus
interesants veids, kas ir

44
00:02:08,509 --> 00:02:11,550
diezgan atšķirīgs no
kaut ko mēs esam redzējuši līdz šim.

45
00:02:11,550 --> 00:02:16,750
Tagad mēs izmantot datus kā ceļvedis
orientēties šo datu struktūra.

46
00:02:16,750 --> 00:02:18,710
Un, ja mēs varam sekot
Ceļvedī, ja mēs varam

47
00:02:18,710 --> 00:02:22,390
sekojiet datus no
sākuma līdz beigām, mēs

48
00:02:22,390 --> 00:02:24,945
zināt, vai šiem datiem
pastāv TRIE.

49
00:02:24,945 --> 00:02:28,310
>> Un, ja mēs nevaram sekot karti
no nozīmē beigt vispār,

50
00:02:28,310 --> 00:02:30,600
datus nevar pastāvēt.

51
00:02:30,600 --> 00:02:32,890
Atkal, taustiņi šeit ir
garantēta unikāls.

52
00:02:32,890 --> 00:02:36,020
Un tā atšķirībā no hash tabulu, mēs nekad
jātiek galā ar sadursmes šeit.

53
00:02:36,020 --> 00:02:39,090
Un nav divu gabali datu
ir tieši tāds pats ceļvedi

54
00:02:39,090 --> 00:02:40,530
ja vien, ka dati ir identiski.

55
00:02:40,530 --> 00:02:44,580
>> Ja mēs ievietotu Jāni, tad
mēs meklētu John.

56
00:02:44,580 --> 00:02:47,430
Tas ir divas identiskas gabali
dati, labi, mēs meklējam cauri.

57
00:02:47,430 --> 00:02:49,880
Bet citādi, jebkura
divi gabali dati ir

58
00:02:49,880 --> 00:02:52,750
garantēta, ir unikālas ceļvežus
izmantojot šo datu struktūru.

59
00:02:52,750 --> 00:02:56,210
Un mēs esam gatavojas veikt apskatīt
vizuāli tas tikai brīdi.

60
00:02:56,210 --> 00:02:58,810
>> Mēs to darām, mēģinot
izveidot jaunu datu struktūra,

61
00:02:58,810 --> 00:03:00,564
kartēšanas šādas galvenās vērtības pārus.

62
00:03:00,564 --> 00:03:03,480
Šajā gadījumā, mēs nebrauksim, lai izmantotu
kaut kas tik vienkāršs kā Būla.

63
00:03:03,480 --> 00:03:06,200
Mēs faktiski saglabās virkni.

64
00:03:06,200 --> 00:03:08,690
Un tas string gatavojas
būt nosaukums universitātē.

65
00:03:08,690 --> 00:03:12,140
>> Un galvenais, būs gads
ja šī universitāte tika dibināta.

66
00:03:12,140 --> 00:03:15,380
Visi gadi augstskolām
gribam būt četri cipari.

67
00:03:15,380 --> 00:03:19,840
Un tāpēc mēs izmantosim šos četrus ciparus uz
pārvietoties pa šo datu struktūru.

68
00:03:19,840 --> 00:03:22,270
Un mēs redzēsim, atkal, kā
mēs darīt, ka tikai sekundi.

69
00:03:22,270 --> 00:03:25,110
>> Beigās ceļu,
mēs redzēsim vārdu

70
00:03:25,110 --> 00:03:30,250
no universitātes, kas atbilst
šai atslēgai, šie četri cipari.

71
00:03:30,250 --> 00:03:34,390
Pamatideja ir TRIE
ir mums ir centrālā ceļu.

72
00:03:34,390 --> 00:03:35,640
Tāpēc domāju par to, kā koks.

73
00:03:35,640 --> 00:03:39,211
Un tas ir līdzīgs pareizrakstības
un koncepcijas, lai kokā.

74
00:03:39,211 --> 00:03:41,460
Parasti, kad mēs domājam par
koki reālajā pasaulē,

75
00:03:41,460 --> 00:03:44,090
viņiem ir saknes, kas ir iekļauts
zemes un tie aug uz augšu

76
00:03:44,090 --> 00:03:46,830
un tie ir filiāles
un tie ir lapas.

77
00:03:46,830 --> 00:03:49,450
Un būtībā ideja
trie ir tieši tas pats,

78
00:03:49,450 --> 00:03:51,755
izņemot to, ka sakne ir noenkurots
kaut kur debesīs.

79
00:03:51,755 --> 00:03:53,130
Un lapas ir apakšā.

80
00:03:53,130 --> 00:03:55,750
>> Tātad, tas ir veids, piemēram, ņemot koks
un tikai flipping otrādi.

81
00:03:55,750 --> 00:03:56,880
Bet ir vēl filiāles.

82
00:03:56,880 --> 00:03:59,463
Un tie būtu mūsu ceļi,
tie būs mūsu savienojumi

83
00:03:59,463 --> 00:04:02,220
no saknes līdz lapām.

84
00:04:02,220 --> 00:04:04,200
Šajā gadījumā, tie
takas, šie zari

85
00:04:04,200 --> 00:04:08,490
ir apzīmēti ar cipariem, kas pateiks mums
kādā veidā iet no kurienes mēs esam.

86
00:04:08,490 --> 00:04:11,800
>> Ja mēs redzam 0, mēs ejam uz leju šo darbības veidu,
ja mēs redzam 1, mēs ejam uz leju šo darbības veidu,

87
00:04:11,800 --> 00:04:12,900
un tā un tā tālāk.

88
00:04:12,900 --> 00:04:14,060
Nu, ko tas nozīmē?

89
00:04:14,060 --> 00:04:16,519
Nu, tas nozīmē, ka
katrā krustojuma vietā

90
00:04:16,519 --> 00:04:19,260
un katru mezglu
vidū un katru filiāle,

91
00:04:19,260 --> 00:04:23,020
tur ir 10 iespējas
vietas, ka mēs varam iet.

92
00:04:23,020 --> 00:04:27,690
Tātad ir 10 norādes
No katras vietas.

93
00:04:27,690 --> 00:04:30,610
>> Un tas ir, ja mēģina var iegūt
mazliet biedējoša kādu

94
00:04:30,610 --> 00:04:34,460
kurš nav daudz
pieredze datorzinātnēs pirms.

95
00:04:34,460 --> 00:04:35,960
Bet mēģina ir tiešām diezgan laba.

96
00:04:35,960 --> 00:04:37,793
Un, ja jums ir
iespēja strādāt ar viņiem

97
00:04:37,793 --> 00:04:40,420
un jūs esat gatavi rakt-in
un eksperimentēt ar tām,

98
00:04:40,420 --> 00:04:44,234
viņi tiešām diezgan interesanti
datu struktūras strādāt.

99
00:04:44,234 --> 00:04:46,900
Ja mēs vēlamies, lai ievietotu elementu
uz TRIE, viss, kas mums jādara,

100
00:04:46,900 --> 00:04:51,360
ir veidot pareizo ceļu
no saknes uz lapas.

101
00:04:51,360 --> 00:04:55,390
Lūk, ko katrs solis kopā
veids varētu izskatīties.

102
00:04:55,390 --> 00:04:59,660
Mēs ejam, lai definētu jaunu datu
struktūra par jaunu mezglu sauc trie.

103
00:04:59,660 --> 00:05:02,560
>> Un iekšpusē šo datu
struktūra ir divi gabali.

104
00:05:02,560 --> 00:05:05,460
Mēs ejam, lai saglabātu
Nosaukums universitātē.

105
00:05:05,460 --> 00:05:09,410
Un mēs ejam, lai saglabātu
masīvs norādes

106
00:05:09,410 --> 00:05:12,190
uz citiem punktiem tā paša tipa.

107
00:05:12,190 --> 00:05:14,780
Tātad, atkal, tas ir, ka sava
par jēdziena visur

108
00:05:14,780 --> 00:05:18,567
mēs esam, mēs pie 10 iespējams
vietas, mēs varam iet.

109
00:05:18,567 --> 00:05:20,150
Ja mēs redzam 0, mēs ejam pa šo filiāli.

110
00:05:20,150 --> 00:05:22,690
Ja mēs redzam 1, šī filiāle,
un tā tālāk, un tā tālāk, un tā tālāk.

111
00:05:22,690 --> 00:05:25,160
Ja mēs sakām 9, mēs ejam pa šo filiāli.

112
00:05:25,160 --> 00:05:28,220
Tātad katrā krustojuma vietā,
mēs varam iet 10 iespējamās vietas.

113
00:05:28,220 --> 00:05:35,740
Tātad katrs mezgls ir jāsatur 10 norādes
uz citiem mezgliem, uz 10 citiem mezgliem.

114
00:05:35,740 --> 00:05:39,810
>> Un dati mēs glabāšanai ir
tikai nosaukums universitātes.

115
00:05:39,810 --> 00:05:41,060
Tātad pieņemsim būvēt trie.

116
00:05:41,060 --> 00:05:44,860
Pieņemsim ievietot pāris
vienību mūsu TRIE.

117
00:05:44,860 --> 00:05:46,740
Tātad pašā augšā,
Tas ir mūsu saknes mezgla.

118
00:05:46,740 --> 00:05:49,740
Tas ir iespējams, būs kaut kas
jūs gatavojas globāli deklarēt.

119
00:05:49,740 --> 00:05:53,450
Un jūs gatavojas globāli saglabāt
rādītājs šajā mezglā vienmēr.

120
00:05:53,450 --> 00:05:55,360
>> Jūs gatavojas teikt,
sakne ir vienāds, un jūs esat

121
00:05:55,360 --> 00:05:57,580
gatavojas malloc sev trie mezglā.

122
00:05:57,580 --> 00:05:59,850
Un jūs nekad gatavojas
pieskarties saknes atkal.

123
00:05:59,850 --> 00:06:02,300
Katru reizi, kad jūs vēlaties
sākt navigāciju pa,

124
00:06:02,300 --> 00:06:05,802
jums noteikt citu rādītāju
vienāds ar saknes, piemēram, trav,

125
00:06:05,802 --> 00:06:07,760
kas ir piemērs es
izmantot daudzi mani video

126
00:06:07,760 --> 00:06:11,090
šeit skursteņi un rindas
un saite sarakstus un tā tālāk.

127
00:06:11,090 --> 00:06:13,320
>> Jūs noteikt citu rādītāju
aicināja Trav par šķērsošana.

128
00:06:13,320 --> 00:06:15,890
Un jūs izmantojat trav orientēties
caur datu struktūru.

129
00:06:15,890 --> 00:06:17,500
Tātad, pieņemsim redzēt, kā tas varētu izskatīties.

130
00:06:17,500 --> 00:06:19,880
Tāpēc tieši tagad, ko
tas mezglu izskatās?

131
00:06:19,880 --> 00:06:22,920
Nu, tāpat kā mūsu datiem
struktūra deklarācija norādīja,

132
00:06:22,920 --> 00:06:26,906
mums ir virkne, kas
šajā gadījumā ir tukšs.

133
00:06:26,906 --> 00:06:27,780
Tur nekas šeit.

134
00:06:27,780 --> 00:06:29,550
>> Un masīvs 10 norādes.

135
00:06:29,550 --> 00:06:31,790
Un tieši tagad, mēs tikai
ir 1 mezglu šajā TRIE.

136
00:06:31,790 --> 00:06:33,110
Tur nekas cits tajā.

137
00:06:33,110 --> 00:06:36,020
Tātad visi 10 no tiem
norādes punkts null.

138
00:06:36,020 --> 00:06:38,090
Tas ir tas, ko sarkanā norāda.

139
00:06:38,090 --> 00:06:39,500
>> Pieņemsim ievietot virkni Harvard.

140
00:06:39,500 --> 00:06:41,999
Pieņemsim ievietot Universitāte
Harvard šajā TRIE, kas

141
00:06:41,999 --> 00:06:43,940
tika nodibināta gadā 1636.

142
00:06:43,940 --> 00:06:48,220
Mēs vēlamies izmantot šo taustiņu,
1636, lai pastāstītu mums, kur mēs esam

143
00:06:48,220 --> 00:06:50,140
gatavojas glabāt Harvard šajā TRIE.

144
00:06:50,140 --> 00:06:51,470
Tagad, kā varētu mēs to darām?

145
00:06:51,470 --> 00:06:52,886
>> Tas varētu izskatīties kaut kas līdzīgs šim.

146
00:06:52,886 --> 00:06:54,160
Sākam pie saknes.

147
00:06:54,160 --> 00:06:56,920
Un mums ir šie 10 vietas, mēs varam iet.

148
00:06:56,920 --> 00:06:59,900
Saknes ir tāpat kā jebkurš
cita mezgla TRIE.

149
00:06:59,900 --> 00:07:02,850
Ir 10 vietas, mēs varam aiziet no šejienes.

150
00:07:02,850 --> 00:07:07,215
>> Kur mēs, iespējams, vēlas
lai iet, ja atslēga ir 1636?

151
00:07:07,215 --> 00:07:08,340
Tur tiešām divas iespējas.

152
00:07:08,340 --> 00:07:08,450
Tiesības.

153
00:07:08,450 --> 00:07:10,825
Mēs varam veidot atslēgu
labās puses uz kreiso, un sākt ar 6.

154
00:07:10,825 --> 00:07:14,000
Vai mēs varētu veidot atslēgu
kreisās uz labo un sākt ar 1.

155
00:07:14,000 --> 00:07:16,140
>> Tas ir iespējams, vairāk
intuitīva kā cilvēks

156
00:07:16,140 --> 00:07:18,110
izprast mēs
vienkārši iet pa kreisi uz labo.

157
00:07:18,110 --> 00:07:21,140
Un tāpēc, ja es gribu, lai ievietotu
Harvard šajā TRIE,

158
00:07:21,140 --> 00:07:23,560
Es, iespējams, vēlas sākt
sākot pie saknes,

159
00:07:23,560 --> 00:07:25,720
skatoties uz maniem 10 iespējas
man priekšā, un sakot

160
00:07:25,720 --> 00:07:28,700
Es gribu iet uz leju 1 ceļu.

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

162
00:07:29,700 --> 00:07:31,810
>> Tagad, 1 ceļš šobrīd null.

163
00:07:31,810 --> 00:07:35,920
Tātad, ja es gribu turpināt noteikts, ka ceļu
lai ievietotu šo elementu vērā TRIE,

164
00:07:35,920 --> 00:07:42,040
Man ir malloc jaunu mezglu, ir 1
punktu tur, un tad es esmu labi iet.

165
00:07:42,040 --> 00:07:46,460
>> Tāpēc es būtībā esmu pie
punkts, kur es stāvu

166
00:07:46,460 --> 00:07:50,270
pie koka saknēm vai
trie un tur ir 10 filiāles.

167
00:07:50,270 --> 00:07:52,260
Bet katrai filiālei has a
vārtu priekšā no tā.

168
00:07:52,260 --> 00:07:53,060
Tiesības.

169
00:07:53,060 --> 00:07:54,850
Jo tur ir nekas cits tur ir.

170
00:07:54,850 --> 00:07:56,522
Nav droši pārvietoties.

171
00:07:56,522 --> 00:07:58,980
Tas nozīmē, ka tur nekas
noteikti kāds no šiem zariem.

172
00:07:58,980 --> 00:08:02,532
Ja es gribu, lai sāktu ēkas
kaut ko, es gribu, lai noņemtu vārtiem.

173
00:08:02,532 --> 00:08:04,490
Es gribu, lai novērstu vārtiem
priekšā numuru 1.

174
00:08:04,490 --> 00:08:05,698
Un es gribu iet uz leju, ka.

175
00:08:05,698 --> 00:08:08,060
Un es gribu, lai izveidotu
vēl viena vieta, kur man iet.

176
00:08:08,060 --> 00:08:09,470
>> Un tas, ko es esmu darījusi šeit.

177
00:08:09,470 --> 00:08:11,430
Tātad 1 vairs norāda null.

178
00:08:11,430 --> 00:08:13,830
Man teica, ka ir droši iet uz leju šeit tagad.

179
00:08:13,830 --> 00:08:15,789
Man būvētas vēl mezglā.

180
00:08:15,789 --> 00:08:18,330
Un, kad es nokļūt uz šo mezglu, es
ir vēl viens lēmums padarīt.

181
00:08:18,330 --> 00:08:20,890
Kur es esmu gatavojas aiziet no šejienes?

182
00:08:20,890 --> 00:08:22,700
>> Nu, es esmu jau gājusi uz leju 1.

183
00:08:22,700 --> 00:08:24,470
Tāpēc tagad es droši vien gribu iet uz leju 6.

184
00:08:24,470 --> 00:08:24,970
Tiesības.

185
00:08:24,970 --> 00:08:27,100
Atkal, man ir 10 vietas, es varu izvēlēties.

186
00:08:27,100 --> 00:08:30,060
Tātad pieņemsim, tagad iet uz leju numuru 6.

187
00:08:30,060 --> 00:08:32,280
Tāpēc es notīrīt vārtiem
priekšā skaita 6.

188
00:08:32,280 --> 00:08:33,250
Un es iet tur lejā.

189
00:08:33,250 --> 00:08:34,580
Un es būvēt vēl vienu mezglu.

190
00:08:34,580 --> 00:08:37,630
Un es esmu sasniedzis vēl krustojumam punktu.

191
00:08:37,630 --> 00:08:40,289
>> Atkal, man ir 10 izvēles
lai kur es varu iet.

192
00:08:40,289 --> 00:08:42,799
Man pārvietots no 1 līdz 6.

193
00:08:42,799 --> 00:08:44,215
Tāpēc tagad es, iespējams, vēlas doties uz 3.

194
00:08:44,215 --> 00:08:45,381
3, tur ir nekur es varu iet.

195
00:08:45,381 --> 00:08:48,980
Tāpēc man ir, lai pavērtu ceļu
un veidot sev jaunu telpu.

196
00:08:48,980 --> 00:08:50,870
Un tad no 3, kur vēlos iet?

197
00:08:50,870 --> 00:08:52,450
Es gribu iet uz leju 6.

198
00:08:52,450 --> 00:08:54,770
>> Un atkal, man nācās
pavērtu ceļu, lai to izdarītu.

199
00:08:54,770 --> 00:08:59,179
Tāpēc tagad es esmu, ko izmanto savu atslēgu, lai ievietotu radītu
mezglus un sākt veidot šo trie.

200
00:08:59,179 --> 00:09:00,220
Esmu sācis pie saknes.

201
00:09:00,220 --> 00:09:03,666
Es esmu gājusi uz leju 1636.

202
00:09:03,666 --> 00:09:05,540
Un tagad es esmu apakšā
tur šajā mezglā.

203
00:09:05,540 --> 00:09:06,610
Un jūs varētu
redzēt ekrānā.

204
00:09:06,610 --> 00:09:07,735
>> Tas ir izcelta dzeltenā krāsā.

205
00:09:07,735 --> 00:09:10,020
Tas ir, ja es šobrīd esmu.

206
00:09:10,020 --> 00:09:11,300
Mans galvenais ir izdarīts.

207
00:09:11,300 --> 00:09:13,030
Esmu izsmeltas visas pozīcijas manā atslēgu.

208
00:09:13,030 --> 00:09:15,040
Tāpēc es nevaru iet tālāk.

209
00:09:15,040 --> 00:09:17,720
Tātad šajā brīdī, visi man
tiešām ir nepieciešams darīt, ir teikt, OK.

210
00:09:17,720 --> 00:09:18,990
Tas ir veids, piemēram meklē
lejup uz zemi,

211
00:09:18,990 --> 00:09:21,115
ja jūs Paredzot
sevi kā šāda veida ceļš

212
00:09:21,115 --> 00:09:22,350
ar dažādiem savienojumiem.

213
00:09:22,350 --> 00:09:25,800
Kārtot skatoties uz leju un veida
spray glezna Harvard uz zemes.

214
00:09:25,800 --> 00:09:26,800
Tas ir vārds no tā.

215
00:09:26,800 --> 00:09:28,300
Zinu, ka tas, kas ir šajā vietā.

216
00:09:28,300 --> 00:09:31,870
Ja sākam pie saknes, un mēs ejam uz leju
1 un pēc tam 6 un pēc tam 3 un pēc tam 6,

217
00:09:31,870 --> 00:09:32,780
Kur mēs esam?

218
00:09:32,780 --> 00:09:35,640
Nu, ja mēs skatāmies uz leju
un mēs redzam Harvard, tad

219
00:09:35,640 --> 00:09:38,960
mēs zinām, ka Harvard bija
dibināta 1636, pamatojoties uz to, kā

220
00:09:38,960 --> 00:09:41,400
mēs īstenojot šo datu struktūra.

221
00:09:41,400 --> 00:09:43,177
Tā, ka bija cerams vienkārša.

222
00:09:43,177 --> 00:09:44,760
Mēs darīsim vēl divas ievietošanas.

223
00:09:44,760 --> 00:09:50,060
Un cerams, tas būs palīdzēt
skatīt darīts divas reizes vairāk.

224
00:09:50,060 --> 00:09:52,210
>> Tagad, pieņemsim ievietot citā augstskolā.

225
00:09:52,210 --> 00:09:54,630
Pieņemsim ievietot Yale šajā TRIE.

226
00:09:54,630 --> 00:09:57,037
Yale tika dibināta 1701. gadā.

227
00:09:57,037 --> 00:09:58,870
Tāpēc mēs sāksim pie
saknes, jo mēs vienmēr darīt.

228
00:09:58,870 --> 00:09:59,890
Un mēs noteikti šķērsošana rādītāju.

229
00:09:59,890 --> 00:10:01,624
Mēs spēsim izmantot šo, lai pārvietotos pa.

230
00:10:01,624 --> 00:10:03,790
Pirmā lieta, ko mēs gribam
darīt, ir iet uz leju 1 ceļu.

231
00:10:03,790 --> 00:10:05,830
Tas ir pirmais cipars mūsu atslēgu.

232
00:10:05,830 --> 00:10:08,420
Par laimi, lai gan, mums nav
ir darīt jebkuru darbu šajā laikā.

233
00:10:08,420 --> 00:10:09,919
1 ceļš jau ir noskaidroti.

234
00:10:09,919 --> 00:10:13,520
Es noskaidroti to iepriekš, kad es
tika ievietojot Harvard 1636.

235
00:10:13,520 --> 00:10:18,090
Lai es varētu droši pārvietot
leju 1 un tikai iet uz turieni.

236
00:10:18,090 --> 00:10:20,150
Ja var pārvietot uz leju 1.

237
00:10:20,150 --> 00:10:22,930
>> Tagad, lai gan, es gribu iet uz 7.

238
00:10:22,930 --> 00:10:24,280
Es pavērusi ceļu pie 6.

239
00:10:24,280 --> 00:10:27,050
Es zinu, ka varu droši
turpināt pa 6 ceļu.

240
00:10:27,050 --> 00:10:29,220
Bet man ir nepieciešams, lai turpinātu par 7 ceļu.

241
00:10:29,220 --> 00:10:30,580
Tātad, kas man jādara?

242
00:10:30,580 --> 00:10:35,070
Nu, tāpat kā agrāk, es vienkārši vajag
lai notīrītu vārtiem, izkļūt no tā,

243
00:10:35,070 --> 00:10:38,740
un veidot jaunu mezglu no 7. ceļa.

244
00:10:38,740 --> 00:10:40,250
Tāpat kā šis.

245
00:10:40,250 --> 00:10:42,930
>> Tāpēc tagad es esmu pārcelts 1 un pēc tam 7.

246
00:10:42,930 --> 00:10:45,550
Un tagad paziņojums, es esmu veida
par šo jauno apakšnozare.

247
00:10:45,550 --> 00:10:46,050
Tiesības.

248
00:10:46,050 --> 00:10:49,260
Viss pārējais no 16
tālāk, man nav rūp.

249
00:10:49,260 --> 00:10:50,720
Es to nedaru 16 neko.

250
00:10:50,720 --> 00:10:51,750
Es esmu darot 17 lietas.

251
00:10:51,750 --> 00:10:58,380
>> Tātad tagad no 17 uz, man
kārtot aizsvilties jaunas takas šeit.

252
00:10:58,380 --> 00:11:00,462
Nākamais cipars mans galvenais ir 0.

253
00:11:00,462 --> 00:11:01,670
Es skaidri nevaru nokļūt jebkur.

254
00:11:01,670 --> 00:11:02,628
Es tikko uzcelta šī mezglā.

255
00:11:02,628 --> 00:11:04,550
Tāpēc es zinu, tur nav
ceļi uz priekšu no šejienes.

256
00:11:04,550 --> 00:11:06,370
Tāpēc man ir veikt vienu sevi.

257
00:11:06,370 --> 00:11:09,360
>> Tāpēc es malloc jaunu mezglu
un ir 0 punktu tur.

258
00:11:09,360 --> 00:11:12,770
Un tad vēl vienu reizi, es malloc
jaunu mezglu un ir viens punkts tur.

259
00:11:12,770 --> 00:11:15,870
Atkal, es esmu izsmēlusi savu atslēgu, 1701.

260
00:11:15,870 --> 00:11:18,472
Tāpēc es skatos, un es aerosola krāsu Yale.

261
00:11:18,472 --> 00:11:19,680
Tas ir vārds šajā mezglā.

262
00:11:19,680 --> 00:11:24,660
>> Un tāpēc tagad, ja man kādreiz vajadzēs, lai redzētu, Yale
ir šajā TRIE, es sāku pie saknes,

263
00:11:24,660 --> 00:11:27,060
Es iet uz leju 1701, un skatīties uz leju.

264
00:11:27,060 --> 00:11:30,030
Un, ja es redzu Yale aerosols
krāsoti uz zemes, tad

265
00:11:30,030 --> 00:11:32,200
Es zinu, Yale pastāv šajā TRIE.

266
00:11:32,200 --> 00:11:32,950
Darīsim vienu vairāk.

267
00:11:32,950 --> 00:11:36,430
Pieņemsim ievietot Dartmouth vērā šo
trie, kas tika dibināta 1769..

268
00:11:36,430 --> 00:11:37,750
>> Sākt pie saknes vēlreiz.

269
00:11:37,750 --> 00:11:39,445
Mans pirmais cipars no maniem galvenajiem ir 1.

270
00:11:39,445 --> 00:11:40,820
Es varu droši virzīties lejup šo ceļu.

271
00:11:40,820 --> 00:11:42,400
Ka jau eksistē.

272
00:11:42,400 --> 00:11:44,040
Nākamais cipars no maniem galvenajiem ir 7.

273
00:11:44,040 --> 00:11:45,890
Es varu droši virzīties lejup šo ceļu.

274
00:11:45,890 --> 00:11:47,540
Tā pastāv kā labi.

275
00:11:47,540 --> 00:11:49,000
>> Mans nākamais ir 6.

276
00:11:49,000 --> 00:11:52,860
No šejienes, no kurienes es esmu šobrīd
dzeltenā tur šajā vidū mezglā,

277
00:11:52,860 --> 00:11:56,060
6. pašlaik bloķēta off.

278
00:11:56,060 --> 00:11:58,830
Ja es gribu iet uz leju, ka ceļu,
Man ir veidot to pats.

279
00:11:58,830 --> 00:12:02,250
Tāpēc es ņemšu malloc jaunu mezglu
un ir 6. punktu tur.

280
00:12:02,250 --> 00:12:04,250
Un tad, atkal, es esmu
degošs jaunas takas šeit.

281
00:12:04,250 --> 00:12:10,750
>> Tāpēc es malloc jaunu mezglu, lai no
ka node-- ceļa numurs 9-- un tad tagad

282
00:12:10,750 --> 00:12:13,584
ja es ceļot 1769, un es skatos.

283
00:12:13,584 --> 00:12:15,500
Nav nekas šobrīd
aerosols krāsotas tur.

284
00:12:15,500 --> 00:12:16,930
Es varu uzrakstīt Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Un es esmu ievietots
Dartmouth uz TRIE.

286
00:12:20,710 --> 00:12:23,450
>> Tātad tas ir ievietojot
lietas fani TRIE.

287
00:12:23,450 --> 00:12:25,384
Tagad mēs vēlamies, lai meklētu lietas.

288
00:12:25,384 --> 00:12:27,050
Kā mēs meklētu lietām TRIE?

289
00:12:27,050 --> 00:12:29,170
Nu, tas ir diezgan daudz to pašu ideju.

290
00:12:29,170 --> 00:12:33,620
Tagad mēs tikai izmantot ciparus atslēgu
lai redzētu, vai mēs varam pārvietoties no saknes

291
00:12:33,620 --> 00:12:37,170
lai kur mēs gribam iet uz TRIE.

292
00:12:37,170 --> 00:12:41,620
>> Ja mēs hit strupceļā jebkurā brīdī, tad
mēs zinām, ka šis elements nevar eksistē

293
00:12:41,620 --> 00:12:44,500
vai arī, ka ceļš būtu
jau ir noskaidroti.

294
00:12:44,500 --> 00:12:45,930
Ja mēs to visu ceļu uz
beigas, viss, kas mums jādara,

295
00:12:45,930 --> 00:12:48,471
ir skatīties uz leju un redzēt, ja tas ir
elements mēs meklējam.

296
00:12:48,471 --> 00:12:49,335
Ja tā ir, veiksme.

297
00:12:49,335 --> 00:12:52,610
Ja tā nav, neizdoties.

298
00:12:52,610 --> 00:12:54,940
>> Tātad pieņemsim meklēt
Harvard šajā TRIE.

299
00:12:54,940 --> 00:12:56,020
Sākam pie saknes.

300
00:12:56,020 --> 00:12:58,228
Un atkal, mēs ejam, lai
izveidot šķērsošana rādītāju

301
00:12:58,228 --> 00:12:59,390
darīt mūsu kustas mums.

302
00:12:59,390 --> 00:13:02,080
No saknes, mēs zinām, ka
pirmā vieta, mums ir jāiet, ir 1,

303
00:13:02,080 --> 00:13:03,390
mēs varam darīt?

304
00:13:03,390 --> 00:13:03,982
Jā mēs varam.

305
00:13:03,982 --> 00:13:04,690
Ja droši eksistē.

306
00:13:04,690 --> 00:13:06,660
Mēs varam iet uz turieni.

307
00:13:06,660 --> 00:13:08,440
>> Tagad nākamais vieta, mums ir nepieciešams, lai iet, ir 6.

308
00:13:08,440 --> 00:13:10,557
Vai 6 ceļš pastāv no šejienes?

309
00:13:10,557 --> 00:13:11,140
Jā, tā dara.

310
00:13:11,140 --> 00:13:12,690
Mēs varam iet uz leju 6 ceļu.

311
00:13:12,690 --> 00:13:13,905
Un mēs galu galā šeit.

312
00:13:13,905 --> 00:13:16,130
>> Vai mēs varam iet uz leju 3 ceļu no šejienes?

313
00:13:16,130 --> 00:13:18,450
Nu, kā izrādās,
jā, ka pastāv pārāk.

314
00:13:18,450 --> 00:13:20,790
Un mēs varam iegūt par 6 ceļu no šejienes?

315
00:13:20,790 --> 00:13:21,982
Jā mēs varam.

316
00:13:21,982 --> 00:13:24,002
>> Mēs neesam gluži atbildēja
jautājums vēl.

317
00:13:24,002 --> 00:13:25,710
Tur ir vēl viens
solis, kas tagad

318
00:13:25,710 --> 00:13:28,520
mums ir jāskatās uz leju un
redzēt, ja tas ir actually--

319
00:13:28,520 --> 00:13:32,660
ja mēs meklējam Harvard, ir tas, ka
Ko mēs redzam, kad mēs izplūdes atslēgu?

320
00:13:32,660 --> 00:13:35,430
Šajā piemērā mēs izmantojam šeit,
gadi vienmēr ir četri cipari.

321
00:13:35,430 --> 00:13:40,280
Bet jūs varētu būt, izmantojot, piemēram, ja
jums ir uzglabātu vārdnīcas vārdiem.

322
00:13:40,280 --> 00:13:44,060
>> Un tā vietā, 10 norādes
manu atrašanās vietu, jūs varētu būt 26.

323
00:13:44,060 --> 00:13:46,040
Viena katram alfabēta burtam.

324
00:13:46,040 --> 00:13:50,350
Un tur ir daži vārdi, piemēram, nūja,
kas ir apakškopa partijas, piemēram.

325
00:13:50,350 --> 00:13:53,511
Un, pat ja jums uz
no galvenajiem beigas un paskatās uz leju,

326
00:13:53,511 --> 00:13:55,260
jūs nevarēsiet redzēt, ko
jūs meklējat.

327
00:13:55,260 --> 00:13:58,500
>> Tātad jums vienmēr ir traversa
visu ceļu un pēc tam

328
00:13:58,500 --> 00:14:01,540
ja Jums bija iespēja veiksmīgi
lai šķērsotu visu ceļu,

329
00:14:01,540 --> 00:14:03,440
skatīties uz leju un darīt vienu galīgo apstiprinājumu.

330
00:14:03,440 --> 00:14:05,120
Vai tas, ko es meklēju?

331
00:14:05,120 --> 00:14:07,740
Nu, es skatos pēc sākuma
augšā un iet 1636.

332
00:14:07,740 --> 00:14:08,240
Es skatos uz leju.

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

334
00:14:09,400 --> 00:14:11,689
Tātad, jā, man izdevās.

335
00:14:11,689 --> 00:14:13,980
Ko darīt, ja tas, ko es esmu meklē
neatrodas TRIE, lai gan.

336
00:14:13,980 --> 00:14:17,200
Ko darīt, ja es esmu meklē Princeton,
kas tika dibināta 1746.

337
00:14:17,200 --> 00:14:20,875
Un tā 1746. kļūst mana atslēga
lai pārvietotos pa TRIE.

338
00:14:20,875 --> 00:14:22,040
Nu, es sāku pie saknes.

339
00:14:22,040 --> 00:14:24,760
Un pirmā vieta es gribu
lai iet uz leju 1 ceļu.

340
00:14:24,760 --> 00:14:25,590
Vai es varu to darīt?

341
00:14:25,590 --> 00:14:26,490
Jā es varu.

342
00:14:26,490 --> 00:14:28,730
>> Vai es varu iet uz leju 7 ceļu no turienes?

343
00:14:28,730 --> 00:14:29,230
Jā, es varu.

344
00:14:29,230 --> 00:14:30,750
Ka pastāv pārāk.

345
00:14:30,750 --> 00:14:32,460
Bet es varu iet uz leju 4 ceļu no šejienes?

346
00:14:32,460 --> 00:14:35,550
Tas ir tāpat kā uzdodot jautājumu, var
Es doties uz leju, ka maz kvadrātveida

347
00:14:35,550 --> 00:14:37,114
ka es esmu izcelta dzeltenā krāsā?

348
00:14:37,114 --> 00:14:38,030
Nav nekas tur.

349
00:14:38,030 --> 00:14:38,610
Tiesības.

350
00:14:38,610 --> 00:14:41,310
>> Nav veids, kā virzīties uz leju 4 ceļu.

351
00:14:41,310 --> 00:14:46,480
Ja Princeton bija šajā TRIE, ka 4
būtu noskaidroti mums jau.

352
00:14:46,480 --> 00:14:49,130
Un lai šajā brīdī
mēs esam sasnieguši strupceļā.

353
00:14:49,130 --> 00:14:50,250
Mēs nevaram iet tālāk.

354
00:14:50,250 --> 00:14:53,440
Un tā mēs varam teikt, galīgi, nē.

355
00:14:53,440 --> 00:14:56,760
Princeton neeksistē šajā TRIE.

356
00:14:56,760 --> 00:14:58,860
>> Tātad, ko tas viss nozīmē?

357
00:14:58,860 --> 00:14:59,360
Tiesības.

358
00:14:59,360 --> 00:15:01,000
Tur ir daudz kas notiek šeit.

359
00:15:01,000 --> 00:15:02,500
Tur ir norādes visā vietā.

360
00:15:02,500 --> 00:15:04,249
Un, kā jūs varat redzēt
tikai no diagrammas,

361
00:15:04,249 --> 00:15:07,010
tur ir daudz mezglu, kas
ir sava veida peld apkārt.

362
00:15:07,010 --> 00:15:13,480
Bet paziņojums katru reizi, kad mēs vēlējāmies
pārbaudīt, vai kaut kas bija TRIE,

363
00:15:13,480 --> 00:15:15,000
mums tikai bija jāveic 4 gājienus.

364
00:15:15,000 --> 00:15:17,208
>> Katru reizi, kad mēs vēlējāmies
ievietot kaut ko TRIE,

365
00:15:17,208 --> 00:15:20,440
mums ir jāveic 4 gājienus, iespējams,
mallocing daži sīkumi gar ceļu.

366
00:15:20,440 --> 00:15:23,482
Bet kā mēs redzējām, kad mēs ievietota
Dartmouth uz TRIE,

367
00:15:23,482 --> 00:15:25,940
dažreiz daži no ceļa
iespējams, jau ir noskaidroti mums.

368
00:15:25,940 --> 00:15:30,520
Un tā kā mūsu trie kļūst lielāka un
lielāks, mums ir jādara mazāk darba ikreiz

369
00:15:30,520 --> 00:15:32,270
ievietot jaunas lietas
jo mēs esam jau

370
00:15:32,270 --> 00:15:35,746
built daudz starpprodukta
Nozares gar ceļu.

371
00:15:35,746 --> 00:15:38,370
Ja mēs tikai kādreiz ir apskatīt
4 lietas, 4 ir tikai nemainīga.

372
00:15:38,370 --> 00:15:41,750
Mēs patiešām ir sava veida tuvojas
konstante laiks ievietošana

373
00:15:41,750 --> 00:15:44,501
un nemainīgs laiks lookup.

374
00:15:44,501 --> 00:15:47,500
Tradeoff, protams, ir tas, ka
Tas trie, kā jūs, iespējams, varat pateikt,

375
00:15:47,500 --> 00:15:49,030
ir milzīgs.

376
00:15:49,030 --> 00:15:51,040
Katrs no šiem mezgliem
aizņem daudz vietas.

377
00:15:51,040 --> 00:15:52,090
>> Bet tas ir tradeoff.

378
00:15:52,090 --> 00:15:55,260
Ja mēs gribam tiešām ātri
ievietošanas, tiešām ātri dzēšanu,

379
00:15:55,260 --> 00:15:59,630
un tiešām ātri lookup, mums ir
ir daudz datu peld apkārt.

380
00:15:59,630 --> 00:16:03,590
Mums ir atcelt daudz vietas
un atmiņas par šo datu struktūras

381
00:16:03,590 --> 00:16:04,290
pastāvēt.

382
00:16:04,290 --> 00:16:05,415
>> Un tā tas ir tradeoff.

383
00:16:05,415 --> 00:16:07,310
Bet izskatās, ka mums
varētu būt atradis.

384
00:16:07,310 --> 00:16:09,560
Mēs, iespējams, ir konstatēts, ka
svēts grail datu struktūras

385
00:16:09,560 --> 00:16:12,264
ar ātru ievietošanas,
dzēšanu, un lookup.

386
00:16:12,264 --> 00:16:14,430
Un varbūt tas būs
gadījumā datu struktūra

387
00:16:14,430 --> 00:16:18,890
izmantot kāda informācija
mēs cenšamies veikalā.

388
00:16:18,890 --> 00:16:21,860
Es esmu Doug Lloyd, tas ir CS50.

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