KEVIN SCHMID: Manchmal, wenn ein Gebäude Programm, möchten Sie zu nutzen, könnte ein Datenstruktur als Wörterbuch bezeichnet. Ein Wörterbuch, Karten-Tasten, die sind normalerweise Strings, auf Werte, ints, Zeichen, ein Zeiger auf ein Objekt, was wir wollen. Es ist wie bei gewöhnlichen Wörterbüchern Karte, dass Worte durch Definitionen. 

Wörterbücher bieten uns die Fähigkeit, Informationen zu speichern, mit etwas verbunden und schauen Sie später. So, wie wir tatsächlich umzusetzen ein Wörterbuch in, sagen wir, C-Code, dass wir die Verwendung in einem unserer Programme? Nun, es gibt eine Menge Möglichkeiten, die wir könnten ein Wörterbuch zu implementieren. 

Zum einen haben wir ein Array nutzen könnten, dass wir dynamisch die Größe neu oder wir verwenden ein verketteten Liste, Hash-Tabelle oder ein binärer Baum. Aber was auch immer wir uns entscheiden, wir sollten darauf achten, die Effizienz und Leistung der Implementierung. Wir sollten über den Algorithmus verwendet denken einzusetzen und zu schauen Elemente in unsere Datenstruktur. 

Denn jetzt, nehmen wir an, dass wir wollen Strings als Schlüssel zu verwenden. Lassen Sie uns über eine Möglichkeit zu sprechen, eine Datenstruktur, genannt Trie. Also hier ist eine visuelle Darstellung einer Trie. 

Wie das Bild schon sagt, ein Trie eine Baumdatenstruktur mit Knoten miteinander verbunden sind. Wir sehen, dass es eindeutig eine Wurzel Knoten mit ein paar Links, die sich auf anderen Knoten. Aber was hat jeder Knoten aus? Wenn wir davon ausgehen, dass wir Speicherung der Schlüssel mit nur alphabetische Zeichen und wir nicht über Kapitalisierung kümmern, hier ist eine Definition von einem Knoten, genügt. 

Ein Objekt, dessen Typ struct Knoten zwei Teile Daten genannt und Kinder. Wir haben die Daten teilweise als Kommentar verfasst durch eine Komponente ersetzt Erklärung an, wenn struct Knoten in einem C-Programm eingebunden. Der Datenteil eines Knotens könnte ein Boolean-Wert, um anzugeben, ob nicht der Knoten für den Abschluss von einem Wörterbuch-Taste oder könnte es sein, ein String, der die Definition ein Wort im Wörterbuch. 

Wir werden einen Smiley verwenden, um anzug wenn Daten in einem Knoten vorhanden sind. Es gibt 26 Elemente in unserer Kinder-Array, einen Index pro alphabetischen Zeichen. Wir werden sehen, die Bedeutung dies bald. 

Lassen Sie uns einen genaueren Blick des Wurzelknotens in unserem Diagramm, die keine Daten hat damit verbunden, wie durch die angegebene Abwesenheit des Smiley-Gesicht in die Datenteil. Die Pfeile, die sich von den Teilen der die Kinder Array stellen nicht-Knoten Zeiger auf andere Knoten. Beispielsweise der Pfeil, der von das zweite Element des Kinder steht für den Buchstaben B Schlüssel in einem Wörterbuch. Und in den größeren Diagramm wir beschriften Sie sie mit einem B. 

Beachten Sie, dass in den größeren Diagramm, wenn wir ziehen einen Zeiger auf einen anderen Knoten, es Egal, wo die Pfeilspitze trifft, dass andere Knoten. Unsere Probe Wörterbuch Trie enthält zwei Worte, das und Zoom. Lassen Sie uns durch ein Beispiel zu Fuß Nachschlagen Daten für einen Schlüssel. 

Angenommen, wir wollten schauen die entsprechenden Wert für den Schlüssel-Bad. Wir werden unseren Blick nach oben beginnen am Wurzelknoten. Dann werden wir den ersten Buchstaben unseres nehmen Schlüssel, B, und finden Sie die entsprechenden vor Ort in unseren Kindern Array. Beachten Sie, dass es genau 26 Punkte in der Anordnung, eine für jeden Buchstaben das Alphabet. Und wir müssen die Punkte stellen die Buchstaben des Alphabets in Ordnung. 

Wir werden in der zweiten Index schauen dann, Index eines, B. In der Regel, wenn man haben einige alphabetischen Zeichen C wir könnte die entsprechende Stelle zu bestimmen, in der Kinder-Array mit eine Berechnung wie diese. Wir könnten einen größeren Kinder verwendet haben Array, wenn wir schauen aus bieten wollte Schlüssel mit einem breiteren Bereich von Zeichen, wie die gesamte ASCII-Zeichensatz. 

In diesem Fall wird der Zeiger in unsere Kinder-Array an Index ein nicht null ist. Also werden wir weiterhin auf der Suche bis der Schlüssel Badewanne. Wenn wir jemals einen Null-Zeiger gestoßen an der richtigen Stelle in der Kinder Array durchlaufen, während wir die Knoten, dann müssen wir, dass wir sagen, konnte nichts für diesen Schlüssel zu finden. 

Nun werden wir den zweiten Buchstaben des nehmen unser Schlüssel, A, und folgen Zeiger auf diese Weise, bis wir erreichen das Ende unserer wichtigsten. Wenn wir das Ende des Schlüssels zu erreichen, ohne auf irgendwelche Sackgassen, Null-Pointer, wie hier der Fall ist, dann wird nur wir müssen noch eine Sache zu überprüfen. Ist dieser Schlüssel tatsächlich im Wörterbuch? 

Wenn ja, sollten wir einen Wert zu finden, gut ein Smiley-Symbol in unserem Diagramm, in dem das Wort endet. Wenn es etwas anderes mit gespeichert die Daten, dann können wir es zurück. Beispielsweise ist der Schlüssel nicht in die zoo Wörterbuch, obwohl wir haben könnten erreichte das Ende dieses Schlüssels, ohne je Kollision mit einem Null-Zeiger, während wir durchlaufen Trie. 

Wenn wir versucht haben, schauen die Taste Bad, die Sekunde, um Array-Index des letzten Knoten entspricht dem Buchstaben H, würde haben eine Null-Zeiger statt. So Bad ist nicht im Wörterbuch. Und so ein Trie ist einzigartig, da die Tasten nie explizit gespeichert die Datenstruktur. So, wie wir etwas einfügen in einen Trie? 

Lassen Sie den Schlüssel stecken Zoo in unsere Trie. Denken Sie daran, dass ein Smiley-Gesicht an einem Knoten könnte in einem einfachen Code entsprechen Boolean-Wert, dass die Zoo zeigen im Wörterbuch enthalten ist, oder es wird entsprechen mehr, dass wir wollen mit dem Schlüssel Zoo zu verknüpfen, wie die Definition der Wort oder etwas anderes. In gewisser Weise ist das Verfahren zum Einfügen was zu einem Trie ähnelt ein Nachschlagen in einem Trie. 

Wir werden mit den Root-Knoten erneut zu starten, folgenden Hinweise entsprechend die Buchstaben der Taste. Zum Glück waren wir in der Lage, Zeiger folgen den ganzen Weg, bis wir erreicht das Ende des Schlüssels. Seit Zoo ist ein Präfix des Wortes Zoom, der ein Mitglied der ist Wörterbuch, brauchen wir nicht zu zuteilen keine neuen Knoten. 

Wir können die Knoten zu ändern, um anzuzeigen, dass der Pfad von Zeichen, die zu es einen Schlüssel im Wörterbuch steht. Jetzt wollen wir versuchen, das Einsetzen BAD Schlüssel in die Trie. Wir werden am Wurzelknoten starten und folgen Zeiger wieder. Aber in dieser Situation, einen toten treffen wir zu beenden, bevor wir in der Lage, um das zu bekommen Ende des Schlüssels. Nun müssen wir einige neue zuweisen Knoten müssen Sie eine neue Zuweisung Knoten für jede verbleibende Brief unserer wichtigsten. 

In diesem Fall brauchen wir nur zu einem neuen Knoten zuordnen. Dann werden wir brauchen, um die H-Index machen verweist auf diesen neuen Knoten. Auch hier kann man den Knoten zu modifizieren zeigen an, dass der Pfad der Zeichen was zu es stellt eine Schlüssel im Wörterbuch. Lassen Sie uns über die asymptotische Vernunft Komplexität der Verfahren für diese zwei Operationen. 

Wir bemerken, daß in beiden Fällen die Anzahl Schritte von unserem Algorithmus nahm, war proportional zu der Anzahl der Buchstaben in das Schlüsselwort. Das ist richtig. Wenn Sie wollen, in ein um ein Wort Trie brauchen Sie nur durch laufen die Buchstaben einer nach dem anderen, bis Sie entweder bis zum Ende des Wortes oder eine Sackgasse in der Trie. 

Und wenn Sie einen Schlüssel einfügen wollen Wert-Paar in ein Trie mit dem Verfahren, das wir diskutiert, den schlimmsten Fall haben Sie einen neuen Knoten Zuteilung für jeden Buchstaben. Und wir gehen davon aus, dass die Zuweisung eine konstante Zeitbetrieb. Wenn wir also annehmen, dass die Schlüssellänge eine feste Konstante ist, die beide begrenzt Einsetzen und schauen konstant sind Zeit-Operationen für einen Trie. 

Wenn wir diese Annahme nicht machen, dass Die Schlüssellänge ist durch eine feste begrenzte konstant, so Einsetzen und schauen, im ungünstigsten Fall werden in der linearen Länge des Schlüssels. Beachten Sie, dass die Anzahl der Elemente gespeichert in dem Trie keinen Einfluss auf die Nachschlag oder Einlegezeit. Es ist nur durch die betroffen Länge des Schlüssels. 

Dagegen Hinzufügen von Einträgen in, sagen wir, eine Hash-Tabelle neigt dazu, Zukunft schauen langsamer. Während dies auf den ersten ansprechend klingen, sollten wir im Hinterkopf behalten, dass ein günstige asymptotische Komplexität nicht bedeuten, dass in der Praxis die Daten Struktur ist unbedingt über jeden Zweifel erhaben. Wir müssen auch bedenken, dass die Speicherung ein Wort in einem Trie wir im schlimmsten Fall eine Anzahl von Knoten proportional der Länge des Wortes selber. 

Versuche sind in der Regel viel Platz verwenden. Das ist im Gegensatz zu einer Hash-Tabelle, wo wir brauchen nur einen neuen Knoten speichern wir einige Schlüssel-Wert-Paar. Jetzt, wieder in der Theorie, viel Platz Verbrauch nicht wie eine große scheinen umzugehen, zumal moderne Computer haben und Gigabyte Gigabyte Speicher. Aber es stellt sich heraus, dass wir noch über die Speichernutzung und Sorgen Organisation zum Wohle Leistung, da moderne Rechner haben Mechanismen, die unter Haube Speicherzugriff beschleunigt. 

Aber diese Mechanismen funktionieren am besten, wenn Speicherzugriffe in kompakter gemacht Regionen oder Gebiete. Und die Knoten eines Trie könnte aufzuhalten irgendwo in diesem Haufen. Aber das sind Kompromisse dass wir berücksichtigen müssen. 

Denken Sie daran, dass bei der Auswahl eines Daten Struktur für eine bestimmte Aufgabe, wir sollten Sie darüber nachdenken, welche Arten von Operationen der Datenstruktur muss Unterstützung und wie viel Leistung jedes dieser Operationen ist uns wichtig. Diese Operationen können sogar erstrecken sich über gerade Basic-Look und Insertion. Angenommen, wir wollen eine Art umsetzen wollte der Auto-Vervollständigen-Funktion, viel wie Google Suchmaschine tut. Das heißt, alle Schlüssel zurückgeben und Werte, die potenziell eine gegebene Präfix. 

Ein Trie ist eindeutig nützlich für diesen Vorgang. Es ist einfach zu durchlaufen der Trie für jedes Zeichen das Präfix. Genau wie eine nachschlagen Betrieb wir könnten Zeiger folgen Zeichen für Zeichen. Dann, wenn wir an dem Ende der Präfix, konnten wir durch die laufen verbleibende Teil der Datenstruktur Da eine der Tasten über dieser Punkt mit dem Präfix. 

Es ist auch einfach, um dieses Angebot zu erhalten in alphabetischer Reihenfolge, da die Elemente der Kinder-Array sind alphabetisch geordnet. So werden Sie hoffentlich betrachten Geben versucht einen Versuch. Ich bin Kevin Schmid, und das ist CS50. 

Ah, das ist der Anfang der Niedergang. Es tut mir leid. Entschuldigung. Entschuldigung. Entschuldigung. 

Schlagen vier. Ich bin aus. Entschuldigung. Entschuldigung. Entschuldigung. Sorry für die Herstellung der Person, die hat mit der Bearbeitung dieses verrückt. 

Entschuldigung. Entschuldigung. Entschuldigung. Entschuldigung. 

Sprecher 1: Gut gemacht. Das war wirklich gut gemacht.