1
00:00:00,000 --> 00:00:02,994
>> [Muusika mängib]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Nii et me oleme sammkäik lähemale
ja lähemale, et Püha Graal andmeid

4
00:00:08,550 --> 00:00:13,050
struktuurid, mis meil on võimalik lisada
arvesse, kustutada ja otsida

5
00:00:13,050 --> 00:00:15,440
konstantse ajaga.

6
00:00:15,440 --> 00:00:16,270
Õigus.

7
00:00:16,270 --> 00:00:17,280
See on omamoodi eesmärk.

8
00:00:17,280 --> 00:00:19,720
Me tahame, et oleks võimalik teha
asju väga kiiresti.

9
00:00:19,720 --> 00:00:22,580
>> Kas me leidsime siin kui
me räägime üritab?

10
00:00:22,580 --> 00:00:23,670
Noh, võtame pilk.

11
00:00:23,670 --> 00:00:25,628
Nii et me oleme näinud mitmeid
erinevad andmestruktuurid

12
00:00:25,628 --> 00:00:28,680
et hakkama kaardistamine
nn võtme-väärtuse paarid,

13
00:00:28,680 --> 00:00:32,080
kaardistada mõned tükk andmed
mõne muu tükk andmed

14
00:00:32,080 --> 00:00:36,020
nii et me teame, kust leida
teabe struktuuri.

15
00:00:36,020 --> 00:00:40,060
>> Nii massiiv, näiteks
Oluline on elemendi indeks või massiivi

16
00:00:40,060 --> 00:00:42,600
asukoha 0 või massiivi 1 ja nii edasi.

17
00:00:42,600 --> 00:00:46,140
Ja väärtus on andmed
mis on olemas selles kohas.

18
00:00:46,140 --> 00:00:48,550
Mis siis salvestatakse massiivi 0?

19
00:00:48,550 --> 00:00:54,290
Mis on talletatud rida 1 versus lihtsalt
0 ja 1, mis oleks võtmed.

20
00:00:54,290 --> 00:00:56,360
>> Mis hash tabelis on
omamoodi sama mõte.

21
00:00:56,360 --> 00:01:00,690
Mis hash tabelit, meil on see hash
funktsiooni, mis genereerib räsikoodid.

22
00:01:00,690 --> 00:01:03,670
Nii et võti on räsikoodiga andmeid.

23
00:01:03,670 --> 00:01:06,530
Ja väärtus, eriti
me rääkisime aheldamine

24
00:01:06,530 --> 00:01:10,590
video kohta hash tabeleid,
on see, et seotud andmete loetelu

25
00:01:10,590 --> 00:01:12,550
et hashes sellele räsikood.

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

27
00:01:14,050 --> 00:01:16,050
Aga teine ​​lähenemine
Selle meetodi kuigi?

28
00:01:16,050 --> 00:01:21,000
Aga meetod, kus
võti on garanteeritud olema unikaalne,

29
00:01:21,000 --> 00:01:25,410
Erinevalt hash tabelit, kus saime
lõpuks kaks tükki andmeid

30
00:01:25,410 --> 00:01:27,200
võttes samal räsikood.

31
00:01:27,200 --> 00:01:30,020
Ja siis me peame tegelema
et kas sondeerimine või enama

32
00:01:30,020 --> 00:01:33,340
soovitavalt aheldamine määrata see probleem.

33
00:01:33,340 --> 00:01:37,520
>> Nüüd saame garanteerida
et meie peamine on ainulaadne.

34
00:01:37,520 --> 00:01:39,690
Ja mis siis, kui meie väärtus oli
lihtsalt midagi nii lihtne

35
00:01:39,690 --> 00:01:44,080
kui õige ja vale, mis ütleb meile, kas
või mitte, et osa teabest

36
00:01:44,080 --> 00:01:45,610
olemas struktuur?

37
00:01:45,610 --> 00:01:48,180
Tõeväärtus võib olla sama lihtne kui natuke.

38
00:01:48,180 --> 00:01:52,660
Reaalselt tähendab see tõenäoliselt
byte tõenäolisem kui natuke.

39
00:01:52,660 --> 00:01:55,410
Aga see on palju väiksem kui
ladustamiseks võibolla 50-märgijada,

40
00:01:55,410 --> 00:01:57,360
näiteks.

41
00:01:57,360 --> 00:02:02,210
>> Nii katseid sarnaseid räsitabeli,
mis ühendavad massiivid ja seotud nimekirja,

42
00:02:02,210 --> 00:02:05,790
üritab ühendada massiivid,
struktuuride ja suunanäitajaks

43
00:02:05,790 --> 00:02:08,509
koos andmete säilitamine
huvitav, kuidas see on

44
00:02:08,509 --> 00:02:11,550
päris erinev
midagi, mida me oleme näinud siiani.

45
00:02:11,550 --> 00:02:16,750
Nüüd me kasutame andmeid tegevuskava
liikuda andmete struktuuri.

46
00:02:16,750 --> 00:02:18,710
Ja kui me suudame järgida
tegevuskava, kui me suudame

47
00:02:18,710 --> 00:02:22,390
järgige andmeid
Algusest lõpuni, siis me

48
00:02:22,390 --> 00:02:24,945
tea, kas need andmed
olemas Prefiksipuu.

49
00:02:24,945 --> 00:02:28,310
>> Ja kui me ei saa järgida kaart
alates tähendab lõppu üldse,

50
00:02:28,310 --> 00:02:30,600
andmed ei ole olemas.

51
00:02:30,600 --> 00:02:32,890
Jällegi, võtmed siin on
garanteeritud olema unikaalne.

52
00:02:32,890 --> 00:02:36,020
Ja nii erinevalt hash tabelit, me ei saa iial
peavad tegelema kokkupõrkeid siin.

53
00:02:36,020 --> 00:02:39,090
Ja no kaks tükki andmeid
on täpselt sama tegevuskava

54
00:02:39,090 --> 00:02:40,530
kui see on andmed identsed.

55
00:02:40,530 --> 00:02:44,580
>> Kui me lisada John, siis
otsime John.

56
00:02:44,580 --> 00:02:47,430
See on kaks ühesugust tükki
andmed, õigus, otsime läbi.

57
00:02:47,430 --> 00:02:49,880
Aga muidu kõik
kaks tükki andmed on

58
00:02:49,880 --> 00:02:52,750
tagatud on unikaalne tegevuskavad
selle kaudu andmete struktuuri.

59
00:02:52,750 --> 00:02:56,210
Ja me ei kavatse võtta pilk
visuaalne seda vaid hetkeks.

60
00:02:56,210 --> 00:02:58,810
>> Me teeme seda, üritades
luua uusi andmeid struktuuri,

61
00:02:58,810 --> 00:03:00,564
kaardistada järgmiste põhiväärtus paari.

62
00:03:00,564 --> 00:03:03,480
Sel juhul me ei kavatse kasutada
midagi nii lihtne kui Boole'i.

63
00:03:03,480 --> 00:03:06,200
Me tegelikult salvestab string.

64
00:03:06,200 --> 00:03:08,690
Ja see string läheb
olla nime ülikoolis.

65
00:03:08,690 --> 00:03:12,140
>> Ja võti saab olema aasta
kui see ülikool asutati.

66
00:03:12,140 --> 00:03:15,380
Kõik aastat ülikoolide
hakkavad olema neljakohaline.

67
00:03:15,380 --> 00:03:19,840
Ja nii me kasutame neid neli numbrit
liikuda andmete struktuuri.

68
00:03:19,840 --> 00:03:22,270
Ja me näeme jälle, kuidas
me teha vaid teise.

69
00:03:22,270 --> 00:03:25,110
>> Lõpus tee,
me näeme nime

70
00:03:25,110 --> 00:03:30,250
ülikooli, mis vastab
sellele võtmele, need neli numbrit.

71
00:03:30,250 --> 00:03:34,390
Põhiidee Prefiksipuu
on meil keskne liinil.

72
00:03:34,390 --> 00:03:35,640
Nii mõelda nagu puu.

73
00:03:35,640 --> 00:03:39,211
Ja see on sarnane kirjapilt
ja mõiste puu.

74
00:03:39,211 --> 00:03:41,460
Üldiselt, kui me mõtleme
puud reaalses maailmas,

75
00:03:41,460 --> 00:03:44,090
nad on juur, mis on ka
maa ja nad kasvavad üles

76
00:03:44,090 --> 00:03:46,830
ja neil on filiaalid
ja neil on lehed.

77
00:03:46,830 --> 00:03:49,450
Ja põhimõtteliselt idee
Prefiksipuu on täpselt sama,

78
00:03:49,450 --> 00:03:51,755
välja arvatud root on ankurdatud
kuskil taevas.

79
00:03:51,755 --> 00:03:53,130
Ja lehed on allosas.

80
00:03:53,130 --> 00:03:55,750
>> Nii et see on selline nagu võttes puu
ja lihtsalt flipping tagurpidi.

81
00:03:55,750 --> 00:03:56,880
Kuid on veel oksad.

82
00:03:56,880 --> 00:03:59,463
Ja need oleks meie teed,
need on meie ühendused

83
00:03:59,463 --> 00:04:02,220
juurest lehed.

84
00:04:02,220 --> 00:04:04,200
Sel juhul on need
teed, need oksad

85
00:04:04,200 --> 00:04:08,490
on märgistatud numbrit, mis meile
mis suunas minna sealt, kus me oleme.

86
00:04:08,490 --> 00:04:11,800
>> Kui me näeme 0, me läheme selle filiaal,
kui näeme 1, me läheme selle filiaal,

87
00:04:11,800 --> 00:04:12,900
ja nii ja nii edasi.

88
00:04:12,900 --> 00:04:14,060
Noh, mida see tähendab?

89
00:04:14,060 --> 00:04:16,519
Noh, see tähendab, et
igal ristmikul punkti

90
00:04:16,519 --> 00:04:19,260
ja iga sõlme
keskel, igasse filiaali,

91
00:04:19,260 --> 00:04:23,020
seal on 10 võimalik
kohti, et me ei lähe.

92
00:04:23,020 --> 00:04:27,690
Nii on 10 suunanäitajaks
igast asukohast.

93
00:04:27,690 --> 00:04:30,610
>> Ja see on koht, kus üritab saavad
natuke hirmutada keegi

94
00:04:30,610 --> 00:04:34,460
kes ei ole palju
kogemus infotehnoloogia enne.

95
00:04:34,460 --> 00:04:35,960
Vaid püüab tõesti päris vinge.

96
00:04:35,960 --> 00:04:37,793
Ja kui teil on
võimalus töötada koos nendega

97
00:04:37,793 --> 00:04:40,420
ja sa oled valmis kaevama sisse
ja katsetada neid,

98
00:04:40,420 --> 00:04:44,234
nad tõesti päris huvitav
andmestruktuuride töötada.

99
00:04:44,234 --> 00:04:46,900
Kui me tahame, et sisestada element
arvesse Prefiksipuu, kõik me peame tegema

100
00:04:46,900 --> 00:04:51,360
on ehitada õige tee
juurest lehed.

101
00:04:51,360 --> 00:04:55,390
Siin on, mida igal sammul
Muide tunduda.

102
00:04:55,390 --> 00:04:59,660
Me läheme määratleda uued andmed
struktuuri uue sõlme nimetatakse Prefiksipuu.

103
00:04:59,660 --> 00:05:02,560
>> Ja sees, et andmed
struktuuri on kaks tükki.

104
00:05:02,560 --> 00:05:05,460
Me läheme salvestada
nimi ülikooli.

105
00:05:05,460 --> 00:05:09,410
Ja me ei kavatse hoida
massiivi osuti

106
00:05:09,410 --> 00:05:12,190
teiste sõlmede sama tüüpi.

107
00:05:12,190 --> 00:05:14,780
Niisiis, jälle see, et sorteerida
on mõiste kõikjal

108
00:05:14,780 --> 00:05:18,567
oleme, meil on 10 võimalik
kohti saame minna.

109
00:05:18,567 --> 00:05:20,150
Kui me näeme 0, me läheme selle filiaal.

110
00:05:20,150 --> 00:05:22,690
Kui me näeme, 1, selle filiaali,
ja nii edasi ja nii edasi ja nii edasi.

111
00:05:22,690 --> 00:05:25,160
Kui me ütleme, 9, me läheme selle filiaal.

112
00:05:25,160 --> 00:05:28,220
Nii igal ristmikul punkti,
saame minna 10 võimalikud kohad.

113
00:05:28,220 --> 00:05:35,740
Nii et iga sõlm peab sisaldama 10 suunanäitajaks
teiste sõlmede, 10 muude sõlmede.

114
00:05:35,740 --> 00:05:39,810
>> Ja andmeid me hoidmiseks on
just ülikooli nime.

115
00:05:39,810 --> 00:05:41,060
Nii saab ehitada Prefiksipuu.

116
00:05:41,060 --> 00:05:44,860
Lisame paar
objekte meie Prefiksipuu.

117
00:05:44,860 --> 00:05:46,740
Nii tipus,
see on meie Juursõlme.

118
00:05:46,740 --> 00:05:49,740
See on ilmselt saab olema midagi
sa lähed globaalselt kuulutada.

119
00:05:49,740 --> 00:05:53,450
Ja sa lähed globaalselt säilitada
kursor selle sõlme alati.

120
00:05:53,450 --> 00:05:55,360
>> Sa ütled,
root võrdne, ja sa oled

121
00:05:55,360 --> 00:05:57,580
läheb malloc ise Prefiksipuu sõlme.

122
00:05:57,580 --> 00:05:59,850
Ja sa ei saa kunagi
puudutada root uuesti.

123
00:05:59,850 --> 00:06:02,300
Iga kord, kui soovite
alustada navigeerimist läbi,

124
00:06:02,300 --> 00:06:05,802
te valite mõne pointer
võrdne juur, nagu matk,

125
00:06:05,802 --> 00:06:07,760
mis on näiteks mina
kasutada väga paljudes oma videos

126
00:06:07,760 --> 00:06:11,090
siin korstnad ja järjekorrad
ja link nimekirju ja nii edasi.

127
00:06:11,090 --> 00:06:13,320
>> Sa valid teise pointer
nimetatakse trav eest läbipääsusüsteemid.

128
00:06:13,320 --> 00:06:15,890
Ja te kasutate trav navigeerida
kaudu andmestruktuur.

129
00:06:15,890 --> 00:06:17,500
Vaatame, kuidas see võiks välja näha.

130
00:06:17,500 --> 00:06:19,880
Nii kohe, mida
ei sõlm välja näeb?

131
00:06:19,880 --> 00:06:22,920
Noh, nagu meie andmeid
struktuuri deklaratsiooni märgitud,

132
00:06:22,920 --> 00:06:26,906
meil on string, mis
Sel juhul on tühjad.

133
00:06:26,906 --> 00:06:27,780
Siin ei ole midagi.

134
00:06:27,780 --> 00:06:29,550
>> Ja massiivi 10 suunanäitajaks.

135
00:06:29,550 --> 00:06:31,790
Ja just nüüd, me ainult
on 1 sõlm selles Prefiksipuu.

136
00:06:31,790 --> 00:06:33,110
Seal on midagi muud seal.

137
00:06:33,110 --> 00:06:36,020
Nii et kõik 10 neid
viiteid punkti tühjaks.

138
00:06:36,020 --> 00:06:38,090
Seda punast näitab.

139
00:06:38,090 --> 00:06:39,500
>> Lisame string Harvard.

140
00:06:39,500 --> 00:06:41,999
Lisame Ülikooli
Harvardi sellesse Prefiksipuu, mis

141
00:06:41,999 --> 00:06:43,940
asutati aastal 1636.

142
00:06:43,940 --> 00:06:48,220
Me tahame kasutada võtit,
1636, et meile öelda, kus me oleme

143
00:06:48,220 --> 00:06:50,140
läheb salvestada Harvardi Prefiksipuu.

144
00:06:50,140 --> 00:06:51,470
Nüüd, kuidas võiks seda teha?

145
00:06:51,470 --> 00:06:52,886
>> See näeks välja umbes selline.

146
00:06:52,886 --> 00:06:54,160
Alustame keskmes.

147
00:06:54,160 --> 00:06:56,920
Ja meil on neid 10 kohta saame minna.

148
00:06:56,920 --> 00:06:59,900
Juur on nagu iga
muu sõlme Prefiksipuu.

149
00:06:59,900 --> 00:07:02,850
Seal on 10 kohta saame siit edasi minna.

150
00:07:02,850 --> 00:07:07,215
>> Kus me ilmselt tahad
minna, kui võti on 1636?

151
00:07:07,215 --> 00:07:08,340
Seal on tõesti kaks võimalust.

152
00:07:08,340 --> 00:07:08,450
Õigus.

153
00:07:08,450 --> 00:07:10,825
Me võime ehitada võti
paremalt vasakule ja alustada 6.

154
00:07:10,825 --> 00:07:14,000
Või me võiks ehitada võti
vasakult paremale ja alustada 1.

155
00:07:14,000 --> 00:07:16,140
>> See on ilmselt rohkem
intuitiivne kui inimene

156
00:07:16,140 --> 00:07:18,110
mõista me
minge vasakult paremale.

157
00:07:18,110 --> 00:07:21,140
Ja nii kui ma tahan lisada
Harvardi sellesse Prefiksipuu,

158
00:07:21,140 --> 00:07:23,560
Ma ilmselt tahavad alustada
alustades keskmes,

159
00:07:23,560 --> 00:07:25,720
vaatasin 10 valikud
minu ees, ja öelda

160
00:07:25,720 --> 00:07:28,700
Ma tahan minna 1 tee.

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

162
00:07:29,700 --> 00:07:31,810
>> Nüüd, 1 rada on praegu null.

163
00:07:31,810 --> 00:07:35,920
Nii et kui ma tahan minna seda teed
lisada seda asjaolu Prefiksipuu,

164
00:07:35,920 --> 00:07:42,040
Pean malloc Uue sõlme on 1
juhtida seal, ja siis ma olen hea minna.

165
00:07:42,040 --> 00:07:46,460
>> Nii et ma põhimõtteliselt olen juures
kus ma seisan

166
00:07:46,460 --> 00:07:50,270
keskmes puu või
Prefiksipuu ja seal on 10 filiaali.

167
00:07:50,270 --> 00:07:52,260
Aga iga haru on
värava ees.

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

169
00:07:53,060 --> 00:07:54,850
Sest pole midagi seal.

170
00:07:54,850 --> 00:07:56,522
No ohutu läbipääsu.

171
00:07:56,522 --> 00:07:58,980
See tähendab, et seal on midagi
maha kõik need oksad.

172
00:07:58,980 --> 00:08:02,532
Kui ma tahan alustada hoone
midagi, ma tahan, et eemaldada värava.

173
00:08:02,532 --> 00:08:04,490
Ma tahan, et eemaldada värava
ees number 1.

174
00:08:04,490 --> 00:08:05,698
Ja ma tahan jalutada mööda seda.

175
00:08:05,698 --> 00:08:08,060
Ja ma tahan, et ehitada
teine ​​koht mul minna.

176
00:08:08,060 --> 00:08:09,470
>> Ja see, mida ma olen teinud siin.

177
00:08:09,470 --> 00:08:11,430
Nii 1 enam punkte tühjaks.

178
00:08:11,430 --> 00:08:13,830
Ma olen öelnud, et see on ohutu minna siin nüüd.

179
00:08:13,830 --> 00:08:15,789
Ma ehitasin teise sõlme.

180
00:08:15,789 --> 00:08:18,330
Ja kui ma saan, et sõlm, ma
on teise otsuse tegema.

181
00:08:18,330 --> 00:08:20,890
Kuhu ma lähen minema siit?

182
00:08:20,890 --> 00:08:22,700
>> Noh, ma olen juba läinud alla 1.

183
00:08:22,700 --> 00:08:24,470
Nüüd ma ilmselt tahad minna 6.

184
00:08:24,470 --> 00:08:24,970
Õigus.

185
00:08:24,970 --> 00:08:27,100
Jällegi, mul on 10 kohtadesse võin valida.

186
00:08:27,100 --> 00:08:30,060
Nii saab nüüd minna number 6.

187
00:08:30,060 --> 00:08:32,280
Nii et ma selge värava
ees number 6.

188
00:08:32,280 --> 00:08:33,250
Ja ma kõnnin seal.

189
00:08:33,250 --> 00:08:34,580
Ja ma ehitada teise sõlme.

190
00:08:34,580 --> 00:08:37,630
Ja ma olen jõudnud teise ristmikul punkti.

191
00:08:37,630 --> 00:08:40,289
>> Jällegi, mul on 10 valikuid
jaoks, kus ma ei saa minna.

192
00:08:40,289 --> 00:08:42,799
Olen liikunud 1-6.

193
00:08:42,799 --> 00:08:44,215
Nüüd ma ilmselt tahad minna 3.

194
00:08:44,215 --> 00:08:45,381
3, seal kuskil ma ei lähe.

195
00:08:45,381 --> 00:08:48,980
Nii et mul on selge, kuidas
ja ehitada endale uue ruumi.

196
00:08:48,980 --> 00:08:50,870
Ja siis 3, kus ma tahan minna?

197
00:08:50,870 --> 00:08:52,450
Ma tahan minna 6.

198
00:08:52,450 --> 00:08:54,770
>> Ja jällegi, ma pidin
selge viis seda teha.

199
00:08:54,770 --> 00:08:59,179
Nüüd olen kasutanud minu võti sisestada luua
sõlmed ja hakata ehitama seda Prefiksipuu.

200
00:08:59,179 --> 00:09:00,220
Olen hakanud keskmes.

201
00:09:00,220 --> 00:09:03,666
Olen langenud 1636.

202
00:09:03,666 --> 00:09:05,540
Ja nüüd ma olen allosas
seal, et sõlme.

203
00:09:05,540 --> 00:09:06,610
Ja sa võiksid
vaata seda ekraanil.

204
00:09:06,610 --> 00:09:07,735
>> See on kollase värviga.

205
00:09:07,735 --> 00:09:10,020
See, kui ma praegu olen.

206
00:09:10,020 --> 00:09:11,300
Minu peamine tehakse.

207
00:09:11,300 --> 00:09:13,030
Olen ära igas asendis minu võti.

208
00:09:13,030 --> 00:09:15,040
Nii et ma ei saa minna kaugemale.

209
00:09:15,040 --> 00:09:17,720
Nii sel hetkel, ma
tõesti vaja teha, on öelda, OK.

210
00:09:17,720 --> 00:09:18,990
See on nagu vaadates
alla maapinnale,

211
00:09:18,990 --> 00:09:21,115
kui sa ette kujutama
ise nagu selline tee

212
00:09:21,115 --> 00:09:22,350
erinevate ühendustega.

213
00:09:22,350 --> 00:09:25,800
Omamoodi vaatab alla ja omamoodi
Värvimine Harvard kohapeal.

214
00:09:25,800 --> 00:09:26,800
See nimi see.

215
00:09:26,800 --> 00:09:28,300
Tea, et just see on see koht.

216
00:09:28,300 --> 00:09:31,870
Kui hakkame keskmes ja me läheme
1 ja seejärel 6 ja seejärel 3 ja seejärel 6,

217
00:09:31,870 --> 00:09:32,780
kus me oleme?

218
00:09:32,780 --> 00:09:35,640
Noh, kui me vaatame alla
ja me näeme Harvard, siis

219
00:09:35,640 --> 00:09:38,960
me teame, et oli Harvardi
asutatud 1636 põhineb viis

220
00:09:38,960 --> 00:09:41,400
me rakendatakse andmete struktuuri.

221
00:09:41,400 --> 00:09:43,177
Nii et oli loodetavasti arusaadav.

222
00:09:43,177 --> 00:09:44,760
Me teeme veel kaks sisestamisel.

223
00:09:44,760 --> 00:09:50,060
Ja loodetavasti saad aidata
vaata seda teha kaks korda rohkem.

224
00:09:50,060 --> 00:09:52,210
>> Nüüd saab sisestada teises ülikoolis.

225
00:09:52,210 --> 00:09:54,630
Lisame Yale sellesse Prefiksipuu.

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

227
00:09:57,037 --> 00:09:58,870
Nii hakkame juures
root, nagu me alati teeme.

228
00:09:58,870 --> 00:09:59,890
Ja me seame läbipääsusüsteemid pointer.

229
00:09:59,890 --> 00:10:01,624
Me ei kavatse kasutada, et liikuda.

230
00:10:01,624 --> 00:10:03,790
Esimene asi, mida me tahame
tegema, on minna 1 tee.

231
00:10:03,790 --> 00:10:05,830
See on esimene number meie võti.

232
00:10:05,830 --> 00:10:08,420
Õnneks aga meil ei ole
pea tegema muud tööd sel ajal.

233
00:10:08,420 --> 00:10:09,919
1 tee on juba läbinud.

234
00:10:09,919 --> 00:10:13,520
Ma kustutatakse see varem, kui ma
oli sisestamist Harvard at 1.636.

235
00:10:13,520 --> 00:10:18,090
Nii Võin julgelt liikuda
alla 1 ja lihtsalt minna.

236
00:10:18,090 --> 00:10:20,150
Kui ei liiguta alla 1.

237
00:10:20,150 --> 00:10:22,930
>> Nüüd aga ma tahan minna 7.

238
00:10:22,930 --> 00:10:24,280
Ma avab tee 6.

239
00:10:24,280 --> 00:10:27,050
Ma tean, et ma ei saa ohutult
edasi mööda 6 rada.

240
00:10:27,050 --> 00:10:29,220
Aga ma pean toimima 7 teele.

241
00:10:29,220 --> 00:10:30,580
Mida ma pean tegema?

242
00:10:30,580 --> 00:10:35,070
Noh, nagu enne, ma lihtsalt vaja
selge värav, saada välja viis,

243
00:10:35,070 --> 00:10:38,740
ja ehitada uus sõlme 7 teele.

244
00:10:38,740 --> 00:10:40,250
Just niimoodi.

245
00:10:40,250 --> 00:10:42,930
>> Nüüd ma olen liikunud 1 ja seejärel 7.

246
00:10:42,930 --> 00:10:45,550
Ja nüüd märgata, ma olen omamoodi
on selle uue subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Kõik muu on 16
kohta, ma ei hooli.

249
00:10:49,260 --> 00:10:50,720
Ma ei tee 16 midagi.

250
00:10:50,720 --> 00:10:51,750
Ma teen 17 kraami.

251
00:10:51,750 --> 00:10:58,380
>> Nüüd alates 17, ma pean
omamoodi lauk uusi siin.

252
00:10:58,380 --> 00:11:00,462
Järgmine kohaline minu võti on 0.

253
00:11:00,462 --> 00:11:01,670
Ma ei saa ilmselgelt kuhugi.

254
00:11:01,670 --> 00:11:02,628
Ma ehitasin selle sõlme.

255
00:11:02,628 --> 00:11:04,550
Nii et ma tean, seal ei ole
teed edasi siit.

256
00:11:04,550 --> 00:11:06,370
Nii et ma pean tegema ühe ise.

257
00:11:06,370 --> 00:11:09,360
>> Nii et ma malloc uus sõlm
ja on 0 punkti olemas.

258
00:11:09,360 --> 00:11:12,770
Ja siis veel üks kord, ma malloc
uus sõlm ja üks koht olemas.

259
00:11:12,770 --> 00:11:15,870
Jällegi, ma olen ära minu võti, 1701.

260
00:11:15,870 --> 00:11:18,472
Nii ma vaatan alla ja ma spreid Yale.

261
00:11:18,472 --> 00:11:19,680
See on nimi selle sõlme.

262
00:11:19,680 --> 00:11:24,660
>> Ja nii nüüd kui ma kunagi vaja näha, kui Yale
on selles Prefiksipuu, ma hakkan keskmes,

263
00:11:24,660 --> 00:11:27,060
Ma lähen alla 1701, ja vaata alla.

264
00:11:27,060 --> 00:11:30,030
Ja kui ma näen, Yale spray
värvitud maapinnale, siis

265
00:11:30,030 --> 00:11:32,200
Ma tean, Yale olemas selles Prefiksipuu.

266
00:11:32,200 --> 00:11:32,950
Teeme veel ühe.

267
00:11:32,950 --> 00:11:36,430
Lisame Dartmouth sellesse
Prefiksipuu, mis asutati 1769.

268
00:11:36,430 --> 00:11:37,750
>> Alusta keskmes uuesti.

269
00:11:37,750 --> 00:11:39,445
Minu esimene number minu võti on 1.

270
00:11:39,445 --> 00:11:40,820
Võin julgelt liikuda mööda seda teed.

271
00:11:40,820 --> 00:11:42,400
See on juba olemas.

272
00:11:42,400 --> 00:11:44,040
Järgmine kohaline minu võti on 7.

273
00:11:44,040 --> 00:11:45,890
Võin julgelt liikuda mööda seda teed.

274
00:11:45,890 --> 00:11:47,540
See on olemas ka.

275
00:11:47,540 --> 00:11:49,000
>> Minu kõrval on 6.

276
00:11:49,000 --> 00:11:52,860
Siit kust ma praegu olen
kollane seal, et keset sõlme,

277
00:11:52,860 --> 00:11:56,060
6 on praegu lukustatud maha.

278
00:11:56,060 --> 00:11:58,830
Kui ma tahan minna seda teed,
Mul on ehitada ise.

279
00:11:58,830 --> 00:12:02,250
Nii et ma malloc uus sõlm
ja on 6 punkti olemas.

280
00:12:02,250 --> 00:12:04,250
Ja siis jälle, ma olen
lõõskav uus suusarajad siin.

281
00:12:04,250 --> 00:12:10,750
>> Nii et ma malloc uus sõlm, et alates
et node-- liini number 9-- ja siis nüüd

282
00:12:10,750 --> 00:12:13,584
kui ma reisida 1769 ja ma vaatan alla.

283
00:12:13,584 --> 00:12:15,500
Pole midagi praegu
spray värvitud olemas.

284
00:12:15,500 --> 00:12:16,930
Oskan kirjutada Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Ja ma olen järele
Dartmouth sisse Prefiksipuu.

286
00:12:20,710 --> 00:12:23,450
>> Nii et sisestades
asju sisse Prefiksipuu.

287
00:12:23,450 --> 00:12:25,384
Nüüd tahame otsida asju.

288
00:12:25,384 --> 00:12:27,050
Kuidas otsida asju Prefiksipuu?

289
00:12:27,050 --> 00:12:29,170
Noh, see on päris palju sama mõte.

290
00:12:29,170 --> 00:12:33,620
Nüüd me lihtsalt kasutada numbrit võti
et näha, kas me saame liikuda juurest

291
00:12:33,620 --> 00:12:37,170
et kuhu me tahame minna Prefiksipuu.

292
00:12:37,170 --> 00:12:41,620
>> Kui me tabanud tupikusse üheski punktis, siis
me teame, et see element ei eksisteeri

293
00:12:41,620 --> 00:12:44,500
või siis, et tee oleks
on juba kõrvaldatud.

294
00:12:44,500 --> 00:12:45,930
Kui me teeme seda kõik viis
Lõpuks kõik me peame tegema

295
00:12:45,930 --> 00:12:48,471
on odavnema ja vaata, kas see on
element ootame.

296
00:12:48,471 --> 00:12:49,335
Kui on, edu.

297
00:12:49,335 --> 00:12:52,610
Kui see ei ole, ei suuda.

298
00:12:52,610 --> 00:12:54,940
>> Nii saab otsida
Harvardi selles Prefiksipuu.

299
00:12:54,940 --> 00:12:56,020
Alustame keskmes.

300
00:12:56,020 --> 00:12:58,228
Ja jällegi, me ei kavatse
luua läbipääsusüsteemid pointer

301
00:12:58,228 --> 00:12:59,390
teha oma käigud meile.

302
00:12:59,390 --> 00:13:02,080
Juurest me teame, et
esiteks me peame minema on 1,

303
00:13:02,080 --> 00:13:03,390
me saame seda teha?

304
00:13:03,390 --> 00:13:03,982
Jah me saame.

305
00:13:03,982 --> 00:13:04,690
Kui turvaliselt olemas.

306
00:13:04,690 --> 00:13:06,660
Me ei lähe sinna.

307
00:13:06,660 --> 00:13:08,440
>> Nüüd järgmine koht peame minema on 6.

308
00:13:08,440 --> 00:13:10,557
Kas 6 rada olemas siit?

309
00:13:10,557 --> 00:13:11,140
Jah, nii see on.

310
00:13:11,140 --> 00:13:12,690
Me ei saa minna mööda 6 rada.

311
00:13:12,690 --> 00:13:13,905
Ja me lõpuks siin.

312
00:13:13,905 --> 00:13:16,130
>> Kas me saame minna 3 tee siin?

313
00:13:16,130 --> 00:13:18,450
Noh, kui selgub,
jah, et on olemas ka.

314
00:13:18,450 --> 00:13:20,790
Ja me saame on 6 teed siit?

315
00:13:20,790 --> 00:13:21,982
Jah me saame.

316
00:13:21,982 --> 00:13:24,002
>> Me ei ole päris vastas
küsimus veel.

317
00:13:24,002 --> 00:13:25,710
Seal on veel üks
etapp, mis on nüüd

318
00:13:25,710 --> 00:13:28,520
vajame odavnema ja
kas see on actually--

319
00:13:28,520 --> 00:13:32,660
Kui me otsime Harvard, on see, et
mida leiame pärast me ammendab võti?

320
00:13:32,660 --> 00:13:35,430
Näites me kasutame siin
Aastate on alati neli numbrit.

321
00:13:35,430 --> 00:13:40,280
Aga siis võiks kasutada näiteks siis, kui
olete ladustamiseks sõnastik sõnu.

322
00:13:40,280 --> 00:13:44,060
>> Ja nii asemel 10 suunanäitajaks
minu asukohta, siis võib-olla 26.

323
00:13:44,060 --> 00:13:46,040
Üks iga täht.

324
00:13:46,040 --> 00:13:50,350
Ja seal on mõned sõnad, nagu nahkhiir,
mis on alamhulk partii, näiteks.

325
00:13:50,350 --> 00:13:53,511
Ja nii ka siis, kui sa saad
lõpuks võtme ja sa vaatad alla,

326
00:13:53,511 --> 00:13:55,260
sa ei pruugi näha, mida
otsite.

327
00:13:55,260 --> 00:13:58,500
>> Nii et teil on alati läbida
kogu tee ja seejärel

328
00:13:58,500 --> 00:14:01,540
kui sa olid edukalt suudab
läbida kogu tee,

329
00:14:01,540 --> 00:14:03,440
odavnema ja teha üks lõpliku kinnituse.

330
00:14:03,440 --> 00:14:05,120
Kas see, mida ma otsin?

331
00:14:05,120 --> 00:14:07,740
Noh, ma vaatan alla pärast käivitamist
tipus ja läheb 1636.

332
00:14:07,740 --> 00:14:08,240
Ma vaatan maha.

333
00:14:08,240 --> 00:14:09,400
Ma näen Harvard.

334
00:14:09,400 --> 00:14:11,689
Nii et jah, ma õnnestus.

335
00:14:11,689 --> 00:14:13,980
Mis siis, kui see, mida ma otsin
ei asu Prefiksipuu, kuigi.

336
00:14:13,980 --> 00:14:17,200
Mis siis, kui ma otsin Princeton,
mis asutati 1746.

337
00:14:17,200 --> 00:14:20,875
Ja nii 1746 muutub minu võti
liikuda Prefiksipuu.

338
00:14:20,875 --> 00:14:22,040
Noh, ma hakkan keskmes.

339
00:14:22,040 --> 00:14:24,760
Ja esimene koht, kus ma tahan
et läheb alla 1 rada.

340
00:14:24,760 --> 00:14:25,590
Kas ma saan seda teha?

341
00:14:25,590 --> 00:14:26,490
Jah, ma saan.

342
00:14:26,490 --> 00:14:28,730
>> Kas ma saan minna 7 tee seal?

343
00:14:28,730 --> 00:14:29,230
Jah, suudan.

344
00:14:29,230 --> 00:14:30,750
See kehtib ka.

345
00:14:30,750 --> 00:14:32,460
Aga ma saan minna 4 tee siin?

346
00:14:32,460 --> 00:14:35,550
See on nagu küsib küsimuse, saab
Ma sõita alla, et vähe kandiline

347
00:14:35,550 --> 00:14:37,114
et ma olen kollase värviga?

348
00:14:37,114 --> 00:14:38,030
Pole midagi seal.

349
00:14:38,030 --> 00:14:38,610
Õigus.

350
00:14:38,610 --> 00:14:41,310
>> Ei ole nii edasi mööda 4 teed.

351
00:14:41,310 --> 00:14:46,480
Kui Princetoni oli selles Prefiksipuu, et 4
oleks läbinud meile juba.

352
00:14:46,480 --> 00:14:49,130
Ja et selles kohas
oleme jõudnud tupikusse.

353
00:14:49,130 --> 00:14:50,250
Me ei saa minna kaugemale.

354
00:14:50,250 --> 00:14:53,440
Ja nii võib öelda, lõplikult ei.

355
00:14:53,440 --> 00:14:56,760
Princetoni ei ole selles Prefiksipuu.

356
00:14:56,760 --> 00:14:58,860
>> Mida see kõik tähendab?

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

358
00:14:59,360 --> 00:15:01,000
Seal on palju siin toimub.

359
00:15:01,000 --> 00:15:02,500
Seal on suunanäitajaks kogu koht.

360
00:15:02,500 --> 00:15:04,249
Ja nagu näed
lihtsalt skeemilt,

361
00:15:04,249 --> 00:15:07,010
seal on palju tippe, et
on selline sõidavad ringi.

362
00:15:07,010 --> 00:15:13,480
Aga teate iga kord, kui me tahtsime
kas midagi oli Prefiksipuu,

363
00:15:13,480 --> 00:15:15,000
meil oli ainult teha 4 liigutust.

364
00:15:15,000 --> 00:15:17,208
>> Iga kord, kui me tahtsime
lisada midagi Prefiksipuu,

365
00:15:17,208 --> 00:15:20,440
peame 4 liigub, võib-olla
mallocing mõned asjad mööda teed.

366
00:15:20,440 --> 00:15:23,482
Aga nagu me nägime, kui me sisestatud
Dartmouth sisse Prefiksipuu,

367
00:15:23,482 --> 00:15:25,940
mõnikord mõned teed
võiks juba kustutatud meile.

368
00:15:25,940 --> 00:15:30,520
Ja nii nagu meie Prefiksipuu muutub suuremaks ja
suurem, on meil teha vähem tööd iga kord

369
00:15:30,520 --> 00:15:32,270
lisada uusi asju
sest me oleme juba

370
00:15:32,270 --> 00:15:35,746
ehitatud palju vahepealse
oksad mööda teed.

371
00:15:35,746 --> 00:15:38,370
Kui me ainult kunagi vaadata
4 asju, 4 on lihtsalt konstant.

372
00:15:38,370 --> 00:15:41,750
Me tõesti on selline läheneb
pidev aja sisestamise

373
00:15:41,750 --> 00:15:44,501
ja pidev aja otsing.

374
00:15:44,501 --> 00:15:47,500
Miinuseks muidugi on see, et
Selle Prefiksipuu, kui saad ilmselt öelda,

375
00:15:47,500 --> 00:15:49,030
on suur.

376
00:15:49,030 --> 00:15:51,040
Igaüks neist sõlmed
võtab palju ruumi.

377
00:15:51,040 --> 00:15:52,090
>> Aga see on kompromiss.

378
00:15:52,090 --> 00:15:55,260
Kui me tahame tõesti kiire
sisestamise tõesti kiire kustutamise,

379
00:15:55,260 --> 00:15:59,630
ja tõesti kiire otsing, peame
on palju andmeid sõidavad ringi.

380
00:15:59,630 --> 00:16:03,590
Me peame kõrvale palju ruumi
ja mälu andmete struktuur

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

382
00:16:04,290 --> 00:16:05,415
>> Ja nii see on kompromiss.

383
00:16:05,415 --> 00:16:07,310
Aga tundub, et me
oleks leidnud.

384
00:16:07,310 --> 00:16:09,560
Me võime on leidnud, et
Püha Graal andmestruktuurid

385
00:16:09,560 --> 00:16:12,264
kiire sisestamine,
kustutamise ja otsimise.

386
00:16:12,264 --> 00:16:14,430
Ja võib-olla see olla
asjakohaste andmete struktuur

387
00:16:14,430 --> 00:16:18,890
kasutada mis tahes teavet
me üritame poodi.

388
00:16:18,890 --> 00:16:21,860
Ma olen Doug Lloyd, see on CS50.

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