Questão de Tecnologia da Informação · CESGRANRIO BASA 01/2018 (nº 46)

Conceito-chave: Em uma árvore binária completa de busca, a cada comparação você descarta metade dos nós restantes. O número máximo de comparações é a altura da árvore, que cresce com o logaritmo do total de nós, não com o total em si.

• (A) Incorreta: $N$ seria o custo de uma busca linear em uma lista, não em uma árvore balanceada. A árvore não exige percorrer todos os nós.
• (B) Incorreta: $N^2$ é um custo quadrático típico de algoritmos de ordenação ingênuos, sem relação com a busca em árvore.
• (C) Correta: Em uma árvore binária completa com $N$ nós, a altura é $\lceil \log_2(N+1) \rceil$. O pior caso de comparações é exatamente essa altura, pois cada nível reduz o espaço de busca pela metade. A fórmula $\log_2(N+1)$ representa o número de níveis (a altura) da árvore completa.
• (D) Incorreta: $(N+1)\log_2(N+1)$ seria o custo de percorrer todos os níveis para cada nó, algo como uma ordenação por árvore, não uma busca simples.
• (E) Incorreta: $\sqrt{N+1}$ é uma função de crescimento intermediário, que não corresponde à estrutura logarítmica da árvore balanceada. A armadilha aqui é confundir "dividir pela metade" com "raiz quadrada", mas a divisão sucessiva por 2 gera logaritmo, não raiz.