1
00:00:00,000 --> 00:00:02,994
>> [RIPRODUZIONE DI BRANI MUSICALI]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Così abbiamo avvicinandosi sempre più
e più vicino che Santo Graal dei dati

4
00:00:08,550 --> 00:00:13,050
strutture, che possiamo inserire
in, eliminare dalla, e guardare in alto

5
00:00:13,050 --> 00:00:15,440
in tempo costante.

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

7
00:00:16,270 --> 00:00:17,280
Questa è una sorta di meta.

8
00:00:17,280 --> 00:00:19,720
Vogliamo essere in grado di fare
cose molto, molto rapidamente.

9
00:00:19,720 --> 00:00:22,580
>> Abbiamo abbiamo trovato qui quando
stiamo parlando di tentativi?

10
00:00:22,580 --> 00:00:23,670
Bene, diamo un'occhiata.

11
00:00:23,670 --> 00:00:25,628
Così abbiamo visto diversi
diverse strutture dati

12
00:00:25,628 --> 00:00:28,680
che gestiscono la mappatura dei
cosiddetti coppie chiave-valore,

13
00:00:28,680 --> 00:00:32,080
mappatura qualche pezzo di dati
a qualche altro pezzo di dati

14
00:00:32,080 --> 00:00:36,020
così sappiamo dove trovare
informazioni nella struttura.

15
00:00:36,020 --> 00:00:40,060
>> Quindi per il campo, per esempio, la
chiave è l'indice di elemento o array

16
00:00:40,060 --> 00:00:42,600
posizione 0 o matrice 1 e così via.

17
00:00:42,600 --> 00:00:46,140
E il valore è il dato
che esiste in quella posizione.

18
00:00:46,140 --> 00:00:48,550
Quindi, ciò che è memorizzato in ordine di 0?

19
00:00:48,550 --> 00:00:54,290
Che cosa viene memorizzato in 1 campo contro solo
0 e 1, che sarebbe i tasti.

20
00:00:54,290 --> 00:00:56,360
>> Con una tabella di hash è
specie della stessa idea.

21
00:00:56,360 --> 00:01:00,690
Con una tabella hash, abbiamo questo hash
funzione che genera codici hash.

22
00:01:00,690 --> 00:01:03,670
Quindi la chiave è il codice hash dei dati.

23
00:01:03,670 --> 00:01:06,530
E il valore, in particolare
abbiamo parlato di concatenamento

24
00:01:06,530 --> 00:01:10,590
nel video su tabelle hash,
è quella lista collegata di dati

25
00:01:10,590 --> 00:01:12,550
che hash di tale codice hash.

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

27
00:01:14,050 --> 00:01:16,050
Che dire di un altro approccio
questo metodo, però?

28
00:01:16,050 --> 00:01:21,000
Che dire un metodo in cui la
chiave è garantito per essere unico,

29
00:01:21,000 --> 00:01:25,410
a differenza di una tabella hash, dove abbiamo potuto
finire con due pezzi di dati

30
00:01:25,410 --> 00:01:27,200
avendo lo stesso codice hash.

31
00:01:27,200 --> 00:01:30,020
E allora abbiamo a che fare con
che da una sonda o più

32
00:01:30,020 --> 00:01:33,340
preferibilmente concatenamento per risolvere questo problema.

33
00:01:33,340 --> 00:01:37,520
>> Così ora possiamo garantire
che la nostra chiave sarà unica.

34
00:01:37,520 --> 00:01:39,690
E se il nostro valore era
solo qualcosa come facile

35
00:01:39,690 --> 00:01:44,080
come vero e falso che ci dice se
o meno quel pezzo di informazioni

36
00:01:44,080 --> 00:01:45,610
esiste nella struttura?

37
00:01:45,610 --> 00:01:48,180
Booleano potrebbe essere semplice come un po '.

38
00:01:48,180 --> 00:01:52,660
Realisticamente è probabilmente una
byte più probabile che un po '.

39
00:01:52,660 --> 00:01:55,410
Ma è molto più piccolo di
memorizzare forse una stringa di 50 caratteri,

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

41
00:01:57,360 --> 00:02:02,210
>> Così cerca, simile alle tabelle,
che combinano array e lista collegata,

42
00:02:02,210 --> 00:02:05,790
cerca combinano gli array,
strutture, e puntatori

43
00:02:05,790 --> 00:02:08,509
insieme a memorizzare i dati in
un modo interessante che è

44
00:02:08,509 --> 00:02:11,550
molto diverso da
tutto ciò che abbiamo visto finora.

45
00:02:11,550 --> 00:02:16,750
Ora usiamo i dati come una tabella di marcia
navigare questa struttura dati.

46
00:02:16,750 --> 00:02:18,710
E se siamo in grado di seguire
la tabella di marcia, se possiamo

47
00:02:18,710 --> 00:02:22,390
seguire i dati
dall'inizio alla fine, ce la faremo

48
00:02:22,390 --> 00:02:24,945
sapere se tali dati
esistere nel trie.

49
00:02:24,945 --> 00:02:28,310
>> E se non possiamo seguire la mappa
da un senso alla fine del tutto,

50
00:02:28,310 --> 00:02:30,600
non possono esistere i dati.

51
00:02:30,600 --> 00:02:32,890
Anche in questo caso, i tasti sono qui
garantito per essere unico.

52
00:02:32,890 --> 00:02:36,020
E così a differenza di una tabella hash, ce la faremo mai
avere a che fare con le collisioni qui.

53
00:02:36,020 --> 00:02:39,090
E non ci sono due pezzi di dati
hanno esattamente la stessa tabella di marcia

54
00:02:39,090 --> 00:02:40,530
a meno che i dati siano identici.

55
00:02:40,530 --> 00:02:44,580
>> Se inseriamo John, poi
cerchiamo John.

56
00:02:44,580 --> 00:02:47,430
Ecco due pezzi identici di
dati, a destra, stiamo guardando attraverso.

57
00:02:47,430 --> 00:02:49,880
Ma per il resto, qualsiasi
due dati sono

58
00:02:49,880 --> 00:02:52,750
la garanzia di avere tabelle di marcia unici
attraverso questa struttura dati.

59
00:02:52,750 --> 00:02:56,210
E stiamo andando a dare un'occhiata a
una visuale di questo in un momento.

60
00:02:56,210 --> 00:02:58,810
>> Lo faremo cercando di
creare una nuova struttura di dati,

61
00:02:58,810 --> 00:03:00,564
mappare le seguenti coppie di valori chiave.

62
00:03:00,564 --> 00:03:03,480
In questo caso, non stiamo andando da usare
qualcosa di semplice come un valore booleano.

63
00:03:03,480 --> 00:03:06,200
Noi in realtà sarà memorizzare la stringa.

64
00:03:06,200 --> 00:03:08,690
E quella corda sta per
essere il nome di una università.

65
00:03:08,690 --> 00:03:12,140
>> E la chiave sarà l'anno
quando fu fondata quella università.

66
00:03:12,140 --> 00:03:15,380
Tutti gli anni per le università
stanno per essere quattro cifre.

67
00:03:15,380 --> 00:03:19,840
E così useremo quelle quattro cifre a
navigare attraverso questa struttura dati.

68
00:03:19,840 --> 00:03:22,270
E vedremo, ancora una volta, come
lo facciamo in appena un secondo.

69
00:03:22,270 --> 00:03:25,110
>> Alla fine del percorso,
vedremo il nome

70
00:03:25,110 --> 00:03:30,250
dell'università che corrisponde
per tale chiave quei quattro cifre.

71
00:03:30,250 --> 00:03:34,390
L'idea alla base di un trie
è che abbiamo un percorso centrale.

72
00:03:34,390 --> 00:03:35,640
Quindi pensare come un albero.

73
00:03:35,640 --> 00:03:39,211
E questo è simile a ortografia
e nel concetto di un albero.

74
00:03:39,211 --> 00:03:41,460
Generalmente quando pensiamo
alberi nel mondo reale,

75
00:03:41,460 --> 00:03:44,090
hanno una radice che è nella
terra e crescono verso l'alto

76
00:03:44,090 --> 00:03:46,830
e che hanno filiali
e hanno foglie.

77
00:03:46,830 --> 00:03:49,450
E fondamentalmente l'idea di
un trie è esattamente lo stesso,

78
00:03:49,450 --> 00:03:51,755
salvo che la radice è ancorata
da qualche parte nel cielo.

79
00:03:51,755 --> 00:03:53,130
E le foglie sono in fondo.

80
00:03:53,130 --> 00:03:55,750
>> Quindi è un po 'come fare un albero
e solo lanciando a testa in giù.

81
00:03:55,750 --> 00:03:56,880
Ma ci sono ancora i rami.

82
00:03:56,880 --> 00:03:59,463
E quelli sarebbero i nostri percorsi,
quelli saranno i nostri collegamenti

83
00:03:59,463 --> 00:04:02,220
dalla radice alle foglie.

84
00:04:02,220 --> 00:04:04,200
In questo caso, quelli
sentieri, quei rami

85
00:04:04,200 --> 00:04:08,490
sono etichettati con le cifre che ci dicono
da che parte andare da dove siamo.

86
00:04:08,490 --> 00:04:11,800
>> Se vediamo un 0, scendiamo questo ramo,
se vediamo un 1, scendiamo questo ramo,

87
00:04:11,800 --> 00:04:12,900
e così e così via.

88
00:04:12,900 --> 00:04:14,060
Ebbene, che cosa significa?

89
00:04:14,060 --> 00:04:16,519
Bene, ciò significa che
in ogni punto di giunzione

90
00:04:16,519 --> 00:04:19,260
e ogni nodo della
medio e ogni ramo,

91
00:04:19,260 --> 00:04:23,020
ci sono 10 possibili
luoghi che possiamo andare.

92
00:04:23,020 --> 00:04:27,690
Quindi ci sono 10 puntatori
da ogni posizione.

93
00:04:27,690 --> 00:04:30,610
>> Ed è qui che tentativi possono ottenere un
po 'intimidatorio per qualcuno

94
00:04:30,610 --> 00:04:34,460
chi è non ha un sacco di
esperienza in informatica prima.

95
00:04:34,460 --> 00:04:35,960
Ma tentativi sono davvero abbastanza impressionante.

96
00:04:35,960 --> 00:04:37,793
E se avete la
possibilità di lavorare con loro

97
00:04:37,793 --> 00:04:40,420
e siete disposti a scavare-in
e sperimentare con loro,

98
00:04:40,420 --> 00:04:44,234
sono davvero molto interessante
strutture di dati per lavorare con.

99
00:04:44,234 --> 00:04:46,900
Se vogliamo inserire un elemento
nel trie, tutto quello che dobbiamo fare

100
00:04:46,900 --> 00:04:51,360
è costruire il percorso corretto
dalla radice alla foglia.

101
00:04:51,360 --> 00:04:55,390
Ecco cosa ogni passo lungo
il modo in cui potrebbe essere simile.

102
00:04:55,390 --> 00:04:59,660
Stiamo per definire una nuova dati
struttura per un nuovo nodo chiamato trie.

103
00:04:59,660 --> 00:05:02,560
>> E all'interno di tali dati
struttura ci sono due pezzi.

104
00:05:02,560 --> 00:05:05,460
Stiamo andando a memorizzare il
il nome di una università.

105
00:05:05,460 --> 00:05:09,410
E stiamo andando a memorizzare
un array di puntatori

106
00:05:09,410 --> 00:05:12,190
ad altri nodi dello stesso tipo.

107
00:05:12,190 --> 00:05:14,780
Quindi, di nuovo, questo è quel genere
di concetto di tutto il mondo

108
00:05:14,780 --> 00:05:18,567
siamo, alle 10 possibili
luoghi possiamo andare.

109
00:05:18,567 --> 00:05:20,150
Se vediamo un 0, scendiamo questo ramo.

110
00:05:20,150 --> 00:05:22,690
Se vediamo un 1, questo ramo,
e così via e così via e così via.

111
00:05:22,690 --> 00:05:25,160
Se diciamo 9, scendiamo questo ramo.

112
00:05:25,160 --> 00:05:28,220
Così, in ogni punto di giunzione,
possiamo andare 10 posti possibili.

113
00:05:28,220 --> 00:05:35,740
Così ogni nodo deve contenere 10 puntatori
ad altri nodi, a 10 altri nodi.

114
00:05:35,740 --> 00:05:39,810
>> E i dati che stiamo memorizzazione è
solo il nome dell'università.

115
00:05:39,810 --> 00:05:41,060
Quindi cerchiamo di costruire un trie.

116
00:05:41,060 --> 00:05:44,860
Inseriamo un paio
di elementi in nostro trie.

117
00:05:44,860 --> 00:05:46,740
Così in cima,
questo è il nostro nodo principale.

118
00:05:46,740 --> 00:05:49,740
Questo è destinata probabilmente ad essere qualcosa
si sta andando a livello globale dichiarare.

119
00:05:49,740 --> 00:05:53,450
E si sta andando a mantenere il livello globale
un puntatore a questo nodo sempre.

120
00:05:53,450 --> 00:05:55,360
>> Stai andando a dire,
radice è uguale, e tu sei

121
00:05:55,360 --> 00:05:57,580
andando a malloc te stesso nodo trie.

122
00:05:57,580 --> 00:05:59,850
E si è mai andare
a toccare di nuovo radice.

123
00:05:59,850 --> 00:06:02,300
Ogni volta che si desidera
iniziare la navigazione attraverso,

124
00:06:02,300 --> 00:06:05,802
si imposta un altro puntatore
pari a radice, come trav,

125
00:06:05,802 --> 00:06:07,760
che è l'esempio I
utilizzare in molti dei miei video

126
00:06:07,760 --> 00:06:11,090
qui su pile e code
e liste di link e così via.

127
00:06:11,090 --> 00:06:13,320
>> È possibile impostare un altro puntatore
chiamato trav per l'attraversamento.

128
00:06:13,320 --> 00:06:15,890
E si utilizza per navigare trav
attraverso la struttura dei dati.

129
00:06:15,890 --> 00:06:17,500
Quindi cerchiamo di vedere come questo potrebbe apparire.

130
00:06:17,500 --> 00:06:19,880
Così adesso, cosa
fa un nodo assomiglia?

131
00:06:19,880 --> 00:06:22,920
Beh, proprio come i nostri dati
dichiarazione di struttura indicata,

132
00:06:22,920 --> 00:06:26,906
abbiamo una stringa, che
in questo caso è vuota.

133
00:06:26,906 --> 00:06:27,780
Non c'è niente qui.

134
00:06:27,780 --> 00:06:29,550
>> E un array di 10 puntatori.

135
00:06:29,550 --> 00:06:31,790
E proprio ora, abbiamo solo
avere 1 nodo in questo trie.

136
00:06:31,790 --> 00:06:33,110
Non c'è niente altro in esso.

137
00:06:33,110 --> 00:06:36,020
Così tutti e 10 di quelli
puntatori point a NULL.

138
00:06:36,020 --> 00:06:38,090
Questo è ciò che il rosso indica.

139
00:06:38,090 --> 00:06:39,500
>> Cerchiamo di inserire la stringa di Harvard.

140
00:06:39,500 --> 00:06:41,999
Inseriamo l'Università di
Harvard in questo trie, che

141
00:06:41,999 --> 00:06:43,940
è stata fondata nell'anno 1636.

142
00:06:43,940 --> 00:06:48,220
Vogliamo usare la chiave,
1636, di dirci dove siamo

143
00:06:48,220 --> 00:06:50,140
andando a memorizzare Harvard nel trie.

144
00:06:50,140 --> 00:06:51,470
Ora, come potremmo farlo?

145
00:06:51,470 --> 00:06:52,886
>> Potrebbe sembrare qualcosa di simile.

146
00:06:52,886 --> 00:06:54,160
Partiamo alla radice.

147
00:06:54,160 --> 00:06:56,920
E abbiamo questi 10 posti si può andare.

148
00:06:56,920 --> 00:06:59,900
La radice è proprio come qualsiasi
altro nodo del trie.

149
00:06:59,900 --> 00:07:02,850
Ci sono 10 posti si può andare da qui.

150
00:07:02,850 --> 00:07:07,215
>> Dove possiamo probabilmente vogliamo
andare se la chiave è 1636?

151
00:07:07,215 --> 00:07:08,340
Non c'è davvero due opzioni.

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

153
00:07:08,450 --> 00:07:10,825
Siamo in grado di costruire la chiave da
da destra a sinistra e iniziare con 6.

154
00:07:10,825 --> 00:07:14,000
Oppure potremmo costruire la chiave da
da sinistra a destra e iniziare con 1.

155
00:07:14,000 --> 00:07:16,140
>> E 'probabilmente più
intuitivo come un essere umano

156
00:07:16,140 --> 00:07:18,110
per capire che ti
Basta andare da sinistra a destra.

157
00:07:18,110 --> 00:07:21,140
E così, se voglio inserire
Harvard in questo trie,

158
00:07:21,140 --> 00:07:23,560
Probabilmente Voglio iniziare
partendo alla radice,

159
00:07:23,560 --> 00:07:25,720
guardando i miei 10 opzioni
di fronte a me, e dicendo

160
00:07:25,720 --> 00:07:28,700
Voglio andare giù per il sentiero 1.

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

162
00:07:29,700 --> 00:07:31,810
>> Ora, 1 percorso è attualmente nullo.

163
00:07:31,810 --> 00:07:35,920
Quindi, se voglio continuare su questa strada
inserire questo elemento nel trie,

164
00:07:35,920 --> 00:07:42,040
Devo malloc un nuovo nodo, avere 1
punto c'è, e poi io sono a posto.

165
00:07:42,040 --> 00:07:46,460
>> Quindi io fondamentalmente sono a un
punto dove mi trovo

166
00:07:46,460 --> 00:07:50,270
alla radice dell'albero o
trie e ci sono 10 filiali.

167
00:07:50,270 --> 00:07:52,260
Ma ogni ramo ha un
cancello di fronte ad esso.

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

169
00:07:53,060 --> 00:07:54,850
Perché non c'è niente altro c'è.

170
00:07:54,850 --> 00:07:56,522
Nessun passaggio sicuro.

171
00:07:56,522 --> 00:07:58,980
Questo significa che non c'è niente
giù uno di questi rami.

172
00:07:58,980 --> 00:08:02,532
Se voglio iniziare a costruire
qualcosa, voglio rimuovere il cancello.

173
00:08:02,532 --> 00:08:04,490
Voglio rimuovere il cancello
davanti al numero 1.

174
00:08:04,490 --> 00:08:05,698
E voglio camminare per questo.

175
00:08:05,698 --> 00:08:08,060
E voglio costruire
un altro posto per me andare.

176
00:08:08,060 --> 00:08:09,470
>> E questo è quello che ho fatto qui.

177
00:08:09,470 --> 00:08:11,430
Quindi 1 non è più punti a null.

178
00:08:11,430 --> 00:08:13,830
Ho detto che è sicuro di andare giù qui ora.

179
00:08:13,830 --> 00:08:15,789
Ho costruito un altro nodo.

180
00:08:15,789 --> 00:08:18,330
E quando arrivo a quel nodo, io
un'altra decisione da prendere.

181
00:08:18,330 --> 00:08:20,890
Dove sto andando andare da qui?

182
00:08:20,890 --> 00:08:22,700
>> Beh, ho già andato giù per la 1.

183
00:08:22,700 --> 00:08:24,470
Così ora probabilmente voglio andare in fondo alla 6.

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

185
00:08:24,970 --> 00:08:27,100
Ancora una volta, ho 10 sedi che posso scegliere.

186
00:08:27,100 --> 00:08:30,060
Quindi cerchiamo di ora scendiamo numero 6.

187
00:08:30,060 --> 00:08:32,280
Così ho chiaro il cancello
davanti al numero 6.

188
00:08:32,280 --> 00:08:33,250
E io cammino laggiù.

189
00:08:33,250 --> 00:08:34,580
E io costruisco un altro nodo.

190
00:08:34,580 --> 00:08:37,630
E ho raggiunto un altro punto di giunzione.

191
00:08:37,630 --> 00:08:40,289
>> Ancora una volta, ho 10 scelte
per dove posso andare.

192
00:08:40,289 --> 00:08:42,799
Ho spostato 1-6.

193
00:08:42,799 --> 00:08:44,215
Così ora probabilmente voglio andare a 3.

194
00:08:44,215 --> 00:08:45,381
3, non c'è niente che posso andare.

195
00:08:45,381 --> 00:08:48,980
Quindi devo spianare la strada
e costruire io un nuovo spazio.

196
00:08:48,980 --> 00:08:50,870
E poi da 3, dove voglio andare?

197
00:08:50,870 --> 00:08:52,450
Voglio andare giù 6.

198
00:08:52,450 --> 00:08:54,770
>> E, ancora una volta, ho dovuto
spianare la strada per farlo.

199
00:08:54,770 --> 00:08:59,179
Così ora ho usato la mia chiave per inserire creare
nodi e iniziano a costruire questo trie.

200
00:08:59,179 --> 00:09:00,220
Ho iniziato alla radice.

201
00:09:00,220 --> 00:09:03,666
Sono andato giù 1636.

202
00:09:03,666 --> 00:09:05,540
E ora sono in fondo
là su tale nodo.

203
00:09:05,540 --> 00:09:06,610
E si potrebbe essere in grado di
vedere sul vostro schermo.

204
00:09:06,610 --> 00:09:07,735
>> E 'evidenziato in giallo.

205
00:09:07,735 --> 00:09:10,020
Ecco dove attualmente sono.

206
00:09:10,020 --> 00:09:11,300
La mia chiave è fatto.

207
00:09:11,300 --> 00:09:13,030
Ho esaurito tutte le posizioni in mia chiave.

208
00:09:13,030 --> 00:09:15,040
Così non posso andare oltre.

209
00:09:15,040 --> 00:09:17,720
Quindi, a questo punto, tutto quello
ha realmente bisogno di fare è dire, OK.

210
00:09:17,720 --> 00:09:18,990
È un po 'come guardare
giù a terra,

211
00:09:18,990 --> 00:09:21,115
se stai immaginando
te stesso come questo tipo di percorso

212
00:09:21,115 --> 00:09:22,350
con diverse connessioni.

213
00:09:22,350 --> 00:09:25,800
Sorta di guardare verso il basso e una sorta di
spruzzare la pittura di Harvard a terra.

214
00:09:25,800 --> 00:09:26,800
Questo è il nome di questo.

215
00:09:26,800 --> 00:09:28,300
Sappiate che è ciò che è in questa posizione.

216
00:09:28,300 --> 00:09:31,870
Se partiamo alla radice e scendiamo
1 e poi 6 e poi 3 e poi 6,

217
00:09:31,870 --> 00:09:32,780
dove siamo?

218
00:09:32,780 --> 00:09:35,640
Beh, se si guarda in giù
e vediamo Harvard, poi

219
00:09:35,640 --> 00:09:38,960
sappiamo che Harvard era
fondata nel 1636 in base al modo

220
00:09:38,960 --> 00:09:41,400
stiamo implementare questa struttura dati.

221
00:09:41,400 --> 00:09:43,177
Così che era spera semplice.

222
00:09:43,177 --> 00:09:44,760
Stiamo per fare altri due inserimenti.

223
00:09:44,760 --> 00:09:50,060
E spero che vi aiuterà a
vedi questo fatto altre due volte.

224
00:09:50,060 --> 00:09:52,210
>> Ora, proviamo ad inserire un'altra università.

225
00:09:52,210 --> 00:09:54,630
Inseriamo Yale in questo trie.

226
00:09:54,630 --> 00:09:57,037
Yale è stata fondata nel 1701.

227
00:09:57,037 --> 00:09:58,870
Quindi inizieremo a
radice, come facciamo sempre.

228
00:09:58,870 --> 00:09:59,890
E abbiamo fissato un puntatore attraversamento.

229
00:09:59,890 --> 00:10:01,624
Stiamo andando a usarlo per muoversi attraverso.

230
00:10:01,624 --> 00:10:03,790
La prima cosa che vogliamo
fare è andare giù per il sentiero 1.

231
00:10:03,790 --> 00:10:05,830
Questa è la prima cifra della nostra chiave.

232
00:10:05,830 --> 00:10:08,420
Fortunatamente, però, non lo facciamo
hanno a che fare qualsiasi lavoro questa volta.

233
00:10:08,420 --> 00:10:09,919
Il percorso 1 è già stato eliminato.

234
00:10:09,919 --> 00:10:13,520
Ho rimosso in precedenza quando ho
è stato l'inserimento di Harvard a 1.636.

235
00:10:13,520 --> 00:10:18,090
Così posso muoversi in sicurezza
giù 1 e basta andare lì.

236
00:10:18,090 --> 00:10:20,150
Se può muoversi lungo la 1.

237
00:10:20,150 --> 00:10:22,930
>> Ora, però, voglio andare a 7.

238
00:10:22,930 --> 00:10:24,280
Ho aperto la strada alle 6.

239
00:10:24,280 --> 00:10:27,050
So che posso tranquillamente
procedete lungo il sentiero 6.

240
00:10:27,050 --> 00:10:29,220
Ma ho bisogno di proseguire sul sentiero 7.

241
00:10:29,220 --> 00:10:30,580
Allora, cosa devo fare?

242
00:10:30,580 --> 00:10:35,070
Beh, proprio come prima, ho solo bisogno
per cancellare la porta, uscire di strada,

243
00:10:35,070 --> 00:10:38,740
e costruire un nuovo nodo dal percorso 7.

244
00:10:38,740 --> 00:10:40,250
Proprio come questo.

245
00:10:40,250 --> 00:10:42,930
>> Così ora ho spostato 1 e poi 7.

246
00:10:42,930 --> 00:10:45,550
E ora notare, Sono una specie
di questa nuova subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Tutto il resto da 16
su, non mi preoccupo.

249
00:10:49,260 --> 00:10:50,720
Non sto facendo nulla 16.

250
00:10:50,720 --> 00:10:51,750
Sto facendo 17 roba.

251
00:10:51,750 --> 00:10:58,380
>> Così ora da 17 in poi, devo
sorta di Blaze nuovi sentieri qui.

252
00:10:58,380 --> 00:11:00,462
La cifra successiva la mia chiave è 0.

253
00:11:00,462 --> 00:11:01,670
Io chiaramente non può arrivare ovunque.

254
00:11:01,670 --> 00:11:02,628
Ho appena costruito questo nodo.

255
00:11:02,628 --> 00:11:04,550
Quindi so non c'è
percorsi in avanti da qui.

256
00:11:04,550 --> 00:11:06,370
Quindi devo fare uno io.

257
00:11:06,370 --> 00:11:09,360
>> Così ho malloc un nuovo nodo
e hanno 0 punti lì.

258
00:11:09,360 --> 00:11:12,770
E poi ancora una volta, ho una malloc
nuovo nodo e avere un punto lì.

259
00:11:12,770 --> 00:11:15,870
Ancora una volta, ho esaurito la mia chiave, 1701.

260
00:11:15,870 --> 00:11:18,472
Così guardo giù e vernice spray di Yale.

261
00:11:18,472 --> 00:11:19,680
Questo è il nome di questo nodo.

262
00:11:19,680 --> 00:11:24,660
>> E così ora se mai bisogno di vedere se Yale
è in questo trie, comincio alla radice,

263
00:11:24,660 --> 00:11:27,060
Scendo 1701, e guardo giù.

264
00:11:27,060 --> 00:11:30,030
E se vedo Yale spruzzo
dipinta sul terreno, poi

265
00:11:30,030 --> 00:11:32,200
So Yale esiste in questo trie.

266
00:11:32,200 --> 00:11:32,950
Facciamone un altro.

267
00:11:32,950 --> 00:11:36,430
Inseriamo Dartmouth in questo
trie, che è stata fondata nel 1769.

268
00:11:36,430 --> 00:11:37,750
>> Inizia alla radice di nuovo.

269
00:11:37,750 --> 00:11:39,445
La mia prima cifra della mia chiave è 1.

270
00:11:39,445 --> 00:11:40,820
Posso muovermi tranquillamente su questa strada.

271
00:11:40,820 --> 00:11:42,400
Che esiste già.

272
00:11:42,400 --> 00:11:44,040
La cifra successiva della mia chiave è 7.

273
00:11:44,040 --> 00:11:45,890
Posso muovermi tranquillamente su questa strada.

274
00:11:45,890 --> 00:11:47,540
Esiste pure.

275
00:11:47,540 --> 00:11:49,000
>> Il mio prossimo è 6.

276
00:11:49,000 --> 00:11:52,860
Da qui, da dove attualmente sono
in giallo lì in quel nodo centrale,

277
00:11:52,860 --> 00:11:56,060
6 è attualmente bloccato al largo.

278
00:11:56,060 --> 00:11:58,830
Se voglio andare su questa strada,
Devo costruire da solo.

279
00:11:58,830 --> 00:12:02,250
Quindi io malloc un nuovo nodo
e hanno 6 punti lì.

280
00:12:02,250 --> 00:12:04,250
E poi, di nuovo, io sono
nuove strade qui.

281
00:12:04,250 --> 00:12:10,750
>> Così ho malloc un nuovo nodo in modo che dal
che il sentiero node-- 9-- e quindi ora

282
00:12:10,750 --> 00:12:13,584
se sono in viaggio 1769, e guardo giù.

283
00:12:13,584 --> 00:12:15,500
Non c'è niente al momento
spruzzo lì verniciato.

284
00:12:15,500 --> 00:12:16,930
Posso scrivere Dartmouth.

285
00:12:16,930 --> 00:12:20,710
E ho inserito
Dartmouth nel trie.

286
00:12:20,710 --> 00:12:23,450
>> Ecco, questo è l'inserimento di
le cose nel trie.

287
00:12:23,450 --> 00:12:25,384
Ora vogliamo cercare le cose.

288
00:12:25,384 --> 00:12:27,050
Come si cerca per le cose nel trie?

289
00:12:27,050 --> 00:12:29,170
Beh, è ​​praticamente la stessa idea.

290
00:12:29,170 --> 00:12:33,620
Ora usiamo le cifre della chiave
per vedere se siamo in grado di passare dalla radice

291
00:12:33,620 --> 00:12:37,170
di dove vogliamo andare nel trie.

292
00:12:37,170 --> 00:12:41,620
>> Se abbiamo raggiunto un vicolo cieco in qualsiasi momento, quindi
sappiamo che questo elemento non può esiste

293
00:12:41,620 --> 00:12:44,500
oppure che il percorso sarebbe
sono già stati cancellati.

294
00:12:44,500 --> 00:12:45,930
Se facciamo tutto il modo per
Alla fine, tutto quello che dobbiamo fare

295
00:12:45,930 --> 00:12:48,471
è guardare in basso e vedere se questo è
l'elemento che stiamo cercando.

296
00:12:48,471 --> 00:12:49,335
Se lo è, il successo.

297
00:12:49,335 --> 00:12:52,610
Se non lo è, fallire.

298
00:12:52,610 --> 00:12:54,940
>> Quindi cerchiamo di ricerca per
Harvard questo trie.

299
00:12:54,940 --> 00:12:56,020
Partiamo alla radice.

300
00:12:56,020 --> 00:12:58,228
E, ancora una volta, stiamo andando a
creare un puntatore attraversamento

301
00:12:58,228 --> 00:12:59,390
a fare le nostre mosse per noi.

302
00:12:59,390 --> 00:13:02,080
Dalla radice sappiamo che la
primo luogo abbiamo bisogno di andare è 1,

303
00:13:02,080 --> 00:13:03,390
possiamo farlo?

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

305
00:13:03,982 --> 00:13:04,690
Se esiste in modo sicuro.

306
00:13:04,690 --> 00:13:06,660
Possiamo andare lì.

307
00:13:06,660 --> 00:13:08,440
>> Ora, il prossimo luogo abbiamo bisogno di andare è 6.

308
00:13:08,440 --> 00:13:10,557
Fa il percorso 6 esiste da qui?

309
00:13:10,557 --> 00:13:11,140
Sì, lo fa.

310
00:13:11,140 --> 00:13:12,690
Possiamo andare giù per il sentiero 6.

311
00:13:12,690 --> 00:13:13,905
E finiamo qui.

312
00:13:13,905 --> 00:13:16,130
>> Possiamo andare lungo il percorso da qui a 3?

313
00:13:16,130 --> 00:13:18,450
Beh, a quanto pare,
sì, esiste anche.

314
00:13:18,450 --> 00:13:20,790
E possiamo salire sul sentiero 6 da qui?

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

316
00:13:21,982 --> 00:13:24,002
>> Non abbiamo ancora risposto
ma la domanda.

317
00:13:24,002 --> 00:13:25,710
C'è ancora un altro
passo, che è ora

318
00:13:25,710 --> 00:13:28,520
abbiamo bisogno di guardare verso il basso e
vedere se questo è actually--

319
00:13:28,520 --> 00:13:32,660
se stiamo cercando di Harvard, è che
ciò che troviamo dopo esauriamo la chiave?

320
00:13:32,660 --> 00:13:35,430
Nell'esempio che stiamo usando qui,
gli anni sono sempre quattro cifre.

321
00:13:35,430 --> 00:13:40,280
Ma si potrebbero utilizzare l'esempio in cui
si memorizza un dizionario di parole.

322
00:13:40,280 --> 00:13:44,060
>> E così invece di avere 10 puntatori
Per la mia città, si potrebbe avere 26.

323
00:13:44,060 --> 00:13:46,040
Uno per ogni lettera dell'alfabeto.

324
00:13:46,040 --> 00:13:50,350
E ci sono alcune parole come pipistrello,
che è un sottoinsieme di lotto, per esempio.

325
00:13:50,350 --> 00:13:53,511
E quindi, anche se si arriva al
fine della chiave e si guarda verso il basso,

326
00:13:53,511 --> 00:13:55,260
si potrebbe non vedere quello che
che stai cercando.

327
00:13:55,260 --> 00:13:58,500
>> In modo da avere sempre a percorrere
l'intero percorso e poi

328
00:13:58,500 --> 00:14:01,540
se tu fossi in grado con successo
attraversare l'intero percorso,

329
00:14:01,540 --> 00:14:03,440
guardare in basso e fare una conferma definitiva.

330
00:14:03,440 --> 00:14:05,120
E 'questo che sto cercando?

331
00:14:05,120 --> 00:14:07,740
Beh, guardo giù dopo l'avvio
in alto e in corso 1636.

332
00:14:07,740 --> 00:14:08,240
Guardo giù.

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

334
00:14:09,400 --> 00:14:11,689
Quindi, sì, ci sono riuscito.

335
00:14:11,689 --> 00:14:13,980
E se quello che sto cercando
non è nel trie, però.

336
00:14:13,980 --> 00:14:17,200
Che cosa succede se sto cercando di Princeton,
che è stata fondata nel 1746.

337
00:14:17,200 --> 00:14:20,875
E così 1746 diventa la mia chiave
per navigare attraverso il trie.

338
00:14:20,875 --> 00:14:22,040
Beh, comincio alla radice.

339
00:14:22,040 --> 00:14:24,760
E il primo posto che voglio
a va lungo il sentiero 1.

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

341
00:14:25,590 --> 00:14:26,490
Sì io posso.

342
00:14:26,490 --> 00:14:28,730
>> Posso andare giù per il sentiero 7 da lì?

343
00:14:28,730 --> 00:14:29,230
Si Io posso.

344
00:14:29,230 --> 00:14:30,750
Che esiste anche.

345
00:14:30,750 --> 00:14:32,460
Ma posso andare giù per il sentiero 4 da qui?

346
00:14:32,460 --> 00:14:35,550
Ecco come fare la domanda, può
Procedo verso il basso che piazzetta

347
00:14:35,550 --> 00:14:37,114
che ho evidenziato in giallo?

348
00:14:37,114 --> 00:14:38,030
Non c'è niente lì.

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

350
00:14:38,610 --> 00:14:41,310
>> Non c'è modo in avanti lungo il sentiero 4.

351
00:14:41,310 --> 00:14:46,480
Se Princeton era in questo trie, che il 4
sarebbe stato eliminato per noi già.

352
00:14:46,480 --> 00:14:49,130
E quindi a questo punto
abbiamo raggiunto un vicolo cieco.

353
00:14:49,130 --> 00:14:50,250
Non possiamo andare oltre.

354
00:14:50,250 --> 00:14:53,440
E così si può dire, in definitiva, n.

355
00:14:53,440 --> 00:14:56,760
Princeton non esiste in questo trie.

356
00:14:56,760 --> 00:14:58,860
>> Che cosa significa tutto questo?

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

358
00:14:59,360 --> 00:15:01,000
Ci sono un sacco di cose qui.

359
00:15:01,000 --> 00:15:02,500
C'è puntatori in tutto il luogo.

360
00:15:02,500 --> 00:15:04,249
E, come si può vedere
solo dal diagramma,

361
00:15:04,249 --> 00:15:07,010
ci sono un sacco di nodi che
sono specie di volano intorno.

362
00:15:07,010 --> 00:15:13,480
Ma notare ogni volta che volevamo
verificare se c'era qualcosa nel trie,

363
00:15:13,480 --> 00:15:15,000
abbiamo solo dovuto fare 4 mosse.

364
00:15:15,000 --> 00:15:17,208
>> Ogni volta che volevamo
inserire qualcosa nel trie,

365
00:15:17,208 --> 00:15:20,440
dobbiamo fare 4 mosse, forse
mallocing alcune cose lungo la strada.

366
00:15:20,440 --> 00:15:23,482
Ma, come abbiamo visto quando abbiamo inserito
Dartmouth nel trie,

367
00:15:23,482 --> 00:15:25,940
volte alcuni di percorso
potrebbe già essere eliminato per noi.

368
00:15:25,940 --> 00:15:30,520
E così come la nostra trie diventa più grande e
più grande, dobbiamo fare meno lavoro ogni volta

369
00:15:30,520 --> 00:15:32,270
inserire nuove cose
perché abbiamo già

370
00:15:32,270 --> 00:15:35,746
costruito un sacco dell'intermedio
rami lungo la strada.

371
00:15:35,746 --> 00:15:38,370
Se abbiamo sempre e solo guardare a
4 cose, 4 è solo una costante.

372
00:15:38,370 --> 00:15:41,750
Abbiamo davvero stiamo avvicinando tipo di
inserimento costante di tempo

373
00:15:41,750 --> 00:15:44,501
e costante di tempo di ricerca.

374
00:15:44,501 --> 00:15:47,500
Il compromesso, naturalmente, è che
questo trie, come si può probabilmente dire,

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

376
00:15:49,030 --> 00:15:51,040
Ognuno di questi nodi
prende un sacco di spazio.

377
00:15:51,040 --> 00:15:52,090
>> Ma questo è il compromesso.

378
00:15:52,090 --> 00:15:55,260
Se vogliamo davvero veloce
inserimento, cancellazione davvero veloce,

379
00:15:55,260 --> 00:15:59,630
e di ricerca molto veloce, dobbiamo
hanno un sacco di dati che volano intorno.

380
00:15:59,630 --> 00:16:03,590
Dobbiamo mettere da parte un sacco di spazio
e memoria per quella struttura di dati

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

382
00:16:04,290 --> 00:16:05,415
>> E così che è il compromesso.

383
00:16:05,415 --> 00:16:07,310
Ma sembra che
potrebbe aver trovato.

384
00:16:07,310 --> 00:16:09,560
Avremmo potuto scoperto che
Santo Graal di strutture di dati

385
00:16:09,560 --> 00:16:12,264
con l'inserimento rapido,
la cancellazione, e ricerca.

386
00:16:12,264 --> 00:16:14,430
E forse questo sarà un
adeguata struttura di dati

387
00:16:14,430 --> 00:16:18,890
da utilizzare per qualsiasi informazione
stiamo cercando di negozio.

388
00:16:18,890 --> 00:16:21,860
Sono Doug Lloyd, questo è CS50.

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