[RIPRODUZIONE DI BRANI MUSICALI] DOUG LLOYD: Così abbiamo avvicinandosi sempre più e più vicino che Santo Graal dei dati strutture, che possiamo inserire in, eliminare dalla, e guardare in alto in tempo costante. Destra. Questa è una sorta di meta. Vogliamo essere in grado di fare cose molto, molto rapidamente. 

Abbiamo abbiamo trovato qui quando stiamo parlando di tentativi? Bene, diamo un'occhiata. Così abbiamo visto diversi diverse strutture dati che gestiscono la mappatura dei cosiddetti coppie chiave-valore, mappatura qualche pezzo di dati a qualche altro pezzo di dati così sappiamo dove trovare informazioni nella struttura. 

Quindi per il campo, per esempio, la chiave è l'indice di elemento o array posizione 0 o matrice 1 e così via. E il valore è il dato che esiste in quella posizione. Quindi, ciò che è memorizzato in ordine di 0? Che cosa viene memorizzato in 1 campo contro solo 0 e 1, che sarebbe i tasti. 

Con una tabella di hash è specie della stessa idea. Con una tabella hash, abbiamo questo hash funzione che genera codici hash. Quindi la chiave è il codice hash dei dati. E il valore, in particolare abbiamo parlato di concatenamento nel video su tabelle hash, è quella lista collegata di dati che hash di tale codice hash. Destra. Che dire di un altro approccio questo metodo, però? Che dire un metodo in cui la chiave è garantito per essere unico, a differenza di una tabella hash, dove abbiamo potuto finire con due pezzi di dati avendo lo stesso codice hash. E allora abbiamo a che fare con che da una sonda o più preferibilmente concatenamento per risolvere questo problema. 

Così ora possiamo garantire che la nostra chiave sarà unica. E se il nostro valore era solo qualcosa come facile come vero e falso che ci dice se o meno quel pezzo di informazioni esiste nella struttura? Booleano potrebbe essere semplice come un po '. Realisticamente è probabilmente una byte più probabile che un po '. Ma è molto più piccolo di memorizzare forse una stringa di 50 caratteri, per esempio. 

Così cerca, simile alle tabelle, che combinano array e lista collegata, cerca combinano gli array, strutture, e puntatori insieme a memorizzare i dati in un modo interessante che è molto diverso da tutto ciò che abbiamo visto finora. Ora usiamo i dati come una tabella di marcia navigare questa struttura dati. E se siamo in grado di seguire la tabella di marcia, se possiamo seguire i dati dall'inizio alla fine, ce la faremo sapere se tali dati esistere nel trie. 

E se non possiamo seguire la mappa da un senso alla fine del tutto, non possono esistere i dati. Anche in questo caso, i tasti sono qui garantito per essere unico. E così a differenza di una tabella hash, ce la faremo mai avere a che fare con le collisioni qui. E non ci sono due pezzi di dati hanno esattamente la stessa tabella di marcia a meno che i dati siano identici. 

Se inseriamo John, poi cerchiamo John. Ecco due pezzi identici di dati, a destra, stiamo guardando attraverso. Ma per il resto, qualsiasi due dati sono la garanzia di avere tabelle di marcia unici attraverso questa struttura dati. E stiamo andando a dare un'occhiata a una visuale di questo in un momento. 

Lo faremo cercando di creare una nuova struttura di dati, mappare le seguenti coppie di valori chiave. In questo caso, non stiamo andando da usare qualcosa di semplice come un valore booleano. Noi in realtà sarà memorizzare la stringa. E quella corda sta per essere il nome di una università. 

E la chiave sarà l'anno quando fu fondata quella università. Tutti gli anni per le università stanno per essere quattro cifre. E così useremo quelle quattro cifre a navigare attraverso questa struttura dati. E vedremo, ancora una volta, come lo facciamo in appena un secondo. 

Alla fine del percorso, vedremo il nome dell'università che corrisponde per tale chiave quei quattro cifre. L'idea alla base di un trie è che abbiamo un percorso centrale. Quindi pensare come un albero. E questo è simile a ortografia e nel concetto di un albero. Generalmente quando pensiamo alberi nel mondo reale, hanno una radice che è nella terra e crescono verso l'alto e che hanno filiali e hanno foglie. E fondamentalmente l'idea di un trie è esattamente lo stesso, salvo che la radice è ancorata da qualche parte nel cielo. E le foglie sono in fondo. 

Quindi è un po 'come fare un albero e solo lanciando a testa in giù. Ma ci sono ancora i rami. E quelli sarebbero i nostri percorsi, quelli saranno i nostri collegamenti dalla radice alle foglie. In questo caso, quelli sentieri, quei rami sono etichettati con le cifre che ci dicono da che parte andare da dove siamo. 

Se vediamo un 0, scendiamo questo ramo, se vediamo un 1, scendiamo questo ramo, e così e così via. Ebbene, che cosa significa? Bene, ciò significa che in ogni punto di giunzione e ogni nodo della medio e ogni ramo, ci sono 10 possibili luoghi che possiamo andare. Quindi ci sono 10 puntatori da ogni posizione. 

Ed è qui che tentativi possono ottenere un po 'intimidatorio per qualcuno chi è non ha un sacco di esperienza in informatica prima. Ma tentativi sono davvero abbastanza impressionante. E se avete la possibilità di lavorare con loro e siete disposti a scavare-in e sperimentare con loro, sono davvero molto interessante strutture di dati per lavorare con. Se vogliamo inserire un elemento nel trie, tutto quello che dobbiamo fare è costruire il percorso corretto dalla radice alla foglia. Ecco cosa ogni passo lungo il modo in cui potrebbe essere simile. Stiamo per definire una nuova dati struttura per un nuovo nodo chiamato trie. 

E all'interno di tali dati struttura ci sono due pezzi. Stiamo andando a memorizzare il il nome di una università. E stiamo andando a memorizzare un array di puntatori ad altri nodi dello stesso tipo. Quindi, di nuovo, questo è quel genere di concetto di tutto il mondo siamo, alle 10 possibili luoghi possiamo andare. Se vediamo un 0, scendiamo questo ramo. Se vediamo un 1, questo ramo, e così via e così via e così via. Se diciamo 9, scendiamo questo ramo. Così, in ogni punto di giunzione, possiamo andare 10 posti possibili. Così ogni nodo deve contenere 10 puntatori ad altri nodi, a 10 altri nodi. 

E i dati che stiamo memorizzazione è solo il nome dell'università. Quindi cerchiamo di costruire un trie. Inseriamo un paio di elementi in nostro trie. Così in cima, questo è il nostro nodo principale. Questo è destinata probabilmente ad essere qualcosa si sta andando a livello globale dichiarare. E si sta andando a mantenere il livello globale un puntatore a questo nodo sempre. 

Stai andando a dire, radice è uguale, e tu sei andando a malloc te stesso nodo trie. E si è mai andare a toccare di nuovo radice. Ogni volta che si desidera iniziare la navigazione attraverso, si imposta un altro puntatore pari a radice, come trav, che è l'esempio I utilizzare in molti dei miei video qui su pile e code e liste di link e così via. 

È possibile impostare un altro puntatore chiamato trav per l'attraversamento. E si utilizza per navigare trav attraverso la struttura dei dati. Quindi cerchiamo di vedere come questo potrebbe apparire. Così adesso, cosa fa un nodo assomiglia? Beh, proprio come i nostri dati dichiarazione di struttura indicata, abbiamo una stringa, che in questo caso è vuota. Non c'è niente qui. 

E un array di 10 puntatori. E proprio ora, abbiamo solo avere 1 nodo in questo trie. Non c'è niente altro in esso. Così tutti e 10 di quelli puntatori point a NULL. Questo è ciò che il rosso indica. 

Cerchiamo di inserire la stringa di Harvard. Inseriamo l'Università di Harvard in questo trie, che è stata fondata nell'anno 1636. Vogliamo usare la chiave, 1636, di dirci dove siamo andando a memorizzare Harvard nel trie. Ora, come potremmo farlo? 

Potrebbe sembrare qualcosa di simile. Partiamo alla radice. E abbiamo questi 10 posti si può andare. La radice è proprio come qualsiasi altro nodo del trie. Ci sono 10 posti si può andare da qui. 

Dove possiamo probabilmente vogliamo andare se la chiave è 1636? Non c'è davvero due opzioni. Destra. Siamo in grado di costruire la chiave da da destra a sinistra e iniziare con 6. Oppure potremmo costruire la chiave da da sinistra a destra e iniziare con 1. 

E 'probabilmente più intuitivo come un essere umano per capire che ti Basta andare da sinistra a destra. E così, se voglio inserire Harvard in questo trie, Probabilmente Voglio iniziare partendo alla radice, guardando i miei 10 opzioni di fronte a me, e dicendo Voglio andare giù per il sentiero 1. OK. 

Ora, 1 percorso è attualmente nullo. Quindi, se voglio continuare su questa strada inserire questo elemento nel trie, Devo malloc un nuovo nodo, avere 1 punto c'è, e poi io sono a posto. 

Quindi io fondamentalmente sono a un punto dove mi trovo alla radice dell'albero o trie e ci sono 10 filiali. Ma ogni ramo ha un cancello di fronte ad esso. Destra. Perché non c'è niente altro c'è. Nessun passaggio sicuro. Questo significa che non c'è niente giù uno di questi rami. Se voglio iniziare a costruire qualcosa, voglio rimuovere il cancello. Voglio rimuovere il cancello davanti al numero 1. E voglio camminare per questo. E voglio costruire un altro posto per me andare. 

E questo è quello che ho fatto qui. Quindi 1 non è più punti a null. Ho detto che è sicuro di andare giù qui ora. Ho costruito un altro nodo. E quando arrivo a quel nodo, io un'altra decisione da prendere. Dove sto andando andare da qui? 

Beh, ho già andato giù per la 1. Così ora probabilmente voglio andare in fondo alla 6. Destra. Ancora una volta, ho 10 sedi che posso scegliere. Quindi cerchiamo di ora scendiamo numero 6. Così ho chiaro il cancello davanti al numero 6. E io cammino laggiù. E io costruisco un altro nodo. E ho raggiunto un altro punto di giunzione. 

Ancora una volta, ho 10 scelte per dove posso andare. Ho spostato 1-6. Così ora probabilmente voglio andare a 3. 3, non c'è niente che posso andare. Quindi devo spianare la strada e costruire io un nuovo spazio. E poi da 3, dove voglio andare? Voglio andare giù 6. 

E, ancora una volta, ho dovuto spianare la strada per farlo. Così ora ho usato la mia chiave per inserire creare nodi e iniziano a costruire questo trie. Ho iniziato alla radice. Sono andato giù 1636. E ora sono in fondo là su tale nodo. E si potrebbe essere in grado di vedere sul vostro schermo. 

E 'evidenziato in giallo. Ecco dove attualmente sono. La mia chiave è fatto. Ho esaurito tutte le posizioni in mia chiave. Così non posso andare oltre. Quindi, a questo punto, tutto quello ha realmente bisogno di fare è dire, OK. È un po 'come guardare giù a terra, se stai immaginando te stesso come questo tipo di percorso con diverse connessioni. Sorta di guardare verso il basso e una sorta di spruzzare la pittura di Harvard a terra. Questo è il nome di questo. Sappiate che è ciò che è in questa posizione. Se partiamo alla radice e scendiamo 1 e poi 6 e poi 3 e poi 6, dove siamo? Beh, se si guarda in giù e vediamo Harvard, poi sappiamo che Harvard era fondata nel 1636 in base al modo stiamo implementare questa struttura dati. Così che era spera semplice. Stiamo per fare altri due inserimenti. E spero che vi aiuterà a vedi questo fatto altre due volte. 

Ora, proviamo ad inserire un'altra università. Inseriamo Yale in questo trie. Yale è stata fondata nel 1701. Quindi inizieremo a radice, come facciamo sempre. E abbiamo fissato un puntatore attraversamento. Stiamo andando a usarlo per muoversi attraverso. La prima cosa che vogliamo fare è andare giù per il sentiero 1. Questa è la prima cifra della nostra chiave. Fortunatamente, però, non lo facciamo hanno a che fare qualsiasi lavoro questa volta. Il percorso 1 è già stato eliminato. Ho rimosso in precedenza quando ho è stato l'inserimento di Harvard a 1.636. Così posso muoversi in sicurezza giù 1 e basta andare lì. Se può muoversi lungo la 1. 

Ora, però, voglio andare a 7. Ho aperto la strada alle 6. So che posso tranquillamente procedete lungo il sentiero 6. Ma ho bisogno di proseguire sul sentiero 7. Allora, cosa devo fare? Beh, proprio come prima, ho solo bisogno per cancellare la porta, uscire di strada, e costruire un nuovo nodo dal percorso 7. Proprio come questo. 

Così ora ho spostato 1 e poi 7. E ora notare, Sono una specie di questa nuova subbranch. Destra. Tutto il resto da 16 su, non mi preoccupo. Non sto facendo nulla 16. Sto facendo 17 roba. 

Così ora da 17 in poi, devo sorta di Blaze nuovi sentieri qui. La cifra successiva la mia chiave è 0. Io chiaramente non può arrivare ovunque. Ho appena costruito questo nodo. Quindi so non c'è percorsi in avanti da qui. Quindi devo fare uno io. 

Così ho malloc un nuovo nodo e hanno 0 punti lì. E poi ancora una volta, ho una malloc nuovo nodo e avere un punto lì. Ancora una volta, ho esaurito la mia chiave, 1701. Così guardo giù e vernice spray di Yale. Questo è il nome di questo nodo. 

E così ora se mai bisogno di vedere se Yale è in questo trie, comincio alla radice, Scendo 1701, e guardo giù. E se vedo Yale spruzzo dipinta sul terreno, poi So Yale esiste in questo trie. Facciamone un altro. Inseriamo Dartmouth in questo trie, che è stata fondata nel 1769. 

Inizia alla radice di nuovo. La mia prima cifra della mia chiave è 1. Posso muovermi tranquillamente su questa strada. Che esiste già. La cifra successiva della mia chiave è 7. Posso muovermi tranquillamente su questa strada. Esiste pure. 

Il mio prossimo è 6. Da qui, da dove attualmente sono in giallo lì in quel nodo centrale, 6 è attualmente bloccato al largo. Se voglio andare su questa strada, Devo costruire da solo. Quindi io malloc un nuovo nodo e hanno 6 punti lì. E poi, di nuovo, io sono nuove strade qui. 

Così ho malloc un nuovo nodo in modo che dal che il sentiero node-- 9-- e quindi ora se sono in viaggio 1769, e guardo giù. Non c'è niente al momento spruzzo lì verniciato. Posso scrivere Dartmouth. E ho inserito Dartmouth nel trie. 

Ecco, questo è l'inserimento di le cose nel trie. Ora vogliamo cercare le cose. Come si cerca per le cose nel trie? Beh, è ​​praticamente la stessa idea. Ora usiamo le cifre della chiave per vedere se siamo in grado di passare dalla radice di dove vogliamo andare nel trie. 

Se abbiamo raggiunto un vicolo cieco in qualsiasi momento, quindi sappiamo che questo elemento non può esiste oppure che il percorso sarebbe sono già stati cancellati. Se facciamo tutto il modo per Alla fine, tutto quello che dobbiamo fare è guardare in basso e vedere se questo è l'elemento che stiamo cercando. Se lo è, il successo. Se non lo è, fallire. 

Quindi cerchiamo di ricerca per Harvard questo trie. Partiamo alla radice. E, ancora una volta, stiamo andando a creare un puntatore attraversamento a fare le nostre mosse per noi. Dalla radice sappiamo che la primo luogo abbiamo bisogno di andare è 1, possiamo farlo? Si NOI possiamo. Se esiste in modo sicuro. Possiamo andare lì. 

Ora, il prossimo luogo abbiamo bisogno di andare è 6. Fa il percorso 6 esiste da qui? Sì, lo fa. Possiamo andare giù per il sentiero 6. E finiamo qui. 

Possiamo andare lungo il percorso da qui a 3? Beh, a quanto pare, sì, esiste anche. E possiamo salire sul sentiero 6 da qui? Si NOI possiamo. 

Non abbiamo ancora risposto ma la domanda. C'è ancora un altro passo, che è ora abbiamo bisogno di guardare verso il basso e vedere se questo è actually-- se stiamo cercando di Harvard, è che ciò che troviamo dopo esauriamo la chiave? Nell'esempio che stiamo usando qui, gli anni sono sempre quattro cifre. Ma si potrebbero utilizzare l'esempio in cui si memorizza un dizionario di parole. 

E così invece di avere 10 puntatori Per la mia città, si potrebbe avere 26. Uno per ogni lettera dell'alfabeto. E ci sono alcune parole come pipistrello, che è un sottoinsieme di lotto, per esempio. E quindi, anche se si arriva al fine della chiave e si guarda verso il basso, si potrebbe non vedere quello che che stai cercando. 

In modo da avere sempre a percorrere l'intero percorso e poi se tu fossi in grado con successo attraversare l'intero percorso, guardare in basso e fare una conferma definitiva. E 'questo che sto cercando? Beh, guardo giù dopo l'avvio in alto e in corso 1636. Guardo giù. Vedo Harvard. Quindi, sì, ci sono riuscito. E se quello che sto cercando non è nel trie, però. Che cosa succede se sto cercando di Princeton, che è stata fondata nel 1746. E così 1746 diventa la mia chiave per navigare attraverso il trie. Beh, comincio alla radice. E il primo posto che voglio a va lungo il sentiero 1. Posso farlo? Sì io posso. 

Posso andare giù per il sentiero 7 da lì? Si Io posso. Che esiste anche. Ma posso andare giù per il sentiero 4 da qui? Ecco come fare la domanda, può Procedo verso il basso che piazzetta che ho evidenziato in giallo? Non c'è niente lì. Destra. 

Non c'è modo in avanti lungo il sentiero 4. Se Princeton era in questo trie, che il 4 sarebbe stato eliminato per noi già. E quindi a questo punto abbiamo raggiunto un vicolo cieco. Non possiamo andare oltre. E così si può dire, in definitiva, n. Princeton non esiste in questo trie. 

Che cosa significa tutto questo? Destra. Ci sono un sacco di cose qui. C'è puntatori in tutto il luogo. E, come si può vedere solo dal diagramma, ci sono un sacco di nodi che sono specie di volano intorno. Ma notare ogni volta che volevamo verificare se c'era qualcosa nel trie, abbiamo solo dovuto fare 4 mosse. 

Ogni volta che volevamo inserire qualcosa nel trie, dobbiamo fare 4 mosse, forse mallocing alcune cose lungo la strada. Ma, come abbiamo visto quando abbiamo inserito Dartmouth nel trie, volte alcuni di percorso potrebbe già essere eliminato per noi. E così come la nostra trie diventa più grande e più grande, dobbiamo fare meno lavoro ogni volta inserire nuove cose perché abbiamo già costruito un sacco dell'intermedio rami lungo la strada. Se abbiamo sempre e solo guardare a 4 cose, 4 è solo una costante. Abbiamo davvero stiamo avvicinando tipo di inserimento costante di tempo e costante di tempo di ricerca. Il compromesso, naturalmente, è che questo trie, come si può probabilmente dire, è enorme. Ognuno di questi nodi prende un sacco di spazio. 

Ma questo è il compromesso. Se vogliamo davvero veloce inserimento, cancellazione davvero veloce, e di ricerca molto veloce, dobbiamo hanno un sacco di dati che volano intorno. Dobbiamo mettere da parte un sacco di spazio e memoria per quella struttura di dati esistere. 

E così che è il compromesso. Ma sembra che potrebbe aver trovato. Avremmo potuto scoperto che Santo Graal di strutture di dati con l'inserimento rapido, la cancellazione, e ricerca. E forse questo sarà un adeguata struttura di dati da utilizzare per qualsiasi informazione stiamo cercando di negozio. Sono Doug Lloyd, questo è CS50.