Certo documento possui 1 milhão de palavras não repetidas e ...

Alternativa Correta: B - 20 comparações.

Vamos explicar detalhadamente o raciocínio por trás dessa questão para garantir uma compreensão clara e eficaz.

O enunciado menciona que um documento possui 1 milhão de palavras não repetidas, e estas palavras estão armazenadas em uma Árvore Binária de Busca (ABB) de altura mínima. Esta estrutura de dados é utilizada para facilitar a localização das palavras.

Primeiro, precisamos entender o conceito de uma Árvore Binária de Busca de altura mínima. Uma ABB de altura mínima é aquela que está balanceada, ou seja, a diferença de altura entre as subárvores esquerda e direita de qualquer nó é no máximo 1. Esta característica é crucial para otimizar o tempo de busca, inserção e remoção de elementos.

Em uma ABB balanceada, a altura da árvore é aproximadamente log₂(n), onde n é o número de nós da árvore. Isso ocorre porque, em cada nível da árvore, o número de nós dobra.

No nosso problema, temos 1 milhão de palavras. Portanto, para determinar a altura da árvore, calculamos log₂(1.000.000).

Sabemos que:

log₂(1.000.000) ≈ 20

Isso significa que a altura da ABB é aproximadamente 20. Na pior das hipóteses, para localizar uma palavra, seriam necessárias 20 comparações, correspondendo ao número de níveis da árvore.

Justificando a Alternativa Correta:

B - 20 comparações é correta porque, com uma ABB balanceada contendo 1 milhão de palavras, a altura da árvore será cerca de 20, e é o número máximo de comparações necessárias para encontrar qualquer palavra na árvore.

Analisando as Alternativas Incorretas:

A - 1 milhão de comparações: Esta alternativa está incorreta, pois sugerir 1 milhão de comparações indica uma busca linear em uma lista desordenada, o que não se aplica a uma ABB, especialmente uma balanceada.

C - 32 comparações: Esta alternativa também está incorreta porque, para uma ABB de 1 milhão de nós, a altura da árvore é muito mais próxima de 20 do que de 32.

D - log₁₀1000000 comparações: Esta alternativa está incorreta porque está usando o logaritmo na base 10. Para árvores binárias, utilizamos o logaritmo na base 2, e log₂(1.000.000) ≈ 20, não log₁₀.

E - 2 milhões de comparações: Esta alternativa está incorreta pela mesma razão da alternativa A. Sugere uma quantidade de comparações irrealista e não aplicável a uma ABB balanceada.

Espero que esta explicação tenha esclarecido o raciocínio por trás da questão e ajudado a entender melhor o funcionamento das Árvores Binárias de Busca!

Esta questão é fácil de ser resolvida, se tiver um calculadora.
Busca em árvore binária tem complexidade de log na base 2.
Pegando isso como base, já podemos eliminar a, d e, restando b e c. Aí vai da noção de cada um, já que na prova não terá um calculadora. 
Gabarito: letra B. 
Log 2 (1.000.000) = 19.931 ~= 20

Jerico Mulambo, podemos dar uma avançada a mais no seu cálculo para termos uma melhor certeza da resposta na prova sem usar uma calculadora, empregando um pouco as propriedades dos logaritmos:

log 2 (1000000) = log 2 (10^6) = 6 . log 2 (10)  *

Então, a que número 2 deve ser elevado para que resulte 10? Vamos pegar por aproximação 3, já que 2^3 = 8. Então, fica assim:

6 . log 2 (10) = 6 . 3 ~= 18

A resposta mais próxima disso é a alternativa b (20).

Obs.: Conforme Jerico Mulambo disse, busca em árvore binária tem complexidade log 2 (n), onde 2 é a base e n é o número de elementos. Aliás, o algoritmo pesquisa binária (ou busca binária) também tem essa mesma complexidade.

* Isso vem da segunte propriedade dos logaritmos: log a (b^n) = n . log a (b)

Busca árvore binária é log (no. de elementos) na base 2, então log 10**6 na base 2.

Como se faz para tornar log de base 2 no log de base 10?

Divido o log do número que quero encontrar, só que na base 10 por log de 2 na base 10

Nesse caso específico eu tenho:

=log 10 **6 na base 10 / log 2 na base 10

Separadamente 1) log 10 **6 na base 10 = a que numero elevo 10 para chegar a 10 **6? resposta=6

e 2) log 2 na base 10 é aproximadamente 3/10

unindo 1)/2):

= 6/3/10

=6 * 10/3

=60/3

=20 (letra B)

Força Guerreiro!!!!!!