Complexidade em Árvores Binárias de Busca Balanceadas
Gabarito: letra D. Em uma árvore binária de busca balanceada, como a árvore AVL, as operações de busca, inserção e remoção possuem complexidade de tempo O(log n) no caso médio (e também no pior caso, graças ao balanceamento). A alternativa D é a única que lista todas as três operações, sendo a afirmação completa e correta.
O artigo sobre árvore AVL do conteúdo de apoio confirma: "As operações de busca, inserção e remoção de elementos possuem complexidade O(log n)". Isso vale para qualquer BST balanceada (AVL, Rubro-Negra, etc.), pois o balanceamento mantém a altura da árvore proporcional a log n, garantindo que percorrer da raiz até uma folha leva tempo logarítmico.
Alternativa A — ❌ Incorreta
Afirma que apenas inserção e remoção exibem O(log n), omitindo a busca. Em uma BST balanceada, a busca também tem complexidade O(log n). Portanto, a afirmação é incompleta.
Alternativa B — ❌ Incorreta
Afirma que apenas remoção e busca exibem O(log n), omitindo a inserção. A inserção também possui a mesma complexidade, pois segue o mesmo percurso de busca para encontrar a posição, além do rebalanceamento posterior.
Alternativa C — ❌ Incorreta
Afirma que apenas inserção e busca exibem O(log n), omitindo a remoção. A remoção também é O(log n), pois encontra o nó e, se necessário, realiza rotações de balanceamento, que são operações de custo constante.
Alternativa D — ✅ Correta ⟵ GABARITO
Lista todas as três operações (inserção, remoção e busca), todas com complexidade O(log n) em uma BST balanceada. Esta é a afirmação completa e correta.
Gabarito: letra D.