Considere que a Manausprev armazena os nomes dos beneficiári...

Alternativa Correta: E

Vamos entender a questão e analisar cada uma das alternativas para esclarecer por que a alternativa E é a correta.

Uma Árvore Binária de Busca (ABB) é uma estrutura de dados muito usada para fins de busca eficiente. Em uma ABB, para cada nó, todos os elementos da subárvore esquerda são menores que o nó, e todos os elementos da subárvore direita são maiores que o nó.

Para resolver a questão, precisamos considerar a ordem de inserção dos nomes e construir a árvore passo a passo:

1. Inserindo Marcos - vira a raiz.
2. Inserindo José - vai para a esquerda de Marcos.
3. Inserindo Carolina - vai para a esquerda de José.
4. Inserindo Paula - vai para a direita de Marcos.
5. Inserindo Rui - vai para a direita de Paula.
6. Inserindo Pedro - vai para a esquerda de Rui.
7. Inserindo Maria - vai para a esquerda de Paula e direita de Marcos.

Com a construção, a árvore não é perfeitamente balanceada, e será necessário verificar quantas comparações são necessárias para localizar qualquer um dos 7 nomes.

Análise das Alternativas:

A - é perfeitamente balanceada.

Esta alternativa está incorreta. Uma árvore binária de busca perfeitamente balanceada teria todos os níveis de nós preenchidos de maneira equilibrada, o que não é o caso aqui.

B - tem altura 3, que corresponde à altura mínima para armazenar os 7 nomes.

A alternativa está incorreta. A árvore resultante tem uma altura maior que 3 devido à forma como os nomes foram inseridos. A altura mínima para armazenar 7 nomes seria 3, mas isso não ocorre com a ordem de inserção dada.

C - possui como folhas os nomes Rui e Maria.

Esta alternativa está incorreta. Analisando a árvore, vemos que Rui não é uma folha (possui filho) e Maria também não é uma folha.

D - requer no máximo 3 comparações para localizar qualquer um dos 7 nomes.

Esta alternativa está incorreta. Como a árvore não está balanceada, localizar alguns nomes pode exigir mais de 3 comparações.

E - requer no máximo 4 comparações para localizar qualquer um dos 7 nomes.

Esta alternativa está correta. Na árvore resultante, o caminho mais longo para localizar um nome (Carolina ou Rui, por exemplo) exige 4 comparações. Logo, é o número máximo de comparações necessárias.

Espero que esta explicação tenha facilitado a compreensão do tema. Se precisar de mais alguma ajuda, estou à disposição!

A árvore final fica assim:

Padrão: Nó (Filho Esquerda, Filho Direita);

Marcos (José, Paula);

José (Carolina, Null);

Paula (Maria, Rui);

Rui (Pedro, Null);

Carolina, Maria, Pedro: (Null, Null);

Para garantir o acesso a qualquer nó, é necessário pelo menos 4 comparações. 

Para ver como a árvore é montada, segue o link: https://www.cs.usfca.edu/~galles/visualization/BST.html

A: entendo que não é possível afirmar que a árvore é perfeitamente balanceada com a informação dada no enunciado. A questão afirma a ordem da inserção dos nós, mas não aponta onde eles são inseridos. Assim, não é possível afirmar que todos os nós pais possuem dois filhos.

B: caso os nós, com exceção das folhas, tenham 2 filhos, a altura mínima dessa árvore seria 2.

C: pela mesma justificativa da alternativa A, não é possível afirmar que Rui e Maria são folhas.

D: caso os nós, com exceção das folhas, tenham 2 filhos, vamos precisar fazer 4 comparações. Então, não é possível afirmar que tal árvore requer NO MÁXIMO 3 comparações para localizar qualquer um dos 7 nomes.

E: vide comentários sobre a alternativa D.

Assumindo (embora o enunciado não tenha tornado isso explícito)

- que estamos falando de uma ordem alfabética

- que as palavras com letra "menor" (anteriores no alfabeto) ficam na esquerda

- que as palavras com letra "maior" ou igual ficam na direita

Teremos uma árvore com esse aspecto:

                M

               /   \

            J       P

          /        /    \

      C        M      R

                       /

                    P

[email protected]

Árvore perfeitamente balanceada: para cada nó, o número de nós de suas sub-árvores esquerda e direita diferem em, no máximo, 1. Não é o caso dessa árvore.

a) E. 

 b) E. Tem altura de 4. 

 c) E, Rui não é folha. 

 d) E. Conforme Maurício afirmou: caso os nós, com exceção das folhas, tenham 2 filhos, vamos precisar fazer 4 comparações. Então, não é possível afirmar que tal árvore requer NO MÁXIMO 3 comparações para localizar qualquer um dos 7 nomes.

 e) C. Vide comentário item 'd'

Força Guerreiro!!!!!!