Lista de exercícios

Árvores digitais: leitura e interpretação

Nove exercícios com figuras prontas e respostas comentadas sobre trie, Patricia, prefixos, regras de manutenção, custos e aplicações.

Leia uma questão por vez e confira sua solução antes de avançar. Cada questão fornece o apoio necessário. As figuras e os resultados apresentados já estão prontos. Responda com explicações curtas.

Resposta esperada é referência para autocorreção, sem entrega ou correção individual. Outras redações são válidas quando apresentam o raciocínio solicitado. Os 60 minutos estimados incluem leitura, tentativa e conferência, sem limite rígido.

Vocabulário para consulta

Chave: sequência usada para localizar uma informação, como um comando.
Prefixo: início de uma chave.
Trie: árvore em que os símbolos da chave definem o caminho. Nesta lista, cada aresta da trie comum corresponde a uma letra.
Marca de fim: indica que o caminho representa uma chave cadastrada. Nas figuras, aparece como *.
Subárvore: um nó e seus descendentes. A raiz é o nó inicial. Uma folha não tem filhos.

Exercício 1: distinguir sugestão de comando completo

Explique a diferença entre os dois resultados deste terminal:

Ao digitar le, aparecem as sugestões led e ler.
Ao confirmar ler, o terminal reconhece o comando de leitura do sensor.

A consulta por prefixo reúne as chaves com o início informado. Na trie, suas continuações ficam na mesma subárvore. A busca exata exige uma chave completa cadastrada. Os comandos deste exemplo são led, ler, ligar e listar.

Como agrupar comandos pelo prefixo ajuda nas sugestões sem transformar le em um comando válido?

Solução

Explicação

le delimita o grupo de led e ler. Isso ajuda a apresentar as opções pertinentes, deixando fora ligar e listar, de outro início. O agrupamento não cadastra uma palavra completa. Reconhecer o comando exige sua marca de fim.

Objetivo de aprendizagem: distinguir a finalidade da consulta por prefixo da busca exata em uma aplicação de engenharia.

Resposta esperada

O prefixo le reúne as sugestões led e ler, deixando ligar e listar fora desse grupo. Isso oferece opções de preenchimento, mas le continua sem representar uma palavra completa cadastrada. O reconhecimento exige um comando completo, como ler.

Exercício 2: interpretar uma palavra com filhos

Avalie a afirmação: “Em uma trie, somente as folhas podem representar palavras cadastradas.”

Na figura, * indica palavra cadastrada. Os nomes nas caixas mostram os prefixos para facilitar a leitura.

Trie pronta das palavras ar, aro, asa, ato e sol, com ar marcado e com um descendente

A afirmação representa corretamente esse cadastro? Justifique com um nó da figura.

Solução

Explicação

Ter filhos informa que o prefixo continua em outras palavras. A marca de fim informa se esse prefixo também é uma palavra cadastrada. Essas duas características podem existir no mesmo nó.

Objetivo de aprendizagem: interpretar a marca de fim independentemente da presença de filhos.

Resposta esperada

Não. ar* representa a palavra cadastrada ar. O filho pela letra o representa sua continuação em aro. A marca de fim, e não a condição de folha, identifica a palavra completa.

Exercício 3: verificar a regra das ligações

Verifique este relatório de uma trie comum:

Um nó possui duas ligações com a letra r.
Cada ligação leva a um filho diferente.

Na trie comum, a próxima letra da chave deve identificar um único filho do nó atual.

A organização descrita respeita essa regra? Justifique.

Solução

Explicação

Ao receber a letra r, o programa teria duas continuações diferentes para a mesma decisão. A trie compartilha esse prefixo, em vez de criar filhos separados para a mesma próxima letra.

Objetivo de aprendizagem: reconhecer a unicidade da ligação de cada símbolo em um nó da trie.

Resposta esperada

Não. Um nó pode ter, no máximo, um filho para a próxima letra r. Duas ligações para filhos diferentes tornariam essa escolha ambígua.

Exercício 4: compreender o compartilhamento nas atualizações

Interprete dois resultados de manutenção já fornecidos:

A inclusão de arte preservou as palavras ar e aro, compartilhando o prefixo ar.
Depois, a retirada de ar preservou aro e arte, mantendo esse prefixo e retirando somente sua marca de fim.

Os dois resultados podem estar corretos? Justifique pelo papel do caminho e da marca de fim.

Solução

Explicação

O caminho de um prefixo pode servir a várias palavras. Incluir uma nova continuação não cancela uma palavra já marcada. Retirar uma palavra também não exige apagar o caminho que outras ainda utilizam.

Objetivo de aprendizagem: explicar como o compartilhamento de prefixos preserva palavras durante inclusões e remoções.

Resposta esperada

Sim. A inclusão pode reutilizar ar sem retirar sua marca. Na remoção de ar, a marca deixa de existir, mas o caminho permanece necessário para representar aro e arte.

Exercício 5: interpretar a compactação

Compare as duas representações prontas do mesmo cadastro. Na trie compactada, uma aresta pode representar várias letras. A contagem inclui a raiz.

Comparação de uma trie com onze nós e uma trie compactada com sete nós, ambas contendo ar, aro, asa, ato e sol

O que a compactação economizou e qual informação precisa continuar representada?

Solução

Explicação

Trechos sem bifurcação passam a ocupar menos nós e ligações. As letras continuam nos rótulos das arestas, e os finais das palavras continuam identificados. O nó de ar* permanece necessário, mesmo tendo uma única continuação.

Objetivo de aprendizagem: relacionar a redução de nós à preservação das chaves e de suas marcas de fim.

Resposta esperada

A compactação reduziu os nós intermediários, de 11 para 7. Todas as letras e os finais das cinco palavras continuam representados. Isso pode economizar memória, mas os bytes usados também dependem dos rótulos e das referências.

Exercício 6: interpretar os números da Patricia

Interprete o rótulo b0? nos nós internos da figura. As chaves têm quatro bits: b3 b2 b1 b0, da esquerda para a direita. b0 fica à direita e é o bit menos significativo.

Na Patricia binária, um nó interno indica qual posição da chave orienta a escolha entre os ramos 0 e 1. As folhas guardam as chaves completas.

Patricia com testes b3 e b0 e as chaves completas 0010, 0011, 1010 e 1011 nas folhas

Um colega diz que b0? é uma chave armazenada naquele nó. Essa leitura está correta? Explique o rótulo e o salto de b3 para b0.

Solução

Explicação

O rótulo indica qual bit consultar para escolher um ramo, não uma chave armazenada. Os testes podem saltar posições que não distinguem as chaves daquele trecho. Os bits continuam presentes nas chaves completas das folhas.

Objetivo de aprendizagem: distinguir o índice de decisão de uma Patricia das chaves armazenadas nas folhas.

Resposta esperada

Não. b0? significa testar o bit mais à direita da chave consultada. O salto de b3 para b0 evita testar b2 e b1, que não separam as chaves nesses trechos. Esses bits permanecem nas chaves completas. Os índices diminuem no percurso.

Exercício 7: confirmar a chave da folha alcançada

Avalie o resultado de uma consulta em Patricia, já realizada pelo sistema:

Chave consultada: 1000.
Chave armazenada na folha alcançada: 1010.

Neste modelo, b0 fica à direita. A consulta 1000 segue b3 = 1 e depois b0 = 0, chegando à folha já armazenada 1010. Os testes saltam b2 e b1. Chegar à folha ainda exige comparar sua chave inteira com a consulta.

O sistema pode informar que encontrou a chave consultada? Justifique pela comparação necessária.

Solução

Explicação

Chegar à folha não significa ter encontrado a chave consultada. 1000 e 1010 diferem em b1, que não foi testado no percurso. A comparação completa impede aceitar uma chave que diferiu em uma posição não testada no caminho.

Objetivo de aprendizagem: justificar a confirmação completa da chave em uma busca exata na Patricia.

Resposta esperada

Não. 1000 é diferente de 1010. A diferença em b1 rejeita a correspondência com a folha e confirma a ausência de 1000.

Exercício 8: relacionar custo e comprimento da chave

Analise uma trie com acesso direto ao filho de cada letra e alfabeto fixo. Todas as chaves têm comprimento máximo L. Nesse modelo, a busca exata tem custo $O(L)$ : o limite do percurso acompanha o comprimento da chave.

O cadastro dobrou de tamanho, mas L permaneceu igual.

Isso obriga uma busca exata a examinar o dobro de palavras? Justifique pelo modelo de custo.

Solução

Explicação

A busca segue os símbolos da chave consultada. Ela não compara a consulta separadamente com cada palavra cadastrada. O limite do percurso continua relacionado a L, embora o cadastro maior possa ocupar mais memória.

Essa análise vale para a busca exata. Listar sugestões também exige visitar e produzir os resultados.

Objetivo de aprendizagem: distinguir o comprimento da chave do número de palavras no custo de uma busca exata em trie.

Resposta esperada

Não. A busca acompanha um caminho definido pela chave, com custo $O(L)$ nas condições dadas. Dobrar o cadastro não obriga a comparar a consulta com o dobro de palavras.

Exercício 9: justificar uma escolha de engenharia

Recomende uma trie comum ou uma Patricia para avaliação neste equipamento:

O cadastro usa identificadores binários de tamanho fixo.
A trie atual tem muitos trechos longos com uma única continuação.
A memória ocupada pelos nós é uma preocupação.

Escreva uma justificativa curta que conecte a escolha, o benefício esperado e um limite que permanece. A trie comum mantém os caminhos por símbolo. Patricia compacta trechos sem bifurcação.

Solução

Explicação

O problema informado está nos nós intermediários de caminhos sem alternativas. Patricia atua nessa organização. A economia precisa ser verificada na implementação, pois também existem rótulos, referências e chaves completas para armazenar.

Objetivo de aprendizagem: justificar uma escolha de estrutura pela necessidade da aplicação, sem transformar um benefício possível em garantia.

Resposta esperada

Patricia merece avaliação. A compactação pode reduzir os nós intermediários e seu consumo de memória. A economia real precisa ser medida, e a busca exata ainda exige confirmar a chave completa na folha.