[Música tocando] Doug LLOYD: Entón, nós estamos avanzando máis preto e máis preto que Santo Graal de datos estruturas, que podemos inserir en, eliminar de, e mirar para arriba en tempo constante. Dereita. Isto é unha especie de meta. Queremos ser capaces de fazê- cousas moi, moi rapidamente. 

Ten que atopar aquí cando estamos a falar de intentos? Ben, imos dar un ollo. Entón, nós vimos varios diferentes estruturas de datos que xestione o mapeamento de chamados pares de valores clave, mapear algúns peza de datos a algún outro anaco de datos polo que sabemos onde encontrá- información na estrutura. 

Así, por matriz, por exemplo, a clave é o índice de elemento ou matriz 0 lugar ou matriz 1 e así por diante. E o valor é o de datos que hai nese local. Entón, o que son almacenadas na matriz 0? O que se garda na agrupación de 1 versus só 0 e 1, o que sería a tecla. 

Cunha táboa hash é especie do mesmo idea. Cunha táboa hash, temos ese hash función que xera código de hash. Polo tanto, a clave é o código de hash dos datos. E o valor, especialmente falamos de fío no vídeo en táboas de hash, é que lista ligada de datos que hashes para que hashcode. Dereita. E sobre outra visión este método, aínda que? Que tal un método no que o clave é a garantía de ser único, ao contrario dunha táboa hash, onde poderiamos acabar con dous anacos de datos tendo o mesmo código hash. E entón temos que xestione que por calquera enquisa ou máis fío de preferencia para corrixir este problema. 

Entón, agora podemos garantir que a nosa clave será única. E se o seu valor foi só algo tan sinxelo como o verdadeiro eo falso que nos di se ou non ese anaco de información existe na estrutura? Un valor booleano pode ser tan sinxelo como un pouco. Realista pode ser unha byte máis probable que un pouco. Pero iso é moito menor que almacenar quizais unha secuencia de 50 caracteres, por exemplo. 

Entón intentos, semellante ao de hash táboas, que combinan matrices e lista ligada, tenta combinar arrays, estruturas, e punteiros en conxunto para almacenar datos en unha forma interesante que é moi diferente do todo o que vimos ata agora. Agora usan os datos como un guión para navegar esta estrutura de datos. E se podemos seguir o guión, se pudermos seguir os datos de comezo ao fin, imos saber se eses datos existir no trie. 

E se nós non podemos seguir o mapa de significado para rematar en todo, os datos non poden existir. Unha vez máis, as teclas son aquí a garantía de ser único. E así a diferenza dunha táboa hash, nunca nos ten que xestionar colisións aquí. E non hai dúas pezas de datos teñen exactamente o mesmo guión a non ser que os datos son idénticos. 

Se nós inserimos John, a continuación, buscamos John. Iso é dúas pezas idénticas datos, non, nós estamos mirando a través. Pero por outra banda, calquera dous anacos de datos son garantía de guións exclusivos a través desta estrutura de datos. E nós imos dar un ollo a un visual deste en só un momento. 

Nós imos facer isto, intentando crear unha nova estrutura de datos, mapeando os seguintes pares de valores clave. Neste caso, non estamos indo a usar algo tan sinxelo como un booleano. Nós, en realidade, vai almacenar a cadea. E esa corda vai ser o nome dunha universidade. 

E a clave será o ano cando esta universidade foi fundada. Cada ano para universidades van ser catro díxitos. E por iso imos usar estes catro díxitos á navegar por esta estrutura de datos. E imos ver, unha vez máis, como facemos iso en só un segundo. 

Ao final do percorrido, imos ver o nome da universidade correspondente a esa chave, estas catro díxitos. A idea básica por tras dun trie é que temos unha ruta central. Entón, pense nisto como unha árbore. E esta é semellante en ortografía e no concepto dunha árbore. Xeralmente cando pensamos sobre árbores no mundo real, eles teñen unha raíz que está na chan e crecen cara arriba e eles teñen filiais e eles teñen follas. E, basicamente, a idea de un trie é exactamente o mesmo, agás que a raíz está ancorado nalgún lugar no ceo. E as follas están na parte inferior. 

Entón, é tipo de como se fai unha árbore e só virá-lo de cabeza para baixo. Pero aínda hai ramas. E os serían os nosos camiños, esas serán as nosas conexións desde a raíz ata as follas. Neste caso, os traxectos, estes ramos son rotulado con díxitos que nos din que camiño seguir desde onde estamos. 

Se vemos un 0, descendemos este sector, se vemos a 1, descendemos este sector, e así e así por diante. Ben, o que significa isto? Ben, iso significa que en cada punto de unión e cada nodo no medio e cada sector, hai 10 posibles lugares que podemos ir. Polo tanto, hai 10 punteiros de todos os lugares. 

E é neste punto que intentos pode obter unha pouco intimidante para alguén que é non ter unha chea de experiencia en ciencia da computación antes. Pero intentos son realmente moi impresionante. E se ten o oportunidade de traballar con eles e está disposto a cavar-in probar con eles, son realmente moi interesante estruturas de datos para traballar. Se queremos introducir un elemento no trie, todo o que cómpre facer é construír o camiño correcto a partir da raíz para a folla. Aquí está o que cada paso ao longo o xeito no que pode parecer. Imos definir unha nova datos estrutura para un novo nodo chamado trie. 

E dentro destes datos estrutura existen dúas pezas. Estamos indo para almacenar o nome dunha universidade. E nós estamos indo para almacenar unha matriz de punteiros para outros nós do mesmo tipo. Entón, de novo, este é este tipo do concepto de todas partes somos, o 10 posibles lugares onde podemos ir. Se vemos un 0, descendemos este sector. Se vemos a 1, neste sector, e así por diante e así por diante e así por diante. Se dicimos 9, descendemos este sector. Así, en cada punto de unión, podemos ir 10 lugares posibles. Así, cada nodo debe conter 10 punteiros para outros nós, aos 10 outros nós. 

E os datos que estamos almacenando é só o nome da universidade. Entón, imos construír un trie. Imos introducir unha parella de elementos no noso trie. Así, na parte superior, este é o noso nodo raíz. Isto probablemente vai ser algo está indo a globalmente declare. E está indo a manter globalmente un punteiro para este nodo sempre. 

Vai dicir, raíz é igual, e está vai malloc mesmo nodo trie. E nunca vai para tocar raíz de novo. Cada vez que quere comezar a navegar a través, establecer outro punteiro igual a raíz, como trav, que é o exemplo I usar en moitos dos meus vídeos aquí en pilas e colas e listas de enlaces e así por diante. 

Establecer outro punteiro trav chamado para paso. E usa para navegar trav a través da estrutura de datos. Entón, imos ver como iso pode parecer. Entón, agora, o que un nó parece? Ben, como os nosos datos declaración de estrutura indicada, temos unha cadea, que Neste caso está baleiro. Non hai nada aquí. 

E unha matriz de 10 punteiros. E agora temos só ten un nó nesta trie. Non hai máis nada nel. Polo tanto, todos os 10 de punteiros punto para null. Iso é o que o vermello indica. 

Imos introducir a secuencia de Harvard. Imos introducir a Universidade de Harvard para este trie, que foi fundada no ano 1636. Queremos usar a chave, 1636, de nos dicir onde estamos indo para almacenar Harvard no trie. Agora, como podemos facelo? 

Podería ser algo así. Comezamos na raíz. E nós temos estes 10 sitios onde podemos ir. A raíz é como calquera outro nodo do trie. Hai 10 sitios onde podemos ir dende aquí. 

Onde nós probablemente quere para ir a clave é 1636? Non hai realmente dúas opcións. Dereita. Podemos construír a clave dereita a esquerda e comece con 6. Ou poderíamos construír a clave esquerda a dereita e comezar con unha. 

É probabelmente máis intuitivo como un ser humano para entender imos Só tes que ir esquerda a dereita. E por iso, se quero introducir Harvard para este trie, Eu probablemente quere comezar iniciando na raíz, mirando para os meus 10 opcións na miña fronte, e dicindo: Eu quero ir para o camiño 1. Aceptar. 

Agora, un camiño é actualmente nulo. Entón, se eu queira continuar por ese camiño para introducir este elemento ao trie, Teño que malloc un novo nodo, ten un punto alí, e entón eu son bo para ir. 

Entón eu basicamente estou nunha punto onde eu estou de pé na raíz da árbore ou a trie e hai 10 filiais. Pero cada rama ten un porta diante del. Dereita. Porque non hai nada máis hai. Ningunha pasaxe segura. Isto significa que non hai nada abaixo calquera destes ramos. Se eu queira comezar a construír algo, quero eliminar a porta. Quero eliminar a porta diante do número 1. E quero que descenda. E quero construír outro lugar para ir. 

E iso é o que eu fixen aquí. Entón 1 xa non apunta a null. Eu xa dixen que é seguro para baixar aquí agora. Eu constrúe outro nodo. E cando chegar a ese nó, I ter outra decisión a tomar. Onde é que eu vou saír de aquí? 

Ben, eu xa baixou a 1. Entón agora eu probablemente vai querer ir para abaixo a 6. Dereita. De novo, eu teño 10 locais podo escoller. Entón, imos agora ir para abaixo o número 6. Entón eu limpar a porta diante do número 6. E eu ando alí abaixo. E eu construír outro nodo. E eu xa alcanzou outro punto de intersección. 

De novo, eu teño 10 opcións onde podo ir. Eu me mudei 1-6. Entón agora eu probablemente vai querer ir a 3. 3, non hai ningún lugar podo ir. Entón eu teño que limpar o camiño e eu construír un novo espazo. E, a continuación, a partir de 3, onde quere ir? Eu quero ir para abaixo 6. 

E, unha vez máis, eu tiven que limpar o camiño para facelo. Entón agora eu usei a miña clave para introducir crear nós e comezar a construír esta trie. Comece na raíz. Eu teño ido para abaixo 1636. E agora eu estou no fondo hai nese nó. E pode ser capaz de velo en pantalla. 

É destacada en amarelo. É onde eu son actualmente. Miña clave está feito. Eu xa esgotou todas as posicións na miña clave. Entón eu non podo ir máis lonxe. Entón, neste momento, todo o que eu realmente cómpre facer é dicir, Aceptar. É unha especie de como a procura abaixo, para o chan, se está imaxinando como este tipo de camiño con conexións diferentes. Clasificar de ollar para abaixo e tipo de pintura de pulverizado Harvard no chan. Ese é o nome deste. Sabe que o que é neste lugar. Se comezar na raíz e descendemos 1 e, a continuación, 6 e, a continuación, 3 e 6, a continuación, onde estamos? Ben, se miramos para abaixo e vemos Harvard, a continuación, sabemos que foi Harvard fundada en 1636 con base na forma estamos aplicando esa estrutura de datos. Así que foi esperanza simple. Nós imos facer dúas insercións. E espero que vai axudar a ver este feito dúas veces máis. 

Agora, imos introducir outra universidade. Imos introducir Yale para este trie. Yale foi fundada en 1701. Entón, imos comezar o administrador, como sempre facemos. E nós definir un punteiro de paso. Nós imos usar isto para percorrer. O primeiro que queremos facer é ir ao camiño 1. Ese é o primeiro díxito da nosa clave. Felizmente, non obstante, non o facemos ten que facer un traballo esta vez. A un camiño xa foi desmatada. Limpar-lo previamente, cando foi a inserción de Harvard en 1636. Entón, podo mover con seguridade down 1 e só ir alí. Se pode mover para abaixo a 1. 

Agora, porén, quero ir ao 7. Eu abriu o camiño ás 6. Sei que podo con seguridade continúe no camiño 6. Pero que avanzar no camiño 7. Entón o que eu teño que facer? Ben, así como antes, eu só teño para limpar a porta, saír do camiño, e construír un novo nodo do camiño 7. Así como este. 

Entón agora eu mudei 1 e, a continuación, 7. E agora aviso, eu son unha especie de sobre esta nova subbranch. Dereita. O resto a partir de 16 , Eu non me importa. Eu non estou facendo nada 16. Estou facendo 17 cousas. 

Polo tanto, agora de 17 en diante, eu teño que tipo de albiscar novos camiños aquí. O seguinte díxito miña clave é 0. Eu claramente non pode obter en calquera lugar. Acaba de construír ese nó. Entón eu sei que non hai camiños para adiante a partir de aquí. Entón eu teño que facer un eu mesmo. 

Entón eu malloc un novo nodo e ten 0 punto alí. E, a continuación, unha vez máis, eu malloc un novo nó e ten un punto alí. Unha vez máis, eu xa esgotou a miña chave de 1701. Entón eu ollo para abaixo e eu pintura spray Yale. Ese é o nome deste nó. 

E agora, se eu ter a ver se Yale é neste trie, eu comezo a raíz, Descendo 1701, e mirar para abaixo. E se eu vexo spray de Yale pintados no chan, a continuación, Sei Yale existe neste trie. Imos facer un máis. Imos introducir Dartmouth neste trie, que foi fundada en 1769. 

Comezar na raíz de novo. O meu primeiro díxito da miña clave é 1. Eu podo mover con seguridade por ese camiño. Que xa existe. O seguinte díxito da miña clave é 7. Eu podo mover con seguridade por ese camiño. Existe tamén. 

Meu próximo é 6. A partir de aquí, de onde eu son actualmente en amarelo alí naquel nó medio, 6 está pechada off. Se quero ir por ese camiño, Teño que construír iso só. Entón, eu vou malloc un novo nodo e ten 6 puntos alí. E entón, de novo, eu son abrindo novos camiños aquí. 

Entón eu malloc un novo nodo de xeito que a partir de este número camiño node-- 9-- e entón agora se eu viaxar de 1769, e eu ollo para abaixo. Non hai nada actualmente pulverizado pintado alí. Podo escribir Dartmouth. E eu teño inserida Dartmouth no trie. 

Entón, iso é inserindo cousas para o trie. Agora queremos buscar cousas. Como é que imos buscar cousas no trie? Ben, é practicamente a mesma idea. Agora é só usar os díxitos da clave a ver se é posible navegar a partir da raíz onde queremos ir no trie. 

Se se loita unha rúa sen saída en calquera punto, a continuación, sabemos que ese elemento non pode existir ou ben ese camiño sería xa foron apurada. Se facemos que todo o camiño para Ao final, todo o que necesitamos facer é mirar para abaixo e ver se iso o elemento que estamos buscando. Se é, o éxito. Se non é, falla. 

Entón, imos buscar Harvard neste trie. Comezamos na raíz. E, unha vez máis, imos crear un punteiro de paso para facer os nosos movementos para nós. A partir da raíz sabemos que o Primeiro, necesitamos ir é 1, podemos facelo? Si podemos. Se existe de forma segura. Podemos ir alí. 

Agora, o seguinte lugar que ten que ir é 6. Será que o camiño 6 existir dende aquí? Si, fai. Podemos ir ao camiño 6. E acabamos aquí. 

Podemos ir ao camiño 3 a partir de aquí? Ben, como se ve, si, que hai tamén. E podemos entrar no camiño de 6 a partir de aquí? Si podemos. 

Non temos bastante respondeu a cuestión aínda. Aínda hai unha paso, que é agora temos que mirar para abaixo e ver se isto é actually-- se nós estamos mirando para Harvard, é que o que atopamos tras esgotar a clave? No exemplo que estamos usando aquí, ano son sempre catro díxitos. Pero pode estar usando o exemplo onde está almacenando un dicionario de palabras. 

E así, en vez de ter 10 punteiros para o meu lugar, pode que 26. Un para cada letra do alfabeto. E hai algunhas palabras como bastón, que é un subconxunto do solar, por exemplo. E así mesmo se chegar ao final da clave e mira para abaixo, non pode ver o que está a procurar. 

Así, sempre ten que atravesar todo o camiño e logo se fose capaz éxito para percorrer todo o camiño, mirar para abaixo e facer unha confirmación final. Isto é o que eu estou buscando? Ben, eu ollar para abaixo despois do inicio na parte superior e indo 1636. Eu ollo para abaixo. Vexo Harvard. Entón, si, eu puiden. E se o que eu estou buscando non está no trie, con todo. E se eu estou buscando Princeton, que foi fundada en 1746. E así pasa a ser a miña chave de 1746 para navegar a través do trie. Ben, eu comezar na raíz. E o primeiro que quero para se pon en camiño 1. Podo facelo? Si, podo. 

Podo ir ao camiño 7 de alí? Si, eu podo. Iso existe tamén. Pero podo ir ao camiño 4 a partir de aquí? Isto é como preguntar a pregunta, pode Eu continuar por ese pequeno cadrado que teño resaltado en amarelo? Non hai nada alí. Dereita. 

Non hai ningunha forma de avanzar no camiño 4. Se Princeton foi neste trie, que 4 sería liberado para nós xa. E por iso neste momento chegamos a unha rúa sen saída. Non podemos ir máis lonxe. E así podemos dicir, en definitiva, non. Princeton non existe neste trie. 

Entón o que iso todo significa? Dereita. Hai moita cousa a ocorrer aquí. Hai punteiros en todo o lugar. E, como se pode ver xa desde o diagrama, hai unha gran cantidade de nós que son do tipo que voan arredor. Pero teña en conta cada vez que quería comprobar se algo foi o trie, nós só tivemos que facer 4 movementos. 

Cada vez que quería introducir algo no trie, temos que facer 4 movementos, posiblemente mallocing algunhas cousas ao longo do camiño. Pero, como vimos cando inserido Dartmouth no trie, por veces algún do camiño xa pode ser liberado para nós. E así como o noso se fai maior e trie maior, temos facer menos traballo cada vez para inserir cousas novas porque xa construíu unha morea de o intermediario ramas ao longo do camiño. Se sempre só ten que ollar para 4 cousas, 4 é só unha constante. Nós realmente estamos tipo de visión inserción de tempo constante e investigación de tempo constante. A desvantaxe, por suposto, que sendo este trie, como pode ser dicir, é enorme. Cada un destes nós ten unha morea de espazo. 

Pero ese é o tradeoff. Se queremos realmente rápido inserción, eliminación realmente rápido, e lookup moi rápido, temos que ten unha morea de datos que voan arredor. Debemos deixar de lado unha morea de espazo e memoria para esa estrutura de datos a existir. 

E entón esa é a cambio. Pero parece que pode telo atopado. Poderiamos descubriron que Santo Graal de estruturas de datos con inserción rápida, exclusión e de investigación. E quizais este será un estrutura de datos apropiada para usar por calquera información estamos intentando tenda. Eu son Doug Lloyd, este é CS50.