GabaritoA — log(n)
Gabarito: letra A. A inserção em uma árvore AVL – estrutura binária balanceada – tem complexidade O(log n) no pior caso, tanto pela busca da posição de inserção quanto pelo rebalanceamento (rotações). O contexto da questão (Wikipédia) confirma que "as operações de busca, inserção e remoção de elementos possuem complexidade O(log n)".
A expressão "no meio da árvore" não altera essa análise: a AVL é naturalmente balanceada, e o caminho percorrido da raiz até o local de inserção tem altura O(log n). As rotações, quando necessárias, também são executadas em tempo constante O(1) ao longo do caminho de volta, perpetuando a complexidade logarítmica.
Operação | Estrutura | Complexidade (pior caso) | Justificativa |
|---|---|---|---|
Inserção | Árvore AVL | O(log n) | Busca binária pela posição + rebalanceamento com rotações O(1) ao longo do caminho de altura O(log n) |
Inserção | Árvore binária de busca (desbalanceada) | O(n) | Pior caso: árvore degenerada (linear), busca sequencial |
Inserção | Lista encadeada | O(n) | Busca linear pela posição |
Inserção | Vetor ordenado | O(n) | Deslocamento de elementos para abrir espaço |
Inserção | Tabela hash (média) | O(1) | Função hash direta (sem colisões) |
A inserção em AVL demanda localizar a posição correta (busca binária, O(log n)) e, se o balanceamento for violado, realizar uma ou mais rotações (cada rotação é O(1) e ocorre no máximo ao longo de um caminho de altura O(log n)). Logo, o custo total é O(log n).
O(n) corresponderia a uma busca linear, típica de listas encadeadas ou árvores degeneradas (ex: árvore binária de busca sem balanceamento em pior caso). Em uma AVL, a altura é mantida O(log n), portanto linear está incorreto.
O(n log n) aparece em algoritmos como a ordenação por intercalação (merge sort). Não é a complexidade de uma única inserção em AVL, que é O(log n).
O(n²) é típico de algoritmos como bubble sort ou insertion sort em vetores. Não se aplica à inserção em AVL.
O(n² log n) combina fatores ainda maiores, sem fundamento para uma estrutura balanceada. Trata-se de um distrator sem correspondência teórica.
"No meio da árvore" pode sugerir que a inserção exige deslocamento linear de nós, como ocorreria em um vetor ou em uma árvore desbalanceada. Lembre-se: a AVL é balanceada – a altura é sempre O(log n), e a busca/inserção segue esse limite. O "meio" é apenas um ponto qualquer da estrutura, não um fator que degrade a complexidade.
Resumo: A complexidade da inserção em AVL é O(log n), resposta letra A.
Link permanente: /questoes/cg011424