GabaritoE — Árvore AVL
Gabarito: letra E. A única estrutura que garante complexidade O(log n) para inserção, remoção e busca tanto no melhor quanto no pior caso é a Árvore AVL, uma árvore binária de busca balanceada que mantém sua altura logarítmica através de rotações.
A questão testa o conhecimento sobre o comportamento assintótico das operações fundamentais em diferentes estruturas. O ponto central é que a complexidade deve ser O(log n) independentemente do caso, ou seja, no pior caso também.
Pilha: inserção (push) e remoção (pop) são O(1), mas a procura (busca por um elemento) é O(n) no pior caso, pois é necessário percorrer a pilha sequencialmente.
Árvore Binária: se não houver balanceamento, a árvore pode degenerar em uma lista encadeada, fazendo com que inserção, remoção e busca se tornem O(n) no pior caso. Apenas árvores balanceadas garantem O(log n).
Tabela Hash: as operações de inserção e busca têm complexidade média O(1), mas no pior caso (muitas colisões) podem ser O(n). Além disso, não há garantia de O(log n) em nenhum cenário.
Fila duplamente encadeada: inserção e remoção nas extremidades são O(1), mas a busca por um elemento específico requer percorrer a fila, resultando em O(n) no pior caso.
Árvore AVL: é uma árvore binária de busca balanceada, onde a diferença de altura entre subárvores é no máximo 1. Isso garante que a altura da árvore seja sempre O(log n), e consequentemente as operações de inserção, remoção e busca (que dependem da altura) são O(log n) no pior caso, independentemente da sequência de inserções.
Para identificar a estrutura com complexidade logarítmica garantida em todos os casos, lembre-se de que apenas as árvores balanceadas (AVL, Rubro-Negra, etc.) oferecem essa garantia. Árvores binárias comuns podem degenerar e perder a eficiência.
Gabarito: letra E
Link permanente: /questoes/qq805496