Alternativa correta: B - (V); (F); (V); (V).

Tema central da questão: Esta questão aborda o funcionamento das árvores Trie (ou árvores prefixadas), estrutura de dados crucial para operações de busca eficiente por prefixos em conjuntos de strings. Saber distinguir suas características frente a outras estruturas é fundamental para concursos, pois Tries são muito usadas em autocompletar, dicionários e sistemas de busca.

Resumo teórico: Uma Trie é uma árvore M-ária (cada nó pode ter até M filhos), onde cada nível representa um caractere da chave. Caminhar na Trie consiste em seguir, caractere a caractere (ou bit a bit, dependendo do contexto), até encontrar (ou não) a chave desejada. Ao contrário de árvores binárias de busca, o formato da Trie independe da ordem de inserção; depende dos prefixos das chaves. (Fonte: Mark Allen Weiss, "Estruturas de Dados e Algoritmos em C")

Justificativa da alternativa correta (B):

• (V) 1ª assertiva: Uma Trie realmente é uma árvore M-ária, onde cada nó contém M possíveis caminhos, um para cada caractere válido. Isso está correto.
• (F) 2ª assertiva: Errada porque não é verdade que cada nó no nível i representa o conjunto de M/2 chaves; o número de chaves pode variar, pois depende dos prefixos e da distribuição das strings, não há relação fixa com M/2.
• (V) 3ª assertiva: Verdadeira: quando as chaves são vistas como bits (M=2), o algoritmo de busca segue os bits, sem comparação entre chaves, apenas caminhando pelo próximo dígito.
• (V) 4ª assertiva: Correta: diferentemente das árvores binárias, a estrutura da Trie não depende da ordem de inserção, mas da distribuição dos caracteres/bits das chaves inseridas.

Análise das alternativas incorretas:

• A: Considera a segunda assertiva como verdadeira, mas ela é falsa.
• C: Considera a terceira como falsa e a quarta como falsa, ambas são verdadeiras.
• D: Considera a terceira e quarta como falsas, incorreto conforme explicado acima.

Dicas de prova: Identifique termos técnicos como "ordem de inserção" e "distribuição dos bits". Pegadinhas comuns envolvem atribuir propriedades das árvores binárias às Tries. Sempre relacione o funcionamento da estrutura com exemplos práticos!

Gostou do comentário? Deixe sua avaliação aqui embaixo!

Vamos analisar cada assertiva:

(1) ✔️ Verdadeiro

A Trie é, de fato, uma árvore M-ária, em que cada nó normalmente possui um vetor de M posições, correspondentes aos possíveis caracteres (ou dígitos/bits) do alfabeto utilizado para formar as chaves.

(2) ❌ Falso

Cada nó no nível i representa o conjunto de chaves que compartilham o mesmo prefixo de comprimento i, e não “M/2 chaves”. Esse valor não faz sentido no contexto das Tries.

(3) ✔️ Verdadeiro

Quando as chaves são vistas como sequências de bits (M = 2), a pesquisa digital percorre a árvore de acordo com os bits da chave, e não por comparações entre chaves, o que caracteriza as árvores digitais (Tries binárias).

(4) ✔️ Verdadeiro

Diferentemente das árvores binárias de busca, o formato da Trie não depende da ordem de inserção das chaves, mas sim da estrutura das próprias chaves e da distribuição de seus bits ou caracteres.

V – F – V – V