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ão, nós estamos avançando mais perto
e mais perto que santo graal de dados

4
00:00:08,550 --> 00:00:13,050
estruturas, que podemos inserir
em, excluir de, e olhar para cima

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

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

7
00:00:16,270 --> 00:00:17,280
Isso é uma espécie de meta.

8
00:00:17,280 --> 00:00:19,720
Nós queremos ser capazes de fazê-
coisas muito, muito rapidamente.

9
00:00:19,720 --> 00:00:22,580
>> Tem que encontramos aqui quando
estamos falando de tentativas?

10
00:00:22,580 --> 00:00:23,670
Bem, vamos dar uma olhada.

11
00:00:23,670 --> 00:00:25,628
Então, nós temos visto vários
diferentes estruturas de dados

12
00:00:25,628 --> 00:00:28,680
que lidar com o mapeamento de
chamados pares de valores-chave,

13
00:00:28,680 --> 00:00:32,080
mapear alguns pedaço de dados
a algum outro pedaço de dados

14
00:00:32,080 --> 00:00:36,020
por isso sabemos onde encontrá-
informações na estrutura.

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

16
00:00:40,060 --> 00:00:42,600
0 local ou matriz 1 e assim por diante.

17
00:00:42,600 --> 00:00:46,140
E o valor é o de dados
que existe naquele local.

18
00:00:46,140 --> 00:00:48,550
Então, o que são armazenadas na matriz 0?

19
00:00:48,550 --> 00:00:54,290
O que é armazenada no agrupamento de 1 versus apenas
0 e 1, o que seria as teclas.

20
00:00:54,290 --> 00:00:56,360
>> Com uma tabela hash é
espécie da mesma idéia.

21
00:00:56,360 --> 00:01:00,690
Com uma tabela hash, temos esse hash
função que gera códigos de hash.

22
00:01:00,690 --> 00:01:03,670
Portanto, a chave é o código de hash dos dados.

23
00:01:03,670 --> 00:01:06,530
E o valor, particularmente
nós falamos sobre encadeamento

24
00:01:06,530 --> 00:01:10,590
no vídeo em tabelas de hash,
é que lista ligada de dados

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

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

27
00:01:14,050 --> 00:01:16,050
E sobre outra abordagem
este método, embora?

28
00:01:16,050 --> 00:01:21,000
Que tal um método em que o
chave é a garantia de ser único,

29
00:01:21,000 --> 00:01:25,410
ao contrário de uma tabela hash, onde poderíamos
acabar com dois pedaços de dados

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ão nós temos de lidar com
que por qualquer sondagem ou mais

32
00:01:30,020 --> 00:01:33,340
encadeamento de preferência para corrigir esse problema.

33
00:01:33,340 --> 00:01:37,520
>> Então, agora nós podemos garantir
que a nossa chave será única.

34
00:01:37,520 --> 00:01:39,690
E se o nosso valor foi
apenas algo tão fácil

35
00:01:39,690 --> 00:01:44,080
como o verdadeiro eo falso que nos diz se
ou não esse pedaço de informação

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

37
00:01:45,610 --> 00:01:48,180
Um valor booleano pode ser tão simples como um pouco.

38
00:01:48,180 --> 00:01:52,660
Realisticamente é provavelmente uma
byte mais provável do que um pouco.

39
00:01:52,660 --> 00:01:55,410
Mas isso é muito menor do que
armazenar talvez uma seqüência de 50 caracteres,

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

41
00:01:57,360 --> 00:02:02,210
>> Então tentativas, semelhante ao de hash tabelas,
que combinam matrizes e lista ligada,

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

43
00:02:05,790 --> 00:02:08,509
em conjunto para armazenar dados em
uma forma interessante que é

44
00:02:08,509 --> 00:02:11,550
muito diferente do
tudo que vimos até agora.

45
00:02:11,550 --> 00:02:16,750
Agora usamos os dados como um roteiro
para navegar esta estrutura de dados.

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

47
00:02:18,710 --> 00:02:22,390
seguir os dados a partir de
começo ao fim, vamos

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

49
00:02:24,945 --> 00:02:28,310
>> E se nós não podemos seguir o mapa
de significado para terminar em tudo,

50
00:02:28,310 --> 00:02:30,600
os dados não podem existir.

51
00:02:30,600 --> 00:02:32,890
Mais uma vez, as teclas são aqui
a garantia de ser único.

52
00:02:32,890 --> 00:02:36,020
E assim ao contrário de uma tabela hash, nós nunca nos
tem que lidar com colisões aqui.

53
00:02:36,020 --> 00:02:39,090
E não há duas peças de dados
têm exatamente o mesmo roteiro

54
00:02:39,090 --> 00:02:40,530
a menos que os dados são idênticos.

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

56
00:02:44,580 --> 00:02:47,430
Isso é duas peças idênticas de
dados, certo, nós estamos olhando através.

57
00:02:47,430 --> 00:02:49,880
Mas por outro lado, qualquer
dois pedaços de dados são

58
00:02:49,880 --> 00:02:52,750
garantia de ter roteiros exclusivos
através desta estrutura de dados.

59
00:02:52,750 --> 00:02:56,210
E nós vamos dar uma olhada em
um visual deste em apenas um momento.

60
00:02:56,210 --> 00:02:58,810
>> Nós vamos fazer isso, tentando
criar uma nova estrutura de dados,

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

62
00:03:00,564 --> 00:03:03,480
Neste caso, nós não estamos indo para usar
algo tão simples como um booleano.

63
00:03:03,480 --> 00:03:06,200
Nós, na verdade, vai armazenar a cadeia.

64
00:03:06,200 --> 00:03:08,690
E essa corda vai
ser o nome de uma universidade.

65
00:03:08,690 --> 00:03:12,140
>> E a chave vai ser o ano
quando essa universidade foi fundada.

66
00:03:12,140 --> 00:03:15,380
Todos os anos para universidades
vão ser quatro dígitos.

67
00:03:15,380 --> 00:03:19,840
E por isso vamos usar esses quatro dígitos à
navegar por esta estrutura de dados.

68
00:03:19,840 --> 00:03:22,270
E vamos ver, mais uma vez, como
fazemos isso em apenas um segundo.

69
00:03:22,270 --> 00:03:25,110
>> No final do percurso,
vamos ver o nome

70
00:03:25,110 --> 00:03:30,250
da universidade que corresponde
a essa chave, estas quatro dígitos.

71
00:03:30,250 --> 00:03:34,390
A idéia básica por trás de um trie
é que temos uma rota central.

72
00:03:34,390 --> 00:03:35,640
Então, pense nisso como uma árvore.

73
00:03:35,640 --> 00:03:39,211
E esta é semelhante em ortografia
e no conceito de uma árvore.

74
00:03:39,211 --> 00:03:41,460
Geralmente quando pensamos sobre
árvores no mundo real,

75
00:03:41,460 --> 00:03:44,090
eles têm uma raiz que está na
chão e eles crescem para cima

76
00:03:44,090 --> 00:03:46,830
e eles têm filiais
e eles têm folhas.

77
00:03:46,830 --> 00:03:49,450
E, basicamente, a idéia de
um trie é exatamente o mesmo,

78
00:03:49,450 --> 00:03:51,755
exceto que a raiz está ancorado
em algum lugar no céu.

79
00:03:51,755 --> 00:03:53,130
E as folhas estão na parte inferior.

80
00:03:53,130 --> 00:03:55,750
>> Então, é tipo de como tirar uma árvore
e apenas virá-lo de cabeça para baixo.

81
00:03:55,750 --> 00:03:56,880
Mas ainda há ramos.

82
00:03:56,880 --> 00:03:59,463
E aqueles seriam os nossos caminhos,
essas serão as nossas ligações

83
00:03:59,463 --> 00:04:02,220
desde a raiz até as folhas.

84
00:04:02,220 --> 00:04:04,200
Neste caso, aqueles
trajetos, esses ramos

85
00:04:04,200 --> 00:04:08,490
são rotulados com dígitos que nos dizem
que caminho seguir a partir de onde estamos.

86
00:04:08,490 --> 00:04:11,800
>> Se vemos um 0, descemos este ramo,
se vemos a 1, descemos este ramo,

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

88
00:04:12,900 --> 00:04:14,060
Bem, o que isso significa?

89
00:04:14,060 --> 00:04:16,519
Bem, isso significa que
em cada ponto de junção

90
00:04:16,519 --> 00:04:19,260
e cada nó no
meio e cada ramo,

91
00:04:19,260 --> 00:04:23,020
existem 10 possíveis
lugares que podemos ir.

92
00:04:23,020 --> 00:04:27,690
Portanto, há 10 ponteiros
de todos os locais.

93
00:04:27,690 --> 00:04:30,610
>> E é neste ponto que tentativas pode obter uma
pouco intimidante para alguém

94
00:04:30,610 --> 00:04:34,460
que é não ter um monte de
experiência em ciência da computação antes.

95
00:04:34,460 --> 00:04:35,960
Mas tentativas são realmente bastante impressionante.

96
00:04:35,960 --> 00:04:37,793
E se você tiver o
oportunidade de trabalhar com eles

97
00:04:37,793 --> 00:04:40,420
e você está disposto a cavar-in
e experimentar com eles,

98
00:04:40,420 --> 00:04:44,234
eles são realmente bastante interessante
estruturas de dados para trabalhar.

99
00:04:44,234 --> 00:04:46,900
Se queremos inserir um elemento
no trie, tudo o que precisamos fazer

100
00:04:46,900 --> 00:04:51,360
é construir o caminho correto
a partir da raiz para a folha.

101
00:04:51,360 --> 00:04:55,390
Aqui está o que cada passo ao longo
a forma como pode parecer.

102
00:04:55,390 --> 00:04:59,660
Vamos definir uma nova dados
estrutura para um novo nó chamado de trie.

103
00:04:59,660 --> 00:05:02,560
>> E dentro desses dados
estrutura existem duas peças.

104
00:05:02,560 --> 00:05:05,460
Nós estamos indo para armazenar o
nome de uma universidade.

105
00:05:05,460 --> 00:05:09,410
E nós estamos indo para armazenar
uma matriz de ponteiros

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ão, novamente, este é esse tipo
do conceito de todos os lugares

108
00:05:14,780 --> 00:05:18,567
somos, em 10 possíveis
lugares onde podemos ir.

109
00:05:18,567 --> 00:05:20,150
Se vemos um 0, descemos este ramo.

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

111
00:05:22,690 --> 00:05:25,160
Se dissermos 9, descemos este ramo.

112
00:05:25,160 --> 00:05:28,220
Assim, em cada ponto de junção,
podemos ir 10 lugares possíveis.

113
00:05:28,220 --> 00:05:35,740
Assim, cada nó deve conter 10 ponteiros
para os outros nós, aos 10 outros nós.

114
00:05:35,740 --> 00:05:39,810
>> E os dados que nós estamos armazenando é
apenas o nome da universidade.

115
00:05:39,810 --> 00:05:41,060
Então, vamos construir um trie.

116
00:05:41,060 --> 00:05:44,860
Vamos inserir um casal
de itens em nosso trie.

117
00:05:44,860 --> 00:05:46,740
Assim, no topo,
este é o nosso nó raiz.

118
00:05:46,740 --> 00:05:49,740
Isso provavelmente vai ser algo
você está indo para globalmente declare.

119
00:05:49,740 --> 00:05:53,450
E você está indo para manter globalmente
um ponteiro para este nó sempre.

120
00:05:53,450 --> 00:05:55,360
>> Você vai dizer,
raiz é igual, e você está

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

122
00:05:57,580 --> 00:05:59,850
E você nunca vai
para tocar raiz novamente.

123
00:05:59,850 --> 00:06:02,300
Toda vez que você quiser
começar a navegar através,

124
00:06:02,300 --> 00:06:05,802
você definir outro ponteiro
igual a raiz, como trav,

125
00:06:05,802 --> 00:06:07,760
que é o exemplo I
usar em muitos de meus vídeos

126
00:06:07,760 --> 00:06:11,090
aqui em pilhas e filas
e listas de links e assim por diante.

127
00:06:11,090 --> 00:06:13,320
>> Você definir outro ponteiro
trav chamado para passagem.

128
00:06:13,320 --> 00:06:15,890
E você usa para navegar trav
através da estrutura de dados.

129
00:06:15,890 --> 00:06:17,500
Então, vamos ver como isso pode parecer.

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

131
00:06:19,880 --> 00:06:22,920
Bem, tal como os nossos dados
declaração de estrutura indicada,

132
00:06:22,920 --> 00:06:26,906
temos uma string, que
Neste caso está vazio.

133
00:06:26,906 --> 00:06:27,780
Não há nada aqui.

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

135
00:06:29,550 --> 00:06:31,790
E agora, temos apenas
tem um nó nesta trie.

136
00:06:31,790 --> 00:06:33,110
Não há mais nada nele.

137
00:06:33,110 --> 00:06:36,020
Portanto, todos os 10 de
ponteiros ponto para null.

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

139
00:06:38,090 --> 00:06:39,500
>> Vamos inserir a seqüência de Harvard.

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

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

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

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

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

145
00:06:51,470 --> 00:06:52,886
>> Poderia ser algo como isto.

146
00:06:52,886 --> 00:06:54,160
Nós começamos na raiz.

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

148
00:06:56,920 --> 00:06:59,900
A raiz é como qualquer
outro nó do trie.

149
00:06:59,900 --> 00:07:02,850
Há 10 lugares onde podemos ir a partir daqui.

150
00:07:02,850 --> 00:07:07,215
>> Onde nós provavelmente quer
para ir se a chave é 1636?

151
00:07:07,215 --> 00:07:08,340
Não há realmente duas opções.

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

153
00:07:08,450 --> 00:07:10,825
Podemos construir a chave
direita para a esquerda e comece com 6.

154
00:07:10,825 --> 00:07:14,000
Ou nós poderíamos construir a chave
esquerda para a direita e começar com uma.

155
00:07:14,000 --> 00:07:16,140
>> É provavelmente mais
intuitivo como um ser humano

156
00:07:16,140 --> 00:07:18,110
para entender nós vamos
Basta ir esquerda para a direita.

157
00:07:18,110 --> 00:07:21,140
E por isso, se eu quero inserir
Harvard para este trie,

158
00:07:21,140 --> 00:07:23,560
Eu provavelmente quer começar
iniciando na raiz,

159
00:07:23,560 --> 00:07:25,720
olhando para os meus 10 opções
na minha frente, e dizendo:

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

161
00:07:28,700 --> 00:07:29,700
ESTÁ BEM.

162
00:07:29,700 --> 00:07:31,810
>> Agora, um caminho é actualmente nulo.

163
00:07:31,810 --> 00:07:35,920
Então, se eu quiser continuar por esse caminho
para inserir esse elemento para o trie,

164
00:07:35,920 --> 00:07:42,040
Eu tenho que malloc um novo nó, tem um
ponto lá, e então eu sou bom para ir.

165
00:07:42,040 --> 00:07:46,460
>> Então eu basicamente estou em uma
ponto onde eu estou de pé

166
00:07:46,460 --> 00:07:50,270
na raiz da árvore ou a
trie e existem 10 filiais.

167
00:07:50,270 --> 00:07:52,260
Mas cada ramo tem um
portão na frente dele.

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

169
00:07:53,060 --> 00:07:54,850
Porque não há nada mais há.

170
00:07:54,850 --> 00:07:56,522
Nenhuma passagem segura.

171
00:07:56,522 --> 00:07:58,980
Isso significa que não há nada
para baixo qualquer um desses ramos.

172
00:07:58,980 --> 00:08:02,532
Se eu quiser começar a construir
alguma coisa, eu quero remover o portão.

173
00:08:02,532 --> 00:08:04,490
Eu quero remover o portão
na frente do número 1.

174
00:08:04,490 --> 00:08:05,698
E eu quero que desça.

175
00:08:05,698 --> 00:08:08,060
E eu quero construir
um outro lugar para eu ir.

176
00:08:08,060 --> 00:08:09,470
>> E isso é o que eu fiz aqui.

177
00:08:09,470 --> 00:08:11,430
Então 1 já não aponta para null.

178
00:08:11,430 --> 00:08:13,830
Eu já disse que é seguro para descer aqui agora.

179
00:08:13,830 --> 00:08:15,789
Eu construí outro nó.

180
00:08:15,789 --> 00:08:18,330
E quando eu chegar a esse nó, I
ter outra decisão a tomar.

181
00:08:18,330 --> 00:08:20,890
Onde é que eu vou sair daqui?

182
00:08:20,890 --> 00:08:22,700
>> Bem, eu já tenha ido para baixo a 1.

183
00:08:22,700 --> 00:08:24,470
Então agora eu provavelmente vai querer ir para baixo a 6.

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

185
00:08:24,970 --> 00:08:27,100
Novamente, eu tenho 10 locais posso escolher.

186
00:08:27,100 --> 00:08:30,060
Então, vamos agora ir para baixo o número 6.

187
00:08:30,060 --> 00:08:32,280
Então eu limpar o portão
na frente do número 6.

188
00:08:32,280 --> 00:08:33,250
E eu ando lá em baixo.

189
00:08:33,250 --> 00:08:34,580
E eu construir um outro nó.

190
00:08:34,580 --> 00:08:37,630
E eu já alcançou outro ponto de junção.

191
00:08:37,630 --> 00:08:40,289
>> Novamente, eu tenho 10 opções
para onde eu posso 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ão agora eu provavelmente vai querer ir a 3.

194
00:08:44,215 --> 00:08:45,381
3, não há nenhum lugar eu posso ir.

195
00:08:45,381 --> 00:08:48,980
Então eu tenho que limpar o caminho
e eu construir um novo espaço.

196
00:08:48,980 --> 00:08:50,870
E, em seguida, a partir de 3, onde eu gostaria de ir?

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

198
00:08:52,450 --> 00:08:54,770
>> E, mais uma vez, eu tive que
limpar o caminho para fazê-lo.

199
00:08:54,770 --> 00:08:59,179
Então agora eu usei minha chave para inserir criar
nós e começar a construir esta trie.

200
00:08:59,179 --> 00:09:00,220
Eu comecei na raiz.

201
00:09:00,220 --> 00:09:03,666
Eu tenho ido para baixo 1636.

202
00:09:03,666 --> 00:09:05,540
E agora eu estou na parte inferior
há nesse nó.

203
00:09:05,540 --> 00:09:06,610
E você pode ser capaz de
vê-lo na tela.

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

205
00:09:07,735 --> 00:09:10,020
É onde eu sou atualmente.

206
00:09:10,020 --> 00:09:11,300
Minha chave é feito.

207
00:09:11,300 --> 00:09:13,030
Eu já esgotou todas as posições na minha chave.

208
00:09:13,030 --> 00:09:15,040
Então eu não posso ir mais longe.

209
00:09:15,040 --> 00:09:17,720
Então, neste momento, tudo o que eu
realmente precisa fazer é dizer, OK.

210
00:09:17,720 --> 00:09:18,990
É uma espécie de como a procura
para baixo, para o chão,

211
00:09:18,990 --> 00:09:21,115
se você está imaginando
se como este tipo de caminho

212
00:09:21,115 --> 00:09:22,350
com ligações diferentes.

213
00:09:22,350 --> 00:09:25,800
Classificar de olhar para baixo e tipo de
pintura de pulverizador Harvard no chão.

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

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

216
00:09:28,300 --> 00:09:31,870
Se começarmos na raiz e descemos
1 e, em seguida, 6 e, em seguida, 3 e 6, em seguida,

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

218
00:09:32,780 --> 00:09:35,640
Bem, se olharmos para baixo
e vemos Harvard, em seguida,

219
00:09:35,640 --> 00:09:38,960
sabemos que foi Harvard
fundada em 1636 com base na maneira

220
00:09:38,960 --> 00:09:41,400
estamos implementando essa estrutura de dados.

221
00:09:41,400 --> 00:09:43,177
Assim que foi esperançosamente simples.

222
00:09:43,177 --> 00:09:44,760
Nós vamos fazer mais duas inserções.

223
00:09:44,760 --> 00:09:50,060
E espero que ele vai ajudar a
ver este feito duas vezes mais.

224
00:09:50,060 --> 00:09:52,210
>> Agora, vamos inserir outra universidade.

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

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

227
00:09:57,037 --> 00:09:58,870
Então, vamos começar no
root, como sempre fazemos.

228
00:09:58,870 --> 00:09:59,890
E nós definir um ponteiro de passagem.

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

230
00:10:01,624 --> 00:10:03,790
A primeira coisa que queremos
fazer é ir para o caminho 1.

231
00:10:03,790 --> 00:10:05,830
Esse é o primeiro dígito da nossa chave.

232
00:10:05,830 --> 00:10:08,420
Felizmente, porém, não o fazemos
tem que fazer algum trabalho desta vez.

233
00:10:08,420 --> 00:10:09,919
A um caminho já foi desmatada.

234
00:10:09,919 --> 00:10:13,520
Limpei-lo previamente, quando eu
foi a inserção de Harvard em 1636.

235
00:10:13,520 --> 00:10:18,090
Então, eu posso mover com segurança
down 1 e apenas ir lá.

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

237
00:10:20,150 --> 00:10:22,930
>> Agora, porém, eu quero ir para o 7.

238
00:10:22,930 --> 00:10:24,280
Eu abriu o caminho às 6.

239
00:10:24,280 --> 00:10:27,050
Eu sei que eu posso com segurança
prossiga no caminho 6.

240
00:10:27,050 --> 00:10:29,220
Mas preciso avançar no caminho 7.

241
00:10:29,220 --> 00:10:30,580
Então o que eu preciso fazer?

242
00:10:30,580 --> 00:10:35,070
Bem, assim como antes, eu só preciso
para limpar a porta, sair do caminho,

243
00:10:35,070 --> 00:10:38,740
e construir um novo nó do caminho 7.

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

245
00:10:40,250 --> 00:10:42,930
>> Então agora eu mudei 1 e, em seguida, 7.

246
00:10:42,930 --> 00:10:45,550
E agora aviso, eu sou uma espécie
de sobre esta nova subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Tudo o resto a partir de 16
, eu não me importo com.

249
00:10:49,260 --> 00:10:50,720
Eu não estou fazendo nada 16.

250
00:10:50,720 --> 00:10:51,750
Estou fazendo 17 coisas.

251
00:10:51,750 --> 00:10:58,380
>> Portanto, agora de 17 em diante, eu tenho que
tipo de vislumbrar novos caminhos aqui.

252
00:10:58,380 --> 00:11:00,462
O próximo dígito minha chave é 0.

253
00:11:00,462 --> 00:11:01,670
Eu claramente não pode obter em qualquer lugar.

254
00:11:01,670 --> 00:11:02,628
Acabei de construir esse nó.

255
00:11:02,628 --> 00:11:04,550
Então eu sei que não há
caminhos para a frente a partir daqui.

256
00:11:04,550 --> 00:11:06,370
Então eu tenho que fazer um eu mesmo.

257
00:11:06,370 --> 00:11:09,360
>> Então eu malloc um novo nó
e tem 0 ponto lá.

258
00:11:09,360 --> 00:11:12,770
E, em seguida, mais uma vez, eu malloc um
novo nó e tem um ponto lá.

259
00:11:12,770 --> 00:11:15,870
Mais uma vez, eu já esgotou a minha chave de 1701.

260
00:11:15,870 --> 00:11:18,472
Então eu olho para baixo e eu tinta spray Yale.

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

262
00:11:19,680 --> 00:11:24,660
>> E agora, se eu precisar para ver se Yale
é neste trie, eu começo a raiz,

263
00:11:24,660 --> 00:11:27,060
Desço 1701, e olhar para baixo.

264
00:11:27,060 --> 00:11:30,030
E se eu vejo spray de Yale
pintados no chão, em seguida,

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

266
00:11:32,200 --> 00:11:32,950
Vamos fazer mais um.

267
00:11:32,950 --> 00:11:36,430
Vamos inserir Dartmouth neste
trie, que foi fundada em 1769.

268
00:11:36,430 --> 00:11:37,750
>> Comece na raiz novamente.

269
00:11:37,750 --> 00:11:39,445
Meu primeiro dígito da minha chave é 1.

270
00:11:39,445 --> 00:11:40,820
Eu posso me mover com segurança por esse caminho.

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

272
00:11:42,400 --> 00:11:44,040
O próximo dígito da minha chave é 7.

273
00:11:44,040 --> 00:11:45,890
Eu posso me mover com segurança por esse caminho.

274
00:11:45,890 --> 00:11:47,540
Existe também.

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

276
00:11:49,000 --> 00:11:52,860
A partir daqui, de onde eu sou atualmente
em amarelo ali naquele nó meio,

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

278
00:11:56,060 --> 00:11:58,830
Se eu quero ir por esse caminho,
Eu tenho que construir isso sozinho.

279
00:11:58,830 --> 00:12:02,250
Então, eu vou malloc um novo nó
e tem 6 pontos lá.

280
00:12:02,250 --> 00:12:04,250
E então, novamente, eu sou
abrindo novos caminhos aqui.

281
00:12:04,250 --> 00:12:10,750
>> Então eu malloc um novo nó de modo que a partir de
esse número caminho node-- 9-- e então agora

282
00:12:10,750 --> 00:12:13,584
se eu viajar de 1769, e eu olho para baixo.

283
00:12:13,584 --> 00:12:15,500
Não há nada atualmente
pulverizador pintado lá.

284
00:12:15,500 --> 00:12:16,930
Eu posso escrever Dartmouth.

285
00:12:16,930 --> 00:12:20,710
E eu tenho inserido
Dartmouth no trie.

286
00:12:20,710 --> 00:12:23,450
>> Então, isso é inserindo
coisas para o trie.

287
00:12:23,450 --> 00:12:25,384
Agora queremos procurar coisas.

288
00:12:25,384 --> 00:12:27,050
Como é que vamos procurar coisas no trie?

289
00:12:27,050 --> 00:12:29,170
Bem, é praticamente a mesma idéia.

290
00:12:29,170 --> 00:12:33,620
Agora é só usar os dígitos da chave
para ver se é possível navegar a partir da raiz

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

292
00:12:37,170 --> 00:12:41,620
>> Se nós batemos um beco sem saída em qualquer ponto, em seguida,
nós sabemos que esse elemento não pode existir

293
00:12:41,620 --> 00:12:44,500
ou então esse caminho seria
já foram apuradas.

294
00:12:44,500 --> 00:12:45,930
Se fizermos com que todo o caminho para
Ao final, tudo o que precisamos fazer

295
00:12:45,930 --> 00:12:48,471
é olhar para baixo e ver se é isso
o elemento que estamos procurando.

296
00:12:48,471 --> 00:12:49,335
Se for, o sucesso.

297
00:12:49,335 --> 00:12:52,610
Se não é, falhar.

298
00:12:52,610 --> 00:12:54,940
>> Então, vamos procurar
Harvard neste trie.

299
00:12:54,940 --> 00:12:56,020
Nós começamos na raiz.

300
00:12:56,020 --> 00:12:58,228
E, mais uma vez, vamos
criar um ponteiro de passagem

301
00:12:58,228 --> 00:12:59,390
para fazer nossos movimentos para nós.

302
00:12:59,390 --> 00:13:02,080
A partir da raiz sabemos que o
primeiro lugar, precisamos de ir é 1,

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

304
00:13:03,390 --> 00:13:03,982
Sim, nós podemos.

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

306
00:13:04,690 --> 00:13:06,660
Nós podemos ir lá.

307
00:13:06,660 --> 00:13:08,440
>> Agora, o próximo lugar que precisa ir é 6.

308
00:13:08,440 --> 00:13:10,557
Será que o caminho 6 existir a partir daqui?

309
00:13:10,557 --> 00:13:11,140
Sim, ele faz.

310
00:13:11,140 --> 00:13:12,690
Nós podemos ir para o caminho 6.

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

312
00:13:13,905 --> 00:13:16,130
>> Podemos ir para o caminho 3 a partir daqui?

313
00:13:16,130 --> 00:13:18,450
Bem, como se vê,
sim, que existe também.

314
00:13:18,450 --> 00:13:20,790
E podemos entrar no caminho de 6 a partir daqui?

315
00:13:20,790 --> 00:13:21,982
Sim, nós podemos.

316
00:13:21,982 --> 00:13:24,002
>> Nós não temos bastante respondeu
a questão ainda.

317
00:13:24,002 --> 00:13:25,710
Ainda há mais uma
passo, que é agora

318
00:13:25,710 --> 00:13:28,520
temos de olhar para baixo e
ver se isso é actually--

319
00:13:28,520 --> 00:13:32,660
se nós estamos olhando para Harvard, é que
o que encontramos depois de esgotar a chave?

320
00:13:32,660 --> 00:13:35,430
No exemplo que estamos usando aqui,
os anos são sempre quatro dígitos.

321
00:13:35,430 --> 00:13:40,280
Mas você pode estar usando o exemplo onde
você está armazenando um dicionário de palavras.

322
00:13:40,280 --> 00:13:44,060
>> E assim, em vez de ter 10 ponteiros
para o meu local, você pode ter 26.

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

324
00:13:46,040 --> 00:13:50,350
E há algumas palavras como bastão,
que é um subconjunto do lote, por exemplo.

325
00:13:50,350 --> 00:13:53,511
E assim mesmo se você chegar ao
final da chave e você olha para baixo,

326
00:13:53,511 --> 00:13:55,260
você não pode ver o que
você está procurando.

327
00:13:55,260 --> 00:13:58,500
>> Assim, você sempre tem que atravessar
todo o caminho e depois

328
00:13:58,500 --> 00:14:01,540
se você fosse capaz êxito
para percorrer todo o caminho,

329
00:14:01,540 --> 00:14:03,440
olhar para baixo e fazer uma confirmação final.

330
00:14:03,440 --> 00:14:05,120
É isso que eu estou procurando?

331
00:14:05,120 --> 00:14:07,740
Bem, eu olhar para baixo após o início
no topo e indo 1636.

332
00:14:07,740 --> 00:14:08,240
Eu olho para baixo.

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

334
00:14:09,400 --> 00:14:11,689
Então, sim, eu consegui.

335
00:14:11,689 --> 00:14:13,980
E se o que eu estou procurando
não está no trie, no entanto.

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

337
00:14:17,200 --> 00:14:20,875
E assim torna-se minha chave de 1746
para navegar através do trie.

338
00:14:20,875 --> 00:14:22,040
Bem, eu começar na raiz.

339
00:14:22,040 --> 00:14:24,760
E o primeiro lugar que eu quero
para se põe a caminho 1.

340
00:14:24,760 --> 00:14:25,590
Posso fazer isso?

341
00:14:25,590 --> 00:14:26,490
Sim eu posso.

342
00:14:26,490 --> 00:14:28,730
>> Eu posso ir para o caminho 7 de lá?

343
00:14:28,730 --> 00:14:29,230
Sim eu posso.

344
00:14:29,230 --> 00:14:30,750
Isso existe também.

345
00:14:30,750 --> 00:14:32,460
Mas eu posso ir para o caminho 4 a partir daqui?

346
00:14:32,460 --> 00:14:35,550
Isso é como perguntar a pergunta, pode
Eu prosseguir por esse pequeno quadrado

347
00:14:35,550 --> 00:14:37,114
que eu tenho realçado em amarelo?

348
00:14:37,114 --> 00:14:38,030
Não há nada lá.

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

350
00:14:38,610 --> 00:14:41,310
>> Não há nenhuma maneira de avançar no caminho 4.

351
00:14:41,310 --> 00:14:46,480
Se Princeton foi neste trie, que 4
teria sido liberado para nós já.

352
00:14:46,480 --> 00:14:49,130
E por isso neste momento
chegamos a um beco sem saída.

353
00:14:49,130 --> 00:14:50,250
Não podemos ir mais longe.

354
00:14:50,250 --> 00:14:53,440
E assim podemos dizer, definitivamente, não.

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

356
00:14:56,760 --> 00:14:58,860
>> Então o que isso tudo significa?

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

358
00:14:59,360 --> 00:15:01,000
Há muita coisa acontecendo aqui.

359
00:15:01,000 --> 00:15:02,500
Há ponteiros em todo o lugar.

360
00:15:02,500 --> 00:15:04,249
E, como você pode ver
apenas a partir do diagrama,

361
00:15:04,249 --> 00:15:07,010
há uma grande quantidade de nós que
são do tipo que voam ao redor.

362
00:15:07,010 --> 00:15:13,480
Mas note cada vez que queria
verificar se algo foi no trie,

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

364
00:15:15,000 --> 00:15:17,208
>> Cada vez que queria
inserir algo no trie,

365
00:15:17,208 --> 00:15:20,440
temos de fazer 4 movimentos, possivelmente
mallocing algumas coisas ao longo do caminho.

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

367
00:15:23,482 --> 00:15:25,940
por vezes algum do caminho
já pode ser liberado para nós.

368
00:15:25,940 --> 00:15:30,520
E assim como o nosso se torna maior e trie
maior, nós temos fazer menos trabalho a cada vez

369
00:15:30,520 --> 00:15:32,270
para inserir coisas novas
porque já

370
00:15:32,270 --> 00:15:35,746
construiu um monte de o intermediário
ramos ao longo do caminho.

371
00:15:35,746 --> 00:15:38,370
Se nós sempre apenas tem que olhar para
4 coisas, 4 é apenas uma constante.

372
00:15:38,370 --> 00:15:41,750
Nós realmente estamos tipo de abordagem
inserção de tempo constante

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

374
00:15:44,501 --> 00:15:47,500
A desvantagem, é claro, que sendo
este trie, como você pode provavelmente dizer,

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

376
00:15:49,030 --> 00:15:51,040
Cada um destes nós
tem um monte de espaço.

377
00:15:51,040 --> 00:15:52,090
>> Mas esse é o tradeoff.

378
00:15:52,090 --> 00:15:55,260
Se queremos realmente rápido
inserção, eliminação realmente rápido,

379
00:15:55,260 --> 00:15:59,630
e lookup muito rápido, temos que
tem um monte de dados que voam ao redor.

380
00:15:59,630 --> 00:16:03,590
Temos de pôr de lado um monte de espaço
e memória para essa estrutura de dados

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

382
00:16:04,290 --> 00:16:05,415
>> E então essa é a troca.

383
00:16:05,415 --> 00:16:07,310
Mas parece que
pode tê-lo encontrado.

384
00:16:07,310 --> 00:16:09,560
Poderíamos descobriram que
Santo Graal de estruturas de dados

385
00:16:09,560 --> 00:16:12,264
com inserção rápida,
exclusão e de pesquisa.

386
00:16:12,264 --> 00:16:14,430
E talvez este será um
estrutura de dados apropriada

387
00:16:14,430 --> 00:16:18,890
para usar por qualquer informação
nós estamos tentando loja.

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

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