GabaritoA — O(n)
Gabarito: letra A — a verificação se uma árvore binária de busca é AVL balanceada exige percorrer todos os nós uma vez, calculando alturas e conferindo o fator de balanceamento, resultando em complexidade O(n).
A questão testa a diferença entre a complexidade das operações em uma árvore AVL (busca, inserção, remoção: O(log n)) e a complexidade de verificar se uma árvore arbitrária obedece à propriedade AVL. Para cada nó, é necessário conhecer a altura das subárvores esquerda e direita; isso pode ser feito em uma única travessia pós-ordem, onde cada nó é visitado uma vez e o trabalho por nó é constante. Portanto, o custo total é linear no número de nós.
O candidato pode confundir a complexidade das operações de busca/inserção/remoção em uma AVL (O(log n)) com a complexidade de verificar se uma árvore é AVL. A verificação exige examinar todos os nós, portanto O(n).
Correta. Percorrer a árvore, calcular alturas dos nós e verificar a condição |hd - he| ≤ 1 para cada nó requer visitar todos os nós exatamente uma vez, resultando em O(n).
O(log n) é a complexidade típica das operações em uma árvore AVL já balanceada, mas não da verificação de balanceamento, que precisa inspecionar todos os nós.
O(n log n) seria o custo de, para cada nó, percorrer sua subárvore para calcular altura, o que não é necessário: as alturas podem ser computadas de forma eficiente durante uma única travessia.
O(n²) é muito maior que o necessário — o problema é linear.
O(log² n) também é inferior a O(n) e não corresponde ao custo de percorrer todos os nós.
Para questões de complexidade, identifique se a operação exige percorrer toda a estrutura (O(n)) ou apenas um caminho da raiz até a folha (O(log n) em árvores balanceadas). A verificação de propriedades globais, como balanceamento, geralmente é O(n).
Gabarito: letra A.
Link permanente: /questoes/qq896692