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

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

3
00:00:05,426 --> 00:00:08,550
DOUG Lloyd: Eli olemme inching lähemmäksi
ja lähempänä että pyhä Graal tiedot

4
00:00:08,550 --> 00:00:13,050
rakenteet, yksi voimme lisätä
osaksi, poistaa, ja etsiä

5
00:00:13,050 --> 00:00:15,440
jatkuvassa aikaa.

6
00:00:15,440 --> 00:00:16,270
Oikea.

7
00:00:16,270 --> 00:00:17,280
Se tavallaan maalia.

8
00:00:17,280 --> 00:00:19,720
Haluamme pystyä tekemään
asiat hyvin, hyvin nopeasti.

9
00:00:19,720 --> 00:00:22,580
>> Onko löysimme sen täällä, kun
puhumme yrittää?

10
00:00:22,580 --> 00:00:23,670
No, katsotaanpa katsomaan.

11
00:00:23,670 --> 00:00:25,628
Joten olemme nähneet useita
eri tietorakenteiden

12
00:00:25,628 --> 00:00:28,680
jotka käsittelevät kartoitus
ns avainarvopareja,

13
00:00:28,680 --> 00:00:32,080
kartoitus joitakin osa tiedoista
joihinkin muihin osa tiedoista

14
00:00:32,080 --> 00:00:36,020
jotta tiedämme mistä löytää
tiedot rakenteessa.

15
00:00:36,020 --> 00:00:40,060
>> Joten array, esimerkiksi,
avain on osa indeksi tai joukko

16
00:00:40,060 --> 00:00:42,600
sijainti 0 tai array 1 ja niin edelleen.

17
00:00:42,600 --> 00:00:46,140
Ja arvo on tiedot
että on kyseisessä paikassa.

18
00:00:46,140 --> 00:00:48,550
Niin mitä on tallennettu array 0?

19
00:00:48,550 --> 00:00:54,290
Mitä tallennetaan array 1 vs. vain
0 ja 1, mikä olisi avaimet.

20
00:00:54,290 --> 00:00:56,360
>> Jossa tiiviste on
tavallaan saman ajatuksen.

21
00:00:56,360 --> 00:01:00,690
Jossa tiiviste, meillä on tämä hash
toiminto, joka luo hash koodeja.

22
00:01:00,690 --> 00:01:03,670
Joten avain on hash tietojen.

23
00:01:03,670 --> 00:01:06,530
Ja arvo, erityisesti
puhuimme ketjuttamalla

24
00:01:06,530 --> 00:01:10,590
in video hash taulukoita,
on että linkitetty lista tietojen

25
00:01:10,590 --> 00:01:12,550
että tiivistyy että hashcode.

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

27
00:01:14,050 --> 00:01:16,050
Entä toinen lähestymistapa
tämä menetelmä, vaikka?

28
00:01:16,050 --> 00:01:21,000
Entä menetelmä, jossa
avain on taatusti ainutlaatuinen,

29
00:01:21,000 --> 00:01:25,410
toisin tiiviste, jossa voisimme
päätyä kaksi kappaletta tietojen

30
00:01:25,410 --> 00:01:27,200
jolla on sama hashcode.

31
00:01:27,200 --> 00:01:30,020
Ja meidän on käsiteltävä
että joko hyvää tai enemmän

32
00:01:30,020 --> 00:01:33,340
edullisesti ketjuttamalla korjata tämä ongelma.

33
00:01:33,340 --> 00:01:37,520
>> Joten nyt voimme taata
että avain on ainutlaatuinen.

34
00:01:37,520 --> 00:01:39,690
Ja mitä jos meidän arvo oli
vain jotain yhtä helppoa

35
00:01:39,690 --> 00:01:44,080
kuten oikean ja väärän, joka kertoo meille,
tai ei, että tieto

36
00:01:44,080 --> 00:01:45,610
olemassa rakenne?

37
00:01:45,610 --> 00:01:48,180
Boolen voisi olla niinkin yksinkertainen kuin hieman.

38
00:01:48,180 --> 00:01:52,660
Realistisesti se on luultavasti
tavu todennäköisemmin kuin vähän.

39
00:01:52,660 --> 00:01:55,410
Mutta se on paljon pienempi kuin
tallentamiseen ehkä 50-merkkijonon,

40
00:01:55,410 --> 00:01:57,360
esimerkiksi.

41
00:01:57,360 --> 00:02:02,210
>> Joten yrittää, samanlainen hash taulukot,
jotka yhdistävät taulukot ja linkitetty lista,

42
00:02:02,210 --> 00:02:05,790
yrittää yhdistää taulukot,
rakenteet, ja osoittimet

43
00:02:05,790 --> 00:02:08,509
yhdessä tietojen tallentaminen
mielenkiintoinen tavalla, joka on

44
00:02:08,509 --> 00:02:11,550
melko erilainen
mitä olemme nähneet tähän mennessä.

45
00:02:11,550 --> 00:02:16,750
Nyt käytämme tietojen tiekartta
navigoida tietojen rakenne.

46
00:02:16,750 --> 00:02:18,710
Ja jos me voimme seurata
tiekartan, jos voimme

47
00:02:18,710 --> 00:02:22,390
seurata tietoja
alusta loppuun, käymme

48
00:02:22,390 --> 00:02:24,945
onko että tiedot
olemassa trie.

49
00:02:24,945 --> 00:02:28,310
>> Ja jos emme voi seurata karttaa
alkaen eli lopettaa ollenkaan,

50
00:02:28,310 --> 00:02:30,600
tietoja ei voi olla olemassa.

51
00:02:30,600 --> 00:02:32,890
Jälleen, avaimet tässä on
taatusti ainutlaatuinen.

52
00:02:32,890 --> 00:02:36,020
Ja niin toisin hajautustaulun, emme koskaan
on käsiteltävä törmäyksiä täällä.

53
00:02:36,020 --> 00:02:39,090
Eikä kaksi kappaletta tietojen
on täsmälleen sama tiekartan

54
00:02:39,090 --> 00:02:40,530
ellei tämä tieto on sama.

55
00:02:40,530 --> 00:02:44,580
>> Jos lisäämme John, sitten
etsimme John.

56
00:02:44,580 --> 00:02:47,430
Se on kaksi samanlaista kappaletta
tiedot, oikea, me etsimme kautta.

57
00:02:47,430 --> 00:02:49,880
Mutta muuten kaikki
kaksi kappaletta tietoa

58
00:02:49,880 --> 00:02:52,750
taatusti on ainutlaatuinen etenemissuunnitelmat
tällä tietorakennetta.

59
00:02:52,750 --> 00:02:56,210
Ja aiomme katsomaan
visuaalinen tästä vain hetken.

60
00:02:56,210 --> 00:02:58,810
>> Teemme tämän yrittämällä
Luo uusi tietorakenne,

61
00:02:58,810 --> 00:03:00,564
kartoitus seuraavat keskeiset arvoparit.

62
00:03:00,564 --> 00:03:03,480
Tässä tapauksessa emme aio käyttää
jotain niin yksinkertaista kuin Boolen.

63
00:03:03,480 --> 00:03:06,200
Me itse asiassa tallentaa merkkijonon.

64
00:03:06,200 --> 00:03:08,690
Ja että merkkijono on menossa
olla nimi yliopisto.

65
00:03:08,690 --> 00:03:12,140
>> Ja avain tulee olemaan vuosi
kun että yliopisto perustettiin.

66
00:03:12,140 --> 00:03:15,380
Kaikki vuotta yliopistoille
tulevat olemaan neljä numeroa.

67
00:03:15,380 --> 00:03:19,840
Ja niin me käyttää näitä neljä numeroa
selata näitä tietoja rakenteen.

68
00:03:19,840 --> 00:03:22,270
Ja näemme, jälleen, miten
teemme sen vain toinen.

69
00:03:22,270 --> 00:03:25,110
>> Lopussa polun,
näemme nimi

70
00:03:25,110 --> 00:03:30,250
Yliopiston joka vastaa
avaimeen, nämä neljä numeroa.

71
00:03:30,250 --> 00:03:34,390
Perusajatuksena trie
on meillä keskeinen reitti.

72
00:03:34,390 --> 00:03:35,640
Joten ajattele sitä kuin puu.

73
00:03:35,640 --> 00:03:39,211
Ja tämä on samanlainen oikeinkirjoitus
ja käsite puuhun.

74
00:03:39,211 --> 00:03:41,460
Yleensä kun ajattelemme
Puut todellisessa maailmassa,

75
00:03:41,460 --> 00:03:44,090
heillä juuri, joka on vuonna
maahan ja ne kasvavat ylöspäin

76
00:03:44,090 --> 00:03:46,830
ja he ovat oksat
ja heillä on lehtiä.

77
00:03:46,830 --> 00:03:49,450
Ja pohjimmiltaan ajatus
trie on täsmälleen sama,

78
00:03:49,450 --> 00:03:51,755
paitsi että juuri on ankkuroitu
jossain taivaalla.

79
00:03:51,755 --> 00:03:53,130
Ja lehdet ovat alareunassa.

80
00:03:53,130 --> 00:03:55,750
>> Joten se on tavallaan kuin ottaa puu
ja vain kääntämällä se ylösalaisin.

81
00:03:55,750 --> 00:03:56,880
Mutta on vielä oksat.

82
00:03:56,880 --> 00:03:59,463
Ja ne olisi meidän polkuja,
ne on meidän yhteydet

83
00:03:59,463 --> 00:04:02,220
juuresta lehtiä.

84
00:04:02,220 --> 00:04:04,200
Tässä tapauksessa nämä
polkuja, ne oksat

85
00:04:04,200 --> 00:04:08,490
leimataan numeroa, jotka kertovat meille
mihin suuntaan mennä, missä olemme.

86
00:04:08,490 --> 00:04:11,800
>> Jos näemme 0, menemme tämän haara,
jos näemme 1, menemme tämän haara,

87
00:04:11,800 --> 00:04:12,900
ja niin ja niin edelleen.

88
00:04:12,900 --> 00:04:14,060
No, mitä tämä tarkoittaa?

89
00:04:14,060 --> 00:04:16,519
No, se tarkoittaa, että
jokaisessa liitoskohtaan

90
00:04:16,519 --> 00:04:19,260
ja jokainen solmu
keski ja jokainen haara,

91
00:04:19,260 --> 00:04:23,020
on 10 mahdollista
paikkoja, että voimme mennä.

92
00:04:23,020 --> 00:04:27,690
Joten on 10 osoittimia
alkaen kaikissa paikoissa.

93
00:04:27,690 --> 00:04:30,610
>> Ja tämä on, jos yrittää saada
hieman uhkaava joku

94
00:04:30,610 --> 00:04:34,460
kuka ei ole paljon
kokemus tietotekniikassa ennen.

95
00:04:34,460 --> 00:04:35,960
Mutta yrittää ovat oikeastaan ​​aika mahtava.

96
00:04:35,960 --> 00:04:37,793
Ja jos sinulla on
mahdollisuus työskennellä heidän kanssaan

97
00:04:37,793 --> 00:04:40,420
ja olet valmis kaivaa sisään
ja kokeilla niitä,

98
00:04:40,420 --> 00:04:44,234
he oikeastaan ​​aika mielenkiintoinen
tietorakenteita työskennellä.

99
00:04:44,234 --> 00:04:46,900
Jos haluamme lisätä elementin
osaksi trie, kaikki meidän täytyy tehdä

100
00:04:46,900 --> 00:04:51,360
on rakentaa oikea polku
juuresta lehtiä.

101
00:04:51,360 --> 00:04:55,390
Tässä mitä jokainen askel pitkin
Muuten voisi näyttää.

102
00:04:55,390 --> 00:04:59,660
Aiomme määritellä uusia tietoja
rakenne uusi solmu nimeltään trie.

103
00:04:59,660 --> 00:05:02,560
>> Ja sisältä että tiedot
rakenne on kaksi kappaletta.

104
00:05:02,560 --> 00:05:05,460
Aiomme säilyttää
nimi yliopiston.

105
00:05:05,460 --> 00:05:09,410
Ja aiomme säilyttää
joukko osoittimia

106
00:05:09,410 --> 00:05:12,190
muihin solmuihin samantyyppisiä.

107
00:05:12,190 --> 00:05:14,780
Joten, jälleen, tämä on tällaista
on käsite kaikkialla

108
00:05:14,780 --> 00:05:18,567
olemme, me 10 mahdollista
paikkoja voimme mennä.

109
00:05:18,567 --> 00:05:20,150
Jos näemme 0, menemme alas tämä osa.

110
00:05:20,150 --> 00:05:22,690
Jos näemme 1, tämä haara,
ja niin edelleen ja niin edelleen ja niin edelleen.

111
00:05:22,690 --> 00:05:25,160
Jos sanomme 9, menemme alas tämä osa.

112
00:05:25,160 --> 00:05:28,220
Joten jokaisessa liitoskohtaan,
voimme mennä 10 mahdollista paikkaa.

113
00:05:28,220 --> 00:05:35,740
Joten jokainen solmu on sisällettävä 10 osoittimia
muihin solmuihin, 10 muut solmut.

114
00:05:35,740 --> 00:05:39,810
>> Ja tiedot me tallentamiseen on
vain yliopiston nimi.

115
00:05:39,810 --> 00:05:41,060
Joten rakentaa trie.

116
00:05:41,060 --> 00:05:44,860
Katsotaanpa lisätä pari
kohteita meidän trie.

117
00:05:44,860 --> 00:05:46,740
Joten huipulla,
tämä on meidän root solmu.

118
00:05:46,740 --> 00:05:49,740
Tämä on luultavasti olemaan jotain
aiot globaalisti julistaa.

119
00:05:49,740 --> 00:05:53,450
Ja olet menossa globaalisti säilyttää
osoitin tähän solmuun aina.

120
00:05:53,450 --> 00:05:55,360
>> Aiot sanoa,
juuri vastaa, ja olet

121
00:05:55,360 --> 00:05:57,580
menossa malloc itse trie solmu.

122
00:05:57,580 --> 00:05:59,850
Ja olet koskaan
koskettaa juuri uudelleen.

123
00:05:59,850 --> 00:06:02,300
Joka kerta haluat
aloittaa navigoinnin kautta,

124
00:06:02,300 --> 00:06:05,802
asetat toinen osoitin
sama juuri, kuten trav,

125
00:06:05,802 --> 00:06:07,760
joka on esimerkki I
käyttää monet minun videoita

126
00:06:07,760 --> 00:06:11,090
täällä pinot ja jonot
ja linkit ja niin edelleen.

127
00:06:11,090 --> 00:06:13,320
>> Voit asettaa toinen osoitin
kehotti trav varten kulkea.

128
00:06:13,320 --> 00:06:15,890
Ja käytät Trav navigoida
kautta tietorakennetta.

129
00:06:15,890 --> 00:06:17,500
Joten miten tämä voisi näyttää.

130
00:06:17,500 --> 00:06:19,880
Joten nyt, mitä
ei solmu näyttää?

131
00:06:19,880 --> 00:06:22,920
No, aivan kuten tiedot
rakenne ilmoitus ilmoitettu,

132
00:06:22,920 --> 00:06:26,906
meillä on merkkijono, joka
tässä tapauksessa on tyhjä.

133
00:06:26,906 --> 00:06:27,780
Täällä ei ole mitään.

134
00:06:27,780 --> 00:06:29,550
>> Ja joukko 10 osoittimia.

135
00:06:29,550 --> 00:06:31,790
Ja juuri nyt, me vain
on 1 solmu tässä trien.

136
00:06:31,790 --> 00:06:33,110
Ei mitään muuta se.

137
00:06:33,110 --> 00:06:36,020
Joten kaikki 10 niistä
viitteitä kohta null.

138
00:06:36,020 --> 00:06:38,090
Sitähän punaisella.

139
00:06:38,090 --> 00:06:39,500
>> Katsotaanpa lisätä merkkijono Harvardin.

140
00:06:39,500 --> 00:06:41,999
Katsotaanpa lisätä yliopistossa
Harvardin tähän trie, joka

141
00:06:41,999 --> 00:06:43,940
perustettiin vuonna 1636.

142
00:06:43,940 --> 00:06:48,220
Haluamme käyttää avain,
1636, kertoa meille, missä olemme

143
00:06:48,220 --> 00:06:50,140
menossa tallentaa Harvardin trien.

144
00:06:50,140 --> 00:06:51,470
Nyt, miten voisi me teemme?

145
00:06:51,470 --> 00:06:52,886
>> Se saattaa näyttää tältä.

146
00:06:52,886 --> 00:06:54,160
Aloitamme juureen.

147
00:06:54,160 --> 00:06:56,920
Ja meillä on nämä 10 paikkaa voimme mennä.

148
00:06:56,920 --> 00:06:59,900
Juuri on aivan kuten mikä tahansa
toisen solmun trie.

149
00:06:59,900 --> 00:07:02,850
On 10 paikkaa voimme mennä tästä.

150
00:07:02,850 --> 00:07:07,215
>> Minne me luultavasti halua
mennä, jos avain on 1636?

151
00:07:07,215 --> 00:07:08,340
On oikeastaan ​​kaksi vaihtoehtoa.

152
00:07:08,340 --> 00:07:08,450
Oikea.

153
00:07:08,450 --> 00:07:10,825
Voimme rakentaa avain
oikealta vasemmalle ja aloittaa 6.

154
00:07:10,825 --> 00:07:14,000
Tai voisimme rakentaa avain
vasemmalta oikealle ja aloittaa 1.

155
00:07:14,000 --> 00:07:16,140
>> Se on luultavasti enemmän
intuitiivinen ihmisenä

156
00:07:16,140 --> 00:07:18,110
ymmärtää me
vain mennä vasemmalta oikealle.

157
00:07:18,110 --> 00:07:21,140
Joten jos haluan lisätä
Harvardin tähän trie,

158
00:07:21,140 --> 00:07:23,560
Luultavasti halua aloittaa
aloittamalla juureen,

159
00:07:23,560 --> 00:07:25,720
katsot minun 10 vaihtoehtoja
edessäni, ja sanoi

160
00:07:25,720 --> 00:07:28,700
Haluan mennä alas 1 polku.

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

162
00:07:29,700 --> 00:07:31,810
>> Nyt 1 polku on tällä hetkellä tyhjä.

163
00:07:31,810 --> 00:07:35,920
Joten jos haluan jatkaa tätä tietä
lisätä tämä seikka trie,

164
00:07:35,920 --> 00:07:42,040
Minun täytyy malloc uusi solmu, on 1
kohta siellä, ja sitten olen hyvä mennä.

165
00:07:42,040 --> 00:07:46,460
>> Olen siis periaatteessa olen at
kohta jossa Seison

166
00:07:46,460 --> 00:07:50,270
juureen puun tai
trie ja on 10 oksat.

167
00:07:50,270 --> 00:07:52,260
Mutta jokainen haara on
portti sen edessä.

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

169
00:07:53,060 --> 00:07:54,850
Koska ei ole mitään muuta siellä.

170
00:07:54,850 --> 00:07:56,522
Ei turvallinen kulku.

171
00:07:56,522 --> 00:07:58,980
Tämä tarkoittaa, että ei ole mitään
alas mitään näistä oksat.

172
00:07:58,980 --> 00:08:02,532
Jos haluan alkaa rakentaa
jotain, haluan poistaa portille.

173
00:08:02,532 --> 00:08:04,490
Haluan poistaa portille
edessä numero 1.

174
00:08:04,490 --> 00:08:05,698
Ja haluan kävellä että.

175
00:08:05,698 --> 00:08:08,060
Ja haluan rakentaa
toinen paikka minun mennä.

176
00:08:08,060 --> 00:08:09,470
>> Ja se, mitä olen tehnyt täällä.

177
00:08:09,470 --> 00:08:11,430
Joten 1 ei enää viittaa null.

178
00:08:11,430 --> 00:08:13,830
Olen sanonut se on turvallista mennä tänne nyt.

179
00:08:13,830 --> 00:08:15,789
Rakensin toisen solmun.

180
00:08:15,789 --> 00:08:18,330
Ja kun saan että solmuun, minä
on toinen päätös.

181
00:08:18,330 --> 00:08:20,890
Minne olen menossa mennä tästä?

182
00:08:20,890 --> 00:08:22,700
>> No, olen jo laskeneet 1.

183
00:08:22,700 --> 00:08:24,470
Joten nyt luultavasti halua mennä alas 6.

184
00:08:24,470 --> 00:08:24,970
Oikea.

185
00:08:24,970 --> 00:08:27,100
Jälleen Olen 10 paikkakunnalla voin valita.

186
00:08:27,100 --> 00:08:30,060
Joten nyt mennä alas numero 6.

187
00:08:30,060 --> 00:08:32,280
Joten en poista portti
edessä numero 6.

188
00:08:32,280 --> 00:08:33,250
Ja kävelen siellä.

189
00:08:33,250 --> 00:08:34,580
Ja minä rakentaa toisen solmun.

190
00:08:34,580 --> 00:08:37,630
Ja olen saavuttanut toisen liitoskohtaan.

191
00:08:37,630 --> 00:08:40,289
>> Jälleen Olen 10 valintoja
minne voin mennä.

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

193
00:08:42,799 --> 00:08:44,215
Joten nyt luultavasti halua mennä 3.

194
00:08:44,215 --> 00:08:45,381
3, missään muualla voin mennä.

195
00:08:45,381 --> 00:08:48,980
Olen siis selkeä tapa
ja rakentaa itselleni uutta tilaa.

196
00:08:48,980 --> 00:08:50,870
Ja sitten 3, mistä haluan mennä?

197
00:08:50,870 --> 00:08:52,450
Haluan mennä alas 6.

198
00:08:52,450 --> 00:08:54,770
>> Ja taas jouduin
selkeä tapa tehdä se.

199
00:08:54,770 --> 00:08:59,179
Joten nyt olen käyttänyt avain lisätä luoda
solmut ja alkaa rakentaa tätä trie.

200
00:08:59,179 --> 00:09:00,220
Olen alkanut juuresta.

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

202
00:09:03,666 --> 00:09:05,540
Ja nyt olen alareunassa
siellä että solmu.

203
00:09:05,540 --> 00:09:06,610
Ja saatat pystyä
nähdä sen näytössä.

204
00:09:06,610 --> 00:09:07,735
>> Se on korostettu keltaisella.

205
00:09:07,735 --> 00:09:10,020
Siellä minä nyt olen.

206
00:09:10,020 --> 00:09:11,300
Avaimeni tehdään.

207
00:09:11,300 --> 00:09:13,030
Olen loppuun kaikissa asennoissa minun avain.

208
00:09:13,030 --> 00:09:15,040
Joten en voi mennä pidemmälle.

209
00:09:15,040 --> 00:09:17,720
Joten tässä vaiheessa, en
todella tarvitsee vain sanoa, OK.

210
00:09:17,720 --> 00:09:18,990
Se on ikään kuin etsivät
alas maahan,

211
00:09:18,990 --> 00:09:21,115
jos olet envisioning
itsesi tällainen polku

212
00:09:21,115 --> 00:09:22,350
eri yhteydet.

213
00:09:22,350 --> 00:09:25,800
Eräänlainen katselee ja tavallaan
spray maalaus Harvardin maahan.

214
00:09:25,800 --> 00:09:26,800
Se on nimi tämän.

215
00:09:26,800 --> 00:09:28,300
Tiedä se mitä tässä paikassa.

216
00:09:28,300 --> 00:09:31,870
Jos me alkavat juuri ja mennään alas
1 ja sitten 6 ja sitten 3 ja sitten 6,

217
00:09:31,870 --> 00:09:32,780
missä olemme?

218
00:09:32,780 --> 00:09:35,640
No jos katsomme alas
ja näemme Harvard, sitten

219
00:09:35,640 --> 00:09:38,960
me tiedämme, että Harvardin oli
perustettiin vuonna 1636 sen mukaan, kuinka

220
00:09:38,960 --> 00:09:41,400
me täytäntöönpanossa tietorakennetta.

221
00:09:41,400 --> 00:09:43,177
Joten se oli toivottavasti yksinkertaista.

222
00:09:43,177 --> 00:09:44,760
Aiomme tehdä kaksi lisäyksiä.

223
00:09:44,760 --> 00:09:50,060
Ja toivottavasti se tulee auttaa
katso tämä tapahtuu kahdesti.

224
00:09:50,060 --> 00:09:52,210
>> Nyt, aseta toisen yliopiston.

225
00:09:52,210 --> 00:09:54,630
Katsotaanpa lisätä Yale tähän trie.

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

227
00:09:57,037 --> 00:09:58,870
Niin me alkavat
root, kuten aina.

228
00:09:58,870 --> 00:09:59,890
Ja asetamme läpikulun osoitin.

229
00:09:59,890 --> 00:10:01,624
Aiomme käyttää tätä liikkua.

230
00:10:01,624 --> 00:10:03,790
Ensimmäinen asia haluamme
tehdä, on mennä alas 1 polku.

231
00:10:03,790 --> 00:10:05,830
Se on ensimmäinen merkki tärkeimmistä.

232
00:10:05,830 --> 00:10:08,420
Onneksi kuitenkin, emme
tarvitse tehdä mitään työtä tällä kertaa.

233
00:10:08,420 --> 00:10:09,919
1 polku on jo selvitetty.

234
00:10:09,919 --> 00:10:13,520
Poistin sen aiemmin, kun
oli lisäämällä Harvardin klo 1636.

235
00:10:13,520 --> 00:10:18,090
Joten en voi turvallisesti liikkua
alas 1 ja vain mennä sinne.

236
00:10:18,090 --> 00:10:20,150
Jos voi liikkua alaspäin 1.

237
00:10:20,150 --> 00:10:22,930
>> Nyt kuitenkin haluan mennä 7.

238
00:10:22,930 --> 00:10:24,280
Olen avannut tien 6.

239
00:10:24,280 --> 00:10:27,050
Tiedän, että voin turvallisesti
jatka alas 6 polku.

240
00:10:27,050 --> 00:10:29,220
Mutta minun täytyy edetä 7 tiellä.

241
00:10:29,220 --> 00:10:30,580
Joten mitä minun pitää tehdä?

242
00:10:30,580 --> 00:10:35,070
No, aivan kuten ennen, minun pitää vain
tyhjentää portille, saada pois tieltä,

243
00:10:35,070 --> 00:10:38,740
ja rakentaa uusi solmun 7 polku.

244
00:10:38,740 --> 00:10:40,250
Juuri näin.

245
00:10:40,250 --> 00:10:42,930
>> Joten nyt olen siirtynyt 1 ja sitten 7.

246
00:10:42,930 --> 00:10:45,550
Ja nyt huomaa, olen tavallaan
on tästä uudesta subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Kaikki muu 16
on, en välitä.

249
00:10:49,260 --> 00:10:50,720
En tee 16 mitään.

250
00:10:50,720 --> 00:10:51,750
Teen 17 juttuja.

251
00:10:51,750 --> 00:10:58,380
>> Joten nyt alkaen 17, minun täytyy
eräänlainen innovaatio täällä.

252
00:10:58,380 --> 00:11:00,462
Seuraava numero avaimeni on 0.

253
00:11:00,462 --> 00:11:01,670
En selvästikään saa mistään.

254
00:11:01,670 --> 00:11:02,628
Olen juuri rakennettu tämän solmun.

255
00:11:02,628 --> 00:11:04,550
Tiedän siis, ei ole
polut eteenpäin täältä.

256
00:11:04,550 --> 00:11:06,370
Joten minun täytyy tehdä sellaisen itse.

257
00:11:06,370 --> 00:11:09,360
>> Joten en malloc uusi solmu
ja on 0 kohta siellä.

258
00:11:09,360 --> 00:11:12,770
Ja sitten vielä kerran, minä malloc
uusi solmu ja on yksi piste siellä.

259
00:11:12,770 --> 00:11:15,870
Jälleen olen loppuun avaimeni, 1701.

260
00:11:15,870 --> 00:11:18,472
Joten katson alas ja minä spray maalata Yale.

261
00:11:18,472 --> 00:11:19,680
Se on nimi tämän solmun.

262
00:11:19,680 --> 00:11:24,660
>> Ja nyt jos joskus täytyy nähdä, jos Yale
on tässä trien, aloitan juuresta,

263
00:11:24,660 --> 00:11:27,060
Menen alas 1701, ja katsoa alas.

264
00:11:27,060 --> 00:11:30,030
Ja jos näen Yale spray
maalattu kiinni maahan, sitten

265
00:11:30,030 --> 00:11:32,200
Tiedän Yale olemassa tässä trie.

266
00:11:32,200 --> 00:11:32,950
Tehdään yksi.

267
00:11:32,950 --> 00:11:36,430
Katsotaanpa lisätä Dartmouth tähän
trie, joka perustettiin vuonna 1769.

268
00:11:36,430 --> 00:11:37,750
>> Aloita juureen uudelleen.

269
00:11:37,750 --> 00:11:39,445
Ensimmäinen numero minun avain on 1.

270
00:11:39,445 --> 00:11:40,820
Voin turvallisesti siirtää sille tielle.

271
00:11:40,820 --> 00:11:42,400
Joka on jo olemassa.

272
00:11:42,400 --> 00:11:44,040
Seuraava numero minun avain on 7.

273
00:11:44,040 --> 00:11:45,890
Voin turvallisesti siirtää sille tielle.

274
00:11:45,890 --> 00:11:47,540
Se on olemassa myös.

275
00:11:47,540 --> 00:11:49,000
>> Seuraava on 6.

276
00:11:49,000 --> 00:11:52,860
Sieltä, mistä minä tällä hetkellä olen
keltainen tuossa keskellä solmu,

277
00:11:52,860 --> 00:11:56,060
6 on lukittu pois.

278
00:11:56,060 --> 00:11:58,830
Jos haluan mennä sille tielle,
Minun täytyy rakentaa sen itse.

279
00:11:58,830 --> 00:12:02,250
Niin minä malloc uusi solmu
ja on 6 kohta siellä.

280
00:12:02,250 --> 00:12:04,250
Ja sitten taas, olen
paahtava uusia polkuja täällä.

281
00:12:04,250 --> 00:12:10,750
>> Joten en malloc uusi solmu niin että
että node-- polkumääräinformaation 9-- ja sitten nyt

282
00:12:10,750 --> 00:12:13,584
jos matkustan 1769, ja odotan alas.

283
00:12:13,584 --> 00:12:15,500
Ei ole mitään tällä hetkellä
spray maalattu siellä.

284
00:12:15,500 --> 00:12:16,930
Osaan kirjoittaa Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Ja olen asetettu
Dartmouth osaksi trie.

286
00:12:20,710 --> 00:12:23,450
>> Niin, että lisäämällä
asiat oikeisiin trie.

287
00:12:23,450 --> 00:12:25,384
Nyt haluamme etsiä asioita.

288
00:12:25,384 --> 00:12:27,050
Miten etsiä asioita trie?

289
00:12:27,050 --> 00:12:29,170
No, se on melko sama ajatus.

290
00:12:29,170 --> 00:12:33,620
Nyt vain käyttää numeroa avaimen
nähdä, jos voimme navigoida juuresta

291
00:12:33,620 --> 00:12:37,170
missä haluamme mennä trie.

292
00:12:37,170 --> 00:12:41,620
>> Jos me osuma umpikujaan missään vaiheessa, sitten
me tiedämme, että tämä osa ei ole olemassa

293
00:12:41,620 --> 00:12:44,500
tai muuta, joka polku olisi
on jo selvitetty.

294
00:12:44,500 --> 00:12:45,930
Jos teemme sen aina
Lopulta kaikki meidän täytyy tehdä

295
00:12:45,930 --> 00:12:48,471
on halveksua ja katso jos se on
elementti etsimme.

296
00:12:48,471 --> 00:12:49,335
Jos se on, menestys.

297
00:12:49,335 --> 00:12:52,610
Jos se ei ole, epäonnistua.

298
00:12:52,610 --> 00:12:54,940
>> Joten etsi
Harvardin tässä trie.

299
00:12:54,940 --> 00:12:56,020
Aloitamme juureen.

300
00:12:56,020 --> 00:12:58,228
Ja taas me aiomme
luoda läpikäynti osoitin

301
00:12:58,228 --> 00:12:59,390
teemme liikkuu meille.

302
00:12:59,390 --> 00:13:02,080
Juurineen tiedämme, että
Ensinnäkin meidän täytyy mennä on 1,

303
00:13:02,080 --> 00:13:03,390
voimme tehdä sen?

304
00:13:03,390 --> 00:13:03,982
Kyllä me voimme.

305
00:13:03,982 --> 00:13:04,690
Jos turvallisesti olemassa.

306
00:13:04,690 --> 00:13:06,660
Voimme mennä sinne.

307
00:13:06,660 --> 00:13:08,440
>> Nyt, seuraava paikka meidän täytyy mennä on 6.

308
00:13:08,440 --> 00:13:10,557
Onko 6 polku olemassa täältä?

309
00:13:10,557 --> 00:13:11,140
Joo, se tekee.

310
00:13:11,140 --> 00:13:12,690
Voimme mennä alas 6 polku.

311
00:13:12,690 --> 00:13:13,905
Ja päädymme täällä.

312
00:13:13,905 --> 00:13:16,130
>> Voimmeko mennä alas 3 polku täällä?

313
00:13:16,130 --> 00:13:18,450
No, kuten on käynyt ilmi,
kyllä, että on olemassa myös.

314
00:13:18,450 --> 00:13:20,790
Ja voimme päästä 6 polku täällä?

315
00:13:20,790 --> 00:13:21,982
Kyllä me voimme.

316
00:13:21,982 --> 00:13:24,002
>> Emme ole aivan vastattu
kysymys vielä.

317
00:13:24,002 --> 00:13:25,710
Vielä yksi
vaihe, joka on nyt

318
00:13:25,710 --> 00:13:28,520
meidän on tarkasteltava alas ja
onko se actually--

319
00:13:28,520 --> 00:13:32,660
jos etsimme Harvard, että
mitä löydämme, kun olemme kata avain?

320
00:13:32,660 --> 00:13:35,430
Esimerkissä käytämme täällä,
vuodet ovat aina neljä numeroa.

321
00:13:35,430 --> 00:13:40,280
Mutta käytössä voi olla esimerkiksi silloin,
tallennat sanakirjan sanoja.

322
00:13:40,280 --> 00:13:44,060
>> Ja niin sen sijaan, että 10 osoittimia
minun paikka, saatat olla 26.

323
00:13:44,060 --> 00:13:46,040
Yksi kutakin kirjaimen.

324
00:13:46,040 --> 00:13:50,350
Ja joitakin sanoja kuten lepakko,
joka on osajoukko erän, esimerkiksi.

325
00:13:50,350 --> 00:13:53,511
Ja joten vaikka saat
lopussa näppäintä ja näytät alas,

326
00:13:53,511 --> 00:13:55,260
et ehkä nähdä, mitä
etsit.

327
00:13:55,260 --> 00:13:58,500
>> Joten sinulla on aina kulkea
koko polku ja sitten

328
00:13:58,500 --> 00:14:01,540
jos olisit onnistuneesti pystynyt
kulkemaan koko polkua,

329
00:14:01,540 --> 00:14:03,440
katso alas ja tee yksi lopullisen vahvistuksen.

330
00:14:03,440 --> 00:14:05,120
Sitäkö etsin?

331
00:14:05,120 --> 00:14:07,740
No, katson alas käynnistyksen jälkeen
huipulla ja menee 1636.

332
00:14:07,740 --> 00:14:08,240
Odotan alas.

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

334
00:14:09,400 --> 00:14:11,689
Joten, kyllä, onnistuin.

335
00:14:11,689 --> 00:14:13,980
Mitä jos, mitä etsin
ei ole trien, vaikka.

336
00:14:13,980 --> 00:14:17,200
Mitä jos Etsin Princeton,
joka on perustettu vuonna 1746.

337
00:14:17,200 --> 00:14:20,875
Ja niin 1746 tulee minun avain
selata trie.

338
00:14:20,875 --> 00:14:22,040
No, aloitan juuresta.

339
00:14:22,040 --> 00:14:24,760
Ja ensimmäinen paikka haluan
että menee alas 1 polku.

340
00:14:24,760 --> 00:14:25,590
Voiko sen tehdä?

341
00:14:25,590 --> 00:14:26,490
Kyllä voin.

342
00:14:26,490 --> 00:14:28,730
>> Voinko mennä alas 7 polku sieltä?

343
00:14:28,730 --> 00:14:29,230
Joo, voin.

344
00:14:29,230 --> 00:14:30,750
Joka on olemassa myös.

345
00:14:30,750 --> 00:14:32,460
Mutta voin mennä alas 4 polku täällä?

346
00:14:32,460 --> 00:14:35,550
Se on kuin kysyisi kysymyksen, voi
Olen edetä alas että pienellä aukiolla

347
00:14:35,550 --> 00:14:37,114
että olen korostettu keltaisella?

348
00:14:37,114 --> 00:14:38,030
Siellä ei ole mitään.

349
00:14:38,030 --> 00:14:38,610
Oikea.

350
00:14:38,610 --> 00:14:41,310
>> Ei ole tie eteenpäin alas 4 polku.

351
00:14:41,310 --> 00:14:46,480
Jos Princeton oli tässä trien, että 4
olisi raivattu meille jo.

352
00:14:46,480 --> 00:14:49,130
Ja niin tässä vaiheessa
olemme päätynyt umpikujaan.

353
00:14:49,130 --> 00:14:50,250
Emme voi mennä pidemmälle.

354
00:14:50,250 --> 00:14:53,440
Ja jotta voimme sanoa lopullisesti, ei.

355
00:14:53,440 --> 00:14:56,760
Princeton ei ole tässä trie.

356
00:14:56,760 --> 00:14:58,860
>> Mitä tämä kaikki tarkoittaa?

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

358
00:14:59,360 --> 00:15:01,000
Siellä on paljon täällä.

359
00:15:01,000 --> 00:15:02,500
On viitteitä koko paikka.

360
00:15:02,500 --> 00:15:04,249
Ja kuten näette
vain kaaviosta,

361
00:15:04,249 --> 00:15:07,010
siellä on paljon solmuja, että
ovat sellaisia ​​lentelee.

362
00:15:07,010 --> 00:15:13,480
Mutta huomaa aina halusimme
onko jotain oli trien,

363
00:15:13,480 --> 00:15:15,000
meillä oli vain tehdä 4 liikkuu.

364
00:15:15,000 --> 00:15:17,208
>> Joka kerta halusimme
aseta jotain trien,

365
00:15:17,208 --> 00:15:20,440
meidän on tehtävä 4 liikkuu, mahdollisesti
mallocing joitakin juttuja matkan varrella.

366
00:15:20,440 --> 00:15:23,482
Mutta kuten näimme kun lisätään
Dartmouth osaksi trie,

367
00:15:23,482 --> 00:15:25,940
joskus jotkut polku
saattaa olla jo raivattu meille.

368
00:15:25,940 --> 00:15:30,520
Ja niin meidän trie saa isompi ja
isompi, meillä on tehdä vähemmän työtä joka kerta

369
00:15:30,520 --> 00:15:32,270
lisätä uusia asioita
koska olemme jo

370
00:15:32,270 --> 00:15:35,746
rakennettu paljon väli-
oksat matkan varrella.

371
00:15:35,746 --> 00:15:38,370
Jos me vain koskaan tarvitse katsoa
4 asioita, 4 on vain vakio.

372
00:15:38,370 --> 00:15:41,750
Me todella on sellainen lähestyy
vakio kerran asennus

373
00:15:41,750 --> 00:15:44,501
ja jatkuva ajan haku.

374
00:15:44,501 --> 00:15:47,500
Kompromissi, tietenkin on, että
Tämän trie, kuten voitte luultavasti kertoa,

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

376
00:15:49,030 --> 00:15:51,040
Jokainen näistä solmuista
vie paljon tilaa.

377
00:15:51,040 --> 00:15:52,090
>> Mutta se on kompromissi.

378
00:15:52,090 --> 00:15:55,260
Jos haluamme todella nopeasti
lisäys, todella nopea poisto,

379
00:15:55,260 --> 00:15:59,630
ja todella nopea lookup, meidän on
on paljon tietoa lentelee.

380
00:15:59,630 --> 00:16:03,590
Meidän on varattu paljon tilaa
ja muisti, että tietojen rakenne

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

382
00:16:04,290 --> 00:16:05,415
>> Ja niin se on kompromissi.

383
00:16:05,415 --> 00:16:07,310
Mutta se Taisimme
ehkä löytänyt sen.

384
00:16:07,310 --> 00:16:09,560
Olisimme havainneet, että
pyhä Graal tietorakenteiden

385
00:16:09,560 --> 00:16:12,264
kanssa nopea lisäys,
poistetaan, ja haku.

386
00:16:12,264 --> 00:16:14,430
Ja ehkä tämä on
asianmukaiset tiedot rakenne

387
00:16:14,430 --> 00:16:18,890
käyttää mitä tahansa tietoa
yritämme myymälä.

388
00:16:18,890 --> 00:16:21,860
Olen Doug Lloyd, tämä on CS50.

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