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 é,
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.