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

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Dus we hebben tippen dichterbij
en dichter die heilige graal van data

4
00:00:08,550 --> 00:00:13,050
structuren, die we kunnen invoegen
in, verwijderen uit en kijk omhoog

5
00:00:13,050 --> 00:00:15,440
in constante tijd.

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

7
00:00:16,270 --> 00:00:17,280
Dat is een soort van het doel.

8
00:00:17,280 --> 00:00:19,720
We willen in staat zijn om te doen
dingen heel, heel snel.

9
00:00:19,720 --> 00:00:22,580
>> Hebben we hier toen het gevonden
we praten over pogingen?

10
00:00:22,580 --> 00:00:23,670
Nou, laten we eens een kijkje nemen.

11
00:00:23,670 --> 00:00:25,628
Daarom hebben we een aantal gezien
verschillende datastructuren

12
00:00:25,628 --> 00:00:28,680
dat omgaan met het in kaart brengen van de
zogenaamde sleutelwaarde paren,

13
00:00:28,680 --> 00:00:32,080
in kaart brengen van een stukje data
sommige andere stuk van de gegevens

14
00:00:32,080 --> 00:00:36,020
zodat we weten waar te vinden
informatie in de structuur.

15
00:00:36,020 --> 00:00:40,060
>> Dus voor array, bijvoorbeeld de
sleutel is het element index of matrix

16
00:00:40,060 --> 00:00:42,600
location 0 of matrix 1 enzovoort.

17
00:00:42,600 --> 00:00:46,140
En de waarde van de data
dat bestaat op die locatie.

18
00:00:46,140 --> 00:00:48,550
Dus wat is opgeslagen in serie 0?

19
00:00:48,550 --> 00:00:54,290
Wat wordt opgeslagen in reeks 1 versus net
0 en 1, die zou de sleutels.

20
00:00:54,290 --> 00:00:56,360
>> Met een hash table is het
soort van hetzelfde idee.

21
00:00:56,360 --> 00:01:00,690
Met een hash tafel, hebben we dit hash
functie die hash codes genereert.

22
00:01:00,690 --> 00:01:03,670
Dus de sleutel is de hash-code van de data.

23
00:01:03,670 --> 00:01:06,530
En de waarde, met name
spraken we over chaining

24
00:01:06,530 --> 00:01:10,590
in de video op hashtabellen,
is dat gelinkte lijst van gegevens

25
00:01:10,590 --> 00:01:12,550
dat hashes van die hash-code.

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

27
00:01:14,050 --> 00:01:16,050
Wat over een andere aanpak
Deze methode, hoewel?

28
00:01:16,050 --> 00:01:21,000
Wat te denken van een methode waarbij de
toets wordt gegarandeerd uniek,

29
00:01:21,000 --> 00:01:25,410
in tegenstelling tot een hash tafel, waar we konden
eindigen met twee gegevens

30
00:01:25,410 --> 00:01:27,200
met dezelfde hashcode.

31
00:01:27,200 --> 00:01:30,020
En dan hebben we te maken met
die door een of meer indringende

32
00:01:30,020 --> 00:01:33,340
bij voorkeur chaining om dat probleem op te lossen.

33
00:01:33,340 --> 00:01:37,520
>> Dus nu kunnen we garanderen
dat onze belangrijkste uniek zal zijn.

34
00:01:37,520 --> 00:01:39,690
En wat als onze waarde was
gewoon iets wat zo makkelijk

35
00:01:39,690 --> 00:01:44,080
als ware en valse die ons vertelt of
of niet dat stukje informatie

36
00:01:44,080 --> 00:01:45,610
bestaat in de constructie?

37
00:01:45,610 --> 00:01:48,180
Een Booleaanse kan zo simpel zijn als een beetje te zijn.

38
00:01:48,180 --> 00:01:52,660
Realistisch is het waarschijnlijk een
byte meer kans dan een beetje.

39
00:01:52,660 --> 00:01:55,410
Maar dat is een stuk kleiner dan
opslaan misschien een 50-tekenreeks,

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

41
00:01:57,360 --> 00:02:02,210
>> Dus probeert, vergelijkbaar met tabellen hash,
die samen arrays en gelinkte lijst,

42
00:02:02,210 --> 00:02:05,790
probeert combineren arrays
structuren en pointers

43
00:02:05,790 --> 00:02:08,509
samen om gegevens in
een interessante manier die

44
00:02:08,509 --> 00:02:11,550
behoorlijk verschillend van
alles wat we tot nu toe gezien.

45
00:02:11,550 --> 00:02:16,750
Nu gebruiken we de gegevens als een routekaart
deze gegevensstructuur te navigeren.

46
00:02:16,750 --> 00:02:18,710
En als we kunnen volgen
de roadmap, als we kunnen

47
00:02:18,710 --> 00:02:22,390
Volg de gegevens van
begin tot eind, zullen we

48
00:02:22,390 --> 00:02:24,945
weten of deze data
bestaan ​​in de trie.

49
00:02:24,945 --> 00:02:28,310
>> En als we niet kunnen volgen de kaart
van betekenis te eindigen bij alle,

50
00:02:28,310 --> 00:02:30,600
de gegevens niet bestaan.

51
00:02:30,600 --> 00:02:32,890
Ook hier zijn de sleutels
gegarandeerd uniek.

52
00:02:32,890 --> 00:02:36,020
En dus in tegenstelling tot een hash-tabel, zullen we nooit
te behandelen botsingen here.

53
00:02:36,020 --> 00:02:39,090
En geen twee stukken van de gegevens
precies dezelfde roadmap

54
00:02:39,090 --> 00:02:40,530
tenzij die data identiek.

55
00:02:40,530 --> 00:02:44,580
>> Als we voegen John, dan
we op zoek naar John.

56
00:02:44,580 --> 00:02:47,430
Dat zijn twee identieke stukken
data, rechts, zijn we op zoek door.

57
00:02:47,430 --> 00:02:49,880
Maar anders, elke
twee stukken gegevens

58
00:02:49,880 --> 00:02:52,750
gegarandeerd unieke roadmaps hebben
door deze gegevensstructuur.

59
00:02:52,750 --> 00:02:56,210
En we gaan om een ​​kijkje te nemen
een visuele van deze in slechts een moment.

60
00:02:56,210 --> 00:02:58,810
>> We zullen dit doen door te proberen
maak een nieuwe datastructuur,

61
00:02:58,810 --> 00:03:00,564
in kaart brengen van de volgende belangrijke waarde paren.

62
00:03:00,564 --> 00:03:03,480
In dit geval, we gaan niet te gebruiken
iets eenvoudigs als een Boolean.

63
00:03:03,480 --> 00:03:06,200
We zullen eigenlijk de snaar slaan.

64
00:03:06,200 --> 00:03:08,690
En die string gaat
is de naam van een universiteit.

65
00:03:08,690 --> 00:03:12,140
>> En de sleutel is naar het jaar
toen die universiteit werd gesticht.

66
00:03:12,140 --> 00:03:15,380
Al jaren voor de universiteiten
zullen worden vier cijfers.

67
00:03:15,380 --> 00:03:19,840
En dus zullen we die vier cijfers gebruiken
navigeren door deze data structuur.

68
00:03:19,840 --> 00:03:22,270
En we zullen zien, nogmaals, hoe
wij dat doen in slechts een seconde.

69
00:03:22,270 --> 00:03:25,110
>> Aan het einde van het pad,
zullen we de naam te zien

70
00:03:25,110 --> 00:03:30,250
van de universiteit die overeenkomt
deze sleutel, die vier cijfers.

71
00:03:30,250 --> 00:03:34,390
Het basisidee achter een trie
is wij een centrale route.

72
00:03:34,390 --> 00:03:35,640
Zo denken als een boom.

73
00:03:35,640 --> 00:03:39,211
En dit is vergelijkbaar in de spelling
en qua concept met een boom.

74
00:03:39,211 --> 00:03:41,460
Over het algemeen wanneer we denken over
bomen in de echte wereld,

75
00:03:41,460 --> 00:03:44,090
hebben ze een wortel die in het
grond en ze omhoog te laten groeien

76
00:03:44,090 --> 00:03:46,830
en ze hebben vestigingen
en ze hebben bladeren.

77
00:03:46,830 --> 00:03:49,450
En eigenlijk het idee
een trie is precies hetzelfde,

78
00:03:49,450 --> 00:03:51,755
behalve dat wortel wordt verankerd
ergens in de lucht.

79
00:03:51,755 --> 00:03:53,130
De bladeren staan ​​onderaan.

80
00:03:53,130 --> 00:03:55,750
>> Dus het is net zoiets als het nemen van een boom
en gewoon flipping het ondersteboven.

81
00:03:55,750 --> 00:03:56,880
Maar er zijn nog takken.

82
00:03:56,880 --> 00:03:59,463
En die zouden onze wegen,
die zullen onze verbindingen

83
00:03:59,463 --> 00:04:02,220
van de wortel naar de bladeren.

84
00:04:02,220 --> 00:04:04,200
In dit geval, die
paden, die takken

85
00:04:04,200 --> 00:04:08,490
zijn gelabeld met cijfers die ons vertellen
welke weg te gaan van waar we zijn.

86
00:04:08,490 --> 00:04:11,800
>> Als we een 0, gaan we naar beneden deze tak,
als we een 1, gaan we naar beneden deze tak,

87
00:04:11,800 --> 00:04:12,900
enzovoort, enzovoort.

88
00:04:12,900 --> 00:04:14,060
Nou ja, wat betekent dit?

89
00:04:14,060 --> 00:04:16,519
Nou, dat betekent dat
op elk knooppunt

90
00:04:16,519 --> 00:04:19,260
en elk knooppunt in het
middelste en elke tak,

91
00:04:19,260 --> 00:04:23,020
Er zijn 10 mogelijke
plaatsen die we kunnen gaan.

92
00:04:23,020 --> 00:04:27,690
Zo zijn er 10 pointers
vanaf elke locatie.

93
00:04:27,690 --> 00:04:30,610
>> En dit is waar probeert een kan krijgen
beetje intimiderend voor iemand

94
00:04:30,610 --> 00:04:34,460
wie heeft niet veel
ervaring in de informatica voor.

95
00:04:34,460 --> 00:04:35,960
Maar probeert zijn echt pretty awesome.

96
00:04:35,960 --> 00:04:37,793
En als je de
kans om te werken met hen

97
00:04:37,793 --> 00:04:40,420
en u bent bereid om te graven in bent
en experimenteren met hen,

98
00:04:40,420 --> 00:04:44,234
ze zijn echt heel interessant
datastructuren te werken.

99
00:04:44,234 --> 00:04:46,900
Als we willen een element in te voegen
in de Trie, alles wat we moeten doen

100
00:04:46,900 --> 00:04:51,360
is het bouwen van de juiste pad
van de wortel naar het blad.

101
00:04:51,360 --> 00:04:55,390
Hier is wat elke stap langs
de weg eruit zou kunnen zien.

102
00:04:55,390 --> 00:04:59,660
We gaan een nieuwe gegevens te definiëren
structuur een nieuwe node een trie.

103
00:04:59,660 --> 00:05:02,560
>> En de binnenkant van die gegevens
structuur zijn er twee stukken.

104
00:05:02,560 --> 00:05:05,460
We gaan naar de winkel
de naam van een universiteit.

105
00:05:05,460 --> 00:05:09,410
En we gaan slaan
een array van pointers

106
00:05:09,410 --> 00:05:12,190
met andere knooppunten van hetzelfde type.

107
00:05:12,190 --> 00:05:14,780
Dus, nogmaals, dit is dat soort
van begrip overal

108
00:05:14,780 --> 00:05:18,567
wij zijn, wij bij 10 mogelijk
plaatsen waar we kunnen gaan.

109
00:05:18,567 --> 00:05:20,150
Als we een 0, gaan we naar beneden deze tak.

110
00:05:20,150 --> 00:05:22,690
Als we een 1, deze tak,
en zo voort en zo voort en zo verder.

111
00:05:22,690 --> 00:05:25,160
Als we zeggen 9, gaan we naar beneden deze tak.

112
00:05:25,160 --> 00:05:28,220
Dus op elk knooppunt,
we kunnen gaan 10 mogelijke plaatsen.

113
00:05:28,220 --> 00:05:35,740
Dus elk knooppunt moet 10 pointers bevat
met andere knooppunten, met 10 andere knooppunten.

114
00:05:35,740 --> 00:05:39,810
>> En de gegevens die wij opslaan is
alleen de naam van de universiteit.

115
00:05:39,810 --> 00:05:41,060
Dus laten we bouwen aan een trie.

116
00:05:41,060 --> 00:05:44,860
Laten we voegen een paar
items in onze trie.

117
00:05:44,860 --> 00:05:46,740
Dus op de top,
dit is onze root node.

118
00:05:46,740 --> 00:05:49,740
Dit is waarschijnlijk iets te zijn
je gaat verklaren wereldwijd.

119
00:05:49,740 --> 00:05:53,450
En je gaat om wereldwijd te behouden
een pointer naar dit knooppunt altijd.

120
00:05:53,450 --> 00:05:55,360
>> Je gaat zeggen,
wortel gelijk, en je bent

121
00:05:55,360 --> 00:05:57,580
gaat jezelf malloc trie node.

122
00:05:57,580 --> 00:05:59,850
En je nooit
wortel aan te raken.

123
00:05:59,850 --> 00:06:02,300
Elke keer dat u wilt
start het navigeren door,

124
00:06:02,300 --> 00:06:05,802
u een andere pointer ingesteld
gelijk aan wortel, zoals trav,

125
00:06:05,802 --> 00:06:07,760
die het voorbeeld I
gebruiken in veel van mijn video's

126
00:06:07,760 --> 00:06:11,090
hier op stapels en wachtrijen
en lijsten enzovoort.

127
00:06:11,090 --> 00:06:13,320
>> U stelt een andere pointer
riep trav voor traversal.

128
00:06:13,320 --> 00:06:15,890
En je trav gebruiken om te navigeren
door de gegevensstructuur.

129
00:06:15,890 --> 00:06:17,500
Dus laten we zien hoe dit eruit zou kunnen zien.

130
00:06:17,500 --> 00:06:19,880
Dus nu, wat
doet een knooppunt eruit?

131
00:06:19,880 --> 00:06:22,920
Nou, net zoals onze gegevens
structuur verklaring aangegeven,

132
00:06:22,920 --> 00:06:26,906
We hebben een string, die
in dit geval is leeg.

133
00:06:26,906 --> 00:06:27,780
Er is hier niets.

134
00:06:27,780 --> 00:06:29,550
>> En een array van 10 pointers.

135
00:06:29,550 --> 00:06:31,790
En op dit moment, maar we
hebben 1 knooppunt in dit trie.

136
00:06:31,790 --> 00:06:33,110
Er is niets anders in.

137
00:06:33,110 --> 00:06:36,020
Dus al 10 van die
pointers punt op null.

138
00:06:36,020 --> 00:06:38,090
Dat is wat de rode geeft.

139
00:06:38,090 --> 00:06:39,500
>> Laten plaatst de string Harvard.

140
00:06:39,500 --> 00:06:41,999
Laten we steek de Universiteit van
Harvard in deze trie, die

141
00:06:41,999 --> 00:06:43,940
werd opgericht in het jaar 1636.

142
00:06:43,940 --> 00:06:48,220
We willen de sleutel te gebruiken,
1636, om ons te vertellen waar we zijn

143
00:06:48,220 --> 00:06:50,140
gaat slaan Harvard in de Trie.

144
00:06:50,140 --> 00:06:51,470
Nu, hoe kunnen we dat doen?

145
00:06:51,470 --> 00:06:52,886
>> Het zou er ongeveer zo uitzien.

146
00:06:52,886 --> 00:06:54,160
We beginnen bij de wortel.

147
00:06:54,160 --> 00:06:56,920
En we hebben deze 10 plaatsen waar we kunnen gaan.

148
00:06:56,920 --> 00:06:59,900
De wortel is net als elke
ander knooppunt van de trie.

149
00:06:59,900 --> 00:07:02,850
Er zijn 10 plaatsen waar we kunnen gaan vanaf hier.

150
00:07:02,850 --> 00:07:07,215
>> Waar doen we waarschijnlijk willen
te gaan als de sleutel is 1636?

151
00:07:07,215 --> 00:07:08,340
Er is echt twee opties.

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

153
00:07:08,450 --> 00:07:10,825
We kunnen de sleutel uit te bouwen
rechts naar links en begin met 6.

154
00:07:10,825 --> 00:07:14,000
Of we kunnen de sleutel uit te bouwen
links naar rechts en beginnen 1.

155
00:07:14,000 --> 00:07:16,140
>> Het is waarschijnlijk meer
intuïtief als een menselijk wezen

156
00:07:16,140 --> 00:07:18,110
te begrijpen we zullen
Ga gewoon links naar rechts.

157
00:07:18,110 --> 00:07:21,140
En dus als ik wilt invoegen
Harvard in deze trie,

158
00:07:21,140 --> 00:07:23,560
Ik wil waarschijnlijk om te beginnen
door te beginnen bij de wortel,

159
00:07:23,560 --> 00:07:25,720
kijken naar mijn 10 opties
voor me, en zeggen

160
00:07:25,720 --> 00:07:28,700
Ik wil gaan op de 1 pad.

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

162
00:07:29,700 --> 00:07:31,810
>> Nu, 1 pad is momenteel nul.

163
00:07:31,810 --> 00:07:35,920
Dus als ik wil om verder te gaan onderaan die weg
dit element te voegen in de trie,

164
00:07:35,920 --> 00:07:42,040
Ik moet een nieuw knooppunt malloc, hebben 1
wijzen daar, en dan ben ik goed om te gaan.

165
00:07:42,040 --> 00:07:46,460
>> Dus ik eigenlijk ben op een
punt waar ik sta

166
00:07:46,460 --> 00:07:50,270
aan de wortel van de boom of het
trie en er zijn 10 vestigingen.

167
00:07:50,270 --> 00:07:52,260
Maar elke tak heeft een
poort aan de voorkant ervan.

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

169
00:07:53,060 --> 00:07:54,850
Want er is niets anders is er.

170
00:07:54,850 --> 00:07:56,522
Geen veilige doorgang.

171
00:07:56,522 --> 00:07:58,980
Dat betekent dat er niets
neer een van deze takken.

172
00:07:58,980 --> 00:08:02,532
Als ik wil om te gaan bouwen
iets, ik wil de poort te verwijderen.

173
00:08:02,532 --> 00:08:04,490
Ik wil naar de gate te verwijderen
tegenover nummer 1.

174
00:08:04,490 --> 00:08:05,698
En ik wil lopen dat.

175
00:08:05,698 --> 00:08:08,060
En ik wil bouwen
een andere plek voor mij om te gaan.

176
00:08:08,060 --> 00:08:09,470
>> En dat is wat ik hier heb gedaan.

177
00:08:09,470 --> 00:08:11,430
Dus 1 niet meer wijst op null.

178
00:08:11,430 --> 00:08:13,830
Ik heb gezegd dat het veilig is om hier beneden te gaan nu.

179
00:08:13,830 --> 00:08:15,789
Ik bouwde een ander knooppunt.

180
00:08:15,789 --> 00:08:18,330
En toen ik naar dat knooppunt, ik
nog een beslissing te maken.

181
00:08:18,330 --> 00:08:20,890
Waar ga ik heen?

182
00:08:20,890 --> 00:08:22,700
>> Nou, ik heb nu al beneden de 1 gegaan.

183
00:08:22,700 --> 00:08:24,470
Dus nu wil ik waarschijnlijk naar beneden gaan de 6.

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

185
00:08:24,970 --> 00:08:27,100
Nogmaals, ik heb 10 locaties ik kan kiezen.

186
00:08:27,100 --> 00:08:30,060
Dus laten we nu naar beneden nummer 6.

187
00:08:30,060 --> 00:08:32,280
Dus ik duidelijk de poort
tegenover nummer 6.

188
00:08:32,280 --> 00:08:33,250
En ik loop daar beneden.

189
00:08:33,250 --> 00:08:34,580
En ik bouwen een ander knooppunt.

190
00:08:34,580 --> 00:08:37,630
En ik heb een ander knooppunt bereikt.

191
00:08:37,630 --> 00:08:40,289
>> Nogmaals, ik heb 10 keuzes
want waar ik kan gaan.

192
00:08:40,289 --> 00:08:42,799
Ik ben verhuisd 1-6.

193
00:08:42,799 --> 00:08:44,215
Dus nu wil ik waarschijnlijk naar 3.

194
00:08:44,215 --> 00:08:45,381
3, er is nergens ik kan gaan.

195
00:08:45,381 --> 00:08:48,980
Dus ik moet de weg vrij
en bouwen mezelf een nieuwe ruimte.

196
00:08:48,980 --> 00:08:50,870
En vervolgens van 3, waar wil ik heen?

197
00:08:50,870 --> 00:08:52,450
Ik wil naar beneden 6 gaan.

198
00:08:52,450 --> 00:08:54,770
>> En, nogmaals, ik moest
de weg vrij om het te doen.

199
00:08:54,770 --> 00:08:59,179
Dus nu heb ik mijn sleutel gebruikt om in te voegen creëren
knooppunten en start deze trie bouwen.

200
00:08:59,179 --> 00:09:00,220
Ik ben begonnen bij de wortel.

201
00:09:00,220 --> 00:09:03,666
Ik heb naar beneden 1636 gegaan.

202
00:09:03,666 --> 00:09:05,540
En nu ben ik op de bodem
daar op dat knooppunt.

203
00:09:05,540 --> 00:09:06,610
En je zou kunnen
Zie het op uw scherm.

204
00:09:06,610 --> 00:09:07,735
>> Het is geel gemarkeerd.

205
00:09:07,735 --> 00:09:10,020
Dat is waar ik nu ben.

206
00:09:10,020 --> 00:09:11,300
Mijn sleutel wordt gedaan.

207
00:09:11,300 --> 00:09:13,030
Ik heb elke positie in mijn sleutel uitgeput.

208
00:09:13,030 --> 00:09:15,040
Dus ik kan niet verder gaan.

209
00:09:15,040 --> 00:09:17,720
Dus op dit punt, alles wat ik
echt nodig om te doen is te zeggen, OK.

210
00:09:17,720 --> 00:09:18,990
Het is net zoiets als kijken
naar de grond,

211
00:09:18,990 --> 00:09:21,115
als je mikt
jezelf als dit soort pad

212
00:09:21,115 --> 00:09:22,350
met verschillende verbindingen.

213
00:09:22,350 --> 00:09:25,800
Soort van naar beneden te kijken en het soort
verfspuiten Harvard op de grond.

214
00:09:25,800 --> 00:09:26,800
Dat is de naam van deze.

215
00:09:26,800 --> 00:09:28,300
Weet dat is wat er op deze locatie.

216
00:09:28,300 --> 00:09:31,870
Als we beginnen bij de wortel en we gaan
1 en vervolgens 6 en dan 3 en 6,

217
00:09:31,870 --> 00:09:32,780
waar zijn we?

218
00:09:32,780 --> 00:09:35,640
Nou als we naar beneden kijken
en we zien Harvard, dan

219
00:09:35,640 --> 00:09:38,960
we weten dat Harvard was
opgericht in 1636 op basis van de weg

220
00:09:38,960 --> 00:09:41,400
we de uitvoering van dit datastructuur.

221
00:09:41,400 --> 00:09:43,177
Dus dat was hopelijk eenvoudig.

222
00:09:43,177 --> 00:09:44,760
We gaan nog twee toevoegingen doen.

223
00:09:44,760 --> 00:09:50,060
En hopelijk zal helpen om
zie dit gedaan tweemaal meer.

224
00:09:50,060 --> 00:09:52,210
>> Nu, laten we voegen een andere universiteit.

225
00:09:52,210 --> 00:09:54,630
Laten we voegen Yale in deze trie.

226
00:09:54,630 --> 00:09:57,037
Yale werd opgericht in 1701.

227
00:09:57,037 --> 00:09:58,870
Dus we zullen beginnen bij de
wortel, zoals we altijd doen.

228
00:09:58,870 --> 00:09:59,890
En we zetten een traversal pointer.

229
00:09:59,890 --> 00:10:01,624
We gaan gebruiken om door te gaan.

230
00:10:01,624 --> 00:10:03,790
Het eerste wat we willen
doen is naar beneden de 1 pad.

231
00:10:03,790 --> 00:10:05,830
Dat is het eerste cijfer van onze belangrijkste.

232
00:10:05,830 --> 00:10:08,420
Gelukkig, hoewel, we doen niet
moet elk werk deze keer doen.

233
00:10:08,420 --> 00:10:09,919
De 1 pad is al gewist.

234
00:10:09,919 --> 00:10:13,520
Ik al eerder toen ik tikte
werd het invoegen van Harvard in 1636.

235
00:10:13,520 --> 00:10:18,090
Dus ik kan veilig te bewegen
down 1 en er gewoon gaan.

236
00:10:18,090 --> 00:10:20,150
Als u naar beneden bewegen van de 1.

237
00:10:20,150 --> 00:10:22,930
>> Nu, hoewel, ik wil naar 7.

238
00:10:22,930 --> 00:10:24,280
Ik maakte de weg vrij om 6.

239
00:10:24,280 --> 00:10:27,050
Ik weet dat ik kan veilig
ga verder naar beneden de 6 pad.

240
00:10:27,050 --> 00:10:29,220
Maar ik moet om verder te gaan op de 7 pad.

241
00:10:29,220 --> 00:10:30,580
Dus wat moet ik doen?

242
00:10:30,580 --> 00:10:35,070
Nou, net als vroeger, ik moet gewoon
naar de gate te wissen, uit de weg,

243
00:10:35,070 --> 00:10:38,740
en het opbouwen van een nieuw knooppunt van de 7 pad.

244
00:10:38,740 --> 00:10:40,250
Net als dit.

245
00:10:40,250 --> 00:10:42,930
>> Dus nu heb ik verhuisd 1 en 7.

246
00:10:42,930 --> 00:10:45,550
En nu ziet, ik ben een soort
van deze nieuwe subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Alles vanaf 16
op, ik niet schelen.

249
00:10:49,260 --> 00:10:50,720
Ik ben geen 16 iets te doen.

250
00:10:50,720 --> 00:10:51,750
Ik doe 17 spul.

251
00:10:51,750 --> 00:10:58,380
>> Dus nu uit op 17, ik moet
soort gloed hier nieuwe paden.

252
00:10:58,380 --> 00:11:00,462
Het volgende cijfer mijn sleutel is 0.

253
00:11:00,462 --> 00:11:01,670
Ik kan natuurlijk niet overal.

254
00:11:01,670 --> 00:11:02,628
Ik bouwde dit knooppunt.

255
00:11:02,628 --> 00:11:04,550
Dus ik weet dat er geen
paden voorwaarts van hier.

256
00:11:04,550 --> 00:11:06,370
Dus ik moet er zelf een te maken.

257
00:11:06,370 --> 00:11:09,360
>> Dus ik malloc een nieuw knooppunt
en hebben 0 punten daar.

258
00:11:09,360 --> 00:11:12,770
En dan nog een keer, malloc ik een
nieuw knooppunt en hebben een punt daar.

259
00:11:12,770 --> 00:11:15,870
Nogmaals, ik heb mijn sleutel, 1701 uitgeput.

260
00:11:15,870 --> 00:11:18,472
Dus ik kijk naar beneden en ik spuitlak Yale.

261
00:11:18,472 --> 00:11:19,680
Dat is de naam van dit knooppunt.

262
00:11:19,680 --> 00:11:24,660
>> En dus nu als ik ooit nodig om te zien of Yale
wordt in dit trie, begin ik bij de wortel,

263
00:11:24,660 --> 00:11:27,060
Ik ga naar beneden 1701, en kijk naar beneden.

264
00:11:27,060 --> 00:11:30,030
En als ik zie Yale spuiten
geschilderd op de grond, dan

265
00:11:30,030 --> 00:11:32,200
Ik weet Yale bestaat in dit trie.

266
00:11:32,200 --> 00:11:32,950
Laten we nog één.

267
00:11:32,950 --> 00:11:36,430
Laten we voegen Dartmouth in deze
trie, die werd opgericht in 1769.

268
00:11:36,430 --> 00:11:37,750
>> Begin bij de wortel weer.

269
00:11:37,750 --> 00:11:39,445
Mijn eerste cijfer van mijn sleutel 1.

270
00:11:39,445 --> 00:11:40,820
Ik kan gerust naar beneden dat pad.

271
00:11:40,820 --> 00:11:42,400
Die al bestaat.

272
00:11:42,400 --> 00:11:44,040
Het volgende cijfer van mijn sleutel is 7.

273
00:11:44,040 --> 00:11:45,890
Ik kan gerust naar beneden dat pad.

274
00:11:45,890 --> 00:11:47,540
Er bestaat ook.

275
00:11:47,540 --> 00:11:49,000
>> Mijn volgende is 6.

276
00:11:49,000 --> 00:11:52,860
Van hier, van waar ik momenteel ben
geel daar in die middelste knooppunt

277
00:11:52,860 --> 00:11:56,060
6 is momenteel geblokkeerd uit.

278
00:11:56,060 --> 00:11:58,830
Als ik wil naar beneden te gaan dat pad,
Ik moet het zelf op te bouwen.

279
00:11:58,830 --> 00:12:02,250
Dus ik zal een nieuw knooppunt malloc
en hebben 6 punt daar.

280
00:12:02,250 --> 00:12:04,250
En dan, nogmaals, ik ben
laaiend nieuwe paden hier.

281
00:12:04,250 --> 00:12:10,750
>> Dus ik malloc een nieuw knooppunt zodat vanaf
dat node-- pad nummer 9-- en dan nu

282
00:12:10,750 --> 00:12:13,584
Als ik reis 1769, en ik kijk naar beneden.

283
00:12:13,584 --> 00:12:15,500
Er is niets dit moment
Spuit er geschilderd.

284
00:12:15,500 --> 00:12:16,930
Ik kan schrijven Dartmouth.

285
00:12:16,930 --> 00:12:20,710
En ik heb gestoken
Dartmouth in de trie.

286
00:12:20,710 --> 00:12:23,450
>> Dus dat is het invoegen
dingen in de trie.

287
00:12:23,450 --> 00:12:25,384
Nu willen we zoeken naar dingen.

288
00:12:25,384 --> 00:12:27,050
Hoe kunnen we zoeken naar dingen in de trie?

289
00:12:27,050 --> 00:12:29,170
Nou, het is vrij veel hetzelfde idee.

290
00:12:29,170 --> 00:12:33,620
Nu zijn we gewoon gebruik maken van de cijfers van de belangrijkste
om te zien of we kunnen navigeren van de wortel

291
00:12:33,620 --> 00:12:37,170
waar we willen gaan in de Trie.

292
00:12:37,170 --> 00:12:41,620
>> Als we raakte een doodlopende weg op een punt, dan
we weten dat dit element niet kan bestaan

293
00:12:41,620 --> 00:12:44,500
of anders dat pad zou
zijn al gewist.

294
00:12:44,500 --> 00:12:45,930
Als we het allemaal de weg naar
het einde, alles wat we moeten doen

295
00:12:45,930 --> 00:12:48,471
is naar beneden kijken en zien of dat is
het element we zoeken.

296
00:12:48,471 --> 00:12:49,335
Als het succes.

297
00:12:49,335 --> 00:12:52,610
Als het niet, mislukken.

298
00:12:52,610 --> 00:12:54,940
>> Dus laten we zoeken naar
Harvard in deze trie.

299
00:12:54,940 --> 00:12:56,020
We beginnen bij de wortel.

300
00:12:56,020 --> 00:12:58,228
En, nogmaals, we gaan
maak een traversal pointer

301
00:12:58,228 --> 00:12:59,390
om onze bewegingen te doen voor ons.

302
00:12:59,390 --> 00:13:02,080
Van de wortel weten we dat de
eerste plaats waar we moeten gaan is 1,

303
00:13:02,080 --> 00:13:03,390
kunnen we dat doen?

304
00:13:03,390 --> 00:13:03,982
Ja, dat kunnen wij.

305
00:13:03,982 --> 00:13:04,690
Als Veilig bestaat.

306
00:13:04,690 --> 00:13:06,660
We kunnen er terecht.

307
00:13:06,660 --> 00:13:08,440
>> Nu, de volgende plaats die we nodig hebben om te gaan is 6.

308
00:13:08,440 --> 00:13:10,557
Heeft de 6 pad bestaan ​​van hier?

309
00:13:10,557 --> 00:13:11,140
Ja, het doet.

310
00:13:11,140 --> 00:13:12,690
We kunnen naar beneden de 6 pad.

311
00:13:12,690 --> 00:13:13,905
En we eindigen hier boven.

312
00:13:13,905 --> 00:13:16,130
>> Kunnen we naar beneden de 3 weg van hier?

313
00:13:16,130 --> 00:13:18,450
Nou, zo blijkt,
ja, dat ook bestaat.

314
00:13:18,450 --> 00:13:20,790
En we kunnen krijgen op de 6 weg van hier?

315
00:13:20,790 --> 00:13:21,982
Ja, dat kunnen wij.

316
00:13:21,982 --> 00:13:24,002
>> We hebben niet helemaal beantwoord
maar de vraag.

317
00:13:24,002 --> 00:13:25,710
Er is nog steeds een meer
stap, dat nu

318
00:13:25,710 --> 00:13:28,520
we moeten kijken naar beneden en
te zien als dat is actually--

319
00:13:28,520 --> 00:13:32,660
als we op zoek bent naar Harvard, is dat
wat we vinden nadat we putten de sleutel?

320
00:13:32,660 --> 00:13:35,430
In het voorbeeld zijn we hier gebruiken,
de jaren zijn altijd vier cijfers.

321
00:13:35,430 --> 00:13:40,280
Maar je zou kunnen worden met behulp van het voorbeeld waar
u het opslaan van een woordenboek van woorden.

322
00:13:40,280 --> 00:13:44,060
>> En dus in plaats van het hebben van 10 pointers
voor mijn locatie, moet u 26.

323
00:13:44,060 --> 00:13:46,040
Één voor elke letter van het alfabet.

324
00:13:46,040 --> 00:13:50,350
En er zijn enkele woorden als vleermuis,
die een onderdeel van batch, bijvoorbeeld.

325
00:13:50,350 --> 00:13:53,511
En dus zelfs als je naar de
einde van de sleutel en je naar beneden kijkt,

326
00:13:53,511 --> 00:13:55,260
u misschien niet zien wat
je zoekt.

327
00:13:55,260 --> 00:13:58,500
>> Zo heb je altijd te doorkruisen
het volledige pad en vervolgens

328
00:13:58,500 --> 00:14:01,540
als je succesvol in staat
het hele pad doorlopen,

329
00:14:01,540 --> 00:14:03,440
kijk naar beneden en doe een definitieve bevestiging.

330
00:14:03,440 --> 00:14:05,120
Is dat wat ik zoek?

331
00:14:05,120 --> 00:14:07,740
Nou, kijk ik naar beneden na het starten
boven en gaan 1636.

332
00:14:07,740 --> 00:14:08,240
Ik kijk naar beneden.

333
00:14:08,240 --> 00:14:09,400
Ik zie Harvard.

334
00:14:09,400 --> 00:14:11,689
Dus ja, slaagde ik.

335
00:14:11,689 --> 00:14:13,980
Wat als wat ik ben op zoek naar
is niet in de Trie, dat wel.

336
00:14:13,980 --> 00:14:17,200
Wat als ik ben op zoek naar Princeton,
die werd opgericht in 1746.

337
00:14:17,200 --> 00:14:20,875
En dus 1746 wordt mijn sleutel
om te navigeren door de Trie.

338
00:14:20,875 --> 00:14:22,040
Nou, begin ik bij de wortel.

339
00:14:22,040 --> 00:14:24,760
En de eerste plaats wil ik
om naar beneden gaat de 1 pad.

340
00:14:24,760 --> 00:14:25,590
Kan ik het doen?

341
00:14:25,590 --> 00:14:26,490
Ja dat kan ik.

342
00:14:26,490 --> 00:14:28,730
>> Kan ik naar beneden de 7 pad vanaf daar?

343
00:14:28,730 --> 00:14:29,230
Ja ik kan.

344
00:14:29,230 --> 00:14:30,750
Dat bestaat ook.

345
00:14:30,750 --> 00:14:32,460
Maar kan ik naar beneden de 4 weg van hier?

346
00:14:32,460 --> 00:14:35,550
Dat is hetzelfde als de vraag te stellen, kan
Ik ga verder bepaald dat pleintje

347
00:14:35,550 --> 00:14:37,114
die ik heb geel gemarkeerd?

348
00:14:37,114 --> 00:14:38,030
Er is niets daar.

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

350
00:14:38,610 --> 00:14:41,310
>> Er is geen weg vooruit naar beneden de 4 pad.

351
00:14:41,310 --> 00:14:46,480
Als Princeton was in deze trie, dat 4
zou zijn al vrijgegeven voor ons.

352
00:14:46,480 --> 00:14:49,130
En dus op dit punt
we hebben een doodlopende weg bereikt.

353
00:14:49,130 --> 00:14:50,250
We kunnen elke niet verder gaan.

354
00:14:50,250 --> 00:14:53,440
En zo kunnen we zeggen, definitief, nee.

355
00:14:53,440 --> 00:14:56,760
Princeton bestaat niet in deze trie.

356
00:14:56,760 --> 00:14:58,860
>> Dus wat betekent dit allemaal?

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

358
00:14:59,360 --> 00:15:01,000
Er is veel aan de hand.

359
00:15:01,000 --> 00:15:02,500
Er is pointers all over the place.

360
00:15:02,500 --> 00:15:04,249
En, zoals je kunt zien
alleen van het diagram,

361
00:15:04,249 --> 00:15:07,010
er is veel van knooppunten die
zijn soort vliegen rond.

362
00:15:07,010 --> 00:15:13,480
Maar merk elke keer als we wilden
te controleren of er iets was in de Trie,

363
00:15:13,480 --> 00:15:15,000
we hadden slechts 4 bewegingen te maken.

364
00:15:15,000 --> 00:15:17,208
>> Elke keer als we wilden
iets te voegen in de Trie,

365
00:15:17,208 --> 00:15:20,440
we moeten 4 bewegingen te maken, eventueel
mallocing sommige dingen langs de weg.

366
00:15:20,440 --> 00:15:23,482
Maar zoals we zagen toen we gestoken
Dartmouth in de trie,

367
00:15:23,482 --> 00:15:25,940
soms enkele baan
misschien al worden gewist voor ons.

368
00:15:25,940 --> 00:15:30,520
En zo als onze trie wordt groter en
groter, hebben we minder werk elke keer doen

369
00:15:30,520 --> 00:15:32,270
om nieuwe dingen te voegen
want we hebben al

370
00:15:32,270 --> 00:15:35,746
bouwde veel van de tussenliggende
takken langs de weg.

371
00:15:35,746 --> 00:15:38,370
Als we alleen maar te kijken naar
4 dingen, 4 is gewoon een constante.

372
00:15:38,370 --> 00:15:41,750
We echt soort naderen
constante tijd invoegen

373
00:15:41,750 --> 00:15:44,501
en constante tijd opzoeken.

374
00:15:44,501 --> 00:15:47,500
Het nadeel, natuurlijk is dat
Dit trie, zoals je kunt waarschijnlijk vertellen,

375
00:15:47,500 --> 00:15:49,030
is enorm.

376
00:15:49,030 --> 00:15:51,040
Elk van deze knooppunten
neemt veel ruimte.

377
00:15:51,040 --> 00:15:52,090
>> Maar dat is de afweging.

378
00:15:52,090 --> 00:15:55,260
Als we willen echt snel
inbrengen, echt snelle verwijdering,

379
00:15:55,260 --> 00:15:59,630
en echt snel opzoeken, moeten we
hebben veel data rond vliegen.

380
00:15:59,630 --> 00:16:03,590
We hebben opzij te zetten een veel ruimte
en geheugen voor die datastructuur

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

382
00:16:04,290 --> 00:16:05,415
>> En dat is dus de afweging.

383
00:16:05,415 --> 00:16:07,310
Maar het lijkt erop dat we
misschien hebben gevonden.

384
00:16:07,310 --> 00:16:09,560
We zouden hebben gevonden dat
heilige graal van datastructuren

385
00:16:09,560 --> 00:16:12,264
met snelle insertie,
wissen en opzoeken.

386
00:16:12,264 --> 00:16:14,430
En misschien is dit zal een
geschikte datastructuur

387
00:16:14,430 --> 00:16:18,890
te gebruiken voor welke informatie
we proberen te slaan.

388
00:16:18,890 --> 00:16:21,860
Ik ben Doug Lloyd, dit is CS50.

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