Uma árvore AVL (Adelson-Velsky e Landis) é uma árvore binária de busca auto-balanceada onde a diferença de altura entre as subárvores esquerda e direita de qualquer nó é no máximo 1. Isso garante que a árvore permaneça aproximadamente balanceada, proporcionando operações eficientes de inserção, remoção e busca.

As árvores AVL foram as primeiras árvores binárias de busca auto-balanceadas a serem inventadas, em 1962, por Georgy Adelson-Velsky e Evgenii Landis. Elas são amplamente utilizadas em aplicações que exigem operações rápidas de busca e atualização, como bancos de dados e sistemas de arquivos.

As principais propriedades de uma árvore AVL incluem: o balanceamento automático, que mantém a altura da árvore em O(log n), garantindo eficiência nas operações; a ordenação dos elementos, facilitando buscas rápidas; e a estrutura hierárquica que organiza os dados de forma eficiente. As rotações (simples e duplas) são usadas para restaurar o balanceamento após inserções e remoções.

A busca em uma árvore AVL é semelhante à busca em uma árvore binária de busca padrão, aproveitando a ordenação dos elementos para localizar rapidamente o valor desejado.

A inserção em uma árvore AVL começa como em uma árvore binária de busca, localizando a posição correta para o novo nó. Após a inserção, é necessário verificar o balanceamento da árvore e, se necessário, realizar rotações para restaurar o equilíbrio. Para entender as operações de inserção em árvores binárias de busca, você pode visitar o nosso simulador de árvore binária de busca.

A remoção em uma árvore AVL também segue o processo de uma árvore binária de busca, mas após a remoção, é necessário verificar e restaurar o balanceamento da árvore, se necessário, utilizando rotações apropriadas.

O balanceamento em uma árvore AVL é mantido através do cálculo do fator de balanceamento para cada nó, que é a diferença entre as alturas das subárvores esquerda e direita. Se o fator de balanceamento de um nó se tornar maior que 1 ou menor que -1 após uma inserção ou remoção, a árvore está desbalanceada e precisa ser corrigida.

Existem quatro casos principais de desbalanceamento que podem ocorrer em uma árvore AVL, cada um exigindo uma rotação específica para restaurar o equilíbrio: