Sobre a estrutura de dados árvore AVL, analise as afirmativas a seguir. I. Ela é uma árvore binária. II. Seu nó raiz, se possui subárvore (à direita ou esquerda), ela é binária. III. Ela não é, necessariamente, uma árvore completa. IV. Se sua altura é h, a altura das subárvores da raiz, à esquerda e à direita, respectivamente, podem ser h – 1 e h – 2. V. A operação completa de inserção de um nó tem, no pior caso, complexidade de ordem constante O(1). Está correto somente o que se afirma em
- A)I, II, III e IV.
Correta, pois I, II, III e IV estão de acordo com as propriedades de uma árvore AVL, e a V é falsa.
- B)III e IV.
Errada, porque I e II também estão corretas, além de III e IV.
- C)I, II, III, IV e V.
Errada, porque a afirmativa V é falsa: inserção em AVL não é O(1) no pior caso.
- D)I, II, III e V.
Errada, porque a afirmativa V é falsa e I, II, III e IV estão corretas.
- E)III, IV e V.
Errada, porque I e II também são verdadeiras, não apenas III e IV.
Gabarito: A
A árvore AVL é uma árvore binária de busca que se mantém balanceada: para cada nó, a diferença de altura entre as subárvores esquerda e direita não pode passar de 1. Em outras palavras, ela não vira uma “bagunça torta” como uma árvore qualquer, porque faz rotações para corrigir o desbalanceamento após inserções e remoções. Por isso, a afirmativa I está correta: AVL é, sim, uma árvore binária. A II também está correta porque, sendo uma árvore binária, qualquer nó pode ter no máximo duas subárvores, uma à esquerda e outra à direita. A III está correta porque AVL não precisa ser uma árvore completa; ela precisa ser balanceada, não perfeita nem cheia em todos os níveis. A IV também pode ocorrer: se a altura da raiz é h, as alturas das subárvores podem diferir em até 1, então combinações como h - 1 e h - 2 são compatíveis com a regra de balanceamento. Já a V está errada, porque inserir em AVL não tem custo constante no pior caso: você precisa percorrer a árvore e eventualmente fazer rotações, então a complexidade é O(log n), não O(1). Assim, o conjunto correto é I, II, III e IV. Em prova, a banca costuma misturar uma verdade estrutural com um exagero de complexidade para ver se você cai no canto da sereia.