KEVIN SCHMID: A volte, quando si costruisce una programma, si potrebbe desiderare di utilizzare un struttura di dati nota come un dizionario. A mappe Dizionario chiavi, che sono di solito stringhe, ai valori, int, caratteri, un puntatore ad un oggetto, quello che vogliamo. E 'proprio come dizionari ordinarie che sugli parole attraverso definizioni. 

Dizionari ci forniscono l' capacità di immagazzinare informazioni associato a qualcosa e guardare più tardi. Quindi, come possiamo realmente attuare una dizionario, per esempio, il codice C che possiamo utilizzare in uno dei nostri programmi? Ebbene, ci sono molti modi in cui potremmo implementare un dizionario. 

Per uno, potremmo utilizzare un array che dinamicamente ridimensionare o potremmo usare un lista collegata, tabella hash o un albero binario. Ma qualsiasi cosa scegliamo, dobbiamo essere consapevoli della efficienza e prestazioni dell'implementazione. Dovremmo pensare l'algoritmo usato di inserire e ricercare elementi in la nostra struttura dati. 

Per ora, supponiamo che ci voler usare le stringhe come chiavi. Parliamo di una possibilità, una struttura di dati chiamata trie. Quindi, ecco una rappresentazione visiva di un trie. 

Come l'immagine suggerisce, un trie è una struttura di dati ad albero con nodi collegati tra loro. Vediamo che c'è chiaramente una radice nodo con alcuni link che estende alla altri nodi. Ma cosa significa ogni nodo consiste? Se assumiamo che stiamo memorizzazione delle chiavi con soli caratteri alfabetici e non ci preoccupiamo di capitalizzazione, ecco una definizione di un nodo che sarà sufficiente. 

Un oggetto il cui tipo è struct nodo ha due parti chiamata dati e bambini. Abbiamo lasciato la parte di dati come un commento per essere sostituito da un componente dichiarazione quando il nodo è struct incorporata in un programma C. La parte di dati di un nodo può essere un Valore booleano per indicare se non il nodo rappresenta il completamento di una chiave di dizionario o potrebbe essere un stringa che rappresenta la definizione di una parola nel dizionario. 

Useremo una faccina sorridente per indicare quando è presente in un nodo di dati. Ci sono 26 elementi nella nostra matrice bambini, un indice per carattere alfabetico. Vedremo il significato di questo presto. 

Prendiamo uno sguardo più da vicino del nodo radice nel nostro schema, che non ha dati ad esso associati, come indicato dal assenza della faccina sorridente nel porzione di dati. Le frecce che si estendono dalle parti di la matrice bambini rappresentano non-node puntatori ad altri nodi. Ad esempio, la freccia estende dal il secondo elemento di bambini rappresenta la lettera B in una chiave di dizionario. E nello schema più grande etichettiamo con una B. 

Si noti che nello schema più grande, quando abbiamo disegnare un puntatore ad un altro nodo, esso Non importa se la punta della freccia risponda a tale nodo. Il nostro trie Dizionario campione contiene due parole, che e zoom. Camminiamo attraverso un esempio di cerca i dati per una chiave. 

Supponiamo di voler cercare l' valore corrispondente per il bagno chiave. Inizieremo il nostro sguardo su al nodo radice. Poi ci prenderemo la prima lettera del nostro chiave, B, e trovare il corrispondente posto nella nostra matrice bambini. Si noti che ci sono esattamente 26 punti nella matrice, una per ogni lettera l'alfabeto. E avremo i punti rappresentano il lettere dell'alfabeto in ordine. 

Vedremo il secondo indice, allora, indice uno, per B. In generale, se avere qualche alfabetico carattere C che potrebbe determinare il punto corrispondente nella matrice dei minori che usano un calcolo come questo. Abbiamo potuto utilizzare per bambini più grandi array se abbiamo voluto offrire sguardo di tasti con una vasta gamma di personaggi, ad esempio l'intera Set di caratteri ASCII. 

In questo caso, il puntatore nei nostri bambini array indice non è nullo. Quindi noi continueremo cercando la vasca chiave. Se mai incontrato un puntatore nullo nel punto corretto nei bambini matrice mentre abbiamo attraversato i nodi, allora dovremo dire che abbiamo non riusciva a trovare nulla per quella chiave. 

Ora, prendiamo la seconda lettera di la nostra chiave, A, e continuare a seguire puntatori in questo modo fino a noi raggiungere la fine della nostra chiave. Se arriviamo alla fine della chiave senza colpire gli vicoli ciechi, puntatori nulli, come è il caso qui, allora abbiamo solo deve controllare una cosa. È questo tasto realtà nel dizionario? 

Se è così, dovremmo trovare un valore, un bene smiley Icona volto nel nostro diagramma in cui la parola finisce. Se c'è qualcos'altro memorizzato con i dati, quindi siamo in grado di restituirlo. Ad esempio, lo zoo chiave non è nella dizionario, anche se potremmo avere raggiunto la fine di questa chiave senza mai colpire un puntatore nullo, mentre noi scorrere l'trie. 

Se abbiamo provato a cercare il bagno tasto, il secondo per indice di matrice di ultimo nodo, corrispondente alla lettera H, sarebbe hanno tenuto un puntatore nullo. Quindi il bagno non è presente nel dizionario. E così un trie è unico in quanto le chiavi vengono mai esplicitamente memorizzati in la struttura di dati. Quindi, come possiamo inseriamo qualcosa in un trie? 

Inseriamo la chiave zoo nel nostro trie. Ricordate che una faccina sorridente in un nodo potrebbe corrispondere in codice per un semplice Valore booleano per indicare che zoo è nel dizionario o potrebbe corrispondono a maggiori informazioni che abbiamo desidera associare con lo zoo chiave, come la definizione del parola o qualcos'altro. In qualche modo, il processo per inserire qualcosa in un trie è simile a guardando qualcosa in un trie. 

Inizieremo con il nodo principale di nuovo, seguenti indicazioni corrispondenti a le lettere della nostra chiave. Per fortuna, siamo riusciti a seguire i puntatori tutta la strada fino a quando abbiamo raggiunto la fine della chiave. Poiché zoo è un prefisso della parola zoom, che è membro del dizionario, non abbiamo bisogno di destinare eventuali nuovi nodi. 

Possiamo modificare il nodo per indicare che il percorso di protagonisti a rappresenta una chiave nel nostro dizionario. Ora, proviamo inserendo il BAGNO chiave nel trie. Inizieremo al nodo radice e seguire di nuovo i puntatori. Ma in questa situazione, ci ha colpito un morto terminare prima che siamo in grado di ottenere il fine della chiave. Ora, abbiamo bisogno di allocare una nuova nodi dovranno allocare una nuova nodo per ogni restante lettera della nostra chiave. 

In questo caso, dobbiamo solo attribuire un nuovo nodo. Poi abbiamo bisogno di rendere l'indice H riferimento a questo nuovo nodo. Ancora una volta, possiamo modificare il nodo indicare che il percorso di caratteri conduce ad esso rappresenta un chiave nel nostro dizionario. Facciamo ragionare sulla asintotico complessità delle nostre procedure per tali due operazioni. 

Notiamo che in entrambi i casi il numero di passaggi nostro algoritmo ha preso è stato proporzionale al numero di lettere della parola chiave. Che è di destra. Se si vuole cercare una parola in un trie basta scorrere le lettere una ad una finché non si raggiungere la fine della parola o colpito un vicolo cieco nel trie. 

E quando si desidera inserire una chiave coppia di valori in un trie usando l' procedura abbiamo discusso, il caso peggiore vi farà assegnazione di un nuovo nodo per ogni lettera. E noi assumiamo che l'assegnazione è un'operazione a tempo costante. Quindi, se si assume che la lunghezza della chiave è delimitata da una costante fissa, sia inserimento e guardare in alto sono costanti operazioni di tempo per un trie. 

Se non facciamo questo presupposto che la lunghezza della chiave è delimitato da una fissa costante, quindi dell'inserimento e guardare in alto, nel caso peggiore, sono lineari nella lunghezza della chiave. Si noti che il numero di elementi memorizzati nel trie non pregiudica il look up o il tempo di inserimento. È influenzato solo dal lunghezza della chiave. 

Per contro, l'aggiunta di voci, per dire, una tabella hash tende a rendere futuro sguardo lento. Anche se questo può sembrare attraente in un primo momento, dovremmo tenere a mente che un favorevole complessità asintotica non significa che in pratica i dati struttura è necessariamente irreprensibile. Dobbiamo anche considerare che per memorizzare un parola in un trie abbiamo bisogno, nella peggiore caso, un numero di nodi proporzionale alla lunghezza della parola stessa. 

Tenta tendono ad usare un sacco di spazio. Questo è in contrasto con una tabella di hash, dove abbiamo solo bisogno di un nuovo nodo memorizzare alcune coppia chiave-valore. Ora, sempre in teoria, ampio spazio consumo non sembra un grande affrontare, soprattutto considerando che la moderna computer hanno gigabyte e gigabyte di memoria. Ma si scopre che abbiamo ancora preoccuparsi di utilizzo della memoria e organizzazione per il bene della prestazioni, dato che i computer moderni disporre di meccanismi in atto sotto la Cappa per accelerare l'accesso alla memoria. 

Ma questi meccanismi funzionano meglio quando accessi alla memoria sono realizzati in versione ridotta regioni o zone. E i nodi di un trie potrebbero risiedere ovunque in quel mucchio. Ma questi sono compromessi che dobbiamo considerare. 

Ricordate che, quando si sceglie un dato struttura per un certo compito, abbiamo dovrebbe pensare a quali tipi di operazioni la struttura di dati deve supporto e qual è il rendimento di ciascuno di tali operazioni è importante per noi. Queste operazioni possono anche estendersi oltre la semplice aspetto di base e di inserimento. Supponiamo di voler realizzare una sorta di funzionalità di completamento automatico, molto come motore di ricerca di Google fa. Cioè, restituire tutte le chiavi e potenzialmente valori che avere un determinato prefisso. 

Un trie è unicamente utile per questa operazione. E 'semplice da scorrere trie per ogni carattere di il prefisso. Proprio come un guardare in alto funzionamento, abbiamo potuto seguire i puntatori carattere per carattere. Poi, quando si arriva alla fine del prefisso, potremmo scorrere l' porzione rimanente della struttura dati poiché uno dei tasti di là questo punto hanno il prefisso. 

E 'anche facile da ottenere questo annuncio in ordine alfabetico poiché l' elementi della matrice bambini sono elencate in ordine alfabetico. Così si spera che prenderemo in considerazione dando prova una prova. Sono Kevin Schmid, e questo è CS50. 

Ah, questo è l'inizio del declino. Mi dispiace. Scusi. Scusi. Scusi. 

Sciopero di quattro. Sono fuori. Scusi. Scusi. Scusi. Ci scusiamo per fare la persona che deve modificare questa impazzire. 

Scusi. Scusi. Scusi. Scusi. 

SPEAKER 1: Ben fatto. Che è stato davvero ben fatto.