>> 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.
>> Schlagen vier.
Ich bin aus.
Entschuldigung.
Sorry für die Herstellung der Person, die hat mit der Bearbeitung dieses verrückt.
>> Entschuldigung.
Entschuldigung.
>> Sprecher 1: Gut gemacht.
Das war wirklich gut gemacht.