Defina árvores A V L (à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ó v, o fator de balanceamento
\text{fb}(v) = h\bigl(\text{subárvore esquerda de }v\bigr) \;-\; h\bigl(\text{subárvore direita de }v\bigr)áá
satisfaz
\text{fb}(v)\in\{-1,0,1\}.
Aqui h(\cdot) é a altura da subárvore. Essa condição garante que a altura total da árvore com n nós seja O(\log n).

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ó v tivermos |\text{fb}(v)|>1, 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 \text{fb}(v)\in\{-1,0,1\}.

Passo 4

Por que usar árvores AVL:
  1. Garantia de altura O(\log n) no pior caso, diferente de uma BST não balanceada, cuja altura pode chegar a O(n).
  2. Todas as operações básicas — busca, inserção e remoção — ficam com complexidade O(\log n) no pior caso.
  3. As rotações custam O(1) cada, e o número de rotações por operação é amortizado constante.

Passo 5

Aplicações em diversos algoritmos e estruturas:
  1. Implementações padrão de dicionários e conjuntos em bibliotecas (por ex., std::map e std::set em C ++).
  2. Índices secundários em sistemas de banco de dados, onde buscas, inserções e deleções precisam ser rápidas e balanceadas.
  3. Gerência de memória dinâmica: listas de blocos livres podem ser mantidas em AVL para velocidade de alocação e liberação.
  4. Algoritmos de geometria computacional (sweep-line), onde se mantém conjuntos de segmentos ordenados por coordenada y.
  5. 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 \{-1,0,1\}. Esse balanceamento é mantido por rotações simples ou duplas após inserções e remoções, assegurando altura O(\log n). 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.