1
00:00:00,000 --> 00:00:02,994
 [MŪZIKA ATSKAŅOTĀSSKAN MŪZIKA]

2
00:00:05,426 --> 00:00:08,764
DUGSDAGS LOIDS: Tāpēc mēs esam
kļuvušinokļuvuši arvien tuvāk datu 

3
00:00:08,764 --> 00:00:12,102
struktūru svētajam grālam, ko mēs
varam ievietot, dzēst un meklēt 

4
00:00:12,102 --> 00:00:15,440
nemainīgā laikā. 

5
00:00:15,440 --> 00:00:16,270
Pareizi.

6
00:00:16,270 --> 00:00:17,280
Tas ir sava veida mērķis.

7
00:00:17,280 --> 00:00:19,720
Mēs vēlamies, lai mēs varētu
paveikt lietas ļoti, ļoti ātri.

8
00:00:19,720 --> 00:00:21,150
Vai mēs to esam atraduši šeit, kad
runājam par 

9
00:00:21,150 --> 00:00:22,580
mēģinājumiemdigitālajiem kokiem? 

10
00:00:22,580 --> 00:00:23,670
Nu, paskatīsimies.

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

12
00:00:26,757 --> 00:00:29,845
kas apstrādā tā saukto
atslēgu-vērtību pāru kartēšanu, kartējot kādu 

13
00:00:29,845 --> 00:00:32,932
datu daļu ar kādu citu datu daļu,
lai mēs zinātu, kur struktūrā 

14
00:00:32,932 --> 00:00:36,020
atrast informāciju. 

15
00:00:36,020 --> 00:00:39,310
Tātad, piemēram, masīvam atslēga ir
elementa indekss vai masīva 

16
00:00:39,310 --> 00:00:42,600
atrašanās 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 dati, kas pastāv šajā
vietā.

18
00:00:46,140 --> 00:00:48,550
Tātad, kas tiek saglabāts masīvā 0?

19
00:00:48,550 --> 00:00:51,420
Kas tiek saglabāts masīvā 1,
salīdzinot ar tikai 0 un 1, kas būtu 

20
00:00:51,420 --> 00:00:54,290
atslēgas. 

21
00:00:54,290 --> 00:00:56,360
 Ar hash tabulujaucējtabulu tā ir
tāda pati ideja.

22
00:00:56,360 --> 00:00:58,525
Izmantojot hash tabulujaucējtabulu,
mums ir šī jaucējfunkcija, kas 

23
00:00:58,525 --> 00:01:00,690
ģenerē jaucējkodus. 

24
00:01:00,690 --> 00:01:03,670
Tātad galvenaisatslēga ir datu
jaucējkods.

25
00:01:03,670 --> 00:01:06,630
Un vērtība, jo īpaši mēs runājām
par ķēdes pievienošanu video par 

26
00:01:06,630 --> 00:01:09,590
hash tabulāmjaucējtabulām, ir
saistītais datu saraksts, kas 

27
00:01:09,590 --> 00:01:12,550
sajaucsajaucas ar šo jaucējkodu. 

28
00:01:12,550 --> 00:01:14,050
Pareizi.

29
00:01:14,050 --> 00:01:16,050
Bet kā ar citu pieeju šai metodei?

30
00:01:16,050 --> 00:01:18,837
Kā ir ar metodi, kurā atslēga tiek
garantēta unikālatiek garantēta 

31
00:01:18,837 --> 00:01:21,625
unikāla atslēga, atšķirībā no
jaucēj tabulasjaucējtabulas, kur mēs 

32
00:01:21,625 --> 00:01:24,412
varētu nonākt pie diviem datu
vienumiem ar vienu un to pašu 

33
00:01:24,412 --> 00:01:27,200
jaucējkodu. 

34
00:01:27,200 --> 00:01:30,270
Un tad mums tas ir jārisina, veicot
zondēšanuizpēti vai, vēlams, 

35
00:01:30,270 --> 00:01:33,340
ķēdivirknēšanu, lai atrisinātu šo
problēmu. 

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

37
00:01:37,520 --> 00:01:40,216
Un kā būtu, ja mūsu vērtība būtu
tikpat vienkārša kā patiesība un 

38
00:01:40,216 --> 00:01:42,913
nepatiesībapatiesi un nepatiesi,
kas mums norāda, vai šī informācija 

39
00:01:42,913 --> 00:01:45,610
struktūrā pastāv vai nēne? 

40
00:01:45,610 --> 00:01:48,180
Būla vērtība varētu būt tikpat
vienkārša kā mazlietbits.

41
00:01:48,180 --> 00:01:50,420
Reāli tas, iespējams, ir par baitu,
visticamāk, nekā mazlietdroši 

42
00:01:50,420 --> 00:01:52,660
vien ir baits, kas ir ticamāks par
bitu. 

43
00:01:52,660 --> 00:01:55,010
Bet tas ir daudz mazāk nekā,
piemēram, 50 rakstzīmju virknes 

44
00:01:55,010 --> 00:01:57,360
saglabāšana. 

45
00:01:57,360 --> 00:02:00,907
Tādējādi mēģinājumidigitālie koki,
līdzīgi kā jaucējtabulas, kas 

46
00:02:00,907 --> 00:02:04,455
apvieno masīvus un saistītos
sarakstus, mēģina apvienot masīvus, 

47
00:02:04,455 --> 00:02:08,002
struktūras un norādes kopā, lai
saglabātu datus interesantā veidā, 

48
00:02:08,002 --> 00:02:11,550
kas ievērojami atšķiras no visa, ko
esam redzējuši līdz šim. 

49
00:02:11,550 --> 00:02:14,150
Tagad mēs izmantojam datus kā
ceļvedi, lai pārvietotos šajā datu 

50
00:02:14,150 --> 00:02:16,750
struktūrā. 

51
00:02:16,750 --> 00:02:19,481
Un, ja mēs varam sekot ceļvedim, ja
mēs varam sekot datiem no sākuma 

52
00:02:19,481 --> 00:02:22,213
līdz beigām, mēs uzzināsim, vai šie
dati pastāv 

53
00:02:22,213 --> 00:02:24,945
izmēģinājumādigitālajā kokā. 

54
00:02:24,945 --> 00:02:27,772
Un, ja mēs vispār nevaram sekot
kartei no nozīmes līdz galam, dati 

55
00:02:27,772 --> 00:02:30,600
nevar pastāvēt. 

56
00:02:30,600 --> 00:02:32,890
Atkal, atslēgas šeit ir garantētas
unikālas.

57
00:02:32,890 --> 00:02:34,455
Un tāpēc atšķirībā no hash
tabulasjaucējtabulas mums šeit nekad nebūs 

58
00:02:34,455 --> 00:02:36,020
jāsaskaras ar sadursmēm. 

59
00:02:36,020 --> 00:02:38,275
Un nevienam divām datu daļām nav
tieši tāda paša ceļveža, ja vien šie 

60
00:02:38,275 --> 00:02:40,530
dati nav identiski. 

61
00:02:40,530 --> 00:02:44,580
 Ja ievietojam JāniJohn, tad
meklējam JāniJohn.

62
00:02:44,580 --> 00:02:46,005
Tie ir divi identiski datidatu
fragmenti, pareizi, mēs skatāmiesko 

63
00:02:46,005 --> 00:02:47,430
mēs apskatām. 

64
00:02:47,430 --> 00:02:50,090
Bet pretējā gadījumā jebkurām divām
datu daļām tiek garantēta 

65
00:02:50,090 --> 00:02:52,750
unikālagarantēts unikāls ceļvedis,
izmantojot šo datu struktūru. 

66
00:02:52,750 --> 00:02:56,210
Un mēs pēc mirkļa apskatīsim šo
vizuālo attēlu.

67
00:02:56,210 --> 00:02:58,387
Mēs to darīsim, mēģinot izveidot
jaunu datu struktūru, kartējot tālāk 

68
00:02:58,387 --> 00:03:00,564
norādītos atslēgu vērtību pārus. 

69
00:03:00,564 --> 00:03:03,480
Šajā gadījumā mēs neizmantosim kaut
ko tik vienkāršu kā Būla vērtību.

70
00:03:03,480 --> 00:03:06,200
Mēs faktiski uzglabāsim virkni.

71
00:03:06,200 --> 00:03:08,690
Un šī virkne būs universitātes
nosaukums.

72
00:03:08,690 --> 00:03:12,140
 Un galvenaisatslēga būs gads, kad
šī universitāte tika dibināta.

73
00:03:12,140 --> 00:03:15,380
Visi universitāšu gadi būs četri
cipari.

74
00:03:15,380 --> 00:03:17,610
Un tāpēc mēs izmantosim šos četrus
ciparus, lai pārvietotos pa šo 

75
00:03:17,610 --> 00:03:19,840
datu struktūru. 

76
00:03:19,840 --> 00:03:22,270
Un mēs atkal redzēsim, kā mēs to
paveiksim tikai pēc sekundes.

77
00:03:22,270 --> 00:03:26,260
Ceļa beigās mēs redzēsim
universitātes nosaukumu, kas atbilst šai 

78
00:03:26,260 --> 00:03:30,250
atslēgai, šie četri ciparišiem
četriem cipariem. 

79
00:03:30,250 --> 00:03:32,320
IzmēģinājumaDigitālā koka
pamatideja ir tāda, ka mums ir centrālais 

80
00:03:32,320 --> 00:03:34,390
maršruts. 

81
00:03:34,390 --> 00:03:35,640
Tāpēc domādomājiet par to kā par
koku.

82
00:03:35,640 --> 00:03:39,211
Un tas pēc pareizrakstības un
koncepcijas ir līdzīgs kokam.

83
00:03:39,211 --> 00:03:43,020
Parasti, kad mēs domājam par kokiem
reālajā pasaulē, tiem ir sakne, 

84
00:03:43,020 --> 00:03:46,830
kas atrodas zemē, un tie aug uz
augšu, un tiem ir zari un lapas. 

85
00:03:46,830 --> 00:03:49,292
Un būtībā triedigitālā koka ideja
ir tieši tāda pati, izņemot to, ka 

86
00:03:49,292 --> 00:03:51,755
sakne ir noenkurota kaut kur
debesīs. 

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

88
00:03:53,130 --> 00:03:55,750
 Tātad tas ir līdzīgi kā paņemt
koku un vienkārši apgriezt to otrādi.

89
00:03:55,750 --> 00:03:56,880
Bet joprojām ir filiāleszari.

90
00:03:56,880 --> 00:04:02,220
Un tie būtu mūsu ceļi, tie būs mūsu
savienojumi no saknēm līdz lapām.

91
00:04:02,220 --> 00:04:05,355
Šajā gadījumā tie ceļi, tie atzari
ir apzīmēti ar cipariem, kas mums 

92
00:04:05,355 --> 00:04:08,490
norāda, uz kuru pusi jāiet no
vietas, kur atrodamies. 

93
00:04:08,490 --> 00:04:10,695
Ja mēs redzam 0, mēs ejam lejup pa
šo zaru, ja mēs redzam 1, mēs ejam 

94
00:04:10,695 --> 00:04:12,900
uz leju pa šo zaru, un tā un tā
tālāk. 

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

96
00:04:14,060 --> 00:04:18,540
Tas nozīmē, ka katrā krustojuma
punktā un katrā mezglā vidū un katrā 

97
00:04:18,540 --> 00:04:23,020
atzarojumā ir 10 iespējamās vietas,
kur mēs varam doties. 

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

99
00:04:27,690 --> 00:04:31,075
Un šeit mēģinājumidigitālie koki
var nedaudz iebiedēt kādu, kam 

100
00:04:31,075 --> 00:04:34,460
iepriekš nav bijusi liela pieredze
datorzinātnēs. 

101
00:04:34,460 --> 00:04:35,960
Bet mēģinājumidigitālie koki ir
patiešām lieliski.

102
00:04:35,960 --> 00:04:38,718
Un, ja jums ir iespēja ar tiem
strādāt un vēlaties ar tiem 

103
00:04:38,718 --> 00:04:41,476
iedziļināties un eksperimentēt ar
tiem, tās patiešām ir diezgan 

104
00:04:41,476 --> 00:04:44,234
interesantas datu struktūras, ar
kurām strādāt. 

105
00:04:44,234 --> 00:04:47,797
Ja mēs vēlamies ievietot elementu
triedigitālajā kokā, viss, kas mums 

106
00:04:47,797 --> 00:04:51,360
jādara, ir izveidot pareizo ceļu no
saknes līdz lapai. 

107
00:04:51,360 --> 00:04:55,390
Lūk, kā varētu izskatīties katrs
solis ceļā.

108
00:04:55,390 --> 00:04:57,525
Mēs definēsim jaunu datu struktūru
jaunam mezglam, ko sauc par 

109
00:04:57,525 --> 00:04:59,660
triedigitālo koku. 

110
00:04:59,660 --> 00:05:02,560
 Un šīs datu struktūras iekšpusē ir
divas daļas.

111
00:05:02,560 --> 00:05:05,460
Mēs saglabāsim universitātes
nosaukumu.

112
00:05:05,460 --> 00:05:12,190
Un mēs saglabāsim norādes uz citiem
tāda paša veida mezgliem.

113
00:05:12,190 --> 00:05:15,378
Tātad, tas atkal ir tāds jēdziens
par,ka visur, kur atrodamies, ir 10 

114
00:05:15,378 --> 00:05:18,567
iespējamās vietāsvietas, kur varam
doties. 

115
00:05:18,567 --> 00:05:20,150
Ja mēs redzam 0, mēs ejam lejup pa
šo zaru.

116
00:05:20,150 --> 00:05:22,690
Ja mēs redzam 1, pa šo zaru un tā
tālāk, un tā tālāk, un tā tālāk.

117
00:05:22,690 --> 00:05:25,160
Ja sakām 9, mēs ejam lejā pa šo
zaru.

118
00:05:25,160 --> 00:05:26,690
Tātad katrā krustojuma punktā mēs
varam doties 10 iespējamās vietāsuz 

119
00:05:26,690 --> 00:05:28,220
10 iespējamām vietām. 

120
00:05:28,220 --> 00:05:31,980
Tātad katrā mezglā ir jāsatur 10
norādes uz citiem mezgliem, uz 10 

121
00:05:31,980 --> 00:05:35,740
citiem mezgliem. 

122
00:05:35,740 --> 00:05:39,810
 Un dati, ko mēs glabājam, ir tikai
universitātes nosaukums.

123
00:05:39,810 --> 00:05:41,060
Tāpēc izveidosim mēģinājumudigitālo
koku.

124
00:05:41,060 --> 00:05:44,860
Ievietosim pāris vienumus mūsu
izmēģinājumādigitālajā kokā.

125
00:05:44,860 --> 00:05:46,740
Tātad pašā augšā šis ir mūsu saknes
mezgls.

126
00:05:46,740 --> 00:05:48,240
Tas, iespējams, būs kaut kas tāds,
par ko jūs paziņosit visā 

127
00:05:48,240 --> 00:05:49,740
pasaulēglobāli. 

128
00:05:49,740 --> 00:05:51,595
Un jūs globāli vienmēr
uzturēsitsaglabāsiet rādītāju uz šo mezglu 

129
00:05:51,595 --> 00:05:53,450
visā pasaulē. 

130
00:05:53,450 --> 00:05:54,826
Jūs sacīsit, sakne ir vienāda, un
jūs iegūsit malloc sevi izmēģināt 

131
00:05:54,826 --> 00:05:56,203
mezglupiešķirsiet atmiņu digitālā
koka mezglā vai piesaistīsiet jaunu 

132
00:05:56,203 --> 00:05:57,580
mezglu. 

133
00:05:57,580 --> 00:05:59,850
Un jūs nekad vairs nepieskarsities
saknei.

134
00:05:59,850 --> 00:06:02,098
Katru reizi, kad vēlaties sākt
navigāciju, jūs iestatāt citu 

135
00:06:02,098 --> 00:06:04,346
rādītāju, kas ir vienāds ar
rootsakni, piemēram, trav, kas ir 

136
00:06:04,346 --> 00:06:06,594
piemērs, ko izmantoju daudzos savos
videoklipos šeit par 

137
00:06:06,594 --> 00:06:08,842
skursteņiemstekiem un rindām, saišu
saistītiem sarakstiem un tā 

138
00:06:08,842 --> 00:06:11,090
tālāk. 

139
00:06:11,090 --> 00:06:12,205
Jūs iestatāt citu rādītāju ar
nosaukumu trav pārvietošanaigrafa 

140
00:06:12,205 --> 00:06:13,320
apstaigāšanai - traversal. 

141
00:06:13,320 --> 00:06:15,890
Un jūs izmantojat trav, lai
pārvietotos pa datu struktūru.

142
00:06:15,890 --> 00:06:17,500
Tātad, redzēsimpaskatīsimies, kā
tas varētu izskatīties.

143
00:06:17,500 --> 00:06:19,880
Tātad, kā šobrīd izskatās mezgls?

144
00:06:19,880 --> 00:06:23,393
Tāpat kā norādīts mūsu datu
struktūras deklarācijā, mums ir virkne, 

145
00:06:23,393 --> 00:06:26,906
kas šajā gadījumā ir tukša. 

146
00:06:26,906 --> 00:06:27,780
Šeit nekā nav.

147
00:06:27,780 --> 00:06:29,550
 Un 10 rādītāju masīvs.

148
00:06:29,550 --> 00:06:31,790
Un šobrīd šajā mēģinājumādigitālajā
kokā mums ir tikai 1 mezgls.

149
00:06:31,790 --> 00:06:33,110
Nekā cita tajā nav.

150
00:06:33,110 --> 00:06:36,020
Tātad visi 10 no šiem
rādītājiemrādītāji norāda uz nulli.

151
00:06:36,020 --> 00:06:38,090
To norāda sarkanais.

152
00:06:38,090 --> 00:06:39,500
 Ieliksim virkni Harvard.

153
00:06:39,500 --> 00:06:41,720
Ievietosim šajā digitālajā kokā
Hārvardas Universitāti šajā 

154
00:06:41,720 --> 00:06:43,940
izmēģinājumā, kas tika dibināta
1636. gadā. 

155
00:06:43,940 --> 00:06:47,040
Mēs vēlamies izmantot atslēgu 1636,
lai pateiktu mums, kur mēs 

156
00:06:47,040 --> 00:06:50,140
glabāsim Hārvardu digitālajā kokā. 

157
00:06:50,140 --> 00:06:51,470
Tagad, kā mēs to varētu izdarīt?

158
00:06:51,470 --> 00:06:52,886
 Tas varētu izskatīties apmēram
šādi.

159
00:06:52,886 --> 00:06:54,160
Mēs sākam no saknes.

160
00:06:54,160 --> 00:06:56,920
Un mums ir šīs 10 vietas, kur varam
doties.

161
00:06:56,920 --> 00:06:59,900
Sakne ir tāda pati kā jebkurš cits
triedigitālā koka mezgls.

162
00:06:59,900 --> 00:07:02,850
No šejienes varam doties uz 10
vietām.

163
00:07:02,850 --> 00:07:07,215
 Kur mēs, iespējams, vēlamies
doties, ja atslēga ir 1636?

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

165
00:07:08,340 --> 00:07:08,450
Pareizi.

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

167
00:07:10,825 --> 00:07:12,412
Vai arī mēs varam izveidot atslēgu
no kreisās puses uz labo un sākt 

168
00:07:12,412 --> 00:07:14,000
ar 1. 

169
00:07:14,000 --> 00:07:16,055
Iespējams, ka cilvēkam ir daudz
intuitīvāk saprast, ka mēs vienkārši 

170
00:07:16,055 --> 00:07:18,110
ejam no kreisās uz labo pusi. 

171
00:07:18,110 --> 00:07:21,640
Un tāpēc, ja es vēlos iekļaut
Hārvardu šajā mēģinājumādigitālajā 

172
00:07:21,640 --> 00:07:25,170
kokā, es, iespējams, vēlos sākt,
sākot ar sakni, aplūkojot manas 10 

173
00:07:25,170 --> 00:07:28,700
iespējas un sakot, ka vēlos iet pa
1. ceļu. 

174
00:07:28,700 --> 00:07:29,700
Labi.

175
00:07:29,700 --> 00:07:31,810
 Pašlaik 1 ceļš ir nulle.

176
00:07:31,810 --> 00:07:35,220
Tātad, ja es vēlos turpināt šo
ceļu, lai ievietotu šo elementu 

177
00:07:35,220 --> 00:07:38,630
izmēģinājumādigitālajā kokā, man ir
jāatrod jauns mezgls, jāiegūst 

178
00:07:38,630 --> 00:07:42,040
1 punkts, un tad man ir labies varu
sākt. 

179
00:07:42,040 --> 00:07:46,155
Tātad es būtībā esmu vietā, kur es
stāvu pie koka vai digitālā koka 

180
00:07:46,155 --> 00:07:50,270
saknes vai zariem un ir 10 zari. 

181
00:07:50,270 --> 00:07:52,260
Bet katram zaram priekšā ir vārti.

182
00:07:52,260 --> 00:07:53,060
Pareizi.

183
00:07:53,060 --> 00:07:54,850
Jo nekā cita tur nav.

184
00:07:54,850 --> 00:07:56,522
Nav drošas pārejas.

185
00:07:56,522 --> 00:07:58,980
Tas nozīmē, ka nevienā no šīm
nozarēmšiem zariem nav nekā.

186
00:07:58,980 --> 00:08:02,532
Ja es gribu sākt kaut ko
būvētveidot, es gribu noņemt vārtus.

187
00:08:02,532 --> 00:08:04,490
Es vēlos noņemt vārtus
numuraskaitļa 1 priekšā.

188
00:08:04,490 --> 00:08:05,698
Un es gribu iet pa to.

189
00:08:05,698 --> 00:08:08,060
Un es vēlos uzceltizveidot citu
vietu, kur man doties.

190
00:08:08,060 --> 00:08:09,470
 Un to es šeit esmu darījis.

191
00:08:09,470 --> 00:08:11,430
Tātad 1 vairs nenorāda uz nulli.

192
00:08:11,430 --> 00:08:13,830
Es teicu, ka tagad šeit ir droši
doties.

193
00:08:13,830 --> 00:08:15,789
Es uzbūvējuizveidoju vēl vienu
mezglu.

194
00:08:15,789 --> 00:08:18,330
Un, kad es nonāku pie šī mezgla,
man ir jāpieņem cits lēmums.

195
00:08:18,330 --> 00:08:20,890
Kurp es no šejienes došos?

196
00:08:20,890 --> 00:08:22,700
 Nu, es jau esmu samazinājies
pargājis pa 1.

197
00:08:22,700 --> 00:08:24,470
Tāpēc tagad es droši vien vēlos
nokāptiet pa 6.

198
00:08:24,470 --> 00:08:24,970
Pareizi.

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

200
00:08:27,100 --> 00:08:30,060
Tātad tagad ejam uz leju ar 6.
numurupa skaitli 6.

201
00:08:30,060 --> 00:08:32,280
Tāpēc es atbrīvoju vārtus 6.
numuraskaitļa 6 priekšā.

202
00:08:32,280 --> 00:08:33,250
Un es eju tur lejāpa to.

203
00:08:33,250 --> 00:08:34,580
Un es izveidoju vēl vienu mezglu.

204
00:08:34,580 --> 00:08:37,630
Un esmu sasniedzis citu
krustpunktu.

205
00:08:37,630 --> 00:08:40,289
 Atkal, man ir 10 izvēles iespējas,
kur es varu doties.

206
00:08:40,289 --> 00:08:42,799
Esmu pārcēlies no 1 uz 6.

207
00:08:42,799 --> 00:08:44,215
Tāpēc tagad es droši vien vēlos
doties uz 3.

208
00:08:44,215 --> 00:08:45,381
3, es nekur nevaru iet.

209
00:08:45,381 --> 00:08:48,980
Tāpēc man ir jāatbrīvo ceļš un
jāveido sev jauna telpa.

210
00:08:48,980 --> 00:08:50,870
Un tad no 3, kur es gribu doties?

211
00:08:50,870 --> 00:08:52,450
Es gribu nolaistiesdoties pa 6.

212
00:08:52,450 --> 00:08:54,770
 Un atkal man bija jāatbrīvo ceļš,
kā to izdarītlai to izdarītu.

213
00:08:54,770 --> 00:08:56,974
Tāpēc tagad esmu izmantojis savu
atslēgu, lai ievietotu 

214
00:08:56,974 --> 00:08:59,179
izveidesizveidotu mezglus un sāktu
veidot šo mēģinājumudigitālo koku. 

215
00:08:59,179 --> 00:09:00,220
Es sāku no saknes.

216
00:09:00,220 --> 00:09:03,666
Esmu samazinājies pardevies pa
1636.

217
00:09:03,666 --> 00:09:05,540
Un tagad es esmu apakšā, tajā
mezglā.

218
00:09:05,540 --> 00:09:06,610
Un jūs, iespējams, varēsit to
redzēt savā ekrānā.

219
00:09:06,610 --> 00:09:07,735
 Tas ir iezīmēts dzeltenā krāsā.

220
00:09:07,735 --> 00:09:10,020
Tieši tur es šobrīd esmu.

221
00:09:10,020 --> 00:09:11,300
Mana atslēga ir gatava.

222
00:09:11,300 --> 00:09:13,030
Esmu izsmēlis visas savas atslēgas
pozīcijas.

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

224
00:09:15,040 --> 00:09:17,720
Tāpēc šobrīd viss, kas man patiešām
jādara, ir pateikt: Labi.

225
00:09:17,720 --> 00:09:20,035
Tas ir līdzīgi kā skatīties uz
zemi, ja jūs iztēlojaties sevi kā šāda 

226
00:09:20,035 --> 00:09:22,350
veida ceļu ar dažādiem
savienojumiem. 

227
00:09:22,350 --> 00:09:24,075
Tāda veidakā skatīšanās uz leju un
Hārvardas smidzināšanas 

228
00:09:24,075 --> 00:09:25,800
krāsošanaiekrāsošana ar aerosolu uz
zemes. 

229
00:09:25,800 --> 00:09:26,800
Tāds ir šīs lietas nosaukums.

230
00:09:26,800 --> 00:09:28,300
Uzziniet, kas atrodas šajā vietā.

231
00:09:28,300 --> 00:09:30,540
Ja mēs sākam no saknes un ejam uz
leju arpa 1 un tad 6, un tad 3, un 

232
00:09:30,540 --> 00:09:32,780
tad 6, kur mēs atrodamies? 

233
00:09:32,780 --> 00:09:35,653
Ja mēs skatāmies uz leju un redzam
Hārvardu, tad mēs zinām, ka 

234
00:09:35,653 --> 00:09:38,526
Hārvarda tika dibināta 1636. gadā,
pamatojoties uz veidu, kā mēs 

235
00:09:38,526 --> 00:09:41,400
ieviešam šo datu struktūru. 

236
00:09:41,400 --> 00:09:43,177
Tātad, cerams, tas bija vienkārši.

237
00:09:43,177 --> 00:09:44,760
Mēs veiksim vēl divus ievietojumus.

238
00:09:44,760 --> 00:09:47,410
Un cerams, ka tas palīdzēs redzēt,
ka tas tiek darīts vēl divas 

239
00:09:47,410 --> 00:09:50,060
reizes. 

240
00:09:50,060 --> 00:09:52,210
 Tagad ievietosim citu
universitāti.

241
00:09:52,210 --> 00:09:54,630
Ievietosim Jēlu - Yale - šajā
mēģinājumādigitālajā kokā.

242
00:09:54,630 --> 00:09:57,037
Jēla tika dibināta 1701. gadā.

243
00:09:57,037 --> 00:09:58,870
Tātad, kā vienmēr, mēs sāksim no
saknes.

244
00:09:58,870 --> 00:09:59,890
Un mēs uzstādījām šķērsošanasgrafa
apstaigāšanas rādītāju.

245
00:09:59,890 --> 00:10:01,624
Mēs to izmantosim, lai pārvietotos
cauri.

246
00:10:01,624 --> 00:10:03,790
Pirmā lieta, ko mēs vēlamies darīt,
ir iet pa 1 ceļu.

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

248
00:10:05,830 --> 00:10:08,420
Tomēr, par laimi, šoreiz mums nekas
nav jādara.

249
00:10:08,420 --> 00:10:09,919
1. ceļš jau ir atbrīvots.

250
00:10:09,919 --> 00:10:13,520
Es to notīrīju iepriekš, kad
ievietoju Hārvardu 1636. gadā.

251
00:10:13,520 --> 00:10:15,805
Tāpēc es varu droši pārvietoties uz
lejupa 1 un vienkārši doties uz 

252
00:10:15,805 --> 00:10:18,090
turieni. 

253
00:10:18,090 --> 00:10:20,150
Ja var pārvietoties uz leju pa 1.

254
00:10:20,150 --> 00:10:22,930
 Tomēr tagad es gribu doties uz 7.

255
00:10:22,930 --> 00:10:24,280
Es atbrīvoju ceļu pulkstenpie 6.

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

257
00:10:27,050 --> 00:10:29,220
Bet man jāturpina pa 7 ceļu.

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

259
00:10:30,580 --> 00:10:34,660
Nu, tāpat kā iepriekš, man
vienkārši jāattīra vārti, jānokļūstjāiziet 

260
00:10:34,660 --> 00:10:38,740
no ceļa un jāuzbūvējāizveido jauns
mezgls no 7 ceļa. 

261
00:10:38,740 --> 00:10:40,250
Gluži kā šis.

262
00:10:40,250 --> 00:10:42,930
 Tāpēc tagad esmu pārcēlisvirzījies
pa 1 un pēc tam 7.

263
00:10:42,930 --> 00:10:45,550
Un tagad ievērojiet, es esmu šajā
jaunajā apakšnozarēapakšzarā.

264
00:10:45,550 --> 00:10:46,050
Pareizi.

265
00:10:46,050 --> 00:10:49,260
Viss pārējais, sākot no 16, man
vienalganerūp.

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

267
00:10:50,720 --> 00:10:51,750
Es daru 17 lietas.

268
00:10:51,750 --> 00:10:58,380
 Tāpēc tagad no pulksten 17 man
šeit ir jāveido jaunas takas.

269
00:10:58,380 --> 00:11:00,462
Nākamais cipars mana atslēgamanā
atslēgā ir 0.

270
00:11:00,462 --> 00:11:01,670
Skaidrs, ka es nekur nevaru tikt.

271
00:11:01,670 --> 00:11:02,628
Es tikko izveidoju šo mezglu.

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

273
00:11:04,550 --> 00:11:06,370
Tāpēc man pašam tas ir
jāizgatavojāizveido.

274
00:11:06,370 --> 00:11:09,360
 Tāpēc es piesaistu jaunu mezglu un
tur ir 0 punkts.

275
00:11:09,360 --> 00:11:11,065
Un tad vēl vienu reizi es piesaistu
jaunu mezglu un tur ir viens 

276
00:11:11,065 --> 00:11:12,770
punkts. 

277
00:11:12,770 --> 00:11:15,870
Es atkal esmu izsmēlis savu
atslēgu, 1701.

278
00:11:15,870 --> 00:11:18,472
Tāpēc es skatos uz leju un
izsmidzinu ar krāsu Yale.

279
00:11:18,472 --> 00:11:19,680
Tas ir šī mezgla nosaukums.

280
00:11:19,680 --> 00:11:22,140
Un tāpēc tagad, ja man kādreiz
vajadzēs redzēt, vai Jēla ir šajā 

281
00:11:22,140 --> 00:11:24,600
mēģinājumādigitālajā kokā, es sāku
no saknes, nokāpjueju pa 1701 un 

282
00:11:24,600 --> 00:11:27,060
skatos uz leju. 

283
00:11:27,060 --> 00:11:29,630
Un, ja es redzu, ka Jēla aerosolsar
aerosolu ir krāsotsiekrāsota uz 

284
00:11:29,630 --> 00:11:32,200
zemes, tad es zinu, ka Jēla pastāv
šajā mēģinājumādigitālajā kokā. 

285
00:11:32,200 --> 00:11:32,950
DarīsimIzdarīsim vēl vienu.

286
00:11:32,950 --> 00:11:34,690
Ievietosim šajā digitālajā kokā
Dartmutu - Dartmouth - šajā trie, kas 

287
00:11:34,690 --> 00:11:36,430
tika dibināta 1769. gadā. 

288
00:11:36,430 --> 00:11:37,750
 Sāciet vēlreiz no saknes.

289
00:11:37,750 --> 00:11:39,445
Mans atslēgas pirmais cipars ir 1.

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

291
00:11:40,820 --> 00:11:42,400
Tas jau pastāv.

292
00:11:42,400 --> 00:11:44,040
Nākamais manas atslēgas cipars ir
7.

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

294
00:11:45,890 --> 00:11:47,540
TāTas arī pastāv.

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

296
00:11:49,000 --> 00:11:52,530
No šejienes, kur es pašlaik esmu
dzeltenā, tajā vidējā mezglā 6 

297
00:11:52,530 --> 00:11:56,060
pašlaik ir bloķēts. 

298
00:11:56,060 --> 00:11:58,830
Ja es gribu iet pa šo ceļu, man tas
ir jābūvējāizveido pašam.

299
00:11:58,830 --> 00:12:02,250
Tāpēc es izvēlēšos jaunu mezglu un
tur iegūšu 6 punktus.

300
00:12:02,250 --> 00:12:04,250
Un tad atkal es te svilinuieminu
jaunas takas.

301
00:12:04,250 --> 00:12:08,917
Tāpēc es piesaistu jaunu mezglu,
lai no šī mezgla — ceļa numurs 9 — 

302
00:12:08,917 --> 00:12:13,584
un tad tagad, ja es ceļoju 1769, es
skatos uz leju. 

303
00:12:13,584 --> 00:12:15,500
Pašlaik tur nekas nav
krāsotsiekrāsots ar aerosolu.

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

305
00:12:16,930 --> 00:12:20,710
Un es esmu ievietojis Dartmouth
triedigitālajā kokā.

306
00:12:20,710 --> 00:12:23,450
 Tā ir lietu ievietošana
izmēģinājumādigitālajā kokā.

307
00:12:23,450 --> 00:12:25,384
Tagad mēs vēlamies meklēt lietas.

308
00:12:25,384 --> 00:12:27,050
Kā mēs meklējam lietas, kas atrodas
izmēģinājumādigitālajā kokā?

309
00:12:27,050 --> 00:12:29,170
Nu, tā ir gandrīz tāda pati ideja.

310
00:12:29,170 --> 00:12:31,836
Tagad mēs vienkārši izmantojam
atslēgas ciparus, lai redzētu, vai mēs 

311
00:12:31,836 --> 00:12:34,503
varam virzīties no saknes uz vietu,
kur vēlamies, lai mēģinātu 

312
00:12:34,503 --> 00:12:37,170
nokļūtdoties digitālajā kokā. 

313
00:12:37,170 --> 00:12:40,835
Ja kādā brīdī nonākam strupceļā,
mēs zinām, ka šis elements nevar 

314
00:12:40,835 --> 00:12:44,500
pastāvēt, pretējā gadījumā šis ceļš
jau būtu notīrīts. 

315
00:12:44,500 --> 00:12:46,485
Ja tiekam līdz galam, mums atliek
tikai skatīties uz leju un 

316
00:12:46,485 --> 00:12:48,471
noskaidrot, vai tas ir tas
elements, ko mēs meklējam. 

317
00:12:48,471 --> 00:12:49,335
Ja tā, tad veiksme.

318
00:12:49,335 --> 00:12:52,610
Ja tā nav, izgāziesneveiksme.

319
00:12:52,610 --> 00:12:54,940
 Tāpēc šajā mēģinājumā meklēsim
Hārvardu.

320
00:12:54,940 --> 00:12:56,020
Mēs sākam no saknes.

321
00:12:56,020 --> 00:12:57,705
Un atkal mēs izveidosim
šķērsošanasgrafa apstaigāšanas rādītāju, kas 

322
00:12:57,705 --> 00:12:59,390
veiks mūsu kustības mūsu vietā. 

323
00:12:59,390 --> 00:13:01,390
No saknes mēs zinām, ka pirmā
vieta, kur mums jāiet, ir 1, vai mēs 

324
00:13:01,390 --> 00:13:03,390
varam to izdarīt? 

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

326
00:13:03,982 --> 00:13:04,690
JaTā droši pastāv.

327
00:13:04,690 --> 00:13:06,660
Mēs varam doties tur.

328
00:13:06,660 --> 00:13:08,440
 Tagad nākamā vieta, kur mums
jāiet, ir 6.

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

330
00:13:10,557 --> 00:13:11,140
Jā, tā darair.

331
00:13:11,140 --> 00:13:12,690
Mēs varam iet pa 6 taku.

332
00:13:12,690 --> 00:13:13,905
Un mēs nonākam šeit.

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

334
00:13:16,130 --> 00:13:18,450
Nu, kā izrādās, jā, arī tādatas
pastāv.

335
00:13:18,450 --> 00:13:20,790
Un vai mēs no šejienes varam nokļūt
6 takā?

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

337
00:13:21,982 --> 00:13:24,002
 Mēs vēl neesam līdz galam
atbildējuši uz šo jautājumu.

338
00:13:24,002 --> 00:13:26,888
Joprojām ir vēl viens solis, un
tagad mums ir jāpaskatās uz leju un 

339
00:13:26,888 --> 00:13:29,774
jānoskaidro, vai tas tiešām ir — ja
mēs meklējam Hārvardu, vai tas ir 

340
00:13:29,774 --> 00:13:32,660
tas, ko mēs atrodam pēc atslēgas
izsmelšanas? 

341
00:13:32,660 --> 00:13:35,430
Piemērā, ko mēs izmantojam šeit,
gadi vienmēr ir četri cipari.

342
00:13:35,430 --> 00:13:40,280
Bet jūs varētu izmantot piemēru,
kur glabājat vārdu vārdnīcu.

343
00:13:40,280 --> 00:13:42,170
Tā vietā, lai 10 rādītāji norādītu
manu atrašanās vietu, jums varētu 

344
00:13:42,170 --> 00:13:44,060
būt 26 norādes. 

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

346
00:13:46,040 --> 00:13:48,195
Un ir daži vārdi, piemēram,
sikspārnisbat, kas ir, piemēram, 

347
00:13:48,195 --> 00:13:50,350
partijasbatch apakškopa. 

348
00:13:50,350 --> 00:13:52,805
Un pat tad, ja nonākat līdz
atslēgas galam un skatāties uz leju, 

349
00:13:52,805 --> 00:13:55,260
iespējams, neredzēsit to, ko
meklējat. 

350
00:13:55,260 --> 00:13:57,986
Tāpēc jums vienmēr ir jāšķērso viss
ceļš un tad, ja esat veiksmīgi 

351
00:13:57,986 --> 00:14:00,713
spējis šķērsot visu ceļu,
skatieties uz leju un veiciet vienu pēdējo 

352
00:14:00,713 --> 00:14:03,440
apstiprinājumu. 

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

354
00:14:05,120 --> 00:14:06,430
Nu, es skatos uz leju pēc tam, kad
sākšusāku no augšas un dodos uz 

355
00:14:06,430 --> 00:14:07,740
1636. 

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

357
00:14:08,240 --> 00:14:09,400
Es redzu Hārvardu.

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

359
00:14:11,689 --> 00:14:13,980
Ko darīt, ja tas, ko es meklēju,
tomēr nav iekļauts digitālajā kokā.?

360
00:14:13,980 --> 00:14:15,590
Ko darīt, ja es meklējuJa nu es
meklētu Prinstonu - Princeton -, kas 

361
00:14:15,590 --> 00:14:17,200
tika dibināta 1746. gadā. 

362
00:14:17,200 --> 00:14:19,037
Un tā 1746 kļūst par manu atslēgu,
lai pārvietotos pa 

363
00:14:19,037 --> 00:14:20,875
mēģinājumudigitālo koku. 

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

365
00:14:22,040 --> 00:14:24,760
Un pirmā vieta, kur es vēlos
doties, iet pa 1 ceļu.

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

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

368
00:14:26,490 --> 00:14:28,730
 Vai no turienes es varu iet pa 7
taku?

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

370
00:14:29,230 --> 00:14:30,750
TasTā arī pastāv.

371
00:14:30,750 --> 00:14:32,460
Bet vai es varu no šejienes iet pa
4 ceļu?

372
00:14:32,460 --> 00:14:34,787
Tas ir tāpat kā uzdot jautājumu,
vai es varu doties lejup pa mazo 

373
00:14:34,787 --> 00:14:37,114
kvadrātu, ko esmu iezīmējis
dzeltenā krāsā? 

374
00:14:37,114 --> 00:14:38,030
Tur nekā nav.

375
00:14:38,030 --> 00:14:38,610
Pareizi.

376
00:14:38,610 --> 00:14:41,310
 Nav ceļa uz priekšu pa 4 ceļu.

377
00:14:41,310 --> 00:14:43,895
Ja Prinstona būtu šajā
mēģinājumādigitālajā kokā, šiešis 4 mums jau 

378
00:14:43,895 --> 00:14:46,480
būtu dzēstinotīrīts. 

379
00:14:46,480 --> 00:14:49,130
Un tāpēc šajā brīdī mēs esam
nonākuši strupceļā.

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

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

382
00:14:53,440 --> 00:14:56,760
Prinstona šajā mēģinājumādigitālajā
kokā nepastāv.

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

384
00:14:58,860 --> 00:14:59,360
Pareizi.

385
00:14:59,360 --> 00:15:01,000
Šeit daudz kas notiek.

386
00:15:01,000 --> 00:15:02,500
Visur ir norādes.

387
00:15:02,500 --> 00:15:04,755
Un, kā jūs varat redzēt tikai no
diagrammas, ir daudz mezglu, kas it 

388
00:15:04,755 --> 00:15:07,010
kā lido apkārt. 

389
00:15:07,010 --> 00:15:11,005
Taču ievērojiet, ka katru reizi,
kad vēlējāmies pārbaudīt, vai kaut 

390
00:15:11,005 --> 00:15:15,000
kas ir triedigitālajā kokā, mums
bija jāveic tikai 4 kustības. 

391
00:15:15,000 --> 00:15:16,813
Ikreiz, kad vēlējāmies kaut ko
ievietot mēģinājumādigitālajā kokā, 

392
00:15:16,813 --> 00:15:18,626
mums ir jāveic 4 gājieni,
iespējams, pa ceļam iznīcinot dažas 

393
00:15:18,626 --> 00:15:20,440
lietaspiešķirot atmiņu dažām lietām
vai izveidojot dažas lietas.. 

394
00:15:20,440 --> 00:15:23,190
Bet, kā mēs redzējām, ievietojot
Dartmutu triejādigitālajā kokā, 

395
00:15:23,190 --> 00:15:25,940
dažkārt daļa ceļa mums jau var būt
atbrīvota. 

396
00:15:25,940 --> 00:15:29,208
Tā kā mūsu mēģinājumsdigitālais
koks kļūst arvien lielāks, mums katru 

397
00:15:29,208 --> 00:15:32,477
reizi ir jādara mazāk darba, lai
ievietotu jaunas lietas, jo mēs jau 

398
00:15:32,477 --> 00:15:35,746
esam izveidojuši daudz starpzaru. 

399
00:15:35,746 --> 00:15:38,370
Ja mums kādreiz ir jāskatās tikai
uz 4 lietām, 4 ir tikai konstante.

400
00:15:38,370 --> 00:15:41,435
Mēs patiešām tuvojastuvojamies
pastāvīgai laika ievietošanai un 

401
00:15:41,435 --> 00:15:44,501
pastāvīgai laika meklēšanai. 

402
00:15:44,501 --> 00:15:46,765
Protams, kompromiss ir tāds, ka šis
mēģinājumsdigitālais koks, kā jūs 

403
00:15:46,765 --> 00:15:49,030
droši vien varat pateikt, ir
milzīgs. 

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

405
00:15:51,040 --> 00:15:52,090
 Bet tas ir kompromiss.

406
00:15:52,090 --> 00:15:55,860
Ja mēs vēlamies patiešām ātru
ievietošanu, ļoti ātru dzēšanu un 

407
00:15:55,860 --> 00:15:59,630
patiešām ātru meklēšanu, mums ir
jāpārvietojasvajadzīgi daudz datu. 

408
00:15:59,630 --> 00:16:01,960
Mums ir jāatvēl daudz vietas un
atmiņas, lai šī datu struktūra 

409
00:16:01,960 --> 00:16:04,290
pastāvētu. 

410
00:16:04,290 --> 00:16:05,415
 Un tas ir kompromiss.

411
00:16:05,415 --> 00:16:07,310
Bet šķiet, ka mēs to varētu
atrastbūt atraduši.

412
00:16:07,310 --> 00:16:09,787
Mēs, iespējams, atradām šo datu
struktūru svēto grālu ar ātru 

413
00:16:09,787 --> 00:16:12,264
ievietošanu, dzēšanu un
uzmeklēšanu. 

414
00:16:12,264 --> 00:16:15,577
Un varbūt šī būs piemērota datu
struktūra, ko izmantot jebkurai 

415
00:16:15,577 --> 00:16:18,890
informācijai, ko mēs cenšamies
saglabāt. 

416
00:16:18,890 --> 00:16:21,860
Es esmu Dags Loids, šis ir cs50.