1
00:00:00,000 --> 00:00:02,994
>> [Música tocando]

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

3
00:00:05,426 --> 00:00:08,550
Doug LLOYD: Entón, nós estamos avanzando máis preto
e máis preto que Santo Graal de datos

4
00:00:08,550 --> 00:00:13,050
estruturas, que podemos inserir
en, eliminar de, e mirar para arriba

5
00:00:13,050 --> 00:00:15,440
en tempo constante.

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

7
00:00:16,270 --> 00:00:17,280
Isto é unha especie de meta.

8
00:00:17,280 --> 00:00:19,720
Queremos ser capaces de fazê-
cousas moi, moi rapidamente.

9
00:00:19,720 --> 00:00:22,580
>> Ten que atopar aquí cando
estamos a falar de intentos?

10
00:00:22,580 --> 00:00:23,670
Ben, imos dar un ollo.

11
00:00:23,670 --> 00:00:25,628
Entón, nós vimos varios
diferentes estruturas de datos

12
00:00:25,628 --> 00:00:28,680
que xestione o mapeamento de
chamados pares de valores clave,

13
00:00:28,680 --> 00:00:32,080
mapear algúns peza de datos
a algún outro anaco de datos

14
00:00:32,080 --> 00:00:36,020
polo que sabemos onde encontrá-
información na estrutura.

15
00:00:36,020 --> 00:00:40,060
>> Así, por matriz, por exemplo, a
clave é o índice de elemento ou matriz

16
00:00:40,060 --> 00:00:42,600
0 lugar ou matriz 1 e así por diante.

17
00:00:42,600 --> 00:00:46,140
E o valor é o de datos
que hai nese local.

18
00:00:46,140 --> 00:00:48,550
Entón, o que son almacenadas na matriz 0?

19
00:00:48,550 --> 00:00:54,290
O que se garda na agrupación de 1 versus só
0 e 1, o que sería a tecla.

20
00:00:54,290 --> 00:00:56,360
>> Cunha táboa hash é
especie do mesmo idea.

21
00:00:56,360 --> 00:01:00,690
Cunha táboa hash, temos ese hash
función que xera código de hash.

22
00:01:00,690 --> 00:01:03,670
Polo tanto, a clave é o código de hash dos datos.

23
00:01:03,670 --> 00:01:06,530
E o valor, especialmente
falamos de fío

24
00:01:06,530 --> 00:01:10,590
no vídeo en táboas de hash,
é que lista ligada de datos

25
00:01:10,590 --> 00:01:12,550
que hashes para que hashcode.

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

27
00:01:14,050 --> 00:01:16,050
E sobre outra visión
este método, aínda que?

28
00:01:16,050 --> 00:01:21,000
Que tal un método no que o
clave é a garantía de ser único,

29
00:01:21,000 --> 00:01:25,410
ao contrario dunha táboa hash, onde poderiamos
acabar con dous anacos de datos

30
00:01:25,410 --> 00:01:27,200
tendo o mesmo código hash.

31
00:01:27,200 --> 00:01:30,020
E entón temos que xestione
que por calquera enquisa ou máis

32
00:01:30,020 --> 00:01:33,340
fío de preferencia para corrixir este problema.

33
00:01:33,340 --> 00:01:37,520
>> Entón, agora podemos garantir
que a nosa clave será única.

34
00:01:37,520 --> 00:01:39,690
E se o seu valor foi
só algo tan sinxelo

35
00:01:39,690 --> 00:01:44,080
como o verdadeiro eo falso que nos di se
ou non ese anaco de información

36
00:01:44,080 --> 00:01:45,610
existe na estrutura?

37
00:01:45,610 --> 00:01:48,180
Un valor booleano pode ser tan sinxelo como un pouco.

38
00:01:48,180 --> 00:01:52,660
Realista pode ser unha
byte máis probable que un pouco.

39
00:01:52,660 --> 00:01:55,410
Pero iso é moito menor que
almacenar quizais unha secuencia de 50 caracteres,

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

41
00:01:57,360 --> 00:02:02,210
>> Entón intentos, semellante ao de hash táboas,
que combinan matrices e lista ligada,

42
00:02:02,210 --> 00:02:05,790
tenta combinar arrays,
estruturas, e punteiros

43
00:02:05,790 --> 00:02:08,509
en conxunto para almacenar datos en
unha forma interesante que é

44
00:02:08,509 --> 00:02:11,550
moi diferente do
todo o que vimos ata agora.

45
00:02:11,550 --> 00:02:16,750
Agora usan os datos como un guión
para navegar esta estrutura de datos.

46
00:02:16,750 --> 00:02:18,710
E se podemos seguir
o guión, se pudermos

47
00:02:18,710 --> 00:02:22,390
seguir os datos de
comezo ao fin, imos

48
00:02:22,390 --> 00:02:24,945
saber se eses datos
existir no trie.

49
00:02:24,945 --> 00:02:28,310
>> E se nós non podemos seguir o mapa
de significado para rematar en todo,

50
00:02:28,310 --> 00:02:30,600
os datos non poden existir.

51
00:02:30,600 --> 00:02:32,890
Unha vez máis, as teclas son aquí
a garantía de ser único.

52
00:02:32,890 --> 00:02:36,020
E así a diferenza dunha táboa hash, nunca nos
ten que xestionar colisións aquí.

53
00:02:36,020 --> 00:02:39,090
E non hai dúas pezas de datos
teñen exactamente o mesmo guión

54
00:02:39,090 --> 00:02:40,530
a non ser que os datos son idénticos.

55
00:02:40,530 --> 00:02:44,580
>> Se nós inserimos John, a continuación,
buscamos John.

56
00:02:44,580 --> 00:02:47,430
Iso é dúas pezas idénticas
datos, non, nós estamos mirando a través.

57
00:02:47,430 --> 00:02:49,880
Pero por outra banda, calquera
dous anacos de datos son

58
00:02:49,880 --> 00:02:52,750
garantía de guións exclusivos
a través desta estrutura de datos.

59
00:02:52,750 --> 00:02:56,210
E nós imos dar un ollo a
un visual deste en só un momento.

60
00:02:56,210 --> 00:02:58,810
>> Nós imos facer isto, intentando
crear unha nova estrutura de datos,

61
00:02:58,810 --> 00:03:00,564
mapeando os seguintes pares de valores clave.

62
00:03:00,564 --> 00:03:03,480
Neste caso, non estamos indo a usar
algo tan sinxelo como un booleano.

63
00:03:03,480 --> 00:03:06,200
Nós, en realidade, vai almacenar a cadea.

64
00:03:06,200 --> 00:03:08,690
E esa corda vai
ser o nome dunha universidade.

65
00:03:08,690 --> 00:03:12,140
>> E a clave será o ano
cando esta universidade foi fundada.

66
00:03:12,140 --> 00:03:15,380
Cada ano para universidades
van ser catro díxitos.

67
00:03:15,380 --> 00:03:19,840
E por iso imos usar estes catro díxitos á
navegar por esta estrutura de datos.

68
00:03:19,840 --> 00:03:22,270
E imos ver, unha vez máis, como
facemos iso en só un segundo.

69
00:03:22,270 --> 00:03:25,110
>> Ao final do percorrido,
imos ver o nome

70
00:03:25,110 --> 00:03:30,250
da universidade correspondente
a esa chave, estas catro díxitos.

71
00:03:30,250 --> 00:03:34,390
A idea básica por tras dun trie
é que temos unha ruta central.

72
00:03:34,390 --> 00:03:35,640
Entón, pense nisto como unha árbore.

73
00:03:35,640 --> 00:03:39,211
E esta é semellante en ortografía
e no concepto dunha árbore.

74
00:03:39,211 --> 00:03:41,460
Xeralmente cando pensamos sobre
árbores no mundo real,

75
00:03:41,460 --> 00:03:44,090
eles teñen unha raíz que está na
chan e crecen cara arriba

76
00:03:44,090 --> 00:03:46,830
e eles teñen filiais
e eles teñen follas.

77
00:03:46,830 --> 00:03:49,450
E, basicamente, a idea de
un trie é exactamente o mesmo,

78
00:03:49,450 --> 00:03:51,755
agás que a raíz está ancorado
nalgún lugar no ceo.

79
00:03:51,755 --> 00:03:53,130
E as follas están na parte inferior.

80
00:03:53,130 --> 00:03:55,750
>> Entón, é tipo de como se fai unha árbore
e só virá-lo de cabeza para baixo.

81
00:03:55,750 --> 00:03:56,880
Pero aínda hai ramas.

82
00:03:56,880 --> 00:03:59,463
E os serían os nosos camiños,
esas serán as nosas conexións

83
00:03:59,463 --> 00:04:02,220
desde a raíz ata as follas.

84
00:04:02,220 --> 00:04:04,200
Neste caso, os
traxectos, estes ramos

85
00:04:04,200 --> 00:04:08,490
son rotulado con díxitos que nos din
que camiño seguir desde onde estamos.

86
00:04:08,490 --> 00:04:11,800
>> Se vemos un 0, descendemos este sector,
se vemos a 1, descendemos este sector,

87
00:04:11,800 --> 00:04:12,900
e así e así por diante.

88
00:04:12,900 --> 00:04:14,060
Ben, o que significa isto?

89
00:04:14,060 --> 00:04:16,519
Ben, iso significa que
en cada punto de unión

90
00:04:16,519 --> 00:04:19,260
e cada nodo no
medio e cada sector,

91
00:04:19,260 --> 00:04:23,020
hai 10 posibles
lugares que podemos ir.

92
00:04:23,020 --> 00:04:27,690
Polo tanto, hai 10 punteiros
de todos os lugares.

93
00:04:27,690 --> 00:04:30,610
>> E é neste punto que intentos pode obter unha
pouco intimidante para alguén

94
00:04:30,610 --> 00:04:34,460
que é non ter unha chea de
experiencia en ciencia da computación antes.

95
00:04:34,460 --> 00:04:35,960
Pero intentos son realmente moi impresionante.

96
00:04:35,960 --> 00:04:37,793
E se ten o
oportunidade de traballar con eles

97
00:04:37,793 --> 00:04:40,420
e está disposto a cavar-in
probar con eles,

98
00:04:40,420 --> 00:04:44,234
son realmente moi interesante
estruturas de datos para traballar.

99
00:04:44,234 --> 00:04:46,900
Se queremos introducir un elemento
no trie, todo o que cómpre facer

100
00:04:46,900 --> 00:04:51,360
é construír o camiño correcto
a partir da raíz para a folla.

101
00:04:51,360 --> 00:04:55,390
Aquí está o que cada paso ao longo
o xeito no que pode parecer.

102
00:04:55,390 --> 00:04:59,660
Imos definir unha nova datos
estrutura para un novo nodo chamado trie.

103
00:04:59,660 --> 00:05:02,560
>> E dentro destes datos
estrutura existen dúas pezas.

104
00:05:02,560 --> 00:05:05,460
Estamos indo para almacenar o
nome dunha universidade.

105
00:05:05,460 --> 00:05:09,410
E nós estamos indo para almacenar
unha matriz de punteiros

106
00:05:09,410 --> 00:05:12,190
para outros nós do mesmo tipo.

107
00:05:12,190 --> 00:05:14,780
Entón, de novo, este é este tipo
do concepto de todas partes

108
00:05:14,780 --> 00:05:18,567
somos, o 10 posibles
lugares onde podemos ir.

109
00:05:18,567 --> 00:05:20,150
Se vemos un 0, descendemos este sector.

110
00:05:20,150 --> 00:05:22,690
Se vemos a 1, neste sector,
e así por diante e así por diante e así por diante.

111
00:05:22,690 --> 00:05:25,160
Se dicimos 9, descendemos este sector.

112
00:05:25,160 --> 00:05:28,220
Así, en cada punto de unión,
podemos ir 10 lugares posibles.

113
00:05:28,220 --> 00:05:35,740
Así, cada nodo debe conter 10 punteiros
para outros nós, aos 10 outros nós.

114
00:05:35,740 --> 00:05:39,810
>> E os datos que estamos almacenando é
só o nome da universidade.

115
00:05:39,810 --> 00:05:41,060
Entón, imos construír un trie.

116
00:05:41,060 --> 00:05:44,860
Imos introducir unha parella
de elementos no noso trie.

117
00:05:44,860 --> 00:05:46,740
Así, na parte superior,
este é o noso nodo raíz.

118
00:05:46,740 --> 00:05:49,740
Isto probablemente vai ser algo
está indo a globalmente declare.

119
00:05:49,740 --> 00:05:53,450
E está indo a manter globalmente
un punteiro para este nodo sempre.

120
00:05:53,450 --> 00:05:55,360
>> Vai dicir,
raíz é igual, e está

121
00:05:55,360 --> 00:05:57,580
vai malloc mesmo nodo trie.

122
00:05:57,580 --> 00:05:59,850
E nunca vai
para tocar raíz de novo.

123
00:05:59,850 --> 00:06:02,300
Cada vez que quere
comezar a navegar a través,

124
00:06:02,300 --> 00:06:05,802
establecer outro punteiro
igual a raíz, como trav,

125
00:06:05,802 --> 00:06:07,760
que é o exemplo I
usar en moitos dos meus vídeos

126
00:06:07,760 --> 00:06:11,090
aquí en pilas e colas
e listas de enlaces e así por diante.

127
00:06:11,090 --> 00:06:13,320
>> Establecer outro punteiro
trav chamado para paso.

128
00:06:13,320 --> 00:06:15,890
E usa para navegar trav
a través da estrutura de datos.

129
00:06:15,890 --> 00:06:17,500
Entón, imos ver como iso pode parecer.

130
00:06:17,500 --> 00:06:19,880
Entón, agora, o que
un nó parece?

131
00:06:19,880 --> 00:06:22,920
Ben, como os nosos datos
declaración de estrutura indicada,

132
00:06:22,920 --> 00:06:26,906
temos unha cadea, que
Neste caso está baleiro.

133
00:06:26,906 --> 00:06:27,780
Non hai nada aquí.

134
00:06:27,780 --> 00:06:29,550
>> E unha matriz de 10 punteiros.

135
00:06:29,550 --> 00:06:31,790
E agora temos só
ten un nó nesta trie.

136
00:06:31,790 --> 00:06:33,110
Non hai máis nada nel.

137
00:06:33,110 --> 00:06:36,020
Polo tanto, todos os 10 de
punteiros punto para null.

138
00:06:36,020 --> 00:06:38,090
Iso é o que o vermello indica.

139
00:06:38,090 --> 00:06:39,500
>> Imos introducir a secuencia de Harvard.

140
00:06:39,500 --> 00:06:41,999
Imos introducir a Universidade de
Harvard para este trie, que

141
00:06:41,999 --> 00:06:43,940
foi fundada no ano 1636.

142
00:06:43,940 --> 00:06:48,220
Queremos usar a chave,
1636, de nos dicir onde estamos

143
00:06:48,220 --> 00:06:50,140
indo para almacenar Harvard no trie.

144
00:06:50,140 --> 00:06:51,470
Agora, como podemos facelo?

145
00:06:51,470 --> 00:06:52,886
>> Podería ser algo así.

146
00:06:52,886 --> 00:06:54,160
Comezamos na raíz.

147
00:06:54,160 --> 00:06:56,920
E nós temos estes 10 sitios onde podemos ir.

148
00:06:56,920 --> 00:06:59,900
A raíz é como calquera
outro nodo do trie.

149
00:06:59,900 --> 00:07:02,850
Hai 10 sitios onde podemos ir dende aquí.

150
00:07:02,850 --> 00:07:07,215
>> Onde nós probablemente quere
para ir a clave é 1636?

151
00:07:07,215 --> 00:07:08,340
Non hai realmente dúas opcións.

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

153
00:07:08,450 --> 00:07:10,825
Podemos construír a clave
dereita a esquerda e comece con 6.

154
00:07:10,825 --> 00:07:14,000
Ou poderíamos construír a clave
esquerda a dereita e comezar con unha.

155
00:07:14,000 --> 00:07:16,140
>> É probabelmente máis
intuitivo como un ser humano

156
00:07:16,140 --> 00:07:18,110
para entender imos
Só tes que ir esquerda a dereita.

157
00:07:18,110 --> 00:07:21,140
E por iso, se quero introducir
Harvard para este trie,

158
00:07:21,140 --> 00:07:23,560
Eu probablemente quere comezar
iniciando na raíz,

159
00:07:23,560 --> 00:07:25,720
mirando para os meus 10 opcións
na miña fronte, e dicindo:

160
00:07:25,720 --> 00:07:28,700
Eu quero ir para o camiño 1.

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

162
00:07:29,700 --> 00:07:31,810
>> Agora, un camiño é actualmente nulo.

163
00:07:31,810 --> 00:07:35,920
Entón, se eu queira continuar por ese camiño
para introducir este elemento ao trie,

164
00:07:35,920 --> 00:07:42,040
Teño que malloc un novo nodo, ten un
punto alí, e entón eu son bo para ir.

165
00:07:42,040 --> 00:07:46,460
>> Entón eu basicamente estou nunha
punto onde eu estou de pé

166
00:07:46,460 --> 00:07:50,270
na raíz da árbore ou a
trie e hai 10 filiais.

167
00:07:50,270 --> 00:07:52,260
Pero cada rama ten un
porta diante del.

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

169
00:07:53,060 --> 00:07:54,850
Porque non hai nada máis hai.

170
00:07:54,850 --> 00:07:56,522
Ningunha pasaxe segura.

171
00:07:56,522 --> 00:07:58,980
Isto significa que non hai nada
abaixo calquera destes ramos.

172
00:07:58,980 --> 00:08:02,532
Se eu queira comezar a construír
algo, quero eliminar a porta.

173
00:08:02,532 --> 00:08:04,490
Quero eliminar a porta
diante do número 1.

174
00:08:04,490 --> 00:08:05,698
E quero que descenda.

175
00:08:05,698 --> 00:08:08,060
E quero construír
outro lugar para ir.

176
00:08:08,060 --> 00:08:09,470
>> E iso é o que eu fixen aquí.

177
00:08:09,470 --> 00:08:11,430
Entón 1 xa non apunta a null.

178
00:08:11,430 --> 00:08:13,830
Eu xa dixen que é seguro para baixar aquí agora.

179
00:08:13,830 --> 00:08:15,789
Eu constrúe outro nodo.

180
00:08:15,789 --> 00:08:18,330
E cando chegar a ese nó, I
ter outra decisión a tomar.

181
00:08:18,330 --> 00:08:20,890
Onde é que eu vou saír de aquí?

182
00:08:20,890 --> 00:08:22,700
>> Ben, eu xa baixou a 1.

183
00:08:22,700 --> 00:08:24,470
Entón agora eu probablemente vai querer ir para abaixo a 6.

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

185
00:08:24,970 --> 00:08:27,100
De novo, eu teño 10 locais podo escoller.

186
00:08:27,100 --> 00:08:30,060
Entón, imos agora ir para abaixo o número 6.

187
00:08:30,060 --> 00:08:32,280
Entón eu limpar a porta
diante do número 6.

188
00:08:32,280 --> 00:08:33,250
E eu ando alí abaixo.

189
00:08:33,250 --> 00:08:34,580
E eu construír outro nodo.

190
00:08:34,580 --> 00:08:37,630
E eu xa alcanzou outro punto de intersección.

191
00:08:37,630 --> 00:08:40,289
>> De novo, eu teño 10 opcións
onde podo ir.

192
00:08:40,289 --> 00:08:42,799
Eu me mudei 1-6.

193
00:08:42,799 --> 00:08:44,215
Entón agora eu probablemente vai querer ir a 3.

194
00:08:44,215 --> 00:08:45,381
3, non hai ningún lugar podo ir.

195
00:08:45,381 --> 00:08:48,980
Entón eu teño que limpar o camiño
e eu construír un novo espazo.

196
00:08:48,980 --> 00:08:50,870
E, a continuación, a partir de 3, onde quere ir?

197
00:08:50,870 --> 00:08:52,450
Eu quero ir para abaixo 6.

198
00:08:52,450 --> 00:08:54,770
>> E, unha vez máis, eu tiven que
limpar o camiño para facelo.

199
00:08:54,770 --> 00:08:59,179
Entón agora eu usei a miña clave para introducir crear
nós e comezar a construír esta trie.

200
00:08:59,179 --> 00:09:00,220
Comece na raíz.

201
00:09:00,220 --> 00:09:03,666
Eu teño ido para abaixo 1636.

202
00:09:03,666 --> 00:09:05,540
E agora eu estou no fondo
hai nese nó.

203
00:09:05,540 --> 00:09:06,610
E pode ser capaz de
velo en pantalla.

204
00:09:06,610 --> 00:09:07,735
>> É destacada en amarelo.

205
00:09:07,735 --> 00:09:10,020
É onde eu son actualmente.

206
00:09:10,020 --> 00:09:11,300
Miña clave está feito.

207
00:09:11,300 --> 00:09:13,030
Eu xa esgotou todas as posicións na miña clave.

208
00:09:13,030 --> 00:09:15,040
Entón eu non podo ir máis lonxe.

209
00:09:15,040 --> 00:09:17,720
Entón, neste momento, todo o que eu
realmente cómpre facer é dicir, Aceptar.

210
00:09:17,720 --> 00:09:18,990
É unha especie de como a procura
abaixo, para o chan,

211
00:09:18,990 --> 00:09:21,115
se está imaxinando
como este tipo de camiño

212
00:09:21,115 --> 00:09:22,350
con conexións diferentes.

213
00:09:22,350 --> 00:09:25,800
Clasificar de ollar para abaixo e tipo de
pintura de pulverizado Harvard no chan.

214
00:09:25,800 --> 00:09:26,800
Ese é o nome deste.

215
00:09:26,800 --> 00:09:28,300
Sabe que o que é neste lugar.

216
00:09:28,300 --> 00:09:31,870
Se comezar na raíz e descendemos
1 e, a continuación, 6 e, a continuación, 3 e 6, a continuación,

217
00:09:31,870 --> 00:09:32,780
onde estamos?

218
00:09:32,780 --> 00:09:35,640
Ben, se miramos para abaixo
e vemos Harvard, a continuación,

219
00:09:35,640 --> 00:09:38,960
sabemos que foi Harvard
fundada en 1636 con base na forma

220
00:09:38,960 --> 00:09:41,400
estamos aplicando esa estrutura de datos.

221
00:09:41,400 --> 00:09:43,177
Así que foi esperanza simple.

222
00:09:43,177 --> 00:09:44,760
Nós imos facer dúas insercións.

223
00:09:44,760 --> 00:09:50,060
E espero que vai axudar a
ver este feito dúas veces máis.

224
00:09:50,060 --> 00:09:52,210
>> Agora, imos introducir outra universidade.

225
00:09:52,210 --> 00:09:54,630
Imos introducir Yale para este trie.

226
00:09:54,630 --> 00:09:57,037
Yale foi fundada en 1701.

227
00:09:57,037 --> 00:09:58,870
Entón, imos comezar o
administrador, como sempre facemos.

228
00:09:58,870 --> 00:09:59,890
E nós definir un punteiro de paso.

229
00:09:59,890 --> 00:10:01,624
Nós imos usar isto para percorrer.

230
00:10:01,624 --> 00:10:03,790
O primeiro que queremos
facer é ir ao camiño 1.

231
00:10:03,790 --> 00:10:05,830
Ese é o primeiro díxito da nosa clave.

232
00:10:05,830 --> 00:10:08,420
Felizmente, non obstante, non o facemos
ten que facer un traballo esta vez.

233
00:10:08,420 --> 00:10:09,919
A un camiño xa foi desmatada.

234
00:10:09,919 --> 00:10:13,520
Limpar-lo previamente, cando
foi a inserción de Harvard en 1636.

235
00:10:13,520 --> 00:10:18,090
Entón, podo mover con seguridade
down 1 e só ir alí.

236
00:10:18,090 --> 00:10:20,150
Se pode mover para abaixo a 1.

237
00:10:20,150 --> 00:10:22,930
>> Agora, porén, quero ir ao 7.

238
00:10:22,930 --> 00:10:24,280
Eu abriu o camiño ás 6.

239
00:10:24,280 --> 00:10:27,050
Sei que podo con seguridade
continúe no camiño 6.

240
00:10:27,050 --> 00:10:29,220
Pero que avanzar no camiño 7.

241
00:10:29,220 --> 00:10:30,580
Entón o que eu teño que facer?

242
00:10:30,580 --> 00:10:35,070
Ben, así como antes, eu só teño
para limpar a porta, saír do camiño,

243
00:10:35,070 --> 00:10:38,740
e construír un novo nodo do camiño 7.

244
00:10:38,740 --> 00:10:40,250
Así como este.

245
00:10:40,250 --> 00:10:42,930
>> Entón agora eu mudei 1 e, a continuación, 7.

246
00:10:42,930 --> 00:10:45,550
E agora aviso, eu son unha especie
de sobre esta nova subbranch.

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

248
00:10:46,050 --> 00:10:49,260
O resto a partir de 16
, Eu non me importa.

249
00:10:49,260 --> 00:10:50,720
Eu non estou facendo nada 16.

250
00:10:50,720 --> 00:10:51,750
Estou facendo 17 cousas.

251
00:10:51,750 --> 00:10:58,380
>> Polo tanto, agora de 17 en diante, eu teño que
tipo de albiscar novos camiños aquí.

252
00:10:58,380 --> 00:11:00,462
O seguinte díxito miña clave é 0.

253
00:11:00,462 --> 00:11:01,670
Eu claramente non pode obter en calquera lugar.

254
00:11:01,670 --> 00:11:02,628
Acaba de construír ese nó.

255
00:11:02,628 --> 00:11:04,550
Entón eu sei que non hai
camiños para adiante a partir de aquí.

256
00:11:04,550 --> 00:11:06,370
Entón eu teño que facer un eu mesmo.

257
00:11:06,370 --> 00:11:09,360
>> Entón eu malloc un novo nodo
e ten 0 punto alí.

258
00:11:09,360 --> 00:11:12,770
E, a continuación, unha vez máis, eu malloc un
novo nó e ten un punto alí.

259
00:11:12,770 --> 00:11:15,870
Unha vez máis, eu xa esgotou a miña chave de 1701.

260
00:11:15,870 --> 00:11:18,472
Entón eu ollo para abaixo e eu pintura spray Yale.

261
00:11:18,472 --> 00:11:19,680
Ese é o nome deste nó.

262
00:11:19,680 --> 00:11:24,660
>> E agora, se eu ter a ver se Yale
é neste trie, eu comezo a raíz,

263
00:11:24,660 --> 00:11:27,060
Descendo 1701, e mirar para abaixo.

264
00:11:27,060 --> 00:11:30,030
E se eu vexo spray de Yale
pintados no chan, a continuación,

265
00:11:30,030 --> 00:11:32,200
Sei Yale existe neste trie.

266
00:11:32,200 --> 00:11:32,950
Imos facer un máis.

267
00:11:32,950 --> 00:11:36,430
Imos introducir Dartmouth neste
trie, que foi fundada en 1769.

268
00:11:36,430 --> 00:11:37,750
>> Comezar na raíz de novo.

269
00:11:37,750 --> 00:11:39,445
O meu primeiro díxito da miña clave é 1.

270
00:11:39,445 --> 00:11:40,820
Eu podo mover con seguridade por ese camiño.

271
00:11:40,820 --> 00:11:42,400
Que xa existe.

272
00:11:42,400 --> 00:11:44,040
O seguinte díxito da miña clave é 7.

273
00:11:44,040 --> 00:11:45,890
Eu podo mover con seguridade por ese camiño.

274
00:11:45,890 --> 00:11:47,540
Existe tamén.

275
00:11:47,540 --> 00:11:49,000
>> Meu próximo é 6.

276
00:11:49,000 --> 00:11:52,860
A partir de aquí, de onde eu son actualmente
en amarelo alí naquel nó medio,

277
00:11:52,860 --> 00:11:56,060
6 está pechada off.

278
00:11:56,060 --> 00:11:58,830
Se quero ir por ese camiño,
Teño que construír iso só.

279
00:11:58,830 --> 00:12:02,250
Entón, eu vou malloc un novo nodo
e ten 6 puntos alí.

280
00:12:02,250 --> 00:12:04,250
E entón, de novo, eu son
abrindo novos camiños aquí.

281
00:12:04,250 --> 00:12:10,750
>> Entón eu malloc un novo nodo de xeito que a partir de
este número camiño node-- 9-- e entón agora

282
00:12:10,750 --> 00:12:13,584
se eu viaxar de 1769, e eu ollo para abaixo.

283
00:12:13,584 --> 00:12:15,500
Non hai nada actualmente
pulverizado pintado alí.

284
00:12:15,500 --> 00:12:16,930
Podo escribir Dartmouth.

285
00:12:16,930 --> 00:12:20,710
E eu teño inserida
Dartmouth no trie.

286
00:12:20,710 --> 00:12:23,450
>> Entón, iso é inserindo
cousas para o trie.

287
00:12:23,450 --> 00:12:25,384
Agora queremos buscar cousas.

288
00:12:25,384 --> 00:12:27,050
Como é que imos buscar cousas no trie?

289
00:12:27,050 --> 00:12:29,170
Ben, é practicamente a mesma idea.

290
00:12:29,170 --> 00:12:33,620
Agora é só usar os díxitos da clave
a ver se é posible navegar a partir da raíz

291
00:12:33,620 --> 00:12:37,170
onde queremos ir no trie.

292
00:12:37,170 --> 00:12:41,620
>> Se se loita unha rúa sen saída en calquera punto, a continuación,
sabemos que ese elemento non pode existir

293
00:12:41,620 --> 00:12:44,500
ou ben ese camiño sería
xa foron apurada.

294
00:12:44,500 --> 00:12:45,930
Se facemos que todo o camiño para
Ao final, todo o que necesitamos facer

295
00:12:45,930 --> 00:12:48,471
é mirar para abaixo e ver se iso
o elemento que estamos buscando.

296
00:12:48,471 --> 00:12:49,335
Se é, o éxito.

297
00:12:49,335 --> 00:12:52,610
Se non é, falla.

298
00:12:52,610 --> 00:12:54,940
>> Entón, imos buscar
Harvard neste trie.

299
00:12:54,940 --> 00:12:56,020
Comezamos na raíz.

300
00:12:56,020 --> 00:12:58,228
E, unha vez máis, imos
crear un punteiro de paso

301
00:12:58,228 --> 00:12:59,390
para facer os nosos movementos para nós.

302
00:12:59,390 --> 00:13:02,080
A partir da raíz sabemos que o
Primeiro, necesitamos ir é 1,

303
00:13:02,080 --> 00:13:03,390
podemos facelo?

304
00:13:03,390 --> 00:13:03,982
Si podemos.

305
00:13:03,982 --> 00:13:04,690
Se existe de forma segura.

306
00:13:04,690 --> 00:13:06,660
Podemos ir alí.

307
00:13:06,660 --> 00:13:08,440
>> Agora, o seguinte lugar que ten que ir é 6.

308
00:13:08,440 --> 00:13:10,557
Será que o camiño 6 existir dende aquí?

309
00:13:10,557 --> 00:13:11,140
Si, fai.

310
00:13:11,140 --> 00:13:12,690
Podemos ir ao camiño 6.

311
00:13:12,690 --> 00:13:13,905
E acabamos aquí.

312
00:13:13,905 --> 00:13:16,130
>> Podemos ir ao camiño 3 a partir de aquí?

313
00:13:16,130 --> 00:13:18,450
Ben, como se ve,
si, que hai tamén.

314
00:13:18,450 --> 00:13:20,790
E podemos entrar no camiño de 6 a partir de aquí?

315
00:13:20,790 --> 00:13:21,982
Si podemos.

316
00:13:21,982 --> 00:13:24,002
>> Non temos bastante respondeu
a cuestión aínda.

317
00:13:24,002 --> 00:13:25,710
Aínda hai unha
paso, que é agora

318
00:13:25,710 --> 00:13:28,520
temos que mirar para abaixo e
ver se isto é actually--

319
00:13:28,520 --> 00:13:32,660
se nós estamos mirando para Harvard, é que
o que atopamos tras esgotar a clave?

320
00:13:32,660 --> 00:13:35,430
No exemplo que estamos usando aquí,
ano son sempre catro díxitos.

321
00:13:35,430 --> 00:13:40,280
Pero pode estar usando o exemplo onde
está almacenando un dicionario de palabras.

322
00:13:40,280 --> 00:13:44,060
>> E así, en vez de ter 10 punteiros
para o meu lugar, pode que 26.

323
00:13:44,060 --> 00:13:46,040
Un para cada letra do alfabeto.

324
00:13:46,040 --> 00:13:50,350
E hai algunhas palabras como bastón,
que é un subconxunto do solar, por exemplo.

325
00:13:50,350 --> 00:13:53,511
E así mesmo se chegar ao
final da clave e mira para abaixo,

326
00:13:53,511 --> 00:13:55,260
non pode ver o que
está a procurar.

327
00:13:55,260 --> 00:13:58,500
>> Así, sempre ten que atravesar
todo o camiño e logo

328
00:13:58,500 --> 00:14:01,540
se fose capaz éxito
para percorrer todo o camiño,

329
00:14:01,540 --> 00:14:03,440
mirar para abaixo e facer unha confirmación final.

330
00:14:03,440 --> 00:14:05,120
Isto é o que eu estou buscando?

331
00:14:05,120 --> 00:14:07,740
Ben, eu ollar para abaixo despois do inicio
na parte superior e indo 1636.

332
00:14:07,740 --> 00:14:08,240
Eu ollo para abaixo.

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

334
00:14:09,400 --> 00:14:11,689
Entón, si, eu puiden.

335
00:14:11,689 --> 00:14:13,980
E se o que eu estou buscando
non está no trie, con todo.

336
00:14:13,980 --> 00:14:17,200
E se eu estou buscando Princeton,
que foi fundada en 1746.

337
00:14:17,200 --> 00:14:20,875
E así pasa a ser a miña chave de 1746
para navegar a través do trie.

338
00:14:20,875 --> 00:14:22,040
Ben, eu comezar na raíz.

339
00:14:22,040 --> 00:14:24,760
E o primeiro que quero
para se pon en camiño 1.

340
00:14:24,760 --> 00:14:25,590
Podo facelo?

341
00:14:25,590 --> 00:14:26,490
Si, podo.

342
00:14:26,490 --> 00:14:28,730
>> Podo ir ao camiño 7 de alí?

343
00:14:28,730 --> 00:14:29,230
Si, eu podo.

344
00:14:29,230 --> 00:14:30,750
Iso existe tamén.

345
00:14:30,750 --> 00:14:32,460
Pero podo ir ao camiño 4 a partir de aquí?

346
00:14:32,460 --> 00:14:35,550
Isto é como preguntar a pregunta, pode
Eu continuar por ese pequeno cadrado

347
00:14:35,550 --> 00:14:37,114
que teño resaltado en amarelo?

348
00:14:37,114 --> 00:14:38,030
Non hai nada alí.

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

350
00:14:38,610 --> 00:14:41,310
>> Non hai ningunha forma de avanzar no camiño 4.

351
00:14:41,310 --> 00:14:46,480
Se Princeton foi neste trie, que 4
sería liberado para nós xa.

352
00:14:46,480 --> 00:14:49,130
E por iso neste momento
chegamos a unha rúa sen saída.

353
00:14:49,130 --> 00:14:50,250
Non podemos ir máis lonxe.

354
00:14:50,250 --> 00:14:53,440
E así podemos dicir, en definitiva, non.

355
00:14:53,440 --> 00:14:56,760
Princeton non existe neste trie.

356
00:14:56,760 --> 00:14:58,860
>> Entón o que iso todo significa?

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

358
00:14:59,360 --> 00:15:01,000
Hai moita cousa a ocorrer aquí.

359
00:15:01,000 --> 00:15:02,500
Hai punteiros en todo o lugar.

360
00:15:02,500 --> 00:15:04,249
E, como se pode ver
xa desde o diagrama,

361
00:15:04,249 --> 00:15:07,010
hai unha gran cantidade de nós que
son do tipo que voan arredor.

362
00:15:07,010 --> 00:15:13,480
Pero teña en conta cada vez que quería
comprobar se algo foi o trie,

363
00:15:13,480 --> 00:15:15,000
nós só tivemos que facer 4 movementos.

364
00:15:15,000 --> 00:15:17,208
>> Cada vez que quería
introducir algo no trie,

365
00:15:17,208 --> 00:15:20,440
temos que facer 4 movementos, posiblemente
mallocing algunhas cousas ao longo do camiño.

366
00:15:20,440 --> 00:15:23,482
Pero, como vimos cando inserido
Dartmouth no trie,

367
00:15:23,482 --> 00:15:25,940
por veces algún do camiño
xa pode ser liberado para nós.

368
00:15:25,940 --> 00:15:30,520
E así como o noso se fai maior e trie
maior, temos facer menos traballo cada vez

369
00:15:30,520 --> 00:15:32,270
para inserir cousas novas
porque xa

370
00:15:32,270 --> 00:15:35,746
construíu unha morea de o intermediario
ramas ao longo do camiño.

371
00:15:35,746 --> 00:15:38,370
Se sempre só ten que ollar para
4 cousas, 4 é só unha constante.

372
00:15:38,370 --> 00:15:41,750
Nós realmente estamos tipo de visión
inserción de tempo constante

373
00:15:41,750 --> 00:15:44,501
e investigación de tempo constante.

374
00:15:44,501 --> 00:15:47,500
A desvantaxe, por suposto, que sendo
este trie, como pode ser dicir,

375
00:15:47,500 --> 00:15:49,030
é enorme.

376
00:15:49,030 --> 00:15:51,040
Cada un destes nós
ten unha morea de espazo.

377
00:15:51,040 --> 00:15:52,090
>> Pero ese é o tradeoff.

378
00:15:52,090 --> 00:15:55,260
Se queremos realmente rápido
inserción, eliminación realmente rápido,

379
00:15:55,260 --> 00:15:59,630
e lookup moi rápido, temos que
ten unha morea de datos que voan arredor.

380
00:15:59,630 --> 00:16:03,590
Debemos deixar de lado unha morea de espazo
e memoria para esa estrutura de datos

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

382
00:16:04,290 --> 00:16:05,415
>> E entón esa é a cambio.

383
00:16:05,415 --> 00:16:07,310
Pero parece que
pode telo atopado.

384
00:16:07,310 --> 00:16:09,560
Poderiamos descubriron que
Santo Graal de estruturas de datos

385
00:16:09,560 --> 00:16:12,264
con inserción rápida,
exclusión e de investigación.

386
00:16:12,264 --> 00:16:14,430
E quizais este será un
estrutura de datos apropiada

387
00:16:14,430 --> 00:16:18,890
para usar por calquera información
estamos intentando tenda.

388
00:16:18,890 --> 00:16:21,860
Eu son Doug Lloyd, este é CS50.

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