[Música tocando] DOUG LLOYD: Então, nós estamos avançando mais perto e mais perto que santo graal de dados estruturas, que podemos inserir em, excluir de, e olhar para cima em tempo constante. Certo. Isso é uma espécie de meta. Nós queremos ser capazes de fazê- coisas muito, muito rapidamente. 

Tem que encontramos aqui quando estamos falando de tentativas? Bem, vamos dar uma olhada. Então, nós temos visto vários diferentes estruturas de dados que lidar com o mapeamento de chamados pares de valores-chave, mapear alguns pedaço de dados a algum outro pedaço de dados por isso sabemos onde encontrá- informações na estrutura. 

Assim, por matriz, por exemplo, a chave é o índice de elemento ou matriz 0 local ou matriz 1 e assim por diante. E o valor é o de dados que existe naquele local. Então, o que são armazenadas na matriz 0? O que é armazenada no agrupamento de 1 versus apenas 0 e 1, o que seria as teclas. 

Com uma tabela hash é espécie da mesma idéia. Com uma tabela hash, temos esse hash função que gera códigos de hash. Portanto, a chave é o código de hash dos dados. E o valor, particularmente nós falamos sobre encadeamento no vídeo em tabelas de hash, é que lista ligada de dados que hashes para que hashcode. Certo. E sobre outra abordagem este método, embora? Que tal um método em que o chave é a garantia de ser único, ao contrário de uma tabela hash, onde poderíamos acabar com dois pedaços de dados tendo o mesmo código hash. E então nós temos de lidar com que por qualquer sondagem ou mais encadeamento de preferência para corrigir esse problema. 

Então, agora nós podemos garantir que a nossa chave será única. E se o nosso valor foi apenas algo tão fácil como o verdadeiro eo falso que nos diz se ou não esse pedaço de informação existe na estrutura? Um valor booleano pode ser tão simples como um pouco. Realisticamente é provavelmente uma byte mais provável do que um pouco. Mas isso é muito menor do que armazenar talvez uma seqüência de 50 caracteres, por exemplo. 

Então tentativas, semelhante ao de hash tabelas, que combinam matrizes e lista ligada, tenta combinar arrays, estruturas, e ponteiros em conjunto para armazenar dados em uma forma interessante que é muito diferente do tudo que vimos até agora. Agora usamos os dados como um roteiro para navegar esta estrutura de dados. E se podemos seguir o roteiro, se pudermos seguir os dados a partir de começo ao fim, vamos saber se esses dados existir no trie. 

E se nós não podemos seguir o mapa de significado para terminar em tudo, os dados não podem existir. Mais uma vez, as teclas são aqui a garantia de ser único. E assim ao contrário de uma tabela hash, nós nunca nos tem que lidar com colisões aqui. E não há duas peças de dados têm exatamente o mesmo roteiro a menos que os dados são idênticos. 

Se nós inserimos John, em seguida, buscamos John. Isso é duas peças idênticas de dados, certo, nós estamos olhando através. Mas por outro lado, qualquer dois pedaços de dados são garantia de ter roteiros exclusivos através desta estrutura de dados. E nós vamos dar uma olhada em um visual deste em apenas um momento. 

Nós vamos fazer isso, tentando criar uma nova estrutura de dados, mapeando os seguintes pares de valores-chave. Neste caso, nós não estamos indo para usar algo tão simples como um booleano. Nós, na verdade, vai armazenar a cadeia. E essa corda vai ser o nome de uma universidade. 

E a chave vai ser o ano quando essa universidade foi fundada. Todos os anos para universidades vão ser quatro dígitos. E por isso vamos usar esses quatro dígitos à navegar por esta estrutura de dados. E vamos ver, mais uma vez, como fazemos isso em apenas um segundo. 

No final do percurso, vamos ver o nome da universidade que corresponde a essa chave, estas quatro dígitos. A idéia básica por trás de um trie é que temos uma rota central. Então, pense nisso como uma árvore. E esta é semelhante em ortografia e no conceito de uma árvore. Geralmente quando pensamos sobre árvores no mundo real, eles têm uma raiz que está na chão e eles crescem para cima e eles têm filiais e eles têm folhas. E, basicamente, a idéia de um trie é exatamente o mesmo, exceto que a raiz está ancorado em algum lugar no céu. E as folhas estão na parte inferior. 

Então, é tipo de como tirar uma árvore e apenas virá-lo de cabeça para baixo. Mas ainda há ramos. E aqueles seriam os nossos caminhos, essas serão as nossas ligações desde a raiz até as folhas. Neste caso, aqueles trajetos, esses ramos são rotulados com dígitos que nos dizem que caminho seguir a partir de onde estamos. 

Se vemos um 0, descemos este ramo, se vemos a 1, descemos este ramo, e assim e assim por diante. Bem, o que isso significa? Bem, isso significa que em cada ponto de junção e cada nó no meio e cada ramo, existem 10 possíveis lugares que podemos ir. Portanto, há 10 ponteiros de todos os locais. 

E é neste ponto que tentativas pode obter uma pouco intimidante para alguém que é não ter um monte de experiência em ciência da computação antes. Mas tentativas são realmente bastante impressionante. E se você tiver o oportunidade de trabalhar com eles e você está disposto a cavar-in e experimentar com eles, eles são realmente bastante interessante estruturas de dados para trabalhar. Se queremos inserir um elemento no trie, tudo o que precisamos fazer é construir o caminho correto a partir da raiz para a folha. Aqui está o que cada passo ao longo a forma como pode parecer. Vamos definir uma nova dados estrutura para um novo nó chamado de trie. 

E dentro desses dados estrutura existem duas peças. Nós estamos indo para armazenar o nome de uma universidade. E nós estamos indo para armazenar uma matriz de ponteiros para outros nós do mesmo tipo. Então, novamente, este é esse tipo do conceito de todos os lugares somos, em 10 possíveis lugares onde podemos ir. Se vemos um 0, descemos este ramo. Se vemos a 1, neste ramo, e assim por diante e assim por diante e assim por diante. Se dissermos 9, descemos este ramo. Assim, em cada ponto de junção, podemos ir 10 lugares possíveis. Assim, cada nó deve conter 10 ponteiros para os outros nós, aos 10 outros nós. 

E os dados que nós estamos armazenando é apenas o nome da universidade. Então, vamos construir um trie. Vamos inserir um casal de itens em nosso trie. Assim, no topo, este é o nosso nó raiz. Isso provavelmente vai ser algo você está indo para globalmente declare. E você está indo para manter globalmente um ponteiro para este nó sempre. 

Você vai dizer, raiz é igual, e você está vai malloc mesmo nó trie. E você nunca vai para tocar raiz novamente. Toda vez que você quiser começar a navegar através, você definir outro ponteiro igual a raiz, como trav, que é o exemplo I usar em muitos de meus vídeos aqui em pilhas e filas e listas de links e assim por diante. 

Você definir outro ponteiro trav chamado para passagem. E você usa para navegar trav através da estrutura de dados. Então, vamos ver como isso pode parecer. Então, agora, o que se um nó parece? Bem, tal como os nossos dados declaração de estrutura indicada, temos uma string, que Neste caso está vazio. Não há nada aqui. 

E uma matriz de 10 ponteiros. E agora, temos apenas tem um nó nesta trie. Não há mais nada nele. Portanto, todos os 10 de ponteiros ponto para null. Isso é o que o vermelho indica. 

Vamos inserir a seqüência de Harvard. Vamos inserir a Universidade de Harvard para este trie, que foi fundada no ano de 1636. Queremos usar a chave, 1636, de nos dizer onde estamos indo para armazenar Harvard no trie. Agora, como podemos fazer isso? 

Poderia ser algo como isto. Nós começamos na raiz. E nós temos estes 10 lugares onde podemos ir. A raiz é como qualquer outro nó do trie. Há 10 lugares onde podemos ir a partir daqui. 

Onde nós provavelmente quer para ir se a chave é 1636? Não há realmente duas opções. Certo. Podemos construir a chave direita para a esquerda e comece com 6. Ou nós poderíamos construir a chave esquerda para a direita e começar com uma. 

É provavelmente mais intuitivo como um ser humano para entender nós vamos Basta ir esquerda para a direita. E por isso, se eu quero inserir Harvard para este trie, Eu provavelmente quer começar iniciando na raiz, olhando para os meus 10 opções na minha frente, e dizendo: Eu quero ir para o caminho 1. ESTÁ BEM. 

Agora, um caminho é actualmente nulo. Então, se eu quiser continuar por esse caminho para inserir esse elemento para o trie, Eu tenho que malloc um novo nó, tem um ponto lá, e então eu sou bom para ir. 

Então eu basicamente estou em uma ponto onde eu estou de pé na raiz da árvore ou a trie e existem 10 filiais. Mas cada ramo tem um portão na frente dele. Certo. Porque não há nada mais há. Nenhuma passagem segura. Isso significa que não há nada para baixo qualquer um desses ramos. Se eu quiser começar a construir alguma coisa, eu quero remover o portão. Eu quero remover o portão na frente do número 1. E eu quero que desça. E eu quero construir um outro lugar para eu ir. 

E isso é o que eu fiz aqui. Então 1 já não aponta para null. Eu já disse que é seguro para descer aqui agora. Eu construí outro nó. E quando eu chegar a esse nó, I ter outra decisão a tomar. Onde é que eu vou sair daqui? 

Bem, eu já tenha ido para baixo a 1. Então agora eu provavelmente vai querer ir para baixo a 6. Certo. Novamente, eu tenho 10 locais posso escolher. Então, vamos agora ir para baixo o número 6. Então eu limpar o portão na frente do número 6. E eu ando lá em baixo. E eu construir um outro nó. E eu já alcançou outro ponto de junção. 

Novamente, eu tenho 10 opções para onde eu posso ir. Eu me mudei 1-6. Então agora eu provavelmente vai querer ir a 3. 3, não há nenhum lugar eu posso ir. Então eu tenho que limpar o caminho e eu construir um novo espaço. E, em seguida, a partir de 3, onde eu gostaria de ir? Eu quero ir para baixo 6. 

E, mais uma vez, eu tive que limpar o caminho para fazê-lo. Então agora eu usei minha chave para inserir criar nós e começar a construir esta trie. Eu comecei na raiz. Eu tenho ido para baixo 1636. E agora eu estou na parte inferior há nesse nó. E você pode ser capaz de vê-lo na tela. 

É destacada em amarelo. É onde eu sou atualmente. Minha chave é feito. Eu já esgotou todas as posições na minha chave. Então eu não posso ir mais longe. Então, neste momento, tudo o que eu realmente precisa fazer é dizer, OK. É uma espécie de como a procura para baixo, para o chão, se você está imaginando se como este tipo de caminho com ligações diferentes. Classificar de olhar para baixo e tipo de pintura de pulverizador Harvard no chão. Esse é o nome deste. Saiba que o que é neste local. Se começarmos na raiz e descemos 1 e, em seguida, 6 e, em seguida, 3 e 6, em seguida, onde estamos? Bem, se olharmos para baixo e vemos Harvard, em seguida, sabemos que foi Harvard fundada em 1636 com base na maneira estamos implementando essa estrutura de dados. Assim que foi esperançosamente simples. Nós vamos fazer mais duas inserções. E espero que ele vai ajudar a ver este feito duas vezes mais. 

Agora, vamos inserir outra universidade. Vamos inserir Yale para este trie. Yale foi fundada em 1701. Então, vamos começar no root, como sempre fazemos. E nós definir um ponteiro de passagem. Nós vamos usar isso para percorrer. A primeira coisa que queremos fazer é ir para o caminho 1. Esse é o primeiro dígito da nossa chave. Felizmente, porém, não o fazemos tem que fazer algum trabalho desta vez. A um caminho já foi desmatada. Limpei-lo previamente, quando eu foi a inserção de Harvard em 1636. Então, eu posso mover com segurança down 1 e apenas ir lá. Se pode mover para baixo a 1. 

Agora, porém, eu quero ir para o 7. Eu abriu o caminho às 6. Eu sei que eu posso com segurança prossiga no caminho 6. Mas preciso avançar no caminho 7. Então o que eu preciso fazer? Bem, assim como antes, eu só preciso para limpar a porta, sair do caminho, e construir um novo nó do caminho 7. Assim como este. 

Então agora eu mudei 1 e, em seguida, 7. E agora aviso, eu sou uma espécie de sobre esta nova subbranch. Certo. Tudo o resto a partir de 16 , eu não me importo com. Eu não estou fazendo nada 16. Estou fazendo 17 coisas. 

Portanto, agora de 17 em diante, eu tenho que tipo de vislumbrar novos caminhos aqui. O próximo dígito minha chave é 0. Eu claramente não pode obter em qualquer lugar. Acabei de construir esse nó. Então eu sei que não há caminhos para a frente a partir daqui. Então eu tenho que fazer um eu mesmo. 

Então eu malloc um novo nó e tem 0 ponto lá. E, em seguida, mais uma vez, eu malloc um novo nó e tem um ponto lá. Mais uma vez, eu já esgotou a minha chave de 1701. Então eu olho para baixo e eu tinta spray Yale. Esse é o nome deste nó. 

E agora, se eu precisar para ver se Yale é neste trie, eu começo a raiz, Desço 1701, e olhar para baixo. E se eu vejo spray de Yale pintados no chão, em seguida, Eu sei Yale existe neste trie. Vamos fazer mais um. Vamos inserir Dartmouth neste trie, que foi fundada em 1769. 

Comece na raiz novamente. Meu primeiro dígito da minha chave é 1. Eu posso me mover com segurança por esse caminho. Que já existe. O próximo dígito da minha chave é 7. Eu posso me mover com segurança por esse caminho. Existe também. 

Meu próximo é 6. A partir daqui, de onde eu sou atualmente em amarelo ali naquele nó meio, 6 está atualmente bloqueado off. Se eu quero ir por esse caminho, Eu tenho que construir isso sozinho. Então, eu vou malloc um novo nó e tem 6 pontos lá. E então, novamente, eu sou abrindo novos caminhos aqui. 

Então eu malloc um novo nó de modo que a partir de esse número caminho node-- 9-- e então agora se eu viajar de 1769, e eu olho para baixo. Não há nada atualmente pulverizador pintado lá. Eu posso escrever Dartmouth. E eu tenho inserido Dartmouth no trie. 

Então, isso é inserindo coisas para o trie. Agora queremos procurar coisas. Como é que vamos procurar coisas no trie? Bem, é praticamente a mesma idéia. Agora é só usar os dígitos da chave para ver se é possível navegar a partir da raiz para onde queremos ir no trie. 

Se nós batemos um beco sem saída em qualquer ponto, em seguida, nós sabemos que esse elemento não pode existir ou então esse caminho seria já foram apuradas. Se fizermos com que todo o caminho para Ao final, tudo o que precisamos fazer é olhar para baixo e ver se é isso o elemento que estamos procurando. Se for, o sucesso. Se não é, falhar. 

Então, vamos procurar Harvard neste trie. Nós começamos na raiz. E, mais uma vez, vamos criar um ponteiro de passagem para fazer nossos movimentos para nós. A partir da raiz sabemos que o primeiro lugar, precisamos de ir é 1, podemos fazer isso? Sim, nós podemos. Se existe de forma segura. Nós podemos ir lá. 

Agora, o próximo lugar que precisa ir é 6. Será que o caminho 6 existir a partir daqui? Sim, ele faz. Nós podemos ir para o caminho 6. E acabamos aqui. 

Podemos ir para o caminho 3 a partir daqui? Bem, como se vê, sim, que existe também. E podemos entrar no caminho de 6 a partir daqui? Sim, nós podemos. 

Nós não temos bastante respondeu a questão ainda. Ainda há mais uma passo, que é agora temos de olhar para baixo e ver se isso é actually-- se nós estamos olhando para Harvard, é que o que encontramos depois de esgotar a chave? No exemplo que estamos usando aqui, os anos são sempre quatro dígitos. Mas você pode estar usando o exemplo onde você está armazenando um dicionário de palavras. 

E assim, em vez de ter 10 ponteiros para o meu local, você pode ter 26. Um para cada letra do alfabeto. E há algumas palavras como bastão, que é um subconjunto do lote, por exemplo. E assim mesmo se você chegar ao final da chave e você olha para baixo, você não pode ver o que você está procurando. 

Assim, você sempre tem que atravessar todo o caminho e depois se você fosse capaz êxito para percorrer todo o caminho, olhar para baixo e fazer uma confirmação final. É isso que eu estou procurando? Bem, eu olhar para baixo após o início no topo e indo 1636. Eu olho para baixo. Vejo Harvard. Então, sim, eu consegui. E se o que eu estou procurando não está no trie, no entanto. E se eu estou procurando Princeton, que foi fundada em 1746. E assim torna-se minha chave de 1746 para navegar através do trie. Bem, eu começar na raiz. E o primeiro lugar que eu quero para se põe a caminho 1. Posso fazer isso? Sim eu posso. 

Eu posso ir para o caminho 7 de lá? Sim eu posso. Isso existe também. Mas eu posso ir para o caminho 4 a partir daqui? Isso é como perguntar a pergunta, pode Eu prosseguir por esse pequeno quadrado que eu tenho realçado em amarelo? Não há nada lá. Certo. 

Não há nenhuma maneira de avançar no caminho 4. Se Princeton foi neste trie, que 4 teria sido liberado para nós já. E por isso neste momento chegamos a um beco sem saída. Não podemos ir mais longe. E assim podemos dizer, definitivamente, não. Princeton não existe neste trie. 

Então o que isso tudo significa? Certo. Há muita coisa acontecendo aqui. Há ponteiros em todo o lugar. E, como você pode ver apenas a partir do diagrama, há uma grande quantidade de nós que são do tipo que voam ao redor. Mas note cada vez que queria verificar se algo foi no trie, nós só tivemos que fazer 4 movimentos. 

Cada vez que queria inserir algo no trie, temos de fazer 4 movimentos, possivelmente mallocing algumas coisas ao longo do caminho. Mas, como vimos quando inserido Dartmouth no trie, por vezes algum do caminho já pode ser liberado para nós. E assim como o nosso se torna maior e trie maior, nós temos fazer menos trabalho a cada vez para inserir coisas novas porque já construiu um monte de o intermediário ramos ao longo do caminho. Se nós sempre apenas tem que olhar para 4 coisas, 4 é apenas uma constante. Nós realmente estamos tipo de abordagem inserção de tempo constante e pesquisa de tempo constante. A desvantagem, é claro, que sendo este trie, como você pode provavelmente dizer, é enorme. Cada um destes nós tem um monte de espaço. 

Mas esse é o tradeoff. Se queremos realmente rápido inserção, eliminação realmente rápido, e lookup muito rápido, temos que tem um monte de dados que voam ao redor. Temos de pôr de lado um monte de espaço e memória para essa estrutura de dados existir. 

E então essa é a troca. Mas parece que pode tê-lo encontrado. Poderíamos descobriram que Santo Graal de estruturas de dados com inserção rápida, exclusão e de pesquisa. E talvez este será um estrutura de dados apropriada para usar por qualquer informação nós estamos tentando loja. Eu sou Doug Lloyd, este é CS50.