Defina com suas palavras o que é uma árvore AVL e como ela funciona.

Passo 1

A questão pede para definirmos, com nossas próprias palavras, o que é uma árvore AVL e como ela funciona; o conteúdo envolve estruturas de dados, mais especificamente árvores binárias de busca auto-balanceadas e as operações de manutenção de equilíbrio.

Passo 2

Uma árvore AVL é uma variante de árvore binária de busca em que, para cada nó, a diferença de altura entre sua subárvore esquerda e sua subárvore direita (fator de balanceamento) é sempre –1, 0 ou +1. Esse critério garante que a árvore mantenha altura O(log n), favorecendo operações rápidas de busca, inserção e remoção.

Passo 3

O fator de balanceamento de um nó é definido como a altura da subárvore direita menos a altura da subárvore esquerda, isto é,
FB(n)=aáá Sempre que uma operação de inserção ou remoção faz com que algum nó viole |FB|≤1, aplicamos rotações para reequilibrar a árvore.

Passo 4

Existem quatro casos de desbalanceamento e suas rotações correspondentes: rotação simples à direita (caso LL), rotação simples à esquerda (caso RR), rotação dupla (esquerda–direita, caso LR) e rotação dupla (direita–esquerda, caso RL). Cada rotação reajusta vínculos de pai e filho e atualiza fatores de balanceamento localmente até restaurar |FB|≤1 em toda a árvore.

Passo 5

Com essas rotações automáticas após inserções e remoções, a árvore AVL mantém-se sempre aproximadamente equilibrada em altura, garantindo complexidade O(log n) tanto para buscas quanto para inserções e exclusões.

Resposta

Uma árvore AVL é uma árvore binária de busca auto-balanceada que, ao manter o fator de balanceamento (diferença de alturas das subárvores) em –1, 0 ou +1 para todo nó, assegura altura O(log n) e executa rotações (LL, RR, LR, RL) após inserções e remoções para restaurar o equilíbrio.

Exercícios relacionados