Qual a diferença de uma árvore binária de busca para uma AVL?

Passo 1

O enunciado pergunta qual a diferença entre uma árvore binária de busca (BST) e uma árvore AVL, que são estruturas de dados usadas para armazenar e buscar itens de forma ordenada. Vamos revisar as definições, as propriedades de balanceamento e o impacto na performance.

Passo 2

Uma árvore binária de busca (BST) é uma árvore em que cada nó possui no máximo dois filhos, e para todo nó com valor X vale: todos os valores na subárvore esquerda são menores que X, e todos os valores na subárvore direita são maiores que X. Não há nenhuma garantia de equilíbrio entre as alturas das subárvores, então a BST pode degeneratedar em uma lista ligada no pior caso.

Passo 3

Uma árvore AVL é uma BST autocontrolada que mantém o fator de balanceamento de cada nó sempre em -1, 0 ou +1. O fator de balanceamento é definido como a diferença entre as alturas das subárvores esquerda e direita. Sempre que uma operação de inserção ou remoção quebra essa condição, a AVL realiza rotações (simples ou duplas) para restaurar o equilíbrio.

Passo 4

Como consequência, uma BST comum pode ter complexidade de busca, inserção e remoção de O(n) no pior caso (quando fica degenerada), enquanto na AVL essas operações são garantidas em O(log n) graças ao balanceamento. O custo extra da AVL está nas rotações que garantem essa altura controlada.

Passo 5

Portanto, a principal diferença está no balanceamento: a BST não impõe restrições de altura e pode ficar muito desequilibrada, já a AVL impõe restrições e usa rotações para manter a árvore sempre balanceada.

Resposta

Uma árvore AVL é uma árvore binária de busca que impõe um fator de balanceamento (-1, 0 ou +1) em cada nó e faz rotações para mantê-lo, garantindo busca, inserção e remoção em O(log n) no pior caso. A BST comum não tem esse mecanismo e pode degenerar em O(n).

Exercícios relacionados