1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Manchmal, wenn ein Gebäude
Programm, möchten Sie zu nutzen, könnte ein

3
00:00:10,890 --> 00:00:13,190
Datenstruktur als Wörterbuch bezeichnet.

4
00:00:13,190 --> 00:00:17,960
Ein Wörterbuch, Karten-Tasten, die sind
normalerweise Strings, auf Werte, ints,

5
00:00:17,960 --> 00:00:21,900
Zeichen, ein Zeiger auf ein Objekt,
was wir wollen.

6
00:00:21,900 --> 00:00:26,510
Es ist wie bei gewöhnlichen Wörterbüchern
Karte, dass Worte durch Definitionen.

7
00:00:26,510 --> 00:00:29,440
>> Wörterbücher bieten uns die
Fähigkeit, Informationen zu speichern,

8
00:00:29,440 --> 00:00:32,750
mit etwas verbunden
und schauen Sie später.

9
00:00:32,750 --> 00:00:36,620
So, wie wir tatsächlich umzusetzen ein
Wörterbuch in, sagen wir, C-Code, dass wir

10
00:00:36,620 --> 00:00:38,460
die Verwendung in einem unserer Programme?

11
00:00:38,460 --> 00:00:41,790
Nun, es gibt eine Menge Möglichkeiten, die
wir könnten ein Wörterbuch zu implementieren.

12
00:00:41,790 --> 00:00:45,930
>> Zum einen haben wir ein Array nutzen könnten, dass wir
dynamisch die Größe neu oder wir verwenden ein

13
00:00:45,930 --> 00:00:49,150
verketteten Liste, Hash-Tabelle
oder ein binärer Baum.

14
00:00:49,150 --> 00:00:52,250
Aber was auch immer wir uns entscheiden, wir sollten
darauf achten, die Effizienz und

15
00:00:52,250 --> 00:00:54,300
Leistung der Implementierung.

16
00:00:54,300 --> 00:00:57,930
Wir sollten über den Algorithmus verwendet denken
einzusetzen und zu schauen Elemente in

17
00:00:57,930 --> 00:00:59,120
unsere Datenstruktur.

18
00:00:59,120 --> 00:01:03,060
>> Denn jetzt, nehmen wir an, dass wir
wollen Strings als Schlüssel zu verwenden.

19
00:01:03,060 --> 00:01:07,290
Lassen Sie uns über eine Möglichkeit zu sprechen,
eine Datenstruktur, genannt Trie.

20
00:01:07,290 --> 00:01:11,210
Also hier ist eine visuelle Darstellung
einer Trie.

21
00:01:11,210 --> 00:01:14,590
>> Wie das Bild schon sagt, ein Trie
eine Baumdatenstruktur mit

22
00:01:14,590 --> 00:01:16,050
Knoten miteinander verbunden sind.

23
00:01:16,050 --> 00:01:19,420
Wir sehen, dass es eindeutig eine Wurzel
Knoten mit ein paar Links, die sich auf

24
00:01:19,420 --> 00:01:20,500
anderen Knoten.

25
00:01:20,500 --> 00:01:23,040
Aber was hat jeder Knoten aus?

26
00:01:23,040 --> 00:01:26,700
Wenn wir davon ausgehen, dass wir Speicherung der Schlüssel
mit nur alphabetische Zeichen und

27
00:01:26,700 --> 00:01:30,150
wir nicht über Kapitalisierung kümmern,
hier ist eine Definition von einem Knoten,

28
00:01:30,150 --> 00:01:31,100
genügt.

29
00:01:31,100 --> 00:01:34,130
>> Ein Objekt, dessen Typ struct
Knoten zwei Teile

30
00:01:34,130 --> 00:01:35,740
Daten genannt und Kinder.

31
00:01:35,740 --> 00:01:39,200
Wir haben die Daten teilweise als Kommentar verfasst
durch eine Komponente ersetzt

32
00:01:39,200 --> 00:01:43,190
Erklärung an, wenn struct Knoten
in einem C-Programm eingebunden.

33
00:01:43,190 --> 00:01:47,040
Der Datenteil eines Knotens könnte ein
Boolean-Wert, um anzugeben, ob

34
00:01:47,040 --> 00:01:51,160
nicht der Knoten für den Abschluss
von einem Wörterbuch-Taste oder könnte es sein, ein

35
00:01:51,160 --> 00:01:54,240
String, der die Definition
ein Wort im Wörterbuch.

36
00:01:54,240 --> 00:01:58,870
>> Wir werden einen Smiley verwenden, um anzug
wenn Daten in einem Knoten vorhanden sind.

37
00:01:58,870 --> 00:02:02,310
Es gibt 26 Elemente in unserer
Kinder-Array, einen Index

38
00:02:02,310 --> 00:02:03,690
pro alphabetischen Zeichen.

39
00:02:03,690 --> 00:02:06,570
Wir werden sehen, die Bedeutung
dies bald.

40
00:02:06,570 --> 00:02:10,759
>> Lassen Sie uns einen genaueren Blick des Wurzelknotens
in unserem Diagramm, die keine Daten hat

41
00:02:10,759 --> 00:02:14,740
damit verbunden, wie durch die angegebene
Abwesenheit des Smiley-Gesicht in die

42
00:02:14,740 --> 00:02:16,110
Datenteil.

43
00:02:16,110 --> 00:02:19,910
Die Pfeile, die sich von den Teilen der
die Kinder Array stellen nicht-Knoten

44
00:02:19,910 --> 00:02:21,640
Zeiger auf andere Knoten.

45
00:02:21,640 --> 00:02:25,500
Beispielsweise der Pfeil, der von
das zweite Element des Kinder

46
00:02:25,500 --> 00:02:28,400
steht für den Buchstaben B
Schlüssel in einem Wörterbuch.

47
00:02:28,400 --> 00:02:31,920
Und in den größeren Diagramm
wir beschriften Sie sie mit einem B.

48
00:02:31,920 --> 00:02:35,810
>> Beachten Sie, dass in den größeren Diagramm, wenn wir
ziehen einen Zeiger auf einen anderen Knoten, es

49
00:02:35,810 --> 00:02:39,100
Egal, wo die Pfeilspitze
trifft, dass andere Knoten.

50
00:02:39,100 --> 00:02:43,850
Unsere Probe Wörterbuch Trie enthält
zwei Worte, das und Zoom.

51
00:02:43,850 --> 00:02:47,040
Lassen Sie uns durch ein Beispiel zu Fuß
Nachschlagen Daten für einen Schlüssel.

52
00:02:47,040 --> 00:02:50,800
>> Angenommen, wir wollten schauen die
entsprechenden Wert für den Schlüssel-Bad.

53
00:02:50,800 --> 00:02:53,610
Wir werden unseren Blick nach oben beginnen
am Wurzelknoten.

54
00:02:53,610 --> 00:02:57,870
Dann werden wir den ersten Buchstaben unseres nehmen
Schlüssel, B, und finden Sie die entsprechenden

55
00:02:57,870 --> 00:03:00,020
vor Ort in unseren Kindern Array.

56
00:03:00,020 --> 00:03:04,490
Beachten Sie, dass es genau 26 Punkte
in der Anordnung, eine für jeden Buchstaben

57
00:03:04,490 --> 00:03:05,330
das Alphabet.

58
00:03:05,330 --> 00:03:08,800
Und wir müssen die Punkte stellen die
Buchstaben des Alphabets in Ordnung.

59
00:03:08,800 --> 00:03:13,960
>> Wir werden in der zweiten Index schauen dann,
Index eines, B. In der Regel, wenn man

60
00:03:13,960 --> 00:03:17,990
haben einige alphabetischen Zeichen C wir
könnte die entsprechende Stelle zu bestimmen,

61
00:03:17,990 --> 00:03:21,520
in der Kinder-Array mit
eine Berechnung wie diese.

62
00:03:21,520 --> 00:03:25,140
Wir könnten einen größeren Kinder verwendet haben
Array, wenn wir schauen aus bieten wollte

63
00:03:25,140 --> 00:03:28,380
Schlüssel mit einem breiteren Bereich von Zeichen,
wie die gesamte

64
00:03:28,380 --> 00:03:29,880
ASCII-Zeichensatz.

65
00:03:29,880 --> 00:03:32,630
>> In diesem Fall wird der Zeiger
in unsere Kinder-Array an

66
00:03:32,630 --> 00:03:34,320
Index ein nicht null ist.

67
00:03:34,320 --> 00:03:36,600
Also werden wir weiterhin auf der Suche
bis der Schlüssel Badewanne.

68
00:03:36,600 --> 00:03:40,130
Wenn wir jemals einen Null-Zeiger gestoßen
an der richtigen Stelle in der Kinder

69
00:03:40,130 --> 00:03:43,230
Array durchlaufen, während wir die Knoten,
dann müssen wir, dass wir sagen,

70
00:03:43,230 --> 00:03:45,630
konnte nichts für diesen Schlüssel zu finden.

71
00:03:45,630 --> 00:03:49,370
>> Nun werden wir den zweiten Buchstaben des nehmen
unser Schlüssel, A, und folgen

72
00:03:49,370 --> 00:03:52,400
Zeiger auf diese Weise, bis wir
erreichen das Ende unserer wichtigsten.

73
00:03:52,400 --> 00:03:56,530
Wenn wir das Ende des Schlüssels zu erreichen, ohne
auf irgendwelche Sackgassen, Null-Pointer,

74
00:03:56,530 --> 00:03:59,730
wie hier der Fall ist, dann wird nur wir
müssen noch eine Sache zu überprüfen.

75
00:03:59,730 --> 00:04:02,110
Ist dieser Schlüssel tatsächlich
im Wörterbuch?

76
00:04:02,110 --> 00:04:07,660
>> Wenn ja, sollten wir einen Wert zu finden, gut ein
Smiley-Symbol in unserem Diagramm, in dem

77
00:04:07,660 --> 00:04:08,750
das Wort endet.

78
00:04:08,750 --> 00:04:12,270
Wenn es etwas anderes mit gespeichert
die Daten, dann können wir es zurück.

79
00:04:12,270 --> 00:04:16,500
Beispielsweise ist der Schlüssel nicht in die zoo
Wörterbuch, obwohl wir haben könnten

80
00:04:16,500 --> 00:04:19,810
erreichte das Ende dieses Schlüssels, ohne je
Kollision mit einem Null-Zeiger, während wir

81
00:04:19,810 --> 00:04:21,089
durchlaufen Trie.

82
00:04:21,089 --> 00:04:25,436
>> Wenn wir versucht haben, schauen die Taste Bad, die
Sekunde, um Array-Index des letzten Knoten

83
00:04:25,436 --> 00:04:28,750
entspricht dem Buchstaben H, würde
haben eine Null-Zeiger statt.

84
00:04:28,750 --> 00:04:31,120
So Bad ist nicht im Wörterbuch.

85
00:04:31,120 --> 00:04:34,800
Und so ein Trie ist einzigartig, da die Tasten
nie explizit gespeichert

86
00:04:34,800 --> 00:04:36,650
die Datenstruktur.

87
00:04:36,650 --> 00:04:38,810
So, wie wir etwas einfügen
in einen Trie?

88
00:04:38,810 --> 00:04:41,780
>> Lassen Sie den Schlüssel stecken
Zoo in unsere Trie.

89
00:04:41,780 --> 00:04:46,120
Denken Sie daran, dass ein Smiley-Gesicht an einem Knoten
könnte in einem einfachen Code entsprechen

90
00:04:46,120 --> 00:04:50,170
Boolean-Wert, dass die Zoo zeigen
im Wörterbuch enthalten ist, oder es wird

91
00:04:50,170 --> 00:04:53,710
entsprechen mehr, dass wir
wollen mit dem Schlüssel Zoo zu verknüpfen,

92
00:04:53,710 --> 00:04:56,860
wie die Definition der
Wort oder etwas anderes.

93
00:04:56,860 --> 00:05:00,350
In gewisser Weise ist das Verfahren zum Einfügen
was zu einem Trie ähnelt

94
00:05:00,350 --> 00:05:02,060
ein Nachschlagen in einem Trie.

95
00:05:02,060 --> 00:05:05,720
>> Wir werden mit den Root-Knoten erneut zu starten,
folgenden Hinweise entsprechend

96
00:05:05,720 --> 00:05:07,990
die Buchstaben der Taste.

97
00:05:07,990 --> 00:05:11,310
Zum Glück waren wir in der Lage, Zeiger folgen
den ganzen Weg, bis wir erreicht

98
00:05:11,310 --> 00:05:12,770
das Ende des Schlüssels.

99
00:05:12,770 --> 00:05:16,480
Seit Zoo ist ein Präfix des Wortes
Zoom, der ein Mitglied der ist

100
00:05:16,480 --> 00:05:19,440
Wörterbuch, brauchen wir nicht zu
zuteilen keine neuen Knoten.

101
00:05:19,440 --> 00:05:23,140
>> Wir können die Knoten zu ändern, um anzuzeigen, dass
der Pfad von Zeichen, die zu

102
00:05:23,140 --> 00:05:25,360
es einen Schlüssel im Wörterbuch steht.

103
00:05:25,360 --> 00:05:28,630
Jetzt wollen wir versuchen, das Einsetzen
BAD Schlüssel in die Trie.

104
00:05:28,630 --> 00:05:32,260
Wir werden am Wurzelknoten starten
und folgen Zeiger wieder.

105
00:05:32,260 --> 00:05:35,620
Aber in dieser Situation, einen toten treffen wir
zu beenden, bevor wir in der Lage, um das zu bekommen

106
00:05:35,620 --> 00:05:36,940
Ende des Schlüssels.

107
00:05:36,940 --> 00:05:40,980
Nun müssen wir einige neue zuweisen
Knoten müssen Sie eine neue Zuweisung

108
00:05:40,980 --> 00:05:43,660
Knoten für jede verbleibende
Brief unserer wichtigsten.

109
00:05:43,660 --> 00:05:46,740
>> In diesem Fall brauchen wir nur
zu einem neuen Knoten zuordnen.

110
00:05:46,740 --> 00:05:50,590
Dann werden wir brauchen, um die H-Index machen
verweist auf diesen neuen Knoten.

111
00:05:50,590 --> 00:05:54,070
Auch hier kann man den Knoten zu modifizieren
zeigen an, dass der Pfad der Zeichen

112
00:05:54,070 --> 00:05:57,120
was zu es stellt eine
Schlüssel im Wörterbuch.

113
00:05:57,120 --> 00:06:00,730
Lassen Sie uns über die asymptotische Vernunft
Komplexität der Verfahren für diese

114
00:06:00,730 --> 00:06:02,110
zwei Operationen.

115
00:06:02,110 --> 00:06:06,420
>> Wir bemerken, daß in beiden Fällen die Anzahl
Schritte von unserem Algorithmus nahm, war

116
00:06:06,420 --> 00:06:09,470
proportional zu der Anzahl der
Buchstaben in das Schlüsselwort.

117
00:06:09,470 --> 00:06:10,220
Das ist richtig.

118
00:06:10,220 --> 00:06:13,470
Wenn Sie wollen, in ein um ein Wort
Trie brauchen Sie nur durch laufen

119
00:06:13,470 --> 00:06:17,100
die Buchstaben einer nach dem anderen, bis Sie entweder
bis zum Ende des Wortes oder

120
00:06:17,100 --> 00:06:19,060
eine Sackgasse in der Trie.

121
00:06:19,060 --> 00:06:22,470
>> Und wenn Sie einen Schlüssel einfügen wollen
Wert-Paar in ein Trie mit dem

122
00:06:22,470 --> 00:06:26,250
Verfahren, das wir diskutiert, den schlimmsten Fall
haben Sie einen neuen Knoten Zuteilung

123
00:06:26,250 --> 00:06:27,550
für jeden Buchstaben.

124
00:06:27,550 --> 00:06:31,290
Und wir gehen davon aus, dass die Zuweisung
eine konstante Zeitbetrieb.

125
00:06:31,290 --> 00:06:35,850
Wenn wir also annehmen, dass die Schlüssellänge
eine feste Konstante ist, die beide begrenzt

126
00:06:35,850 --> 00:06:39,400
Einsetzen und schauen konstant sind
Zeit-Operationen für einen Trie.

127
00:06:39,400 --> 00:06:42,930
>> Wenn wir diese Annahme nicht machen, dass
Die Schlüssellänge ist durch eine feste begrenzte

128
00:06:42,930 --> 00:06:46,650
konstant, so Einsetzen und schauen,
im ungünstigsten Fall werden in der linearen

129
00:06:46,650 --> 00:06:48,240
Länge des Schlüssels.

130
00:06:48,240 --> 00:06:51,800
Beachten Sie, dass die Anzahl der Elemente gespeichert
in dem Trie keinen Einfluss auf die Nachschlag

131
00:06:51,800 --> 00:06:52,820
oder Einlegezeit.

132
00:06:52,820 --> 00:06:55,360
Es ist nur durch die betroffen
Länge des Schlüssels.

133
00:06:55,360 --> 00:06:59,300
>> Dagegen Hinzufügen von Einträgen in, sagen wir,
eine Hash-Tabelle neigt dazu,

134
00:06:59,300 --> 00:07:01,250
Zukunft schauen langsamer.

135
00:07:01,250 --> 00:07:04,520
Während dies auf den ersten ansprechend klingen,
sollten wir im Hinterkopf behalten, dass ein

136
00:07:04,520 --> 00:07:08,740
günstige asymptotische Komplexität nicht
bedeuten, dass in der Praxis die Daten

137
00:07:08,740 --> 00:07:11,410
Struktur ist unbedingt
über jeden Zweifel erhaben.

138
00:07:11,410 --> 00:07:15,860
Wir müssen auch bedenken, dass die Speicherung ein
Wort in einem Trie wir im schlimmsten

139
00:07:15,860 --> 00:07:19,700
Fall eine Anzahl von Knoten proportional
der Länge des Wortes selber.

140
00:07:19,700 --> 00:07:21,880
>> Versuche sind in der Regel viel Platz verwenden.

141
00:07:21,880 --> 00:07:25,620
Das ist im Gegensatz zu einer Hash-Tabelle,
wo wir brauchen nur einen neuen Knoten

142
00:07:25,620 --> 00:07:27,940
speichern wir einige Schlüssel-Wert-Paar.

143
00:07:27,940 --> 00:07:31,370
Jetzt, wieder in der Theorie, viel Platz
Verbrauch nicht wie eine große scheinen

144
00:07:31,370 --> 00:07:34,620
umzugehen, zumal moderne
Computer haben und Gigabyte

145
00:07:34,620 --> 00:07:36,180
Gigabyte Speicher.

146
00:07:36,180 --> 00:07:39,200
Aber es stellt sich heraus, dass wir noch
über die Speichernutzung und Sorgen

147
00:07:39,200 --> 00:07:42,540
Organisation zum Wohle
Leistung, da moderne Rechner

148
00:07:42,540 --> 00:07:46,960
haben Mechanismen, die unter
Haube Speicherzugriff beschleunigt.

149
00:07:46,960 --> 00:07:51,180
>> Aber diese Mechanismen funktionieren am besten, wenn
Speicherzugriffe in kompakter gemacht

150
00:07:51,180 --> 00:07:52,810
Regionen oder Gebiete.

151
00:07:52,810 --> 00:07:55,910
Und die Knoten eines Trie könnte aufzuhalten
irgendwo in diesem Haufen.

152
00:07:55,910 --> 00:07:58,390
Aber das sind Kompromisse
dass wir berücksichtigen müssen.

153
00:07:58,390 --> 00:08:01,440
>> Denken Sie daran, dass bei der Auswahl eines Daten
Struktur für eine bestimmte Aufgabe, wir

154
00:08:01,440 --> 00:08:04,420
sollten Sie darüber nachdenken, welche Arten von
Operationen der Datenstruktur muss

155
00:08:04,420 --> 00:08:07,140
Unterstützung und wie viel Leistung
jedes dieser

156
00:08:07,140 --> 00:08:09,080
Operationen ist uns wichtig.

157
00:08:09,080 --> 00:08:11,300
Diese Operationen können sogar
erstrecken sich über gerade

158
00:08:11,300 --> 00:08:13,430
Basic-Look und Insertion.

159
00:08:13,430 --> 00:08:17,010
Angenommen, wir wollen eine Art umsetzen wollte
der Auto-Vervollständigen-Funktion, viel

160
00:08:17,010 --> 00:08:18,890
wie Google Suchmaschine tut.

161
00:08:18,890 --> 00:08:22,210
Das heißt, alle Schlüssel zurückgeben und
Werte, die potenziell

162
00:08:22,210 --> 00:08:24,130
eine gegebene Präfix.

163
00:08:24,130 --> 00:08:27,050
>> Ein Trie ist eindeutig nützlich
für diesen Vorgang.

164
00:08:27,050 --> 00:08:29,890
Es ist einfach zu durchlaufen
der Trie für jedes Zeichen

165
00:08:29,890 --> 00:08:30,950
das Präfix.

166
00:08:30,950 --> 00:08:33,559
Genau wie eine nachschlagen Betrieb
wir könnten Zeiger folgen

167
00:08:33,559 --> 00:08:35,400
Zeichen für Zeichen.

168
00:08:35,400 --> 00:08:38,659
Dann, wenn wir an dem Ende der
Präfix, konnten wir durch die laufen

169
00:08:38,659 --> 00:08:42,049
verbleibende Teil der Datenstruktur
Da eine der Tasten über

170
00:08:42,049 --> 00:08:43,980
dieser Punkt mit dem Präfix.

171
00:08:43,980 --> 00:08:47,670
>> Es ist auch einfach, um dieses Angebot zu erhalten
in alphabetischer Reihenfolge, da die

172
00:08:47,670 --> 00:08:50,970
Elemente der Kinder-Array
sind alphabetisch geordnet.

173
00:08:50,970 --> 00:08:54,420
So werden Sie hoffentlich betrachten
Geben versucht einen Versuch.

174
00:08:54,420 --> 00:08:56,085
Ich bin Kevin Schmid, und das ist CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, das ist der Anfang
der Niedergang.

177
00:09:00,790 --> 00:09:01,350
Es tut mir leid.

178
00:09:01,350 --> 00:09:01,870
Entschuldigung.

179
00:09:01,870 --> 00:09:02,480
Entschuldigung.

180
00:09:02,480 --> 00:09:03,130
Entschuldigung.

181
00:09:03,130 --> 00:09:03,950
>> Schlagen vier.

182
00:09:03,950 --> 00:09:04,360
Ich bin aus.

183
00:09:04,360 --> 00:09:05,280
Entschuldigung.

184
00:09:05,280 --> 00:09:06,500
Entschuldigung.

185
00:09:06,500 --> 00:09:07,490
Entschuldigung.

186
00:09:07,490 --> 00:09:12,352
Sorry für die Herstellung der Person, die
hat mit der Bearbeitung dieses verrückt.

187
00:09:12,352 --> 00:09:13,280
>> Entschuldigung.

188
00:09:13,280 --> 00:09:13,880
Entschuldigung.

189
00:09:13,880 --> 00:09:15,080
Entschuldigung.

190
00:09:15,080 --> 00:09:15,680
Entschuldigung.

191
00:09:15,680 --> 00:09:16,280
>> Sprecher 1: Gut gemacht.

192
00:09:16,280 --> 00:09:17,530
Das war wirklich gut gemacht.

193
00:09:17,530 --> 00:09:18,430