Defina árvores
(às vezes conhecidas por árvores balanceadas por altura). Descreva como e por que as árvores AVL são usadas em uma variedade de algoritmos diferentes.
Passo 1
O enunciado pede para definirmos o que é uma árvore AVL (uma árvore de busca binária balanceada por altura) e explicarmos como e por que ela aparece em diversos algoritmos. O conteúdo envolve estruturas de dados (árvores binárias de busca) e técnicas de balanceamento baseado em alturas para garantir complexidade logarítmica nas operações de busca, inserção e remoção.
Passo 2
Definição de árvore AVL: é uma árvore binária de busca em que, para todo nó
, o fator de balanceamento
satisfaz
Aqui
é a altura da subárvore. Essa condição garante que a altura total da árvore com
nós seja
.
Passo 3
Manutenção do balanceamento: após cada inserção ou remoção de chave, percorre-se o caminho do nó afetado até a raiz, recalculando alturas e fatores de balanceamento. Se em algum nó
tivermos
, aplica-se uma das rotações:
- Rotação simples à esquerda (caso RR),
- Rotação simples à direita (caso LL),
- Rotação dupla (casos LR ou RL).
Essas rotações reorganizam subárvores preservando a ordem da busca e restauram.
Passo 4
Por que usar árvores AVL:
- Garantia de altura
no pior caso, diferente de uma BST não balanceada, cuja altura pode chegar a . - Todas as operações básicas — busca, inserção e remoção — ficam com complexidade
no pior caso. - As rotações custam
cada, e o número de rotações por operação é amortizado constante.
Passo 5
Aplicações em diversos algoritmos e estruturas:
- Implementações padrão de dicionários e conjuntos em bibliotecas (por ex.,
std::map
estd::set
em C). - Índices secundários em sistemas de banco de dados, onde buscas, inserções e deleções precisam ser rápidas e balanceadas.
- Gerência de memória dinâmica: listas de blocos livres podem ser mantidas em AVL para velocidade de alocação e liberação.
- Algoritmos de geometria computacional (sweep-line), onde se mantém conjuntos de segmentos ordenados por coordenada
. - Estruturas derivadas, como árvores de intervalo e árvores 2-D, usam o balanceamento por altura em cada nó para garantir performance.
Resposta
Árvore AVL é uma árvore binária de busca em que em todo nó o fator de balanceamento (diferença de alturas entre subárvores esquerda e direita) fica em
. Esse balanceamento é mantido por rotações simples ou duplas após inserções e remoções, assegurando altura
. Por isso aparece em muitos algoritmos que exigem buscas, inserções e remoções rápidas e com garantias de pior caso, como dicionários de bibliotecas, índices de banco de dados, gerência de memória e algoritmos de geometria computacional.