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

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Also wir haben rückt immer näher
und näher, daß heilige Gral der Daten

4
00:00:08,550 --> 00:00:13,050
Strukturen, eine, die wir einfügen können
in, zu löschen aus, und schauen

5
00:00:13,050 --> 00:00:15,440
in konstanter Zeit.

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

7
00:00:16,270 --> 00:00:17,280
Das ist eine Art des Ziels.

8
00:00:17,280 --> 00:00:19,720
Wir wollen in der Lage sein zu tun
Dinge sehr, sehr schnell.

9
00:00:19,720 --> 00:00:22,580
>> Haben wir fanden es hier, wenn
wir über Versuche sprechen?

10
00:00:22,580 --> 00:00:23,670
Nun, lassen Sie uns einen Blick.

11
00:00:23,670 --> 00:00:25,628
Also haben wir einige gesehen haben
unterschiedliche Datenstrukturen

12
00:00:25,628 --> 00:00:28,680
, dass die Zuordnung der Handgriff
so genannte Schlüssel-Wert-Paaren,

13
00:00:28,680 --> 00:00:32,080
Abbilden einige Stück von Daten
zu einem anderen Teil von Daten

14
00:00:32,080 --> 00:00:36,020
so dass wir wissen, wo sie zu finden
Informationen in der Struktur.

15
00:00:36,020 --> 00:00:40,060
>> Also Anordnung beispielsweise das
Schlüssel ist die Element-Index oder Array

16
00:00:40,060 --> 00:00:42,600
Stelle 0 oder Array 1 und so weiter.

17
00:00:42,600 --> 00:00:46,140
Und der Wert der Daten
was existiert an dieser Stelle.

18
00:00:46,140 --> 00:00:48,550
Also, was ist in der Anordnung 0 gespeichert?

19
00:00:48,550 --> 00:00:54,290
Was ist in der Anordnung 1 im Vergleich zu nur gespeichert
0 und 1, die die Schlüssel wäre.

20
00:00:54,290 --> 00:00:56,360
>> Mit einer Hash-Tabelle ist es
Art von der gleichen Idee.

21
00:00:56,360 --> 00:01:00,690
Mit einer Hash-Tabelle, haben wir diese Hash-
Funktion, die Hash-Codes generiert.

22
00:01:00,690 --> 00:01:03,670
So ist der Schlüssel der Hash-Code der Daten.

23
00:01:03,670 --> 00:01:06,530
Und der Wert, insbesondere
wir über Verkettung sprachen

24
00:01:06,530 --> 00:01:10,590
im Video auf Hash-Tabellen,
ist, dass verknüpften Liste von Daten

25
00:01:10,590 --> 00:01:12,550
dass Hashes in diesem Hash-Code.

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

27
00:01:14,050 --> 00:01:16,050
Wie sieht es mit einem anderen Ansatz
Diese Methode, obwohl?

28
00:01:16,050 --> 00:01:21,000
Wie wärs mit einem Verfahren, bei dem
Schlüssel ist garantiert einzigartig zu sein,

29
00:01:21,000 --> 00:01:25,410
im Gegensatz zu einem Hash-Tabelle, wo wir konnten,
am Ende mit zwei Daten

30
00:01:25,410 --> 00:01:27,200
mit dem gleichen Hash-Code.

31
00:01:27,200 --> 00:01:30,020
Und dann haben wir zu bewältigen
dass entweder durch Antasten oder mehr

32
00:01:30,020 --> 00:01:33,340
vorzugsweise Verkettung, um dieses Problem zu beheben.

33
00:01:33,340 --> 00:01:37,520
>> So, jetzt können wir garantieren
dass unsere Schlüssel eindeutig sein.

34
00:01:37,520 --> 00:01:39,690
Und was, wenn unsere Wert war
nur etwas so einfach

35
00:01:39,690 --> 00:01:44,080
als wahr und falsch, die uns sagt, ob
oder nicht, dass Information

36
00:01:44,080 --> 00:01:45,610
besteht in der Struktur?

37
00:01:45,610 --> 00:01:48,180
Ein boolescher könnte so einfach wie ein wenig zu sein.

38
00:01:48,180 --> 00:01:52,660
Realistisch gesehen ist es wahrscheinlich eine
Byte wahrscheinlicher als ein bisschen.

39
00:01:52,660 --> 00:01:55,410
Aber das ist viel kleiner als
Speichern vielleicht nach einer 50-Zeichenkette,

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

41
00:01:57,360 --> 00:02:02,210
>> So versucht, ähnlich wie bei Hash-Tabellen,
die kombinieren Arrays und verkettete Liste,

42
00:02:02,210 --> 00:02:05,790
Versuchen kombinieren Arrays,
Strukturen und Zeiger

43
00:02:05,790 --> 00:02:08,509
zusammen, um Daten in speichern
eine interessante Art und Weise, ist

44
00:02:08,509 --> 00:02:11,550
ziemlich unterschiedlich zu
alles, was wir bisher gesehen haben.

45
00:02:11,550 --> 00:02:16,750
Jetzt als Fahrplan nutzen wir die Daten
um diese Datenstruktur zu navigieren.

46
00:02:16,750 --> 00:02:18,710
Und wenn wir folgen können,
die Roadmap, wenn wir können

47
00:02:18,710 --> 00:02:22,390
befolgen Sie die Daten aus
Anfang bis zum Ende, wir

48
00:02:22,390 --> 00:02:24,945
wissen, ob dieser Daten
existieren in der Trie.

49
00:02:24,945 --> 00:02:28,310
>> Und wenn wir können die Karte nicht folgen
aus bedeutet, überhaupt zu beenden,

50
00:02:28,310 --> 00:02:30,600
die Daten nicht vorhanden sind.

51
00:02:30,600 --> 00:02:32,890
Auch hier sind die Schlüssel
garantiert eindeutig sein.

52
00:02:32,890 --> 00:02:36,020
Und so anders als eine Hash-Tabelle, werden wir nie
müssen mit Kollisionen hier umzugehen.

53
00:02:36,020 --> 00:02:39,090
Und keine zwei Datenstücke
genau die gleiche Roadmap

54
00:02:39,090 --> 00:02:40,530
es sei denn, daß die Daten identisch sind.

55
00:02:40,530 --> 00:02:44,580
>> Setzen wir John, dann
wir suchen für John.

56
00:02:44,580 --> 00:02:47,430
Das ist zwei identische Stücke
Daten, rechts, wir durch suchen.

57
00:02:47,430 --> 00:02:49,880
Aber anders, jede
zwei Stücke von Daten sind,

58
00:02:49,880 --> 00:02:52,750
garantiert einzigartige Roadmaps haben
Durch diese Datenstruktur.

59
00:02:52,750 --> 00:02:56,210
Und wir werden ein Blick in
eine visuelle dies in nur einem Augenblick.

60
00:02:56,210 --> 00:02:58,810
>> Wir werden dies, indem Sie versuchen zu tun,
erstellen Sie eine neue Datenstruktur,

61
00:02:58,810 --> 00:03:00,564
Kartierung folgende Schlüsselwertpaare.

62
00:03:00,564 --> 00:03:03,480
In diesem Fall werden wir nicht verwenden
etwas so einfaches wie ein Boolean.

63
00:03:03,480 --> 00:03:06,200
Wir werden tatsächlich die Zeichenfolge zu speichern.

64
00:03:06,200 --> 00:03:08,690
Und das String Nahmen
sei der Name einer Universität.

65
00:03:08,690 --> 00:03:12,140
>> Und der Schlüssel wird sich das Jahr sein,
wenn dieser Universität gegründet.

66
00:03:12,140 --> 00:03:15,380
Alle Jahre für Hochschulen
gehen zu vier Ziffern lang sein.

67
00:03:15,380 --> 00:03:19,840
Und so werden wir diese vier Ziffern zu verwenden,
Navigieren Sie durch diese Datenstruktur.

68
00:03:19,840 --> 00:03:22,270
Und wir werden sehen, noch einmal, wie
wir tun, dass in nur einer Sekunde.

69
00:03:22,270 --> 00:03:25,110
>> Am Ende des Wegs,
wir werden den Namen zu sehen

70
00:03:25,110 --> 00:03:30,250
der Universität, entspricht
für die Taste, die vier Ziffern.

71
00:03:30,250 --> 00:03:34,390
Die Grundidee hinter einem Trie
ist, dass wir eine zentrale Route.

72
00:03:34,390 --> 00:03:35,640
Also denken Sie darüber wie ein Baum.

73
00:03:35,640 --> 00:03:39,211
Und das ist ähnlich wie in der Rechtschreibung
und im Konzept eines Baumes.

74
00:03:39,211 --> 00:03:41,460
Im Allgemeinen, wenn wir denken
Bäume in der realen Welt,

75
00:03:41,460 --> 00:03:44,090
sie eine Wurzel, die in die es haben
Boden und sie nach oben zu wachsen

76
00:03:44,090 --> 00:03:46,830
und sie Niederlassungen haben
und sie haben Blätter.

77
00:03:46,830 --> 00:03:49,450
Und im Grunde die Idee
ein Trie ist genau das gleiche,

78
00:03:49,450 --> 00:03:51,755
außer dass Wurzel verankert
irgendwo in den Himmel.

79
00:03:51,755 --> 00:03:53,130
Und die Blätter sind an der Unterseite.

80
00:03:53,130 --> 00:03:55,750
>> Also es ist eine Art, wie wenn man einen Baum
und nur Spiegeln sie den Kopf.

81
00:03:55,750 --> 00:03:56,880
Aber es sind noch Zweige.

82
00:03:56,880 --> 00:03:59,463
Und diejenigen, würde unsere Wege zu sein,
diese werden unsere Verbindungen sein

83
00:03:59,463 --> 00:04:02,220
von der Wurzel zu den Blättern.

84
00:04:02,220 --> 00:04:04,200
In diesem Fall diejenigen
Wege, diejenigen Zweige

85
00:04:04,200 --> 00:04:08,490
sind mit Ziffern, die uns sagen, beschriftet
die Möglichkeit, von wo wir sind zu gehen.

86
00:04:08,490 --> 00:04:11,800
>> Wenn wir sehen, eine 0, wir hinunter dieser Branche zu gehen,
wenn wir sehen, eine 1, wir hinunter dieser Branche zu gehen,

87
00:04:11,800 --> 00:04:12,900
und so weiter und so fort.

88
00:04:12,900 --> 00:04:14,060
Nun, was bedeutet das?

89
00:04:14,060 --> 00:04:16,519
Nun, das bedeutet, dass
bei jedem Verbindungspunkt

90
00:04:16,519 --> 00:04:19,260
und jeder Knoten in der
mittleren und jeder Zweig,

91
00:04:19,260 --> 00:04:23,020
gibt es 10 möglich
Orte, die wir gehen können.

92
00:04:23,020 --> 00:04:27,690
So gibt es 10 Hinweise
von jedem Ort.

93
00:04:27,690 --> 00:04:30,610
>> Und das ist, wo Versuche kann eine zu bekommen
wenig einschüchternd für jemanden

94
00:04:30,610 --> 00:04:34,460
wer nicht über eine Menge von
Erfahrung in der Informatik vor.

95
00:04:34,460 --> 00:04:35,960
Versucht aber sind wirklich ziemlich genial.

96
00:04:35,960 --> 00:04:37,793
Und wenn Sie die
Chance, mit ihnen zu arbeiten

97
00:04:37,793 --> 00:04:40,420
und Sie sind bereit zu graben-in sind
und experimentieren mit ihnen,

98
00:04:40,420 --> 00:04:44,234
sie sind wirklich sehr interessant
Datenstrukturen, mit zu arbeiten.

99
00:04:44,234 --> 00:04:46,900
Wenn wir ein Element eingefügt werden soll
in den Trie, alles, was wir tun müssen,

100
00:04:46,900 --> 00:04:51,360
wird sie mit den richtigen Pfad
von der Wurzel zu dem Blatt.

101
00:04:51,360 --> 00:04:55,390
Hier ist, was jeder Schritt entlang
der Weg aussehen könnte.

102
00:04:55,390 --> 00:04:59,660
Wir werden eine neue Daten zu definieren
Struktur für einen neuen Knoten genannt trie.

103
00:04:59,660 --> 00:05:02,560
>> Und innerhalb dieses Daten
Struktur gibt es zwei Teile.

104
00:05:02,560 --> 00:05:05,460
Wir gehen in den Laden
Namen einer Universität.

105
00:05:05,460 --> 00:05:09,410
Und wir werden zu speichern
ein Array von Zeigern

106
00:05:09,410 --> 00:05:12,190
mit anderen Knoten des gleichen Typs.

107
00:05:12,190 --> 00:05:14,780
So, auch dies ist diese Art
der Begriff der überall

108
00:05:14,780 --> 00:05:18,567
wir sind, wir bei 10 möglich
Orte, die wir gehen können.

109
00:05:18,567 --> 00:05:20,150
Wenn wir sehen, eine 0, gehen wir diesen Zweig.

110
00:05:20,150 --> 00:05:22,690
Wenn wir sehen, a 1, dieser Zweig,
und so weiter und so weiter und so fort.

111
00:05:22,690 --> 00:05:25,160
Wenn wir sagen, 9, gehen wir diesen Zweig.

112
00:05:25,160 --> 00:05:28,220
So an jedem Knotenpunkt,
Wir können 10 mögliche Orte zu gehen.

113
00:05:28,220 --> 00:05:35,740
Also jeder Knoten bis 10 Zeiger enthalten
zu anderen Knoten, auf 10 anderen Knoten.

114
00:05:35,740 --> 00:05:39,810
>> Und die Daten, die wir speichern ist
nur der Name der Universität.

115
00:05:39,810 --> 00:05:41,060
Also lasst uns bauen eine trie.

116
00:05:41,060 --> 00:05:44,860
Lassen Sie uns stecken ein paar
von Posten in die Trie.

117
00:05:44,860 --> 00:05:46,740
So an der Spitze,
das ist unser Stammknoten.

118
00:05:46,740 --> 00:05:49,740
Dies ist wahrscheinlich, etwas zu sein
Sie gehen zu erklären global.

119
00:05:49,740 --> 00:05:53,450
Und du wirst global zu halten sind
ein Zeiger zu diesem Knoten immer.

120
00:05:53,450 --> 00:05:55,360
>> Du wirst sagen:
root ist gleich, und du bist

121
00:05:55,360 --> 00:05:57,580
wirst dich malloc Trie-Knoten.

122
00:05:57,580 --> 00:05:59,850
Und du wirst nie
root wieder berühren.

123
00:05:59,850 --> 00:06:02,300
Jedes Mal, wenn Sie wollen
Start durch die Navigation,

124
00:06:02,300 --> 00:06:05,802
Sie einen anderen Zeiger festgelegt
gleich Wurzel, wie trav,

125
00:06:05,802 --> 00:06:07,760
Das ist das Beispiel I
verwenden in vielen meiner Videos

126
00:06:07,760 --> 00:06:11,090
hier auf der Stacks und Warteschlangen
und Linklisten und so weiter.

127
00:06:11,090 --> 00:06:13,320
>> Sie legen eine andere Zeiger
genannt trav für Traversal.

128
00:06:13,320 --> 00:06:15,890
Und Sie trav verwenden zu navigieren
durch die Datenstruktur.

129
00:06:15,890 --> 00:06:17,500
Also mal sehen, wie diese aussehen könnte.

130
00:06:17,500 --> 00:06:19,880
So jetzt, was
hat ein Knoten aus?

131
00:06:19,880 --> 00:06:22,920
Nun, so wie unsere Daten
Strukturdeklaration angegeben,

132
00:06:22,920 --> 00:06:26,906
wir haben einen String, der
in diesem Fall ist leer.

133
00:06:26,906 --> 00:06:27,780
Hier ist nichts.

134
00:06:27,780 --> 00:06:29,550
>> Und eine Anordnung von 10 Zeigern.

135
00:06:29,550 --> 00:06:31,790
Und gerade jetzt, nur wir
haben 1-Knoten in diesem Trie.

136
00:06:31,790 --> 00:06:33,110
Es gibt nichts anderes in ihm.

137
00:06:33,110 --> 00:06:36,020
Also alles, 10 von denen,
Zeiger auf null gesetzt.

138
00:06:36,020 --> 00:06:38,090
Das ist, was die rote zeigt.

139
00:06:38,090 --> 00:06:39,500
>> Lassen Sie uns stecken Sie den String Harvard.

140
00:06:39,500 --> 00:06:41,999
Lassen Sie uns stecken die Universität
Harvard in diesem Trie, die

141
00:06:41,999 --> 00:06:43,940
wurde im Jahr 1636 gegründet wurde.

142
00:06:43,940 --> 00:06:48,220
Wir wollen den Schlüssel verwenden,
1636, um uns zu sagen, wo wir sind

143
00:06:48,220 --> 00:06:50,140
werde Harvard im Trie speichern.

144
00:06:50,140 --> 00:06:51,470
Nun, wie können wir das tun?

145
00:06:51,470 --> 00:06:52,886
>> Es könnte etwa wie folgt aussehen.

146
00:06:52,886 --> 00:06:54,160
Wir fangen an der Wurzel.

147
00:06:54,160 --> 00:06:56,920
Und wir haben diese 10 Orte, die wir gehen können.

148
00:06:56,920 --> 00:06:59,900
Die Wurzel ist wie jede
anderen Knoten des Trie.

149
00:06:59,900 --> 00:07:02,850
Es gibt 10 Plätze können wir von hier aus gehen.

150
00:07:02,850 --> 00:07:07,215
>> Wo stehen wir wahrscheinlich wollen
zu gehen, wenn der Schlüssel ist 1636?

151
00:07:07,215 --> 00:07:08,340
Es gibt wirklich zwei Möglichkeiten.

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

153
00:07:08,450 --> 00:07:10,825
Wir können den Schlüssel aus zu bauen
rechts nach links und beginnen mit 6.

154
00:07:10,825 --> 00:07:14,000
Oder wir könnten den Schlüssel aus zu bauen
links nach rechts und beginnen mit 1.

155
00:07:14,000 --> 00:07:16,140
>> Es ist wahrscheinlich mehr
intuitive als Mensch

156
00:07:16,140 --> 00:07:18,110
In den wir verstehen werde
Gehen Sie einfach von links nach rechts.

157
00:07:18,110 --> 00:07:21,140
Und so, wenn ich einfügen
Harvard in diesem Trie,

158
00:07:21,140 --> 00:07:23,560
Ich möchte wohl zu starten
beginnend an der Wurzel,

159
00:07:23,560 --> 00:07:25,720
Blick auf meine 10-Optionen
vor mir, und sagen:

160
00:07:25,720 --> 00:07:28,700
Ich möchte gehen Sie die 1-Pfad.

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

162
00:07:29,700 --> 00:07:31,810
>> Nun, das ist ein Weg zur Zeit null.

163
00:07:31,810 --> 00:07:35,920
Also, wenn ich will gehen auf diesem Weg
um dieses Element in die Trie einzufügen,

164
00:07:35,920 --> 00:07:42,040
Ich habe einen neuen Knoten malloc haben 1
zeigen es, und dann bin ich gut zu gehen.

165
00:07:42,040 --> 00:07:46,460
>> Also ich bin im Grunde auf eine
Punkt, wo ich stehe

166
00:07:46,460 --> 00:07:50,270
an der Wurzel des Baums oder der
trie und es gibt 10 Niederlassungen.

167
00:07:50,270 --> 00:07:52,260
Aber jeder Zweig ein
Gate davor.

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

169
00:07:53,060 --> 00:07:54,850
Denn es gibt nichts anderes da ist.

170
00:07:54,850 --> 00:07:56,522
Keine sichere Passage.

171
00:07:56,522 --> 00:07:58,980
Das bedeutet, dass es gibt nichts,
unten eine dieser Filialen.

172
00:07:58,980 --> 00:08:02,532
Wenn ich will, um Gebäude zu starten
etwas, ich will, um das Tor zu entfernen.

173
00:08:02,532 --> 00:08:04,490
Ich möchte, um das Tor zu entfernen
vor der Nummer 1.

174
00:08:04,490 --> 00:08:05,698
Und ich möchte, dass hinunter.

175
00:08:05,698 --> 00:08:08,060
Und ich will bauen
ein weiterer Ort für mich zu gehen.

176
00:08:08,060 --> 00:08:09,470
>> Und das ist, was ich hier getan.

177
00:08:09,470 --> 00:08:11,430
Also 1 verweist nicht mehr auf null gesetzt.

178
00:08:11,430 --> 00:08:13,830
Ich habe gesagt, es ist sicher hier unten jetzt zu gehen.

179
00:08:13,830 --> 00:08:15,789
Ich baute einen anderen Knoten.

180
00:08:15,789 --> 00:08:18,330
Und wenn ich an diesen Knoten zu bekommen, I
haben eine andere Entscheidung zu treffen.

181
00:08:18,330 --> 00:08:20,890
Wohin gehe ich, um von hier aus?

182
00:08:20,890 --> 00:08:22,700
>> Nun, ich habe bereits auf der 1 weg.

183
00:08:22,700 --> 00:08:24,470
So, jetzt will ich wahrscheinlich gehen Sie die 6.

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

185
00:08:24,970 --> 00:08:27,100
Auch hier habe ich 10 Standorten ich wählen kann.

186
00:08:27,100 --> 00:08:30,060
Lassen Sie uns also jetzt die Nummer 6 nach unten gehen.

187
00:08:30,060 --> 00:08:32,280
Also ich deaktivieren Sie das Gate
vor der Nummer 6.

188
00:08:32,280 --> 00:08:33,250
Und ich gehe da unten.

189
00:08:33,250 --> 00:08:34,580
Und ich bauen einen anderen Knoten.

190
00:08:34,580 --> 00:08:37,630
Und ich habe eine andere Verbindungspunkt erreicht.

191
00:08:37,630 --> 00:08:40,289
>> Auch hier habe ich 10 Entscheidungen
denn wo ich gehen kann.

192
00:08:40,289 --> 00:08:42,799
Ich habe 1-6 bewegt.

193
00:08:42,799 --> 00:08:44,215
So, jetzt will ich wohl bis 3 zu gehen.

194
00:08:44,215 --> 00:08:45,381
3, gibt es nirgendwo ich gehen kann.

195
00:08:45,381 --> 00:08:48,980
So habe ich, den Weg frei
und bauen Sie mir einen neuen Raum.

196
00:08:48,980 --> 00:08:50,870
Und dann von 3, wo will ich hin?

197
00:08:50,870 --> 00:08:52,450
Ich möchte um 6 gehen.

198
00:08:52,450 --> 00:08:54,770
>> Und wieder musste ich
den Weg, es zu tun.

199
00:08:54,770 --> 00:08:59,179
So, jetzt habe ich meine Schlüssel verwendet, um einzufügen erstellen
Knoten und starten, um dieses trie bauen.

200
00:08:59,179 --> 00:09:00,220
Ich habe an der Wurzel gestartet.

201
00:09:00,220 --> 00:09:03,666
Ich habe ab 1636 verschwunden.

202
00:09:03,666 --> 00:09:05,540
Und jetzt bin ich an der Unterseite
dort an diesem Knoten.

203
00:09:05,540 --> 00:09:06,610
Und Sie könnten in der Lage zu sein,
sehen es auf dem Bildschirm.

204
00:09:06,610 --> 00:09:07,735
>> Es ist gelb markiert.

205
00:09:07,735 --> 00:09:10,020
Das ist, wo ich zur Zeit bin.

206
00:09:10,020 --> 00:09:11,300
Mein Schlüssel ist getan.

207
00:09:11,300 --> 00:09:13,030
Ich habe jede Position in meinen Schlüssel erschöpft.

208
00:09:13,030 --> 00:09:15,040
So kann ich nicht mehr weiter geht.

209
00:09:15,040 --> 00:09:17,720
Also an dieser Stelle, alles, was ich
wirklich tun müssen, ist zu sagen, OK.

210
00:09:17,720 --> 00:09:18,990
Es ist wie eine Art der Suche
auf den Boden,

211
00:09:18,990 --> 00:09:21,115
wenn Sie Vorstellungsvermögen sind
sich selbst als diese Art von Pfad

212
00:09:21,115 --> 00:09:22,350
mit verschiedenen Verbindungen.

213
00:09:22,350 --> 00:09:25,800
Art der Suche nach unten und Art
Spritzlackierung Harvard auf dem Boden.

214
00:09:25,800 --> 00:09:26,800
Das ist der Name dafür.

215
00:09:26,800 --> 00:09:28,300
Weiß, dass das, was an diesem Ort.

216
00:09:28,300 --> 00:09:31,870
Wenn wir an der Wurzel, und wir gehen
1 und 6 und dann 3 und dann 6,

217
00:09:31,870 --> 00:09:32,780
wo sind wir?

218
00:09:32,780 --> 00:09:35,640
Nun, wenn wir nach unten schauen
und wir sehen, Harvard, dann

219
00:09:35,640 --> 00:09:38,960
wir wissen, dass Harvard war
im Jahre 1636 auf der Grundlage der Art und Weise gegründet

220
00:09:38,960 --> 00:09:41,400
wir sind der Umsetzung dieses Datenstruktur.

221
00:09:41,400 --> 00:09:43,177
Das war also hoffentlich unkompliziert.

222
00:09:43,177 --> 00:09:44,760
Wir werden zwei weitere Insertionen zu tun.

223
00:09:44,760 --> 00:09:50,060
Und hoffentlich werde es zu helfen,
sehen dies getan zweimal.

224
00:09:50,060 --> 00:09:52,210
>> Lassen Sie uns nun legen Sie eine andere Universität.

225
00:09:52,210 --> 00:09:54,630
Lassen Sie uns stecken Yale in diesem Trie.

226
00:09:54,630 --> 00:09:57,037
Yale wurde im Jahre 1701 gegründet.

227
00:09:57,037 --> 00:09:58,870
Also werden wir am Start
Wurzel, wie wir es immer tun.

228
00:09:58,870 --> 00:09:59,890
Und wir setzen einen Durchlauf-Zeiger.

229
00:09:59,890 --> 00:10:01,624
Wir werden das benutzen, um durch zu bewegen.

230
00:10:01,624 --> 00:10:03,790
Das erste, was wir wollen
zu tun ist, gehen Sie die 1-Pfad.

231
00:10:03,790 --> 00:10:05,830
Das ist die erste Ziffer der Taste.

232
00:10:05,830 --> 00:10:08,420
Zum Glück, obwohl, wir nicht
jede Arbeit dieses Mal zu tun.

233
00:10:08,420 --> 00:10:09,919
Die 1-Pfad bereits gelöscht wurde.

234
00:10:09,919 --> 00:10:13,520
Ich bat ihn, als ich vorher
wurde Harvard Einsetzen bei 1636.

235
00:10:13,520 --> 00:10:18,090
So kann ich sicher bewegen
down 1 und nur dorthin zu gehen.

236
00:10:18,090 --> 00:10:20,150
Wenn sich bewegen Sie die 1.

237
00:10:20,150 --> 00:10:22,930
>> Nun aber, ich will bis 7 gehen.

238
00:10:22,930 --> 00:10:24,280
Ich machte den Weg bei 6.

239
00:10:24,280 --> 00:10:27,050
Ich weiß, ich kann sicher
gehen Sie die 6-Pfad.

240
00:10:27,050 --> 00:10:29,220
Aber ich muss auf der 7-Pfad gehen.

241
00:10:29,220 --> 00:10:30,580
Also, was muss ich tun?

242
00:10:30,580 --> 00:10:35,070
Nun, genau wie vor, ich muss nur
um das Gate zu löschen, aus dem Weg zu gehen,

243
00:10:35,070 --> 00:10:38,740
und bauen Sie einen neuen Knoten aus dem 7-Pfad.

244
00:10:38,740 --> 00:10:40,250
Einfach so.

245
00:10:40,250 --> 00:10:42,930
>> So jetzt habe ich 1 und 7 bewegt.

246
00:10:42,930 --> 00:10:45,550
Und jetzt bemerken, Ich bin Art
der auf diesem neuen Teilzweig.

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

248
00:10:46,050 --> 00:10:49,260
Alles andere aus 16
auf, ich weiß nicht kümmern.

249
00:10:49,260 --> 00:10:50,720
Mache ich nicht 16 etwas.

250
00:10:50,720 --> 00:10:51,750
Ich mache 17 Sachen.

251
00:10:51,750 --> 00:10:58,380
>> So, jetzt von 17 auf, ich muss
Art von Blaze neue Wege hier.

252
00:10:58,380 --> 00:11:00,462
Die nächste Ziffer mein Schlüssel ist 0.

253
00:11:00,462 --> 00:11:01,670
Ich kann natürlich nicht überall zu bekommen.

254
00:11:01,670 --> 00:11:02,628
Ich baute gerade diesen Knoten.

255
00:11:02,628 --> 00:11:04,550
Also ich weiß, gibt es keine
Wege vorwärts von hier.

256
00:11:04,550 --> 00:11:06,370
Also muss ich einen selbst zu machen.

257
00:11:06,370 --> 00:11:09,360
>> So malloc ich einen neuen Knoten
und haben 0 Punkt gibt.

258
00:11:09,360 --> 00:11:12,770
Und dann noch einmal, malloc I a
neuen Knoten und haben einen Punkt gibt.

259
00:11:12,770 --> 00:11:15,870
Auch hier habe ich meine Schlüssel, 1701 erschöpft.

260
00:11:15,870 --> 00:11:18,472
So sehe ich nach unten und ich Sprühfarbe Yale.

261
00:11:18,472 --> 00:11:19,680
Das ist der Name dieses Knotens.

262
00:11:19,680 --> 00:11:24,660
>> Und jetzt, wenn ich jemals brauchen, um zu sehen, wenn Yale
wird in diesem Trie, fange ich an der Wurzel,

263
00:11:24,660 --> 00:11:27,060
Ich mich 1701 zu gehen, und schauen hinunter.

264
00:11:27,060 --> 00:11:30,030
Und wenn ich sehe, Yale Spray
auf den Boden gemalten, dann

265
00:11:30,030 --> 00:11:32,200
Ich weiß, dass Yale in diesem Trie besteht.

266
00:11:32,200 --> 00:11:32,950
Lassen Sie uns noch einen.

267
00:11:32,950 --> 00:11:36,430
Lassen Sie uns stecken Dartmouth in diesem
trie, die im Jahre 1769 gegründet wurde.

268
00:11:36,430 --> 00:11:37,750
>> An der Wurzel beginnen erneut.

269
00:11:37,750 --> 00:11:39,445
Meine erste Stelle mein Schlüssel ist 1.

270
00:11:39,445 --> 00:11:40,820
Ich kann sicher nach unten zu verschieben, diesen Weg.

271
00:11:40,820 --> 00:11:42,400
Das ist bereits vorhanden.

272
00:11:42,400 --> 00:11:44,040
Die nächste Ziffer meiner Schlüssel ist 7.

273
00:11:44,040 --> 00:11:45,890
Ich kann sicher nach unten zu verschieben, diesen Weg.

274
00:11:45,890 --> 00:11:47,540
Es existiert auch.

275
00:11:47,540 --> 00:11:49,000
>> Mein nächstes ist 6.

276
00:11:49,000 --> 00:11:52,860
Von hier aus, von wo ich gerade bin
in gelb gibt in diesem mittleren Knoten,

277
00:11:52,860 --> 00:11:56,060
6 ist derzeit gesperrt aus.

278
00:11:56,060 --> 00:11:58,830
Wenn ich diesen Weg nach unten gehen,
Ich habe es selbst zu bauen.

279
00:11:58,830 --> 00:12:02,250
Also werde ich einen neuen Knoten malloc
und haben 6 Punkt gibt.

280
00:12:02,250 --> 00:12:04,250
Und dann bin ich wieder
neue Wege hier.

281
00:12:04,250 --> 00:12:10,750
>> So malloc ich einen neuen Knoten, so dass aus
dass node-- Weg Nr 9-- und dann jetzt

282
00:12:10,750 --> 00:12:13,584
Wenn ich auf Reisen 1769 und ich freue mich nach unten.

283
00:12:13,584 --> 00:12:15,500
Es gibt nichts, noch
sprühen es gemalt.

284
00:12:15,500 --> 00:12:16,930
Ich kann Dartmouth schreiben.

285
00:12:16,930 --> 00:12:20,710
Und ich habe einge
Dartmouth in den Trie.

286
00:12:20,710 --> 00:12:23,450
>> Das ist also das Einfügen
Dinge in der Trie.

287
00:12:23,450 --> 00:12:25,384
Jetzt wollen wir für Dinge zu suchen.

288
00:12:25,384 --> 00:12:27,050
Wie können wir für die Dinge in der Trie zu suchen?

289
00:12:27,050 --> 00:12:29,170
Nun, es ist so ziemlich das gleiche Idee.

290
00:12:29,170 --> 00:12:33,620
Jetzt verwenden wir nur die Ziffern der Schlüssel
zu sehen, ob wir von der Wurzel zu navigieren

291
00:12:33,620 --> 00:12:37,170
, wo wir in der Trie gehen wollen.

292
00:12:37,170 --> 00:12:41,620
>> Wenn wir in eine Sackgasse an einem beliebigen Punkt, dann
wir wissen, dass das Element nicht vorhanden ist

293
00:12:41,620 --> 00:12:44,500
oder auch, dass Pfad würde
wurden bereits geräumt.

294
00:12:44,500 --> 00:12:45,930
Wenn wir es den ganzen Weg zu
das Ende, alles, was wir tun müssen,

295
00:12:45,930 --> 00:12:48,471
ist Blick nach unten und sehen, ob das
das Element, die wir suchen.

296
00:12:48,471 --> 00:12:49,335
Wenn es ist, den Erfolg.

297
00:12:49,335 --> 00:12:52,610
Wenn es nicht, scheitern.

298
00:12:52,610 --> 00:12:54,940
>> Also lassen Sie uns die Suche nach
Harvard in diesem Trie.

299
00:12:54,940 --> 00:12:56,020
Wir fangen an der Wurzel.

300
00:12:56,020 --> 00:12:58,228
Und wieder werden wir
erstellen Sie einen Zeiger-Traversal

301
00:12:58,228 --> 00:12:59,390
unsere bewegt sich für uns tun.

302
00:12:59,390 --> 00:13:02,080
Von der Wurzel wissen wir, dass die
Erstens müssen wir gehen, ist 1,

303
00:13:02,080 --> 00:13:03,390
können wir das tun?

304
00:13:03,390 --> 00:13:03,982
Ja wir können.

305
00:13:03,982 --> 00:13:04,690
Wenn sicher existiert.

306
00:13:04,690 --> 00:13:06,660
Wir können dorthin gehen.

307
00:13:06,660 --> 00:13:08,440
>> Nun, der nächste Ort, den wir gehen müssen, ist 6.

308
00:13:08,440 --> 00:13:10,557
Hat das 6-Pfad von hier aus gibt es?

309
00:13:10,557 --> 00:13:11,140
Ja, das tut es.

310
00:13:11,140 --> 00:13:12,690
Wir können gehen die 6-Pfad.

311
00:13:12,690 --> 00:13:13,905
Und wir am Ende hier.

312
00:13:13,905 --> 00:13:16,130
>> Können wir auf der 3-Pfad von hier aus?

313
00:13:16,130 --> 00:13:18,450
Nun, wie sich herausstellt,
ja, existiert auch.

314
00:13:18,450 --> 00:13:20,790
Und wir können uns auf die 6 Weg von hier?

315
00:13:20,790 --> 00:13:21,982
Ja wir können.

316
00:13:21,982 --> 00:13:24,002
>> Wir haben nicht ganz beantwortet
doch ist die Frage.

317
00:13:24,002 --> 00:13:25,710
Es gibt noch eine weitere
Schritt, der jetzt

318
00:13:25,710 --> 00:13:28,520
Wir müssen nach unten zu schauen und
sehen, ob das actually--

319
00:13:28,520 --> 00:13:32,660
wenn wir für Harvard suchen, ist, dass
was wir finden, nachdem wir erschöpfen den Schlüssel?

320
00:13:32,660 --> 00:13:35,430
Im Beispiel verwenden wir hier,
Die Jahre sind immer vier Ziffern.

321
00:13:35,430 --> 00:13:40,280
Aber Sie könnten mit dem Beispiel, in dem
Sie speichert ein Wörterbuch von Wörtern.

322
00:13:40,280 --> 00:13:44,060
>> Und so anstatt 10 Zeigern
für meine Lage, haben Sie vielleicht 26.

323
00:13:44,060 --> 00:13:46,040
Eine für jeden Buchstaben des Alphabets.

324
00:13:46,040 --> 00:13:50,350
Und es gibt einige Wörter wie Fledermaus,
die eine Teilmenge der Charge, zum Beispiel.

325
00:13:50,350 --> 00:13:53,511
Und so, auch wenn Sie das bekommen
Ende des Schlüssels und Sie nach unten schauen,

326
00:13:53,511 --> 00:13:55,260
Sie nicht sehen können, was
den Sie suchen.

327
00:13:55,260 --> 00:13:58,500
>> So dass Sie immer zu durchqueren
der gesamte Pfad und dann

328
00:13:58,500 --> 00:14:01,540
wenn Sie erfolgreich in der Lage waren
den gesamten Pfad zu durchlaufen,

329
00:14:01,540 --> 00:14:03,440
Blick nach unten und führen Sie eine Buchungsbestätigung.

330
00:14:03,440 --> 00:14:05,120
Ist das, was ich suche?

331
00:14:05,120 --> 00:14:07,740
Nun, ich schauen hinunter nach dem Start
an der Spitze und geht 1636.

332
00:14:07,740 --> 00:14:08,240
Ich schaue nach unten.

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

334
00:14:09,400 --> 00:14:11,689
Also, ja, gelang es mir.

335
00:14:11,689 --> 00:14:13,980
Was passiert, wenn das, was ich auf der Suche nach
nicht in der Trie, wenn.

336
00:14:13,980 --> 00:14:17,200
Was ist, wenn ich suche nach Princeton,
, die im Jahre 1746 gegründet wurde.

337
00:14:17,200 --> 00:14:20,875
Und so 1746 wird mein Schlüssel
durch den Trie navigieren.

338
00:14:20,875 --> 00:14:22,040
Nun beginne ich an der Wurzel.

339
00:14:22,040 --> 00:14:24,760
Und der erste Ort, den ich möchte
um nach unten geht die 1-Pfad.

340
00:14:24,760 --> 00:14:25,590
Kann ich es schaffen?

341
00:14:25,590 --> 00:14:26,490
Ja, ich kann.

342
00:14:26,490 --> 00:14:28,730
>> Kann ich auf der 7-Pfad von dort aus gehen?

343
00:14:28,730 --> 00:14:29,230
Ja, ich kann.

344
00:14:29,230 --> 00:14:30,750
Das existiert auch.

345
00:14:30,750 --> 00:14:32,460
Aber kann ich auf der 4-Weg von hier aus?

346
00:14:32,460 --> 00:14:35,550
Das ist wie die Frage zu stellen, kann
Ich gehe nach unten, dass kleinen Platz

347
00:14:35,550 --> 00:14:37,114
dass ich gelb markiert?

348
00:14:37,114 --> 00:14:38,030
Da ist nichts.

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

350
00:14:38,610 --> 00:14:41,310
>> Es gibt keinen Weg nach vorne auf der 4-Pfad.

351
00:14:41,310 --> 00:14:46,480
Wenn Princeton war in diesem Trie, dass 4
wäre für uns schon gelöscht haben.

352
00:14:46,480 --> 00:14:49,130
Und so an dieser Stelle
haben wir in einer Sackgasse.

353
00:14:49,130 --> 00:14:50,250
Wir können nicht weiter gehen.

354
00:14:50,250 --> 00:14:53,440
Und so können wir sagen, definitiv nein.

355
00:14:53,440 --> 00:14:56,760
Princeton nicht in diesem Trie existieren.

356
00:14:56,760 --> 00:14:58,860
>> Also, was bedeutet das alles?

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

358
00:14:59,360 --> 00:15:01,000
Es gibt eine Menge los.

359
00:15:01,000 --> 00:15:02,500
Es gibt Hinweise ganz über dem Platz.

360
00:15:02,500 --> 00:15:04,249
Und wie Sie sehen können,
nur aus dem Diagramm,

361
00:15:04,249 --> 00:15:07,010
es gibt eine Menge von Knoten,
sind Art herumfliegen.

362
00:15:07,010 --> 00:15:13,480
Aber beachten Sie jedes Mal, wenn wir wollten,
prüfen, ob etwas nicht in der Trie,

363
00:15:13,480 --> 00:15:15,000
wir mussten nur 4 Schritte zu machen.

364
00:15:15,000 --> 00:15:17,208
>> Jedes Mal, wenn wir wollten,
Einsatz etwas in der Trie,

365
00:15:17,208 --> 00:15:20,440
wir müssen 4 Schritte zu machen, möglicherweise
mallocing paar Sachen auf dem Weg.

366
00:15:20,440 --> 00:15:23,482
Aber wie wir gesehen haben, als wir einge
Dartmouth in den Trie,

367
00:15:23,482 --> 00:15:25,940
manchmal einige der Pfad
vielleicht schon für uns gelöscht werden.

368
00:15:25,940 --> 00:15:30,520
Und so wie unsere Trie wird größer und
größer, wir haben jedes Mal tun, weniger Arbeit

369
00:15:30,520 --> 00:15:32,270
, neue Dinge zu fügen
weil wir bereits haben

370
00:15:32,270 --> 00:15:35,746
baute eine Menge von Zwischen
Niederlassungen auf dem Weg.

371
00:15:35,746 --> 00:15:38,370
Wenn wir immer nur, zu betrachten
4 Dinge, 4 ist nur eine Konstante.

372
00:15:38,370 --> 00:15:41,750
Wir sind wirklich Art von Annäherung
konstanten Zeiteinblendung

373
00:15:41,750 --> 00:15:44,501
und konstante Zeit Lookup.

374
00:15:44,501 --> 00:15:47,500
Der Nachteil ist natürlich, ist, dass
Diese trie, da kann man wohl sagen,

375
00:15:47,500 --> 00:15:49,030
ist groß.

376
00:15:49,030 --> 00:15:51,040
Jeder dieser Knoten
nimmt viel Platz.

377
00:15:51,040 --> 00:15:52,090
>> Aber das ist der Kompromiss.

378
00:15:52,090 --> 00:15:55,260
Wenn wir wollen, wirklich schnell
Insertion, wirklich schnell Löschung,

379
00:15:55,260 --> 00:15:59,630
und wirklich schnelle Suche, müssen wir
haben eine Menge Daten herumfliegen.

380
00:15:59,630 --> 00:16:03,590
Wir haben neben viel Platz zu setzen
und einen Speicher für die Datenstruktur

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

382
00:16:04,290 --> 00:16:05,415
>> Und damit ist der Kompromiss.

383
00:16:05,415 --> 00:16:07,310
Aber es sieht aus wie wir
könnte es gefunden.

384
00:16:07,310 --> 00:16:09,560
Wir könnten festgestellt, dass
Heilige Gral der Datenstrukturen

385
00:16:09,560 --> 00:16:12,264
mit Schnelleinschub,
Löschen und Lookup.

386
00:16:12,264 --> 00:16:14,430
Und vielleicht wird dies eine sein
geeignete Datenstruktur

387
00:16:14,430 --> 00:16:18,890
zu irgendwelchen Informationen benutzen,
wir versuchen zu speichern.

388
00:16:18,890 --> 00:16:21,860
Ich bin Doug Lloyd, ist dies CS50.

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