Cesgranrio 2018 · Informática

Question

Em uma árvore AVL com grande quantidade de nós, o custo para inclusão de um nó no meio da árvore é proporcional a

A) log(n)
B) n
C) n log(n)
D) n2
E) n2 log(n)

Accepted Answer

Gabarito oficial: A. # Comentário da Questão

A alternativa **A está correta** porque a operação de inserção em uma árvore AVL respeita a propriedade fundamental desse tipo de árvore balanceada: a diferença de altura entre as subárvores esquerda e direita de qualquer nó nunca ultrapassa 1. Isso garante que a árvore permaneça aproximadamente balanceada, mantendo a altura sempre proporcional a log(n). A inserção envolve três etapas — busca do ponto de inserção, inserção do nó e rebalanceamento — todas executadas em O(log n).

O rebalanceamento é o diferencial que mantém a complexidade logarítmica. Quando necessário, realiza-se no máximo O(log n) operações de rotação (simples ou dupla), já que apenas os nós no caminho da raiz até o ponto inserido podem sair do equilíbrio. Embora pareça custoso, rotações são operações O(1), então o custo total permanece O(log n).

As alternativas incorretas confundem a complexidade de operações em estruturas não balanceadas ou inadequadas. A opção **B (n)** seria custo de operação linear em lista ligada; **C (n log n)** lembra a complexidade de ordenação merge sort; **D (n²)** típica de busca desorganizada; **E (n² log n)** não descreve nenhuma estrutura comum. A questão explora o conceito central de árvores balanceadas: reduzir altura a log(n) usando propriedades de balanceamento.

Informática — Cesgranrio 2018

Mais questões de Informática

Fonte