[Musikwiedergabe] DOUG LLOYD: Also wir haben rückt immer näher und näher, daß heilige Gral der Daten Strukturen, eine, die wir einfügen können in, zu löschen aus, und schauen in konstanter Zeit. Recht. Das ist eine Art des Ziels. Wir wollen in der Lage sein zu tun Dinge sehr, sehr schnell. 

Haben wir fanden es hier, wenn wir über Versuche sprechen? Nun, lassen Sie uns einen Blick. Also haben wir einige gesehen haben unterschiedliche Datenstrukturen , dass die Zuordnung der Handgriff so genannte Schlüssel-Wert-Paaren, Abbilden einige Stück von Daten zu einem anderen Teil von Daten so dass wir wissen, wo sie zu finden Informationen in der Struktur. 

Also Anordnung beispielsweise das Schlüssel ist die Element-Index oder Array Stelle 0 oder Array 1 und so weiter. Und der Wert der Daten was existiert an dieser Stelle. Also, was ist in der Anordnung 0 gespeichert? Was ist in der Anordnung 1 im Vergleich zu nur gespeichert 0 und 1, die die Schlüssel wäre. 

Mit einer Hash-Tabelle ist es Art von der gleichen Idee. Mit einer Hash-Tabelle, haben wir diese Hash- Funktion, die Hash-Codes generiert. So ist der Schlüssel der Hash-Code der Daten. Und der Wert, insbesondere wir über Verkettung sprachen im Video auf Hash-Tabellen, ist, dass verknüpften Liste von Daten dass Hashes in diesem Hash-Code. Recht. Wie sieht es mit einem anderen Ansatz Diese Methode, obwohl? Wie wärs mit einem Verfahren, bei dem Schlüssel ist garantiert einzigartig zu sein, im Gegensatz zu einem Hash-Tabelle, wo wir konnten, am Ende mit zwei Daten mit dem gleichen Hash-Code. Und dann haben wir zu bewältigen dass entweder durch Antasten oder mehr vorzugsweise Verkettung, um dieses Problem zu beheben. 

So, jetzt können wir garantieren dass unsere Schlüssel eindeutig sein. Und was, wenn unsere Wert war nur etwas so einfach als wahr und falsch, die uns sagt, ob oder nicht, dass Information besteht in der Struktur? Ein boolescher könnte so einfach wie ein wenig zu sein. Realistisch gesehen ist es wahrscheinlich eine Byte wahrscheinlicher als ein bisschen. Aber das ist viel kleiner als Speichern vielleicht nach einer 50-Zeichenkette, beispielsweise. 

So versucht, ähnlich wie bei Hash-Tabellen, die kombinieren Arrays und verkettete Liste, Versuchen kombinieren Arrays, Strukturen und Zeiger zusammen, um Daten in speichern eine interessante Art und Weise, ist ziemlich unterschiedlich zu alles, was wir bisher gesehen haben. Jetzt als Fahrplan nutzen wir die Daten um diese Datenstruktur zu navigieren. Und wenn wir folgen können, die Roadmap, wenn wir können befolgen Sie die Daten aus Anfang bis zum Ende, wir wissen, ob dieser Daten existieren in der Trie. 

Und wenn wir können die Karte nicht folgen aus bedeutet, überhaupt zu beenden, die Daten nicht vorhanden sind. Auch hier sind die Schlüssel garantiert eindeutig sein. Und so anders als eine Hash-Tabelle, werden wir nie müssen mit Kollisionen hier umzugehen. Und keine zwei Datenstücke genau die gleiche Roadmap es sei denn, daß die Daten identisch sind. 

Setzen wir John, dann wir suchen für John. Das ist zwei identische Stücke Daten, rechts, wir durch suchen. Aber anders, jede zwei Stücke von Daten sind, garantiert einzigartige Roadmaps haben Durch diese Datenstruktur. Und wir werden ein Blick in eine visuelle dies in nur einem Augenblick. 

Wir werden dies, indem Sie versuchen zu tun, erstellen Sie eine neue Datenstruktur, Kartierung folgende Schlüsselwertpaare. In diesem Fall werden wir nicht verwenden etwas so einfaches wie ein Boolean. Wir werden tatsächlich die Zeichenfolge zu speichern. Und das String Nahmen sei der Name einer Universität. 

Und der Schlüssel wird sich das Jahr sein, wenn dieser Universität gegründet. Alle Jahre für Hochschulen gehen zu vier Ziffern lang sein. Und so werden wir diese vier Ziffern zu verwenden, Navigieren Sie durch diese Datenstruktur. Und wir werden sehen, noch einmal, wie wir tun, dass in nur einer Sekunde. 

Am Ende des Wegs, wir werden den Namen zu sehen der Universität, entspricht für die Taste, die vier Ziffern. Die Grundidee hinter einem Trie ist, dass wir eine zentrale Route. Also denken Sie darüber wie ein Baum. Und das ist ähnlich wie in der Rechtschreibung und im Konzept eines Baumes. Im Allgemeinen, wenn wir denken Bäume in der realen Welt, sie eine Wurzel, die in die es haben Boden und sie nach oben zu wachsen und sie Niederlassungen haben und sie haben Blätter. Und im Grunde die Idee ein Trie ist genau das gleiche, außer dass Wurzel verankert irgendwo in den Himmel. Und die Blätter sind an der Unterseite. 

Also es ist eine Art, wie wenn man einen Baum und nur Spiegeln sie den Kopf. Aber es sind noch Zweige. Und diejenigen, würde unsere Wege zu sein, diese werden unsere Verbindungen sein von der Wurzel zu den Blättern. In diesem Fall diejenigen Wege, diejenigen Zweige sind mit Ziffern, die uns sagen, beschriftet die Möglichkeit, von wo wir sind zu gehen. 

Wenn wir sehen, eine 0, wir hinunter dieser Branche zu gehen, wenn wir sehen, eine 1, wir hinunter dieser Branche zu gehen, und so weiter und so fort. Nun, was bedeutet das? Nun, das bedeutet, dass bei jedem Verbindungspunkt und jeder Knoten in der mittleren und jeder Zweig, gibt es 10 möglich Orte, die wir gehen können. So gibt es 10 Hinweise von jedem Ort. 

Und das ist, wo Versuche kann eine zu bekommen wenig einschüchternd für jemanden wer nicht über eine Menge von Erfahrung in der Informatik vor. Versucht aber sind wirklich ziemlich genial. Und wenn Sie die Chance, mit ihnen zu arbeiten und Sie sind bereit zu graben-in sind und experimentieren mit ihnen, sie sind wirklich sehr interessant Datenstrukturen, mit zu arbeiten. Wenn wir ein Element eingefügt werden soll in den Trie, alles, was wir tun müssen, wird sie mit den richtigen Pfad von der Wurzel zu dem Blatt. Hier ist, was jeder Schritt entlang der Weg aussehen könnte. Wir werden eine neue Daten zu definieren Struktur für einen neuen Knoten genannt trie. 

Und innerhalb dieses Daten Struktur gibt es zwei Teile. Wir gehen in den Laden Namen einer Universität. Und wir werden zu speichern ein Array von Zeigern mit anderen Knoten des gleichen Typs. So, auch dies ist diese Art der Begriff der überall wir sind, wir bei 10 möglich Orte, die wir gehen können. Wenn wir sehen, eine 0, gehen wir diesen Zweig. Wenn wir sehen, a 1, dieser Zweig, und so weiter und so weiter und so fort. Wenn wir sagen, 9, gehen wir diesen Zweig. So an jedem Knotenpunkt, Wir können 10 mögliche Orte zu gehen. Also jeder Knoten bis 10 Zeiger enthalten zu anderen Knoten, auf 10 anderen Knoten. 

Und die Daten, die wir speichern ist nur der Name der Universität. Also lasst uns bauen eine trie. Lassen Sie uns stecken ein paar von Posten in die Trie. So an der Spitze, das ist unser Stammknoten. Dies ist wahrscheinlich, etwas zu sein Sie gehen zu erklären global. Und du wirst global zu halten sind ein Zeiger zu diesem Knoten immer. 

Du wirst sagen: root ist gleich, und du bist wirst dich malloc Trie-Knoten. Und du wirst nie root wieder berühren. Jedes Mal, wenn Sie wollen Start durch die Navigation, Sie einen anderen Zeiger festgelegt gleich Wurzel, wie trav, Das ist das Beispiel I verwenden in vielen meiner Videos hier auf der Stacks und Warteschlangen und Linklisten und so weiter. 

Sie legen eine andere Zeiger genannt trav für Traversal. Und Sie trav verwenden zu navigieren durch die Datenstruktur. Also mal sehen, wie diese aussehen könnte. So jetzt, was hat ein Knoten aus? Nun, so wie unsere Daten Strukturdeklaration angegeben, wir haben einen String, der in diesem Fall ist leer. Hier ist nichts. 

Und eine Anordnung von 10 Zeigern. Und gerade jetzt, nur wir haben 1-Knoten in diesem Trie. Es gibt nichts anderes in ihm. Also alles, 10 von denen, Zeiger auf null gesetzt. Das ist, was die rote zeigt. 

Lassen Sie uns stecken Sie den String Harvard. Lassen Sie uns stecken die Universität Harvard in diesem Trie, die wurde im Jahr 1636 gegründet wurde. Wir wollen den Schlüssel verwenden, 1636, um uns zu sagen, wo wir sind werde Harvard im Trie speichern. Nun, wie können wir das tun? 

Es könnte etwa wie folgt aussehen. Wir fangen an der Wurzel. Und wir haben diese 10 Orte, die wir gehen können. Die Wurzel ist wie jede anderen Knoten des Trie. Es gibt 10 Plätze können wir von hier aus gehen. 

Wo stehen wir wahrscheinlich wollen zu gehen, wenn der Schlüssel ist 1636? Es gibt wirklich zwei Möglichkeiten. Recht. Wir können den Schlüssel aus zu bauen rechts nach links und beginnen mit 6. Oder wir könnten den Schlüssel aus zu bauen links nach rechts und beginnen mit 1. 

Es ist wahrscheinlich mehr intuitive als Mensch In den wir verstehen werde Gehen Sie einfach von links nach rechts. Und so, wenn ich einfügen Harvard in diesem Trie, Ich möchte wohl zu starten beginnend an der Wurzel, Blick auf meine 10-Optionen vor mir, und sagen: Ich möchte gehen Sie die 1-Pfad. OK. 

Nun, das ist ein Weg zur Zeit null. Also, wenn ich will gehen auf diesem Weg um dieses Element in die Trie einzufügen, Ich habe einen neuen Knoten malloc haben 1 zeigen es, und dann bin ich gut zu gehen. 

Also ich bin im Grunde auf eine Punkt, wo ich stehe an der Wurzel des Baums oder der trie und es gibt 10 Niederlassungen. Aber jeder Zweig ein Gate davor. Recht. Denn es gibt nichts anderes da ist. Keine sichere Passage. Das bedeutet, dass es gibt nichts, unten eine dieser Filialen. Wenn ich will, um Gebäude zu starten etwas, ich will, um das Tor zu entfernen. Ich möchte, um das Tor zu entfernen vor der Nummer 1. Und ich möchte, dass hinunter. Und ich will bauen ein weiterer Ort für mich zu gehen. 

Und das ist, was ich hier getan. Also 1 verweist nicht mehr auf null gesetzt. Ich habe gesagt, es ist sicher hier unten jetzt zu gehen. Ich baute einen anderen Knoten. Und wenn ich an diesen Knoten zu bekommen, I haben eine andere Entscheidung zu treffen. Wohin gehe ich, um von hier aus? 

Nun, ich habe bereits auf der 1 weg. So, jetzt will ich wahrscheinlich gehen Sie die 6. Recht. Auch hier habe ich 10 Standorten ich wählen kann. Lassen Sie uns also jetzt die Nummer 6 nach unten gehen. Also ich deaktivieren Sie das Gate vor der Nummer 6. Und ich gehe da unten. Und ich bauen einen anderen Knoten. Und ich habe eine andere Verbindungspunkt erreicht. 

Auch hier habe ich 10 Entscheidungen denn wo ich gehen kann. Ich habe 1-6 bewegt. So, jetzt will ich wohl bis 3 zu gehen. 3, gibt es nirgendwo ich gehen kann. So habe ich, den Weg frei und bauen Sie mir einen neuen Raum. Und dann von 3, wo will ich hin? Ich möchte um 6 gehen. 

Und wieder musste ich den Weg, es zu tun. So, jetzt habe ich meine Schlüssel verwendet, um einzufügen erstellen Knoten und starten, um dieses trie bauen. Ich habe an der Wurzel gestartet. Ich habe ab 1636 verschwunden. Und jetzt bin ich an der Unterseite dort an diesem Knoten. Und Sie könnten in der Lage zu sein, sehen es auf dem Bildschirm. 

Es ist gelb markiert. Das ist, wo ich zur Zeit bin. Mein Schlüssel ist getan. Ich habe jede Position in meinen Schlüssel erschöpft. So kann ich nicht mehr weiter geht. Also an dieser Stelle, alles, was ich wirklich tun müssen, ist zu sagen, OK. Es ist wie eine Art der Suche auf den Boden, wenn Sie Vorstellungsvermögen sind sich selbst als diese Art von Pfad mit verschiedenen Verbindungen. Art der Suche nach unten und Art Spritzlackierung Harvard auf dem Boden. Das ist der Name dafür. Weiß, dass das, was an diesem Ort. Wenn wir an der Wurzel, und wir gehen 1 und 6 und dann 3 und dann 6, wo sind wir? Nun, wenn wir nach unten schauen und wir sehen, Harvard, dann wir wissen, dass Harvard war im Jahre 1636 auf der Grundlage der Art und Weise gegründet wir sind der Umsetzung dieses Datenstruktur. Das war also hoffentlich unkompliziert. Wir werden zwei weitere Insertionen zu tun. Und hoffentlich werde es zu helfen, sehen dies getan zweimal. 

Lassen Sie uns nun legen Sie eine andere Universität. Lassen Sie uns stecken Yale in diesem Trie. Yale wurde im Jahre 1701 gegründet. Also werden wir am Start Wurzel, wie wir es immer tun. Und wir setzen einen Durchlauf-Zeiger. Wir werden das benutzen, um durch zu bewegen. Das erste, was wir wollen zu tun ist, gehen Sie die 1-Pfad. Das ist die erste Ziffer der Taste. Zum Glück, obwohl, wir nicht jede Arbeit dieses Mal zu tun. Die 1-Pfad bereits gelöscht wurde. Ich bat ihn, als ich vorher wurde Harvard Einsetzen bei 1636. So kann ich sicher bewegen down 1 und nur dorthin zu gehen. Wenn sich bewegen Sie die 1. 

Nun aber, ich will bis 7 gehen. Ich machte den Weg bei 6. Ich weiß, ich kann sicher gehen Sie die 6-Pfad. Aber ich muss auf der 7-Pfad gehen. Also, was muss ich tun? Nun, genau wie vor, ich muss nur um das Gate zu löschen, aus dem Weg zu gehen, und bauen Sie einen neuen Knoten aus dem 7-Pfad. Einfach so. 

So jetzt habe ich 1 und 7 bewegt. Und jetzt bemerken, Ich bin Art der auf diesem neuen Teilzweig. Recht. Alles andere aus 16 auf, ich weiß nicht kümmern. Mache ich nicht 16 etwas. Ich mache 17 Sachen. 

So, jetzt von 17 auf, ich muss Art von Blaze neue Wege hier. Die nächste Ziffer mein Schlüssel ist 0. Ich kann natürlich nicht überall zu bekommen. Ich baute gerade diesen Knoten. Also ich weiß, gibt es keine Wege vorwärts von hier. Also muss ich einen selbst zu machen. 

So malloc ich einen neuen Knoten und haben 0 Punkt gibt. Und dann noch einmal, malloc I a neuen Knoten und haben einen Punkt gibt. Auch hier habe ich meine Schlüssel, 1701 erschöpft. So sehe ich nach unten und ich Sprühfarbe Yale. Das ist der Name dieses Knotens. 

Und jetzt, wenn ich jemals brauchen, um zu sehen, wenn Yale wird in diesem Trie, fange ich an der Wurzel, Ich mich 1701 zu gehen, und schauen hinunter. Und wenn ich sehe, Yale Spray auf den Boden gemalten, dann Ich weiß, dass Yale in diesem Trie besteht. Lassen Sie uns noch einen. Lassen Sie uns stecken Dartmouth in diesem trie, die im Jahre 1769 gegründet wurde. 

An der Wurzel beginnen erneut. Meine erste Stelle mein Schlüssel ist 1. Ich kann sicher nach unten zu verschieben, diesen Weg. Das ist bereits vorhanden. Die nächste Ziffer meiner Schlüssel ist 7. Ich kann sicher nach unten zu verschieben, diesen Weg. Es existiert auch. 

Mein nächstes ist 6. Von hier aus, von wo ich gerade bin in gelb gibt in diesem mittleren Knoten, 6 ist derzeit gesperrt aus. Wenn ich diesen Weg nach unten gehen, Ich habe es selbst zu bauen. Also werde ich einen neuen Knoten malloc und haben 6 Punkt gibt. Und dann bin ich wieder neue Wege hier. 

So malloc ich einen neuen Knoten, so dass aus dass node-- Weg Nr 9-- und dann jetzt Wenn ich auf Reisen 1769 und ich freue mich nach unten. Es gibt nichts, noch sprühen es gemalt. Ich kann Dartmouth schreiben. Und ich habe einge Dartmouth in den Trie. 

Das ist also das Einfügen Dinge in der Trie. Jetzt wollen wir für Dinge zu suchen. Wie können wir für die Dinge in der Trie zu suchen? Nun, es ist so ziemlich das gleiche Idee. Jetzt verwenden wir nur die Ziffern der Schlüssel zu sehen, ob wir von der Wurzel zu navigieren , wo wir in der Trie gehen wollen. 

Wenn wir in eine Sackgasse an einem beliebigen Punkt, dann wir wissen, dass das Element nicht vorhanden ist oder auch, dass Pfad würde wurden bereits geräumt. Wenn wir es den ganzen Weg zu das Ende, alles, was wir tun müssen, ist Blick nach unten und sehen, ob das das Element, die wir suchen. Wenn es ist, den Erfolg. Wenn es nicht, scheitern. 

Also lassen Sie uns die Suche nach Harvard in diesem Trie. Wir fangen an der Wurzel. Und wieder werden wir erstellen Sie einen Zeiger-Traversal unsere bewegt sich für uns tun. Von der Wurzel wissen wir, dass die Erstens müssen wir gehen, ist 1, können wir das tun? Ja wir können. Wenn sicher existiert. Wir können dorthin gehen. 

Nun, der nächste Ort, den wir gehen müssen, ist 6. Hat das 6-Pfad von hier aus gibt es? Ja, das tut es. Wir können gehen die 6-Pfad. Und wir am Ende hier. 

Können wir auf der 3-Pfad von hier aus? Nun, wie sich herausstellt, ja, existiert auch. Und wir können uns auf die 6 Weg von hier? Ja wir können. 

Wir haben nicht ganz beantwortet doch ist die Frage. Es gibt noch eine weitere Schritt, der jetzt Wir müssen nach unten zu schauen und sehen, ob das actually-- wenn wir für Harvard suchen, ist, dass was wir finden, nachdem wir erschöpfen den Schlüssel? Im Beispiel verwenden wir hier, Die Jahre sind immer vier Ziffern. Aber Sie könnten mit dem Beispiel, in dem Sie speichert ein Wörterbuch von Wörtern. 

Und so anstatt 10 Zeigern für meine Lage, haben Sie vielleicht 26. Eine für jeden Buchstaben des Alphabets. Und es gibt einige Wörter wie Fledermaus, die eine Teilmenge der Charge, zum Beispiel. Und so, auch wenn Sie das bekommen Ende des Schlüssels und Sie nach unten schauen, Sie nicht sehen können, was den Sie suchen. 

So dass Sie immer zu durchqueren der gesamte Pfad und dann wenn Sie erfolgreich in der Lage waren den gesamten Pfad zu durchlaufen, Blick nach unten und führen Sie eine Buchungsbestätigung. Ist das, was ich suche? Nun, ich schauen hinunter nach dem Start an der Spitze und geht 1636. Ich schaue nach unten. Ich sehe Harvard. Also, ja, gelang es mir. Was passiert, wenn das, was ich auf der Suche nach nicht in der Trie, wenn. Was ist, wenn ich suche nach Princeton, , die im Jahre 1746 gegründet wurde. Und so 1746 wird mein Schlüssel durch den Trie navigieren. Nun beginne ich an der Wurzel. Und der erste Ort, den ich möchte um nach unten geht die 1-Pfad. Kann ich es schaffen? Ja, ich kann. 

Kann ich auf der 7-Pfad von dort aus gehen? Ja, ich kann. Das existiert auch. Aber kann ich auf der 4-Weg von hier aus? Das ist wie die Frage zu stellen, kann Ich gehe nach unten, dass kleinen Platz dass ich gelb markiert? Da ist nichts. Recht. 

Es gibt keinen Weg nach vorne auf der 4-Pfad. Wenn Princeton war in diesem Trie, dass 4 wäre für uns schon gelöscht haben. Und so an dieser Stelle haben wir in einer Sackgasse. Wir können nicht weiter gehen. Und so können wir sagen, definitiv nein. Princeton nicht in diesem Trie existieren. 

Also, was bedeutet das alles? Recht. Es gibt eine Menge los. Es gibt Hinweise ganz über dem Platz. Und wie Sie sehen können, nur aus dem Diagramm, es gibt eine Menge von Knoten, sind Art herumfliegen. Aber beachten Sie jedes Mal, wenn wir wollten, prüfen, ob etwas nicht in der Trie, wir mussten nur 4 Schritte zu machen. 

Jedes Mal, wenn wir wollten, Einsatz etwas in der Trie, wir müssen 4 Schritte zu machen, möglicherweise mallocing paar Sachen auf dem Weg. Aber wie wir gesehen haben, als wir einge Dartmouth in den Trie, manchmal einige der Pfad vielleicht schon für uns gelöscht werden. Und so wie unsere Trie wird größer und größer, wir haben jedes Mal tun, weniger Arbeit , neue Dinge zu fügen weil wir bereits haben baute eine Menge von Zwischen Niederlassungen auf dem Weg. Wenn wir immer nur, zu betrachten 4 Dinge, 4 ist nur eine Konstante. Wir sind wirklich Art von Annäherung konstanten Zeiteinblendung und konstante Zeit Lookup. Der Nachteil ist natürlich, ist, dass Diese trie, da kann man wohl sagen, ist groß. Jeder dieser Knoten nimmt viel Platz. 

Aber das ist der Kompromiss. Wenn wir wollen, wirklich schnell Insertion, wirklich schnell Löschung, und wirklich schnelle Suche, müssen wir haben eine Menge Daten herumfliegen. Wir haben neben viel Platz zu setzen und einen Speicher für die Datenstruktur existieren. 

Und damit ist der Kompromiss. Aber es sieht aus wie wir könnte es gefunden. Wir könnten festgestellt, dass Heilige Gral der Datenstrukturen mit Schnelleinschub, Löschen und Lookup. Und vielleicht wird dies eine sein geeignete Datenstruktur zu irgendwelchen Informationen benutzen, wir versuchen zu speichern. Ich bin Doug Lloyd, ist dies CS50.