[Παίζει μουσική] DOUG LLOYD: Έτσι έχουμε εγγύτερα και στενότερη ότι Άγιο Δισκοπότηρο των δεδομένων δομές, αυτό που μπορούμε να εισάγουμε σε, να διαγράψετε από, και κοιτάζω προς τα πάνω σε σταθερό χρόνο. Δεξιά. Αυτό είναι το είδος του στόχου. Θέλουμε να είμαστε σε θέση να κάνουμε τα πράγματα είναι πολύ, πολύ γρήγορα. 

Έχετε το βρήκαμε εδώ όταν μιλάμε για προσπάθειες; Λοιπόν, ας ρίξουμε μια ματιά. Έτσι έχουμε δει αρκετές διαφορετικές δομές δεδομένων που χειρίζονται την χαρτογράφηση των λεγόμενη ζεύγη κλειδιού-τιμής, χαρτογράφηση κάποιο κομμάτι των δεδομένων σε κάποιο άλλο κομμάτι δεδομένων έτσι ώστε να γνωρίζουν πού να βρείτε πληροφορίες στη δομή. 

Έτσι, για συστοιχία, για παράδειγμα, το κλειδί είναι ο δείκτης στοιχείο ή συστοιχία τοποθεσία 0 ή συστοιχία 1 και ούτω καθεξής. Και η τιμή είναι τα δεδομένα ότι υπάρχει σε αυτή τη θέση. Έτσι, αυτό που είναι αποθηκευμένα στη σειρά 0; Τι είναι αποθηκευμένα σε σειρά έναντι μόλις 1 0 και 1, τα οποία θα είναι τα κλειδιά. 

Με ένα πίνακα κατακερματισμού είναι το είδος της ίδιας ιδέας. Με ένα πίνακα κατακερματισμού, έχουμε αυτό το κλειδί λειτουργία που δημιουργεί κωδικούς hash. Έτσι, το κλειδί είναι ο κώδικας hash των δεδομένων. Και η τιμή, ιδίως μιλήσαμε για την αλυσιδωτή σύνδεση στο βίντεο για πίνακες κατακερματισμού, είναι εκείνος που συνδέεται κατάλογο των δεδομένων ότι απεικονίζεται σε αυτή την hashCode. Δεξιά. Τι γίνεται με μια άλλη προσέγγιση Αυτή η μέθοδος, όμως; Τι γίνεται με μια μέθοδο, η οποία το κλειδί είναι εγγυημένη για να είναι μοναδική, σε αντίθεση με ένα πίνακα κατακερματισμού, όπου θα μπορούσαμε να καταλήγουν με δύο κομμάτια των στοιχείων που έχουν την ίδια hashCode. Και τότε έχουμε να κάνουμε με ότι είτε διερεύνηση ή περισσότερα κατά προτίμηση αλυσιδωτή σύνδεση για να διορθώσετε αυτό το πρόβλημα. 

Έτσι τώρα μπορούμε να εγγυηθούμε ότι οι βασικές μας θα είναι μοναδική. Και τι θα γινόταν αν ήταν τιμή μας ακριβώς κάτι τόσο εύκολο ως αληθινό και το ψεύτικο που μας λέει αν ή όχι αυτό το κομμάτι των πληροφοριών υπάρχει στην δομή; Μια Boolean θα μπορούσε να είναι τόσο απλό όσο ένα κομμάτι. Ρεαλιστικά είναι πιθανώς μια byte πιο πιθανό από ό, τι ένα κομμάτι. Αλλά αυτό είναι πολύ μικρότερο από ό, τι αποθήκευση ίσως μια σειρά 50 χαρακτήρων, για παράδειγμα. 

Έτσι προσπαθεί, παρόμοια με hash πίνακες, που συνδυάζουν συστοιχίες και συνδεδεμένη λίστα, προσπαθεί συνδυάζουν συστοιχίες, δομές, και δείκτες μαζί με την αποθήκευση δεδομένων σε ένας ενδιαφέρων τρόπος που είναι αρκετά διαφορετική από οτιδήποτε έχουμε δει μέχρι τώρα. Τώρα χρησιμοποιούμε τα δεδομένα ως οδικός χάρτης για να πλοηγηθείτε σε αυτήν τη δομή των δεδομένων. Και αν μπορούμε να ακολουθήσουμε Ο οδικός χάρτης, αν μπορούμε ακολουθήστε τα δεδομένα από αρχή μέχρι το τέλος, θα ξέρω αν αυτά τα δεδομένα υπάρχουν στο Trie. 

Και αν δεν μπορεί να ακολουθήσει το χάρτη από νόημα να καταλήξει σε όλα, δεν μπορεί να υπάρξει τα στοιχεία. Πάλι, τα πλήκτρα είναι εδώ εγγυημένη για να είναι μοναδική. Και έτσι σε αντίθεση με ένα πίνακα κατακερματισμού, εμείς δεν πρόκειται ποτέ πρέπει να ασχοληθεί με συγκρούσεις εδώ. Και δεν υπάρχουν δύο κομμάτια των δεδομένων έχουν ακριβώς το ίδιο οδικό χάρτη εκτός ότι τα δεδομένα είναι πανομοιότυπα. 

Αν εισάγετε τον Ιωάννη, στη συνέχεια, ψάχνουμε για τον John. Αυτό είναι δύο πανομοιότυπα κομμάτια δεδομένων, δεξιά, ψάχνουμε μέσα. Αλλά κατά τα άλλα, οποιαδήποτε δύο κομμάτια των δεδομένων είναι εγγυημένη για να έχουν μοναδικές χάρτες πορείας μέσω αυτής της δομής δεδομένων. Και θα πάμε να ρίξουμε μια ματιά στο μια οπτική του αυτό ακριβώς σε μια στιγμή. 

Θα το κάνουμε αυτό με την προσπάθεια να δημιουργηθεί μια νέα δομή δεδομένων, χαρτογράφηση τα ακόλουθα βασικά ζεύγη τιμών. Σε αυτή την περίπτωση, εμείς δεν πρόκειται να χρησιμοποιήσετε κάτι τόσο απλό όσο ένα Boolean. Είμαστε πραγματικά θα αποθηκεύσει το string. Και αυτή η συμβολοσειρά θα να είναι το όνομα του πανεπιστημίου. 

Και το κλειδί θα είναι η χρονιά όταν το εν λόγω πανεπιστήμιο ιδρύθηκε. Όλα τα έτη για τα πανεπιστήμια πρόκειται να είναι τετραψήφιος. Και έτσι θα χρησιμοποιήσουμε αυτά τα τέσσερα ψηφία πλοηγηθείτε σε αυτήν την δομή των δεδομένων. Και θα δούμε, και πάλι, πώς το κάνουμε αυτό σε μόλις ένα δευτερόλεπτο. 

Στο τέλος της διαδρομής, θα δούμε το όνομα του πανεπιστημίου που αντιστοιχεί σε αυτό το κλειδί, αυτά τα τέσσερα ψηφία. Η βασική ιδέα πίσω από ένα trie είναι ότι έχουμε μια κεντρική διαδρομή. Έτσι σκεφτείτε το σαν ένα δέντρο. Και αυτό είναι παρόμοιο στην ορθογραφία και στην ιδέα για ένα δέντρο. Σε γενικές γραμμές όταν σκεφτόμαστε δέντρα στον πραγματικό κόσμο, έχουν μια ρίζα που είναι στην έδαφος και αναπτύσσονται προς τα πάνω και έχουν υποκαταστήματα και έχουν τα φύλλα. Και βασικά η ιδέα της α trie είναι ακριβώς το ίδιο, εκτός από το ότι η ρίζα αγκυροβολημένο κάπου στον ουρανό. Και τα φύλλα βρίσκονται στο κάτω μέρος. 

Έτσι είναι το είδος του όπως τη λήψη ενός δέντρου και απλά να ρίχνεις ανάποδα. Αλλά εξακολουθούν να υπάρχουν υποκαταστήματα. Και αυτοί θα είναι οδών μας, Αυτές θα είναι οι συνδέσεις μας από τη ρίζα προς τα φύλλα. Σε αυτήν την περίπτωση, εκείνοι μονοπάτια, τα υποκαταστήματα επισημαίνονται με ψηφία που μας λένε ποιο τρόπο να πάει από εκεί που είμαστε. 

Αν δούμε ένα 0, κατεβαίνουμε αυτόν τον κλάδο, Αν δούμε ένα 1, κατεβαίνουμε αυτόν τον κλάδο, και ούτω και ούτω καθεξής. Λοιπόν, τι σημαίνει αυτό; Λοιπόν, αυτό σημαίνει ότι σε κάθε σημείο διασταύρωση και κάθε κόμβος στο μεσαία και κάθε υποκατάστημα, υπάρχουν 10 πιθανές μέρη που μπορούμε να πάμε. Έτσι, υπάρχουν 10 δείκτες από κάθε τοποθεσία. 

Και αυτό είναι που προσπαθεί να πάρει μια λίγο εκφοβιστικό για κάποιον ποιος δεν έχει πολλή εμπειρία στην επιστήμη των υπολογιστών πριν. Αλλά προσπαθεί είναι πραγματικά πολύ ωραία. Και αν έχετε το την ευκαιρία να συνεργαστούμε μαζί τους και είστε πρόθυμοι να σκάψουν στο και να πειραματιστούν μαζί τους, είναι πραγματικά πολύ ενδιαφέρον δομές δεδομένων για να εργαστείτε με. Αν θέλετε να εισάγετε ένα στοιχείο στο trie, το μόνο που χρειάζεται να κάνουμε έχει χτίσει τη σωστή διαδρομή από τη ρίζα στο φύλλο. Εδώ είναι αυτό που σε κάθε βήμα κατά μήκος ο τρόπος που μπορεί να μοιάζει. Εμείς πάμε για να ορίσετε μια νέα δεδομένα δομή για ένα νέο κόμβο που ονομάζεται trie. 

Και μέσα σε αυτά τα δεδομένα δομή υπάρχουν δύο κομμάτια. Εμείς πάμε για να αποθηκεύσετε το το όνομα του πανεπιστημίου. Και θα πάμε να αποθηκεύσετε μια σειρά από δείκτες σε άλλους κόμβους του ίδιου τύπου. Έτσι, και πάλι, αυτό είναι ότι το είδος της έννοιας της παντού είμαστε, σε 10 πιθανές μέρη που μπορούμε να πάμε. Αν δούμε ένα 0, μπορούμε να ακολουθήσουμε αυτόν τον κλάδο. Αν δούμε ένα 1, ο κλάδος αυτός, και ούτω καθεξής και ούτω καθεξής και ούτω καθεξής. Αν λέμε 9, κατηφορίζουμε αυτόν τον κλάδο. Έτσι, σε κάθε σημείο σύνδεσης, μπορούμε να πάμε 10 πιθανές θέσεις. Έτσι, κάθε κόμβος πρέπει να περιέχει 10 δείκτες σε άλλους κόμβους, για 10 άλλους κόμβους. 

Και τα δεδομένα είμαστε αποθήκευσης είναι μόνο το όνομα του πανεπιστημίου. Ας οικοδομήσουμε μια trie. Ας εισάγετε ένα ζευγάρι των στοιχείων σε Trie μας. Έτσι, στην κορυφή, Αυτή είναι η ρίζα του κόμβου μας. Αυτό κατά πάσα πιθανότητα πρόκειται να είναι κάτι θα πάμε να δηλώνουν παγκόσμιο επίπεδο. Και θα πάμε να διατηρήσει παγκόσμιο επίπεδο ένας δείκτης σε αυτόν τον κόμβο πάντα. 

Θα πάμε να πούμε, ρίζα ισούται με, και είστε πρόκειται να malloc εαυτό trie κόμβο. Και αν δεν πρόκειται ποτέ να αγγίξει και πάλι ρίζα. Κάθε φορά που θέλετε να ξεκινήσετε την πλοήγηση μέσα, ορίσετε έναν άλλο δείκτη ίσο με ρίζα, όπως trav, η οποία είναι το παράδειγμα Ι χρήση σε πολλά από τα βίντεό μου εδώ για στοίβες και ουρές και τους καταλόγους σύνδεσμο και ούτω καθεξής. 

Μπορείτε να ορίσετε έναν άλλο δείκτη που ονομάζεται Trav για διάσχιση. Και μπορείτε να χρησιμοποιήσετε για να περιηγηθείτε Trav μέσω της δομής των δεδομένων. Ας δούμε πώς αυτό μπορεί να μοιάζει. Έτσι τώρα, τι ένας κόμβος δεν μοιάζει; Λοιπόν, όπως ακριβώς τα δεδομένα μας δήλωση δομή υποδεικνύεται, έχουμε μια σειρά, η οποία στην περίπτωση αυτή είναι κενή. Δεν υπάρχει τίποτα εδώ. 

Και μια σειρά από 10 δείκτες. Και τώρα, έχουμε μόνο έχουν 1 κόμβος σε αυτή την trie. Δεν υπάρχει τίποτα άλλο σε αυτό. Έτσι, οι 10 από αυτούς δείκτες σημείο σε null. Αυτό είναι ό, τι δείχνει το κόκκινο. 

Ας εισάγετε τα στοιχεία του Χάρβαρντ. Ας προστεθεί το Πανεπιστήμιο του Χάρβαρντ σε αυτό το Trie, η οποία ιδρύθηκε το έτος 1636. Θέλουμε να χρησιμοποιήσετε το πλήκτρο, 1636, για να μας πει πού είμαστε πρόκειται να αποθηκεύσετε το Χάρβαρντ στο Trie. Τώρα, πώς θα μπορούσαμε να το κάνουμε αυτό; 

Θα μπορούσε να είναι κάπως έτσι. Ξεκινάμε από τη ρίζα. Και έχουμε αυτές τις 10 θέσεις που μπορούμε να πάμε. Η ρίζα είναι ακριβώς όπως οποιοδήποτε άλλο κόμβο του Trie. Υπάρχουν 10 θέσεις μπορούμε να πάμε από εδώ. 

Πού θα θελήσετε πιθανώς για να πάει, αν το κλειδί είναι 1636; Υπάρχει πραγματικά δύο επιλογές. Δεξιά. Μπορούμε να οικοδομήσουμε το κλειδί από δεξιά προς τα αριστερά και να αρχίσει με 6. Ή θα μπορούσαμε να οικοδομήσουμε το κλειδί από αριστερά προς τα δεξιά και να αρχίσει με 1. 

Είναι ίσως περισσότερο διαισθητική ως ανθρώπινο ον να καταλαβαίνουμε θα Απλά πηγαίνετε αριστερά προς τα δεξιά. Και έτσι αν θέλετε να εισάγετε Χάρβαρντ σε αυτό το Trie, Μάλλον θέλετε να ξεκινήσετε ξεκινώντας από τη ρίζα, κοιτάζοντας τις επιλογές μου 10 μπροστά μου, και λέγοντας Θέλω να πάω κάτω από το 1 διαδρομή. ΕΝΤΆΞΕΙ. 

Τώρα, 1 μονοπάτι είναι σήμερα μηδενική. Έτσι, αν θέλω να προχωρήσουμε σε αυτή την κατεύθυνση για να εισαγάγετε αυτό το στοιχείο στο Trie, Έχω να malloc ενός νέου κόμβου, έχουν 1 σημείο εκεί, και τότε είμαι καλό να πάει. 

Γι 'αυτό και ουσιαστικά είμαι σε μια σημείο όπου στέκομαι στη ρίζα του δέντρου ή του trie και υπάρχουν 10 υποκαταστήματα. Αλλά κάθε υποκατάστημα έχει πύλη μπροστά του. Δεξιά. Επειδή δεν υπάρχει τίποτα άλλο εκεί. Δεν ασφαλή διέλευση. Αυτό σημαίνει ότι δεν υπάρχει τίποτα κάτω από οποιοδήποτε από τα υποκαταστήματα αυτά. Αν θέλω να αρχίσει η δημιουργία κάτι, θέλω να αφαιρέσω την πύλη. Θέλω να καταργήσω την πύλη μπροστά από τον αριθμό 1. Και θέλω να περπατήσουν κάτω από αυτό. Και θέλω να οικοδομήσουμε ένα άλλο μέρος για μένα να πάω. 

Και αυτό είναι ό, τι έχω κάνει εδώ. Έτσι, δεν είναι πλέον 1 σημεία σε μηδέν. Έχω πει ότι είναι ασφαλές να πάει κάτω εδώ τώρα. Έφτιαξα ένα άλλο κόμβο. Και όταν φτάσουμε σε αυτό τον κόμβο, Ι έχουν άλλη απόφαση να κάνει. Πού θα πάω να πάω από εδώ; 

Λοιπόν, έχω ήδη πάει κάτω από το 1. Έτσι τώρα μπορώ πιθανόν να θέλετε να πάει κάτω από το 6. Δεξιά. Και πάλι, έχω 10 θέσεις μπορώ να επιλέξω. Ας πάμε τώρα κάτω από τον αριθμό 6. Γι 'αυτό και καταργήστε την πύλη μπροστά από τον αριθμό 6. Και περπατώ εκεί κάτω. Και μπορώ να δημιουργήσω έναν άλλο κόμβο. Και έχω φθάσει σε ένα άλλο κομβικό σημείο. 

Και πάλι, έχω 10 επιλογές για το πού μπορώ να πάω. Έχω μετακινηθεί 1-6. Έτσι τώρα μπορώ ίσως θέλουν να πάνε στο 3. 3, δεν υπάρχει πουθενά μπορώ να πάω. Γι 'αυτό πρέπει να ανοίξει το δρόμο και να οικοδομήσουμε τον εαυτό μου ένα νέο χώρο. Και μετά από 3, πού θέλω να πάω; Θέλω να πάω κάτω 6. 

Και, πάλι, έπρεπε να ανοίξει το δρόμο για να το κάνουμε. Μέχρι τώρα έχω χρησιμοποιήσει το κλειδί μου για να εισάγετε τη δημιουργία κόμβους και να αρχίσει να χτίσει αυτό το Trie. Έχω αρχίσει στη ρίζα. Έχω πάει κάτω 1636. Και τώρα είμαι στο κάτω μέρος εκεί σε αυτόν τον κόμβο. Και ίσως να είναι σε θέση να δείτε στην οθόνη σας. 

Είναι επισημαίνονται με κίτρινο χρώμα. Αυτό είναι όπου είμαι σήμερα. Κλειδί μου γίνεται. Έχω εξαντλήσει κάθε θέση κλειδί μου. Έτσι, δεν μπορώ να προχωρήσουμε περαιτέρω. Έτσι, σε αυτό το σημείο, το μόνο που μπορώ πρέπει πραγματικά να κάνουμε είναι να πούμε, εντάξει. Είναι το είδος του αρέσει που αναζητούν κάτω στο έδαφος, αν είστε οραματίζονται τον εαυτό σας όπως αυτό το είδος της διαδρομής με διαφορετικές συνδέσεις. Ταξινόμηση της κοιτάζοντας προς τα κάτω και το είδος σπρέι βαφής Χάρβαρντ στο έδαφος. Αυτό είναι το όνομα του αυτό. Να ξέρετε ότι είναι ό, τι είναι σε αυτή τη θέση. Αν αρχίσουμε από τη ρίζα και κατηφορίζουμε 1 και στη συνέχεια 6 και, στη συνέχεια, 3 και στη συνέχεια 6, που είμαστε? Λοιπόν, αν κοιτάξουμε προς τα κάτω και βλέπουμε Χάρβαρντ, στη συνέχεια, γνωρίζουμε ότι το Χάρβαρντ ήταν ιδρύθηκε το 1636 με βάση τον τρόπο είμαστε εφαρμογή αυτής της δομής δεδομένων. Έτσι, αυτό ήταν ελπίζουμε απλή. Εμείς πάμε να κάνουμε δύο ακόμα προσθήκες. Και ελπίζουμε ότι αυτό θα βοηθήσει να δείτε αυτό το κάνει δύο φορές περισσότερο. 

Τώρα, ας τοποθετήστε ένα άλλο πανεπιστήμιο. Ας προστεθεί Yale σε αυτό το Trie. Yale ιδρύθηκε το 1701. Έτσι θα ξεκινήσει κατά τη ρίζα, όπως κάνουμε πάντα. Και έχουμε δημιουργήσει ένα δείκτη διάσχισης. Εμείς πάμε για να χρησιμοποιήσετε αυτό για να μετακινηθείτε. Το πρώτο πράγμα που θέλουμε να κάνετε είναι να πάτε κάτω από το 1 διαδρομή. Αυτό είναι το πρώτο ψηφίο του κλειδιού μας. Ευτυχώς, όμως, δεν το κάνουμε Πρέπει να κάνει οποιαδήποτε εργασία αυτή τη φορά. Η διαδρομή 1 έχει ήδη εκκαθαριστεί. Μου εκκαθαριστεί προηγουμένως, όταν η εισαγωγή του Χάρβαρντ στο 1636. Γι 'αυτό και μπορεί να κινηθεί με ασφάλεια κάτω από 1 και πήγαινε εκεί. Αν μπορεί να κινηθεί κάτω από το 1. 

Τώρα, όμως, θέλω να πάω στο 7. Θα ανοίξει το δρόμο σε 6. Ξέρω ότι μπορώ με ασφάλεια να προχωρήσει προς τα κάτω το μονοπάτι 6. Αλλά πρέπει να προχωρήσουμε στο δρόμο 7. Οπότε τι πρέπει να κάνω; Λοιπόν, ακριβώς όπως και πριν, το μόνο που χρειάζεται για να καταργήσετε την πύλη, να βγει από το δρόμο, και να οικοδομήσουμε ένα νέο κόμβο από τη διαδρομή 7. Όπως αυτό. 

Έτσι τώρα έχω μετακινηθεί 1 και στη συνέχεια 7. Και τώρα παρατηρήσετε, είμαι το είδος του σε αυτό το νέο subbranch. Δεξιά. Όλα τα υπόλοιπα από 16 σε, εγώ δεν νοιάζονται για. Εγώ δεν κάνω τίποτα 16. Κάνω 17 πράγματα. 

Έτσι τώρα, από τις 17 και στο εξής, θα πρέπει να είδος χαράξει νέα μονοπάτια εδώ. Το επόμενο ψηφίο είναι το κλειδί μου 0. Προφανώς δεν μπορώ να πάρετε οπουδήποτε. Απλά έχτισε αυτό το κόμβο. Έτσι ξέρω ότι δεν υπάρχει κανένας μονοπάτια προς τα εμπρός από εδώ. Έτσι έχω να κάνω τον εαυτό μου. 

Γι 'αυτό και malloc ενός νέου κόμβου και έχουν σημείο 0 εκεί. Και στη συνέχεια, για μια ακόμη φορά, έχω ένα malloc νέο κόμβο και να έχουν ένα σημείο εκεί. Και πάλι, έχω εξαντλήσει το κλειδί μου, 1701. Έτσι κοιτάζω κάτω και σπρέι βαφής Yale. Αυτό είναι το όνομα αυτού του κόμβου. 

Και έτσι τώρα αν ποτέ χρειαστεί να δούμε αν Yale Είναι σε αυτό το trie, μπορώ να ξεκινήσω από τη ρίζα, Κατέβω 1701, και να κοιτάξει κάτω. Και αν δω σπρέι Yale ζωγραφισμένα στο έδαφος, στη συνέχεια, Ξέρω Yale υπάρχει σε αυτή την trie. Ας κάνουμε ένα ακόμη. Ας προστεθεί σε αυτό Ντάρτμουθ trie, η οποία ιδρύθηκε το 1769. 

Ξεκινήστε από τη ρίζα και πάλι. Η πρώτη μου ψηφίο του κλειδιού μου είναι 1. Μπορώ να κινηθεί με ασφάλεια σε αυτή την κατεύθυνση. Που ήδη υπάρχει. Το επόμενο ψηφίο του κλειδιού μου είναι 7. Μπορώ να κινηθεί με ασφάλεια σε αυτή την κατεύθυνση. Υπάρχει επίσης. 

Δίπλα μου είναι 6. Από εδώ, απ 'όπου βρίσκομαι σήμερα σε κίτρινο υπάρχει σε αυτή τη μεσαία κόμβο, 6 είναι κλειδωμένος μακριά. Αν θέλω να πάω σε αυτή την κατεύθυνση, Έχω να το κατασκευάσω μόνος μου. Γι 'αυτό θα malloc ενός νέου κόμβου και έχει 6 σημείο εκεί. Και τότε, και πάλι, είμαι απίστευτα νέα μονοπάτια εδώ. 

Γι 'αυτό και malloc ένα νέο κόμβο έτσι ώστε από ότι node-- αριθμός διαδρομής 9-- και, στη συνέχεια, τώρα αν ταξιδεύω 1769, και κοιτάζω προς τα κάτω. Δεν υπάρχει τίποτα επί του παρόντος σπρέι ζωγραφισμένα εκεί. Μπορώ να γράψω Dartmouth. Και έχω εισαχθεί Dartmouth στο Trie. 

Έτσι, αυτό είναι εισαγωγή τα πράγματα στο Trie. Τώρα θέλουμε να αναζητήσετε τα πράγματα. Πώς μπορώ να ψάχνουμε για πράγματα στο Trie; Λοιπόν, αυτό είναι λίγο πολύ η ίδια ιδέα. Τώρα χρησιμοποιούμε μόνο τα ψηφία του κλειδιού για να δούμε αν μπορούμε να περιηγηθείτε από τη ρίζα στο σημείο όπου θέλουμε να πάμε στο Trie. 

Αν χτυπήσει ένα αδιέξοδο σε οποιοδήποτε σημείο, στη συνέχεια, γνωρίζουμε ότι δεν μπορεί να υπάρχει το στοιχείο αυτό ή αλλιώς η διαδρομή θα έχουν ήδη εκκαθαριστεί. Αν το κάνει όλη τη διαδρομή προς το τέλος, το μόνο που χρειάζεται να κάνουμε είναι να κοιτάξει κάτω και να δούμε αν αυτό είναι το στοιχείο που ψάχνουμε. Αν είναι, η επιτυχία. Αν δεν είναι, αποτυγχάνουν. 

Ας ψάξετε Χάρβαρντ σε αυτό το Trie. Ξεκινάμε από τη ρίζα. Και, πάλι, θα πάμε να δημιουργία ενός δείκτη διάσχιση να κάνει τις κινήσεις μας για μας. Από τη ρίζα γνωρίζουμε ότι η πρώτο μέρος που πρέπει να πάτε είναι 1, μπορούμε να το κάνουμε αυτό; Ναι μπορούμε. Αν υπάρχει ασφάλεια. Μπορούμε να πάμε εκεί. 

Τώρα, το επόμενο μέρος που πρέπει να πάτε είναι 6. Μήπως η διαδρομή 6 υπάρχουν από εδώ; Ναι, αυτό κάνει. Μπορούμε να ακολουθήσουμε τον δρόμο 6. Και καταλήγουμε εδώ. 

Μπορούμε να πάμε κάτω από το 3 μονοπάτι από εδώ; Λοιπόν, όπως αποδεικνύεται, ναι, ότι υπάρχει πάρα πολύ. Και μπορούμε να έχουμε στις 6 μονοπάτι από εδώ; Ναι μπορούμε. 

Δεν έχουμε αρκετά απαντηθεί η ερώτηση ακόμα. Υπάρχει μία ακόμη βήμα, το οποίο είναι τώρα θα πρέπει να κοιτάξουμε προς τα κάτω και να δούμε αν αυτό είναι actually-- αν ψάχνουμε για το Χάρβαρντ, είναι ότι τι θα βρούμε αφού εξαντλεί το κλειδί; Στο παράδειγμα που χρησιμοποιούμε εδώ, τα χρόνια είναι πάντα τέσσερα ψηφία. Αλλά ίσως να χρησιμοποιώντας το παράδειγμα όπου αποθηκεύετε ένα λεξικό των λέξεων. 

Και έτσι αντί να έχουμε 10 δείκτες για τη θέση μου, μπορείτε να έχετε 26. Μία για κάθε γράμμα της αλφαβήτου. Και υπάρχουν κάποιες λέξεις όπως νυχτερίδα, η οποία είναι ένα υποσύνολο της παρτίδας, για παράδειγμα. Και έτσι, ακόμη και αν έχετε να το τέλος του κλειδιού και κοιτάς κάτω, μπορεί να μην δούμε τι ψάχνετε. 

Έτσι, μπορείτε πάντα να διασχίσουμε ολόκληρη η διαδρομή και στη συνέχεια αν ήταν σε θέση επιτυχώς να διασχίσει ολόκληρη τη διαδρομή, κοιτάξει κάτω και να κάνουμε μια τελική επιβεβαίωση. Είναι ότι αυτό που ψάχνω; Λοιπόν, εγώ κοιτάζω προς τα κάτω μετά την έναρξη της στην κορυφή και πηγαίνοντας 1636. Κοιτάζω προς τα κάτω. Βλέπω Χάρβαρντ. Έτσι, ναι, έχω καταφέρει. Τι γίνεται αν αυτό που ψάχνω για δεν είναι στο trie, όμως. Τι θα συμβεί αν ψάχνω για Princeton, η οποία ιδρύθηκε το 1746. Και έτσι γίνεται 1746 κλειδί μου για να πλοηγηθείτε στο Trie. Λοιπόν, μπορώ να ξεκινήσω από τη ρίζα. Και η πρώτη θέση που θέλω να πηγαίνει κάτω από το 1 διαδρομή. Μπορώ να το κάνω; Ναι μπορω. 

Μπορώ να πάω κάτω από το 7 μονοπάτι από εκεί; Ναι, μπορώ. Ότι υπάρχει πάρα πολύ. Αλλά μπορώ να πάω κάτω από το 4 μονοπάτι από εδώ; Αυτό είναι σαν να ζητάμε από την ερώτηση, μπορεί να Θα προχωρήσουμε προς τα κάτω αυτό το μικρό τετράγωνο ότι έχω επισημαίνονται με κίτρινο χρώμα; Δεν υπάρχει τίποτα εκεί. Δεξιά. 

Δεν υπάρχει δρόμος προς τα εμπρός κάτω από την πορεία 4. Εάν Princeton ήταν σε αυτό το trie, ότι 4 θα έχουν εκκαθαριστεί για εμάς ήδη. Και έτσι σε αυτό το σημείο έχουμε φτάσει σε ένα αδιέξοδο. Δεν μπορούμε να προχωρήσουμε περαιτέρω. Και έτσι μπορούμε να πούμε, οριστικά, όχι. Princeton δεν υπάρχει σε αυτό το Trie. 

Έτσι τι σημαίνουν όλα αυτά; Δεξιά. Υπάρχει μια παρτίδα σε εξέλιξη εδώ. Υπάρχει δείκτες σε όλη τη χώρα. Και, όπως μπορείτε να δείτε μόλις από το διάγραμμα, υπάρχει μια μεγάλη κόμβους που είναι το είδος της πετούν γύρω. Αλλά παρατηρήσετε κάθε φορά που θέλαμε να ελέγξτε αν κάτι ήταν στην Trie, είχαμε μόνο να κάνει 4 κινήσεις. 

Κάθε φορά που θέλαμε να εισάγετε κάτι στο Trie, πρέπει να κάνουμε 4 κινήσεις, πιθανώς mallocing κάποια πράγματα στην πορεία. Αλλά, όπως είδαμε όταν εισάγεται Dartmouth στο Trie, μερικές φορές κάποια της διαδρομής μπορεί να είναι ήδη εκκαθαριστεί για εμάς. Και έτσι όπως trie μας παίρνει μεγαλύτερη και μεγαλύτερο, έχουμε κάνει λιγότερη δουλειά κάθε φορά για να εισάγετε νέα πράγματα επειδή έχουμε ήδη έχτισε ένα μεγάλο μέρος της ενδιαμέσου καταστήματα κατά μήκος του τρόπου. Αν έχουμε μόνο ποτέ να εξετάσουμε 4 πράγματα, 4 είναι απλά μια σταθερά. Πραγματικά είναι το είδος της προσέγγισης σταθερή χρονική στιγμή της εισαγωγής και η συνεχής αναζήτηση του χρόνου. Ο συμβιβασμός, φυσικά, είναι ότι trie αυτό, όπως μπορείτε να πείτε ίσως, είναι τεράστια. Κάθε ένα από αυτούς τους κόμβους καταλαμβάνει πολύ χώρο. 

Αλλά αυτό είναι το δίλημμα. Αν θέλουμε πραγματικά γρήγορα εισαγωγής, πραγματικά γρήγορη διαγραφή, και πραγματικά γρήγορη αναζήτηση, θα πρέπει να έχουν πολλά δεδομένα που πετούν γύρω. Πρέπει να αναιρέσει ένα πολύ χώρο και η μνήμη για την εν λόγω δομή δεδομένων να υπάρχει. 

Και έτσι αυτό είναι το δίλημμα. Αλλά φαίνεται σαν να θα μπορούσε να βρει. Θα μπορούσαμε να διαπιστώσει ότι άγιο δισκοπότηρο των δομών δεδομένων με γρήγορη εισαγωγή, διαγραφή και αναζήτηση. Και ίσως αυτό θα είναι ένα κατάλληλη δομή δεδομένων που θα χρησιμοποιηθεί για οποιαδήποτε πληροφορία προσπαθούμε να κατάστημα. Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.