Certo documento possui 1 milhão de palavras não repetidas e foi editado em um editor de textos. Considerando que o editor de textos utiliza uma Árvore Binária de Busca − ABB de alt

Gabarito

B

Comentário do professor

Uma árvore binária de busca com altura mínima organiza N elementos para que, a cada comparação, o espaço restante de busca seja reduzido pela metade. Assim, o número máximo de comparações necessárias para localizar um elemento é dado por \( \lceil \log_{2}(N) \rceil \).

No caso de 1 milhão de palavras, \(N=10^{6}\). Calculando \( \log_{2}(10^{6}) \approx 19{,}93\), portanto o teto é 20 comparações.

Uma aproximação prática: como \(10^{3}\approx 2^{10}\), segue que \(10^{6}=(10^{3})^{2}\approx(2^{10})^{2}=2^{20}\), o que confirma que \( \log_{2}(10^{6})\) é praticamente 20.

Portanto, no pior caso, serão necessárias no máximo 20 comparações.