Uma das operações mais realizadas em sistemas é a operação de busca. Árvores binárias de busca são uma implementação que visa otimizar tal operação pela disposição dos dados no armazenamento. A complexidade da busca em uma árvore é representada por O(n). Podemos afirmar que a complexidade de uma árvore é igual à(ao):
- A)Sua altura.
Certa, porque o custo da busca em uma árvore depende da altura, isto é, da quantidade de níveis percorridos.
- B)Valor do elemento alocado em sua raiz.
Errada, porque o valor da raiz é apenas o primeiro elemento comparado e não define a complexidade da árvore.
- C)Número de elementos armazenados nela.
Errada, porque o número de elementos influencia a árvore, mas não é o fator direto da complexidade da busca.
- D)Metade do número de elementos armazenados nela.
Errada, porque a complexidade não é uma fração fixa do número de elementos; ela depende da estrutura e da altura da árvore.
Gabarito: A
Em árvores binárias de busca, a ideia é comparar o elemento procurado com a raiz e depois descer para a esquerda ou para a direita, seguindo o caminho de comparação. Isso faz com que o tempo de busca dependa da quantidade de níveis percorridos, e não simplesmente da quantidade total de elementos. Em outras palavras, o que manda aqui é a altura da árvore. Se a árvore estiver bem balanceada, a busca fica bem mais rápida. Mas, se ela estiver “torta” demais, parecendo uma lista ligada, a altura pode chegar perto do número de elementos e aí a busca piora para O(n). É por isso que, em análise de pior caso, a complexidade da busca em uma árvore é associada à sua altura. Então, quando a questão diz que a complexidade da busca em uma árvore é O(n), está puxando você para essa ideia de pior caso, em que a altura cresce bastante. A resposta correta é a alternativa A, porque a complexidade de busca em uma árvore está ligada à sua altura. O número de nós importa, mas indiretamente, pois ele afeta como a árvore pode crescer em níveis.