Uma empresa de análise de dados, a equipe está implementando uma árvore binária de busca para otimizar as operações de busca em grandes conjuntos de...

🎓 Gabarito Comentado (AVA):

A afirmativa I "Em uma árvore binária de busca, todos os nós à esquerda de um nó são sempre menores que esse nó" é correta, pois em uma árvore binária de busca (ABB), por definição, todos os nós localizados à esquerda de um dado nó têm valores menores do que o valor desse nó. Esta é uma característica fundamental das ABBs, permitindo operações eficientes de busca, inserção e remoção de elementos, mantendo os dados organizados de maneira que facilite a localização de qualquer item.

A afirmativa II "Uma árvore binária de busca não pode ter dois nós com o mesmo valor" é incorreta, já que embora muitas implementações de árvores binárias de busca prefiram não ter nós duplicados para manter a unicidade dos elementos e simplificar as operações, tecnicamente é possível ter dois ou mais nós com o mesmo valor. No entanto, a maneira como esses nós duplicados são tratados depende da implementação específica da árvore. Algumas estratégias podem incluir a inserção de valores duplicados em um lado específico do nó ou o uso de estruturas adicionais para armazenar múltiplos itens no mesmo nó.

A afirmativa III "A busca em uma árvore binária de busca desbalanceada é tão eficiente quanto em uma balanceada" é incorreta, visto que a eficiência da busca em uma árvore binária de busca desbalanceada pode ser significativamente menor do que em uma árvore balanceada. Em árvores desbalanceadas, a profundidade da árvore pode se aproximar de N em casos extremos (sendo N o número de nós), o que se aproxima de uma pesquisa linear em termos de eficiência. Árvores balanceadas, por outro lado, mantêm uma profundidade logarítmica em relação ao número de nós, garantindo que as operações de busca, inserção e remoção sejam mais eficientes.

A afirmativa IV "O percurso in-ordem em uma árvore binária de busca resulta em uma sequência de valores em ordem crescente" é correta, pois o percurso in-ordem (esquerda, raiz, direita) em uma árvore binária de busca produz uma sequência de valores em ordem crescente. Isso ocorre devido à propriedade inerente das ABBs, onde todos os valores à esquerda de um nó são menores e todos os valores à direita são maiores. Portanto, ao visitar os nós seguindo a ordem in-ordem, os valores são acessados de forma sequencial do menor para o maior.