Estruturas de árvore balanceada: identificando a AVL
Gabarito: letra C. A única estrutura que utiliza fator de balanceamento e rotações para manter altura O(log n) é a árvore AVL, conforme descrição direta do enunciado. As demais alternativas descrevem outras árvores (trie, ABB, B, heap), cada uma com suas características, mas nenhuma atende aos requisitos específicos de rotação e fator de balanceamento.
A questão testa a capacidade de relacionar a descrição de uma estrutura (altura logarítmica, operações de rotação e verificação de fator de balanceamento) ao tipo correto de árvore. Cada alternativa apresenta uma afirmação verdadeira sobre um tipo diferente, mas apenas a árvore AVL casa exatamente com os mecanismos citados no enunciado.
Conteúdo de apoio (Wikipédia):
"Árvore AVL é uma árvore binária de busca balanceada... As operações de busca, inserção e remoção de elementos possuem complexidade O(log n)... Para garantir essa propriedade, a cada inserção ou remoção o fator de balanço deve ser atualizado... aplicar a operação de rotação necessária."
Estrutura | Característica principal | Mecanismo de balanceamento | Altura proporcional a log(n) | Adequação à descrição do enunciado |
|---|
Trie compacta | Compacta prefixos comuns entre strings | Não utiliza balanceamento por altura | Não | ❌ |
ABB sem balanceamento | Organiza nós por comparações sucessivas | Não possui | Não (pode degenerar para O(n)) | ❌ |
AVL | Fator de balanceamento e rotações | Rotações simples/duplas | Sim (O(log n)) | ✅ |
Árvore B | Múltiplos filhos por nó, otimizada para disco | Split e merge de nós | Sim | ❌ |
Heap | Propriedade de prioridade (máximo/mínimo) | Não utiliza rotações | Não (não é adequada para buscas ordenadas) | ❌ |
Alternativa A — ❌ Incorreta
A trie compacta é uma estrutura de prefixos para strings, mas não usa balanceamento por altura nem rotações. Sua eficiência vem da compressão de prefixos, não de critérios de altura. Portanto, não atende à descrição do enunciado.
Alternativa B — ❌ Incorreta
Uma árvore binária de busca (ABB) sem balanceamento pode degenerar para O(n) em inserções sequenciais, não mantém altura proporcional a log(n). A afirmação em si é correta, mas não corresponde à estrutura balanceada descrita.
Alternativa C — ✅ Correta ⟵ GABARITO
A árvore AVL é exatamente a estrutura que utiliza fator de balanceamento (diferença de alturas entre subárvores limitada a -1, 0 ou 1) e rotações (simples ou duplas) para manter a altura O(log n) após inserções e remoções. É a única que atende aos requisitos do enunciado.
Alternativa D — ❌ Incorreta
A árvore B é uma árvore de múltiplos nós (não binária), otimizada para disco, e mantém balanceamento através de split e merge de nós, não por rotações. Embora também tenha altura logarítmica, o mecanismo de balanceamento é diferente – não há rotações.
Alternativa E — ❌ Incorreta
O heap (max-heap ou min-heap) mantém a propriedade de prioridade (pai maior/menor que filhos), mas não é uma árvore de busca – não permite busca eficiente de um valor qualquer (a busca é O(n) no pior caso) nem percurso ordenado simples. A afirmação é verdadeira sobre o heap, mas não se enquadra na estrutura solicitada.
Gabarito: letra C