1
00:00:00,000 --> 00:00:02,994
>> [Jouer de la musique]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Donc nous avons progresse lentement
et plus proche que le Saint-Graal des données

4
00:00:08,550 --> 00:00:13,050
structures, l'une que nous pouvons insérer
en, de supprimer et rechercher

5
00:00:13,050 --> 00:00:15,440
en temps constant.

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

7
00:00:16,270 --> 00:00:17,280
Voilà en quelque sorte le but.

8
00:00:17,280 --> 00:00:19,720
Nous voulons être en mesure de le faire
des choses très, très rapidement.

9
00:00:19,720 --> 00:00:22,580
>> Avons-nous l'avons trouvé ici quand
nous parlons essais?

10
00:00:22,580 --> 00:00:23,670
Eh bien, nous allons jeter un coup d'oeil.

11
00:00:23,670 --> 00:00:25,628
Donc, nous avons vu plusieurs
différentes structures de données

12
00:00:25,628 --> 00:00:28,680
qui manient la cartographie des
soi-disant paires clé-valeur,

13
00:00:28,680 --> 00:00:32,080
la cartographie de certaines données à
à un autre élément de données

14
00:00:32,080 --> 00:00:36,020
donc nous savons où les trouver
l'information dans la structure.

15
00:00:36,020 --> 00:00:40,060
>> Ainsi, par réseau, par exemple, la
clé est l'indice de l'élément ou réseau

16
00:00:40,060 --> 00:00:42,600
emplacement 0 ou un tableau 1 et ainsi de suite.

17
00:00:42,600 --> 00:00:46,140
Et la valeur est les données
qui existe à cet endroit.

18
00:00:46,140 --> 00:00:48,550
Donc ce qui est stocké dans le tableau 0?

19
00:00:48,550 --> 00:00:54,290
Quel est stocké dans le tableau 1 contre seulement
0 et 1, ce qui serait les touches.

20
00:00:54,290 --> 00:00:56,360
>> Avec une table de hachage il est
sorte de la même idée.

21
00:00:56,360 --> 00:01:00,690
Avec une table de hachage, nous avons ce hachage
fonction qui génère des codes de hachage.

22
00:01:00,690 --> 00:01:03,670
Donc, la clé est le code de hachage des données.

23
00:01:03,670 --> 00:01:06,530
Et la valeur, en particulier
nous avons parlé de chaînage

24
00:01:06,530 --> 00:01:10,590
dans la vidéo sur les tables de hachage,
est que la liste chaînée des données

25
00:01:10,590 --> 00:01:12,550
dont le hachage pour ce code de hachage.

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

27
00:01:14,050 --> 00:01:16,050
Qu'en est-il une autre approche
cette méthode, si?

28
00:01:16,050 --> 00:01:21,000
Qu'en est-il une méthode où le
clé est garantie unique,

29
00:01:21,000 --> 00:01:25,410
contrairement à une table de hachage, où nous pourrions
retrouver avec deux morceaux de données

30
00:01:25,410 --> 00:01:27,200
ayant le même code de hachage.

31
00:01:27,200 --> 00:01:30,020
Et puis nous avons à traiter avec
que ce soit par palpage ou plus

32
00:01:30,020 --> 00:01:33,340
chaînage de préférence pour régler ce problème.

33
00:01:33,340 --> 00:01:37,520
>> Alors maintenant, nous pouvons garantir
que notre clé sera unique.

34
00:01:37,520 --> 00:01:39,690
Et si notre valeur était
juste quelque chose aussi facile

35
00:01:39,690 --> 00:01:44,080
comme vrai et le faux qui nous dit si
ou non cette information

36
00:01:44,080 --> 00:01:45,610
existe dans la structure?

37
00:01:45,610 --> 00:01:48,180
Booléenne pourrait être aussi simple que un peu.

38
00:01:48,180 --> 00:01:52,660
De façon réaliste, il est probablement une
octet plus susceptibles que les un peu.

39
00:01:52,660 --> 00:01:55,410
Mais cela est beaucoup plus petit que
le stockage peut être une chaîne de 50 caractères,

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

41
00:01:57,360 --> 00:02:02,210
>> Donc essais, semblable aux différentes tables,
qui combinent les tableaux et les listes chaînées,

42
00:02:02,210 --> 00:02:05,790
tente de combiner les tableaux,
les structures et les pointeurs

43
00:02:05,790 --> 00:02:08,509
ainsi que pour stocker des données en
une façon intéressante qui est

44
00:02:08,509 --> 00:02:11,550
assez différent de
tout ce que nous avons vu jusqu'à présent.

45
00:02:11,550 --> 00:02:16,750
Maintenant, nous utilisons les données de feuille de route
naviguer à cette structure de données.

46
00:02:16,750 --> 00:02:18,710
Et si nous pouvons suivre
la feuille de route, si nous le pouvons

47
00:02:18,710 --> 00:02:22,390
suivre les données de
début à la fin, nous allons

48
00:02:22,390 --> 00:02:24,945
savoir si ces données
exister dans le trie.

49
00:02:24,945 --> 00:02:28,310
>> Et si nous ne pouvons pas suivre la carte
de signifier à la fin du tout,

50
00:02:28,310 --> 00:02:30,600
les données ne peuvent pas exister.

51
00:02:30,600 --> 00:02:32,890
Encore une fois, les touches sont ici
assuré d'être unique.

52
00:02:32,890 --> 00:02:36,020
Et contrairement à une table de hachage, nous ne serons jamais
avoir à traiter avec des collisions ici.

53
00:02:36,020 --> 00:02:39,090
Et ni deux morceaux de données
avoir exactement la même feuille de route

54
00:02:39,090 --> 00:02:40,530
à moins que les données sont identiques.

55
00:02:40,530 --> 00:02:44,580
>> Si nous insérons John, puis
nous recherchons pour John.

56
00:02:44,580 --> 00:02:47,430
Voilà deux pièces identiques de
données, à droite, nous cherchons à travers.

57
00:02:47,430 --> 00:02:49,880
Mais sinon, tout
deux éléments de données sont

58
00:02:49,880 --> 00:02:52,750
la garantie d'avoir des feuilles de route uniques
grâce à cette structure de données.

59
00:02:52,750 --> 00:02:56,210
Et nous allons jeter un oeil à
un visuel de cela dans un instant.

60
00:02:56,210 --> 00:02:58,810
>> Nous allons faire cela en essayant de
créer une nouvelle structure de données,

61
00:02:58,810 --> 00:03:00,564
la cartographie des paires de valeurs clés suivants.

62
00:03:00,564 --> 00:03:03,480
Dans ce cas, on ne va pas à utiliser
quelque chose de simple comme un booléen.

63
00:03:03,480 --> 00:03:06,200
Nous allons effectivement stocker la chaîne.

64
00:03:06,200 --> 00:03:08,690
Et cette chaîne va
être le nom d'une université.

65
00:03:08,690 --> 00:03:12,140
>> Et la clé va être l'année
quand cette université a été fondée.

66
00:03:12,140 --> 00:03:15,380
Tous les ans pour les universités
vont être quatre chiffres.

67
00:03:15,380 --> 00:03:19,840
Et donc nous allons utiliser ces quatre chiffres à
naviguer dans cette structure de données.

68
00:03:19,840 --> 00:03:22,270
Et nous verrons, encore une fois, comment
nous faisons cela en seulement une seconde.

69
00:03:22,270 --> 00:03:25,110
>> A la fin de la trajectoire,
nous verrons le nom

70
00:03:25,110 --> 00:03:30,250
de l'université qui correspond
à cette touche, ces quatre chiffres.

71
00:03:30,250 --> 00:03:34,390
L'idée de base derrière un trie
est que nous avons une voie centrale.

72
00:03:34,390 --> 00:03:35,640
Alors, pensez-y comme un arbre.

73
00:03:35,640 --> 00:03:39,211
Et ce qui est similaire à l'orthographe
et dans le concept à un arbre.

74
00:03:39,211 --> 00:03:41,460
Généralement, lorsque nous pensons à
arbres dans le monde réel,

75
00:03:41,460 --> 00:03:44,090
ils ont une racine qui est dans le
sol et ils poussent à la hausse

76
00:03:44,090 --> 00:03:46,830
et ils ont des succursales
et ils ont des feuilles.

77
00:03:46,830 --> 00:03:49,450
Et fondamentalement l'idée de
un trie est exactement le même,

78
00:03:49,450 --> 00:03:51,755
sauf que racine est ancrée
quelque part dans le ciel.

79
00:03:51,755 --> 00:03:53,130
Et les feuilles sont au fond.

80
00:03:53,130 --> 00:03:55,750
>> Donc, il est un peu comme prendre un arbre
et juste retournant à l'envers.

81
00:03:55,750 --> 00:03:56,880
Mais il ya encore des branches.

82
00:03:56,880 --> 00:03:59,463
Et ceux qui seraient nos voies,
ceux-ci seront nos connexions

83
00:03:59,463 --> 00:04:02,220
partir de la racine vers les feuilles.

84
00:04:02,220 --> 00:04:04,200
Dans ce cas, ceux qui
chemins, ces branches

85
00:04:04,200 --> 00:04:08,490
sont étiquetés avec des chiffres qui nous disent
où aller à partir de là où nous sommes.

86
00:04:08,490 --> 00:04:11,800
>> Si nous voyons un 0, nous descendons cette branche,
si nous voyons un 1, nous descendons cette branche,

87
00:04:11,800 --> 00:04:12,900
et ainsi et ainsi de suite.

88
00:04:12,900 --> 00:04:14,060
Eh bien, qu'est-ce que cela signifie?

89
00:04:14,060 --> 00:04:16,519
Eh bien, cela signifie que
à chaque point de jonction

90
00:04:16,519 --> 00:04:19,260
et chaque noeud de la
milieu et chaque branche,

91
00:04:19,260 --> 00:04:23,020
il y a 10 possible
lieux que nous pouvons aller.

92
00:04:23,020 --> 00:04:27,690
Donc, il ya 10 pointeurs
de chaque emplacement.

93
00:04:27,690 --> 00:04:30,610
>> Et ce est là essais peuvent obtenir un
peu intimidant pour quelqu'un

94
00:04:30,610 --> 00:04:34,460
qui est n'a pas beaucoup de
expérience en informatique avant.

95
00:04:34,460 --> 00:04:35,960
Mais essais sont vraiment assez impressionnant.

96
00:04:35,960 --> 00:04:37,793
Et si vous avez la
chance de travailler avec eux

97
00:04:37,793 --> 00:04:40,420
et vous êtes prêt à creuser dans
et d'expérimenter avec eux,

98
00:04:40,420 --> 00:04:44,234
ils sont vraiment très intéressant
structures de données pour travailler avec.

99
00:04:44,234 --> 00:04:46,900
Si nous voulons insérer un élément
dans le trie, tout ce que nous devons faire

100
00:04:46,900 --> 00:04:51,360
est de construire le chemin correct
de la racine à la feuille.

101
00:04:51,360 --> 00:04:55,390
Voici ce que chaque étape
la façon dont pourrait ressembler.

102
00:04:55,390 --> 00:04:59,660
Nous allons définir une nouvelle donnée
structure d'un nouveau nœud appelé un trie.

103
00:04:59,660 --> 00:05:02,560
>> Et à l'intérieur de ces données
la structure il ya deux morceaux.

104
00:05:02,560 --> 00:05:05,460
Nous allons stocker le
nom d'une université.

105
00:05:05,460 --> 00:05:09,410
Et nous allons stocker
un tableau de pointeurs

106
00:05:09,410 --> 00:05:12,190
à d'autres noeuds du même type.

107
00:05:12,190 --> 00:05:14,780
Donc, encore une fois, cela est ce genre
du concept de partout

108
00:05:14,780 --> 00:05:18,567
nous sommes, nous, à 10 possible
endroits nous pouvons aller.

109
00:05:18,567 --> 00:05:20,150
Si nous voyons un 0, nous descendons cette branche.

110
00:05:20,150 --> 00:05:22,690
Si nous voyons un 1, cette branche,
et ainsi de suite et ainsi de suite et ainsi de suite.

111
00:05:22,690 --> 00:05:25,160
Si nous disons 9, nous descendons cette branche.

112
00:05:25,160 --> 00:05:28,220
Donc, à chaque point de jonction,
nous pouvons aller de 10 places possibles.

113
00:05:28,220 --> 00:05:35,740
Ainsi, chaque noeud doit contenir 10 des pointeurs
à d'autres noeuds, et 10 d'autres nœuds.

114
00:05:35,740 --> 00:05:39,810
>> Et les données que nous stockage est
juste le nom de l'université.

115
00:05:39,810 --> 00:05:41,060
Donc, nous allons construire un trie.

116
00:05:41,060 --> 00:05:44,860
Insérons un couple
des éléments dans notre trie.

117
00:05:44,860 --> 00:05:46,740
Donc, tout en haut,
ceci est notre nœud racine.

118
00:05:46,740 --> 00:05:49,740
Cela va probablement être quelque chose
vous allez déclarer globalement.

119
00:05:49,740 --> 00:05:53,450
Et vous allez maintenir globalement
un pointeur vers ce nœud toujours.

120
00:05:53,450 --> 00:05:55,360
>> Vous allez dire,
root est égal, et vous êtes

121
00:05:55,360 --> 00:05:57,580
allez vous malloc noeud de Trie.

122
00:05:57,580 --> 00:05:59,850
Et vous allez jamais
de toucher à nouveau racine.

123
00:05:59,850 --> 00:06:02,300
Chaque fois que vous voulez
commencer à naviguer à travers,

124
00:06:02,300 --> 00:06:05,802
vous définissez un autre pointeur
égale à la racine, comme trav,

125
00:06:05,802 --> 00:06:07,760
qui est l'exemple que je
utiliser dans plusieurs de mes vidéos

126
00:06:07,760 --> 00:06:11,090
ici sur des piles et files d'attente
et des listes de liens et ainsi de suite.

127
00:06:11,090 --> 00:06:13,320
>> Vous définissez un autre pointeur
trav appelé pour la traversée.

128
00:06:13,320 --> 00:06:15,890
Et vous utilisez trav pour naviguer
à travers la structure de données.

129
00:06:15,890 --> 00:06:17,500
Donc, nous allons voir comment cela pourrait ressembler.

130
00:06:17,500 --> 00:06:19,880
Donc, en ce moment, ce qui
un noeud ne ressemble?

131
00:06:19,880 --> 00:06:22,920
Eh bien, tout comme nos données
déclaration de la structure indiquée,

132
00:06:22,920 --> 00:06:26,906
nous avons une chaîne, qui
dans ce cas est vide.

133
00:06:26,906 --> 00:06:27,780
Il n'y a rien ici.

134
00:06:27,780 --> 00:06:29,550
>> Et un tableau de 10 pointeurs.

135
00:06:29,550 --> 00:06:31,790
Et en ce moment, nous ne
avoir une nœud dans cette trie.

136
00:06:31,790 --> 00:06:33,110
Il n'y a rien d'autre en elle.

137
00:06:33,110 --> 00:06:36,020
Donc, tous les 10 de ceux
pointeurs points à null.

138
00:06:36,020 --> 00:06:38,090
Voilà ce que le rouge indique.

139
00:06:38,090 --> 00:06:39,500
>> Insérons la chaîne de Harvard.

140
00:06:39,500 --> 00:06:41,999
Insérons l'Université de
Harvard dans cette trie, qui

141
00:06:41,999 --> 00:06:43,940
a été fondée en 1636.

142
00:06:43,940 --> 00:06:48,220
Nous voulons utiliser la clé,
1636, pour nous dire où nous en sommes

143
00:06:48,220 --> 00:06:50,140
allez stocker Harvard dans le trie.

144
00:06:50,140 --> 00:06:51,470
Maintenant, comment pourrions-nous le faire?

145
00:06:51,470 --> 00:06:52,886
>> Il pourrait ressembler à ceci.

146
00:06:52,886 --> 00:06:54,160
Nous commençons à la racine.

147
00:06:54,160 --> 00:06:56,920
Et nous avons ces 10 endroits où nous pouvons aller.

148
00:06:56,920 --> 00:06:59,900
La racine est comme tout
autre nœud de l'trie.

149
00:06:59,900 --> 00:07:02,850
Il ya 10 places, nous pouvons aller d'ici.

150
00:07:02,850 --> 00:07:07,215
>> Où voulons-nous probablement
où aller si la clé est 1636?

151
00:07:07,215 --> 00:07:08,340
Il n'y a vraiment deux options.

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

153
00:07:08,450 --> 00:07:10,825
Nous pouvons construire la clé de
de droite à gauche et de commencer avec 6.

154
00:07:10,825 --> 00:07:14,000
Ou nous pourrions construire la clé de
de gauche à droite et de commencer avec 1.

155
00:07:14,000 --> 00:07:16,140
>> Il est probablement plus
intuitive comme un être humain

156
00:07:16,140 --> 00:07:18,110
à nous comprendre va
Il suffit d'aller de gauche à droite.

157
00:07:18,110 --> 00:07:21,140
Et si je veux insérer
Harvard dans cette trie,

158
00:07:21,140 --> 00:07:23,560
Je veux probablement commencer
en partant de la racine,

159
00:07:23,560 --> 00:07:25,720
en regardant mes 10 options
en face de moi, en disant

160
00:07:25,720 --> 00:07:28,700
Je veux aller dans la voie 1.

161
00:07:28,700 --> 00:07:29,700
D'ACCORD.

162
00:07:29,700 --> 00:07:31,810
>> Maintenant, une voie est actuellement nulle.

163
00:07:31,810 --> 00:07:35,920
Donc, si je veux continuer dans cette voie
pour insérer cet élément dans le trie,

164
00:07:35,920 --> 00:07:42,040
Je dois malloc un nouveau nœud, avoir 1
signaler là, et puis je suis bon pour aller.

165
00:07:42,040 --> 00:07:46,460
>> Donc, je suis fondamentalement à une
point où je suis debout

166
00:07:46,460 --> 00:07:50,270
à la racine de l'arbre ou le
Trie et il ya 10 branches.

167
00:07:50,270 --> 00:07:52,260
Mais chaque branche a une
porte en face d'elle.

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

169
00:07:53,060 --> 00:07:54,850
Parce qu'il n'y a rien d'autre, il ya.

170
00:07:54,850 --> 00:07:56,522
Pas de passage en toute sécurité.

171
00:07:56,522 --> 00:07:58,980
Cela signifie qu'il n'y a rien
bas l'une de ces branches.

172
00:07:58,980 --> 00:08:02,532
Si je veux commencer à construire
quelque chose, je veux enlever la porte.

173
00:08:02,532 --> 00:08:04,490
Je veux enlever la porte
en face du numéro 1.

174
00:08:04,490 --> 00:08:05,698
Et je veux marcher dans cela.

175
00:08:05,698 --> 00:08:08,060
Et je veux construire
un autre lieu pour moi d'aller.

176
00:08:08,060 --> 00:08:09,470
>> Et voilà ce que je l'ai fait ici.

177
00:08:09,470 --> 00:08:11,430
Donc 1 ne pointe plus sur null.

178
00:08:11,430 --> 00:08:13,830
Je l'ai dit il est sûr de descendre ici maintenant.

179
00:08:13,830 --> 00:08:15,789
Je construit un autre nœud.

180
00:08:15,789 --> 00:08:18,330
Et quand je reçois à ce nœud, je
avoir une autre décision à prendre.

181
00:08:18,330 --> 00:08:20,890
Où vais-je aller d'ici?

182
00:08:20,890 --> 00:08:22,700
>> Eh bien, je suis déjà allé en bas de la 1.

183
00:08:22,700 --> 00:08:24,470
Alors maintenant, je veux probablement descendre la 6.

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

185
00:08:24,970 --> 00:08:27,100
Encore une fois, je dois 10 emplacements je peux choisir.

186
00:08:27,100 --> 00:08:30,060
Passons donc maintenant en baisse numéro 6.

187
00:08:30,060 --> 00:08:32,280
Donc je effacer la porte
devant le numéro 6.

188
00:08:32,280 --> 00:08:33,250
Et je marche là-bas.

189
00:08:33,250 --> 00:08:34,580
Et je construis un autre nœud.

190
00:08:34,580 --> 00:08:37,630
Et je suis arrivé à un autre point de jonction.

191
00:08:37,630 --> 00:08:40,289
>> Encore une fois, je dois 10 choix
pour où je peux aller.

192
00:08:40,289 --> 00:08:42,799
Je l'ai déplacé de 1 à 6.

193
00:08:42,799 --> 00:08:44,215
Alors maintenant, je veux probablement pour aller à 3.

194
00:08:44,215 --> 00:08:45,381
3, il n'y a nulle part où je peux aller.

195
00:08:45,381 --> 00:08:48,980
Donc, je dois ouvrir la voie
et me construire un nouvel espace.

196
00:08:48,980 --> 00:08:50,870
Et puis à partir de 3, où je veux aller?

197
00:08:50,870 --> 00:08:52,450
Je veux aller en baisse de 6.

198
00:08:52,450 --> 00:08:54,770
>> Et, encore une fois, je devais
effacer la façon de le faire.

199
00:08:54,770 --> 00:08:59,179
Alors maintenant, je l'ai utilisé ma clé pour insérer créer
nœuds et commencent à construire cette trie.

200
00:08:59,179 --> 00:09:00,220
Je l'ai commencé à la racine.

201
00:09:00,220 --> 00:09:03,666
Je suis allé jusqu'à 1,636.

202
00:09:03,666 --> 00:09:05,540
Et maintenant, je suis au fond
il sur ce nœud.

203
00:09:05,540 --> 00:09:06,610
Et vous pourriez être en mesure de
voir sur votre écran.

204
00:09:06,610 --> 00:09:07,735
>> Il est surligné en jaune.

205
00:09:07,735 --> 00:09:10,020
Voilà où je suis actuellement.

206
00:09:10,020 --> 00:09:11,300
Ma clé est fait.

207
00:09:11,300 --> 00:09:13,030
Je suis épuisé toutes les positions dans ma clé.

208
00:09:13,030 --> 00:09:15,040
Donc, je ne peux pas aller plus loin.

209
00:09:15,040 --> 00:09:17,720
Donc, à ce stade, tout ce que je
vraiment besoin de faire est de dire, OK.

210
00:09:17,720 --> 00:09:18,990
Il est un peu comme la recherche
vers le sol,

211
00:09:18,990 --> 00:09:21,115
si vous êtes envisager
vous que ce genre de chemin

212
00:09:21,115 --> 00:09:22,350
avec différentes connexions.

213
00:09:22,350 --> 00:09:25,800
Trier de regarder vers le bas et une sorte de
peinture au pistolet Harvard sur le terrain.

214
00:09:25,800 --> 00:09:26,800
Voilà le nom de cette.

215
00:09:26,800 --> 00:09:28,300
Sachez que est ce qui est à cet endroit.

216
00:09:28,300 --> 00:09:31,870
Si nous commençons à la racine et nous descendons
1 puis 6 puis 3, puis 6,

217
00:09:31,870 --> 00:09:32,780
où sommes-nous?

218
00:09:32,780 --> 00:09:35,640
Eh bien, si nous regardons vers le bas
et nous voyons Harvard, puis

219
00:09:35,640 --> 00:09:38,960
nous savons que Harvard était
fondée en 1636 basée sur le chemin

220
00:09:38,960 --> 00:09:41,400
nous mettons en œuvre cette structure de données.

221
00:09:41,400 --> 00:09:43,177
Donc, ce fut espérons simple.

222
00:09:43,177 --> 00:09:44,760
Nous allons faire deux autres insertions.

223
00:09:44,760 --> 00:09:50,060
Et nous espérons que ça va aider à
cela soit fait deux fois de plus.

224
00:09:50,060 --> 00:09:52,210
>> Maintenant, nous allons insérer une autre université.

225
00:09:52,210 --> 00:09:54,630
Insérons Yale dans cette trie.

226
00:09:54,630 --> 00:09:57,037
Yale a été fondée en 1701.

227
00:09:57,037 --> 00:09:58,870
Nous allons donc commencer à la
racine, comme nous le faisons toujours.

228
00:09:58,870 --> 00:09:59,890
Et nous avons mis un pointeur de parcours.

229
00:09:59,890 --> 00:10:01,624
Nous allons l'utiliser pour se déplacer à travers.

230
00:10:01,624 --> 00:10:03,790
La première chose que nous voulons
faire est d'aller sur la voie 1.

231
00:10:03,790 --> 00:10:05,830
Voilà le premier chiffre de notre clé.

232
00:10:05,830 --> 00:10:08,420
Heureusement, nous ne faisons pas
avoir à faire un travail cette fois.

233
00:10:08,420 --> 00:10:09,919
Le 1 chemin a déjà été effacé.

234
00:10:09,919 --> 00:10:13,520
Je parvient auparavant quand je
a été l'insertion d'Harvard à 1636.

235
00:10:13,520 --> 00:10:18,090
Donc, je peux déplacer en toute sécurité
en baisse de 1 et juste aller là-bas.

236
00:10:18,090 --> 00:10:20,150
Si peut se déplacer sur le 1.

237
00:10:20,150 --> 00:10:22,930
>> Maintenant, cependant, je veux aller à 7.

238
00:10:22,930 --> 00:10:24,280
Je me suis raclé la voie à 6.

239
00:10:24,280 --> 00:10:27,050
Je sais que je peux en toute sécurité
procéder sur la voie 6.

240
00:10:27,050 --> 00:10:29,220
Mais je dois continuer sur le chemin 7.

241
00:10:29,220 --> 00:10:30,580
Alors, que dois-je faire?

242
00:10:30,580 --> 00:10:35,070
Eh bien, comme avant, je dois juste
pour effacer la porte, sortir de la route,

243
00:10:35,070 --> 00:10:38,740
et de construire un nouveau nœud de la voie 7.

244
00:10:38,740 --> 00:10:40,250
Comme ça.

245
00:10:40,250 --> 00:10:42,930
>> Alors maintenant, je suis passé 1 puis 7.

246
00:10:42,930 --> 00:10:45,550
Et maintenant remarquez, je suis en quelque sorte
de ce nouveau sous-branche.

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

248
00:10:46,050 --> 00:10:49,260
Tout le reste de 16
, je ne me soucie pas.

249
00:10:49,260 --> 00:10:50,720
Je ne fais pas 16 quoi que ce soit.

250
00:10:50,720 --> 00:10:51,750
Je fais 17 trucs.

251
00:10:51,750 --> 00:10:58,380
>> Alors maintenant, à partir de 17, je dois
sorte de tracer de nouveaux chemins ici.

252
00:10:58,380 --> 00:11:00,462
Le chiffre suivant ma clé est 0.

253
00:11:00,462 --> 00:11:01,670
Je peux clairement pas aller partout.

254
00:11:01,670 --> 00:11:02,628
Je viens de construire ce noeud.

255
00:11:02,628 --> 00:11:04,550
Donc, je sais qu'il n'y a pas
chemins à terme d'ici.

256
00:11:04,550 --> 00:11:06,370
Donc, je dois faire un moi-même.

257
00:11:06,370 --> 00:11:09,360
>> Donc, je malloc un nouveau noeud
et ont 0 point, il n'y.

258
00:11:09,360 --> 00:11:12,770
Et puis une fois de plus, je malloc un
nouveau nœud et avoir un point là.

259
00:11:12,770 --> 00:11:15,870
Encore une fois, je suis épuisé ma clé 1701.

260
00:11:15,870 --> 00:11:18,472
Donc, je regarde et je pulvériser de la peinture Yale.

261
00:11:18,472 --> 00:11:19,680
Voilà le nom de ce noeud.

262
00:11:19,680 --> 00:11:24,660
>> Et maintenant, si jamais je dois voir si Yale
est dans ce trie, je commence à la racine,

263
00:11:24,660 --> 00:11:27,060
Je descends de 1701, et regarde vers le bas.

264
00:11:27,060 --> 00:11:30,030
Et si je vois Yale pulvérisation
peint sur le sol, puis

265
00:11:30,030 --> 00:11:32,200
Je sais Yale existe dans ce trie.

266
00:11:32,200 --> 00:11:32,950
Faisons un de plus.

267
00:11:32,950 --> 00:11:36,430
Insérons Dartmouth dans cette
Trie, qui a été fondée en 1769.

268
00:11:36,430 --> 00:11:37,750
>> Commencer à la racine de nouveau.

269
00:11:37,750 --> 00:11:39,445
Mon premier chiffre de ma clé est 1.

270
00:11:39,445 --> 00:11:40,820
Je peux me déplacer en toute sécurité dans cette voie.

271
00:11:40,820 --> 00:11:42,400
Cela existe déjà.

272
00:11:42,400 --> 00:11:44,040
Le prochain chiffre de ma clé est de 7.

273
00:11:44,040 --> 00:11:45,890
Je peux me déplacer en toute sécurité dans cette voie.

274
00:11:45,890 --> 00:11:47,540
Il existe aussi.

275
00:11:47,540 --> 00:11:49,000
>> Mon prochain est 6.

276
00:11:49,000 --> 00:11:52,860
De là, d'où je suis actuellement
il en jaune par le fait que le noeud intermédiaire,

277
00:11:52,860 --> 00:11:56,060
6 est actuellement verrouillé off.

278
00:11:56,060 --> 00:11:58,830
Si je veux aller dans cette voie,
Je dois construire moi-même.

279
00:11:58,830 --> 00:12:02,250
Je vais donc malloc un nouveau noeud
et ont 6 points là.

280
00:12:02,250 --> 00:12:04,250
Et puis, encore une fois, je suis
de nouveaux sentiers ici.

281
00:12:04,250 --> 00:12:10,750
>> Donc, je malloc un nouveau noeud de sorte que de
ce numéro de chemin node-- 9-- puis maintenant

282
00:12:10,750 --> 00:12:13,584
si je voyage 1769, et je regarde vers le bas.

283
00:12:13,584 --> 00:12:15,500
Il n'y a rien pour le moment
vaporisez il peint.

284
00:12:15,500 --> 00:12:16,930
Je peux écrire Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Et je l'ai inséré
Dartmouth dans le trie.

286
00:12:20,710 --> 00:12:23,450
>> Voilà donc l'insertion
les choses dans le Trie.

287
00:12:23,450 --> 00:12:25,384
Maintenant, nous voulons chercher des choses.

288
00:12:25,384 --> 00:12:27,050
Comment pouvons-nous cherchons des choses dans le trie?

289
00:12:27,050 --> 00:12:29,170
Eh bien, il est à peu près la même idée.

290
00:12:29,170 --> 00:12:33,620
Maintenant, nous utilisons simplement les chiffres de la clé
pour voir si nous pouvons naviguer à partir de la racine

291
00:12:33,620 --> 00:12:37,170
à l'endroit où nous voulons aller dans le trie.

292
00:12:37,170 --> 00:12:41,620
>> Si nous avons atteint une impasse en tout point, puis
nous savons que cet élément ne peut pas existe

293
00:12:41,620 --> 00:12:44,500
ou bien ce chemin serait
ont déjà été défrichées.

294
00:12:44,500 --> 00:12:45,930
Si nous le faisons tout le chemin à
la fin, tout ce que nous devons faire

295
00:12:45,930 --> 00:12:48,471
est de regarder vers le bas et voir si cela est
l'élément que nous recherchons.

296
00:12:48,471 --> 00:12:49,335
Dans ce cas, le succès.

297
00:12:49,335 --> 00:12:52,610
Si il est pas sûr.

298
00:12:52,610 --> 00:12:54,940
>> Donc, nous allons chercher des
Harvard dans cette trie.

299
00:12:54,940 --> 00:12:56,020
Nous commençons à la racine.

300
00:12:56,020 --> 00:12:58,228
Et, encore une fois, nous allons
créer un pointeur de parcours

301
00:12:58,228 --> 00:12:59,390
faire nos mouvements pour nous.

302
00:12:59,390 --> 00:13:02,080
De la racine nous savons que le
premier lieu, nous devons aller est 1,

303
00:13:02,080 --> 00:13:03,390
pouvons-nous faire cela?

304
00:13:03,390 --> 00:13:03,982
Oui nous pouvons.

305
00:13:03,982 --> 00:13:04,690
Si existe en toute sécurité.

306
00:13:04,690 --> 00:13:06,660
Nous pouvons y aller.

307
00:13:06,660 --> 00:13:08,440
>> Maintenant, le prochain endroit où nous devons aller est 6.

308
00:13:08,440 --> 00:13:10,557
Est-ce que le chemin existe 6 à partir d'ici?

309
00:13:10,557 --> 00:13:11,140
Oui, il le fait.

310
00:13:11,140 --> 00:13:12,690
Nous pouvons aller sur la voie 6.

311
00:13:12,690 --> 00:13:13,905
Et nous nous retrouvons ici.

312
00:13:13,905 --> 00:13:16,130
>> Pouvons-nous aller sur la voie 3 à partir d'ici?

313
00:13:16,130 --> 00:13:18,450
Eh bien, il se trouve que,
Oui, cela existe aussi.

314
00:13:18,450 --> 00:13:20,790
Et pouvons-nous obtenir sur le chemin d'ici 6?

315
00:13:20,790 --> 00:13:21,982
Oui nous pouvons.

316
00:13:21,982 --> 00:13:24,002
>> Nous avons répondu à pas tout à fait
la question encore.

317
00:13:24,002 --> 00:13:25,710
Il ya encore une
étape, qui est maintenant

318
00:13:25,710 --> 00:13:28,520
nous devons regarder vers le bas et
voir si cela est actually--

319
00:13:28,520 --> 00:13:32,660
si nous sommes à la recherche de Harvard, est que
ce que nous trouvons après que nous épuisons la clé?

320
00:13:32,660 --> 00:13:35,430
Dans l'exemple que nous utilisons ici,
les années sont toujours quatre chiffres.

321
00:13:35,430 --> 00:13:40,280
Mais vous utilisez peut-être l'exemple où
vous stockez un dictionnaire de mots.

322
00:13:40,280 --> 00:13:44,060
>> Et au lieu d'avoir 10 des pointeurs
pour ma position, vous pourriez avoir 26.

323
00:13:44,060 --> 00:13:46,040
Un pour chaque lettre de l'alphabet.

324
00:13:46,040 --> 00:13:50,350
Et il ya des mots comme chauve-souris,
qui est un sous-ensemble de lot, par exemple.

325
00:13:50,350 --> 00:13:53,511
Et même si vous arrivez à la
fin de la clé et vous regardez en bas,

326
00:13:53,511 --> 00:13:55,260
vous pourriez ne pas voir ce qui
vous cherchez.

327
00:13:55,260 --> 00:13:58,500
>> Donc, vous avez toujours à traverser
le chemin complet, puis

328
00:13:58,500 --> 00:14:01,540
si vous étiez en mesure succès
pour traverser le chemin d'accès complet,

329
00:14:01,540 --> 00:14:03,440
regarder vers le bas et effectuez l'une confirmation définitive.

330
00:14:03,440 --> 00:14:05,120
Est-ce que ce que je suis à la recherche?

331
00:14:05,120 --> 00:14:07,740
Eh bien, je regarde vers le bas après le démarrage
en haut et en allant 1,636.

332
00:14:07,740 --> 00:14:08,240
Je regarde en bas.

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

334
00:14:09,400 --> 00:14:11,689
Donc, oui, je réussis.

335
00:14:11,689 --> 00:14:13,980
Que faire si ce que je suis à la recherche
est pas dans la trie, cependant.

336
00:14:13,980 --> 00:14:17,200
Que faire si je suis à la recherche de Princeton,
qui a été fondée en 1746.

337
00:14:17,200 --> 00:14:20,875
Et ainsi de 1,746 devient ma clé
pour naviguer dans le trie.

338
00:14:20,875 --> 00:14:22,040
Eh bien, je commence à la racine.

339
00:14:22,040 --> 00:14:24,760
Et le premier endroit où je veux
à descend le chemin 1.

340
00:14:24,760 --> 00:14:25,590
Puis-je le faire?

341
00:14:25,590 --> 00:14:26,490
Oui je peux.

342
00:14:26,490 --> 00:14:28,730
>> Puis-je descendre le chemin à partir de là 7?

343
00:14:28,730 --> 00:14:29,230
Ouais je peux.

344
00:14:29,230 --> 00:14:30,750
Cela existe aussi.

345
00:14:30,750 --> 00:14:32,460
Mais puis-je aller sur le chemin d'ici 4?

346
00:14:32,460 --> 00:14:35,550
Cela est comme posant la question, peut
Je procède bas ce petit carré

347
00:14:35,550 --> 00:14:37,114
que je l'ai souligné en jaune?

348
00:14:37,114 --> 00:14:38,030
Il n'y a rien là-bas.

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

350
00:14:38,610 --> 00:14:41,310
>> Il n'y a pas aller de l'avant sur la voie 4.

351
00:14:41,310 --> 00:14:46,480
Si Princeton était dans ce Trie, que 4
aurait été dégagé pour nous déjà.

352
00:14:46,480 --> 00:14:49,130
Et si à ce stade
nous avons atteint une impasse.

353
00:14:49,130 --> 00:14:50,250
Nous ne pouvons pas aller plus loin.

354
00:14:50,250 --> 00:14:53,440
Et donc on peut dire, en définitive, pas.

355
00:14:53,440 --> 00:14:56,760
Princeton ne existe pas dans ce trie.

356
00:14:56,760 --> 00:14:58,860
>> Alors qu'est-ce que tout cela veut dire?

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

358
00:14:59,360 --> 00:15:01,000
Il ya beaucoup de choses ici.

359
00:15:01,000 --> 00:15:02,500
Il ya des pointeurs dans tous les sens.

360
00:15:02,500 --> 00:15:04,249
Et, comme vous pouvez le voir
simplement à partir du diagramme,

361
00:15:04,249 --> 00:15:07,010
il ya beaucoup de nœuds
sont sorte de voler autour.

362
00:15:07,010 --> 00:15:13,480
Mais notez chaque fois que nous voulions
vérifier si quelque chose était dans le trie,

363
00:15:13,480 --> 00:15:15,000
nous avons seulement eu à faire 4 se déplace.

364
00:15:15,000 --> 00:15:17,208
>> Chaque fois que nous voulions
insérer quelque chose dans le trie,

365
00:15:17,208 --> 00:15:20,440
nous devons faire 4 se déplace, peut-
allouer de certaines choses sur le chemin.

366
00:15:20,440 --> 00:15:23,482
Mais comme nous l'avons vu lorsque nous avons inséré
Dartmouth dans le trie,

367
00:15:23,482 --> 00:15:25,940
parfois une partie du trajet
peut-être déjà défrichées pour nous.

368
00:15:25,940 --> 00:15:30,520
Et comme notre trie devient de plus en
plus, nous avons faire moins de travail à chaque fois

369
00:15:30,520 --> 00:15:32,270
pour insérer de nouvelles choses
parce que nous avons déjà

370
00:15:32,270 --> 00:15:35,746
construit un grand nombre de l'intermédiaire
branches le long du chemin.

371
00:15:35,746 --> 00:15:38,370
Si nous ne jamais avoir à regarder
4 choses, 4 est juste une constante.

372
00:15:38,370 --> 00:15:41,750
Nous sommes vraiment une sorte de approchons
insertion de la constante de temps

373
00:15:41,750 --> 00:15:44,501
et de recherche constante de temps.

374
00:15:44,501 --> 00:15:47,500
Le compromis, bien sûr, étant que
cette trie, comme vous pouvez le dire,

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

376
00:15:49,030 --> 00:15:51,040
Chacun de ces nœuds
prend beaucoup d'espace.

377
00:15:51,040 --> 00:15:52,090
>> Mais voilà le compromis.

378
00:15:52,090 --> 00:15:55,260
Si nous voulons vraiment rapide
insertion, la suppression très rapide,

379
00:15:55,260 --> 00:15:59,630
et recherche très rapide, nous devons
ont beaucoup de données qui volent autour.

380
00:15:59,630 --> 00:16:03,590
Nous devons mettre de côté beaucoup d'espace
et que la mémoire de structure de données

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

382
00:16:04,290 --> 00:16:05,415
>> Et si tel est le compromis.

383
00:16:05,415 --> 00:16:07,310
Mais il semble que nous
aurait trouvé.

384
00:16:07,310 --> 00:16:09,560
Nous aurions peut-être constaté que
Saint-Graal de structures de données

385
00:16:09,560 --> 00:16:12,264
avec insertion rapide,
la suppression et la recherche.

386
00:16:12,264 --> 00:16:14,430
Et peut-être que ce sera un
structure de données appropriée

387
00:16:14,430 --> 00:16:18,890
à utiliser pour toutes les informations
nous essayons de magasin.

388
00:16:18,890 --> 00:16:21,860
Je suis Doug Lloyd, cela est CS50.

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