Questão de Tecnologia da Informação · CESGRANRIO BASA 01/2018 (nº 32)

Uma árvore AVL é uma árvore binária de busca que se autoequilibra: após cada inclusão ou remoção, ela verifica se a diferença de altura entre os lados esquerdo e direito de cada nó é no máximo 1, e se não for, faz rotações para corrigir. Por isso, a altura da árvore é sempre O(log n), e qualquer operação de busca, inclusão ou remoção percorre no máximo um caminho da raiz até uma folha, com custo proporcional à altura.

• (A) Correta: O custo é proporcional à altura da árvore, que é O(log n) — mesmo incluindo no "meio", você desce da raiz até a posição correta, e as rotações de balanceamento são feitas apenas no caminho percorrido, com custo constante por nível.
• (B) Incorreta: O custo O(n) seria o de percorrer todos os nós, o que não acontece numa AVL, pois a busca binária descarta metade dos nós a cada passo, e o balanceamento garante que a altura nunca vire uma lista linear.
• (C) Incorreta: O(n log n) seria o custo de inserir n nós um a um (cada um custa log n), mas a questão pede o custo de uma única inclusão, não de todas.
• (D) Incorreta: O(n²) seria típico de algoritmos de ordenação ingênuos ou de inserir em uma árvore degenerada (lista), o que não ocorre numa AVL, pois ela se reequilibra.
• (E) Incorreta: O(n² log n) é um custo absurdo para uma operação simples; não há nenhum processo na AVL que exija varrer a árvore inteira ou fazer múltiplas passagens quadráticas para inserir um nó.

Armadilha da banca (no distrator mais tentador, a letra B): muitos alunos pensam que "inserir no meio" exige deslocar ou reorganizar todos os nós seguintes, como numa lista ou vetor. Mas numa árvore binária, "meio" é apenas uma posição lógica; você não move outros nós — apenas ajusta ponteiros locais e faz rotações limitadas. A pegadinha é confundir estrutura de dados linear (onde inserir no meio custa O(n)) com árvore balanceada (onde o custo é sempre proporcional à altura, O(log n)).