Árvores AVL

Uma árvore AVL é um tipo de árvore binária de busca. Nomeada em homenagem aos seus criadores, Adelson-Velsky e Landis, as árvores AVL possuem a propriedade de autobalanceamento dinâmico, além de todas as outras propriedades mostradas pelas árvores binárias de busca.

Uma árvore binária de busca, ou BST (do inglês, binary search tree), é uma estrutura de dados compostas de nós. Ela tem as seguintes garantias:

Cada árvore possui um nó raiz (no topo)
O nó raiz tem zero, um ou dois filhos
Cada nó filho tem zero, um ou dois nós filhos.
Cada nó tem até dois filhos
Para cada nó, seus descendentes da esquerda são menores que o nó atual, que é menor que o descendentes da direita

As árvores AVL têm uma garantia adicional:

A diferença entre as profundidade das camadas do lado direito e esquerdo não pode ser maior que um. Essa diferença é chamada de fator de balanço. Para manter essa garantia, a implementação de uma AVL incluirá um algoritmo para balanceamento da árvore quando a adição de um elemento prejudicar essa garantia.

As árvores AVL têm uma complexidade de tempo de busca, inserção e exclusão, no pior dos casos, de O(log n), onde n é o número de nós na árvore. A complexidade de espaço de pior caso é O(n).

Processo de inserção na AVL

A inserção em uma árvore AVL é similar à inserção em uma árvore binária de busca. Depois de inserir um elemento, no entanto, você precisa ajustar as propriedades da AVL utilizando rotações para esquerda ou para a direita:

Se houver um desbalanceamento na subárvore da direita do filho da esquerda do nó, faça uma rotação dupla à direita.
Se houver um desbalanceamento na subárvore da esquerda do filho da esquerda do nó, faça uma rotação simples à direita.
Se houver um desbalanceamento na subárvore da direita do filho da direita do nó, faça uma rotação simples à esquerda.
Se houver um desbalanceamento na subárvore da esquerda do filho da direita do nó, faça uma rotação dupla à esquerda.

Rotações da árvore AVL

Nas árvores AVL, após cada operação, como inserção e exclusão, o fator de balanceamento de cada nó precisa ser verificado. Se cada nó satisfizer a condição do fator de balanceamento, a operação pode ser concluída. Caso contrário, a árvore precisa ser rebalanceada utilizando as operações de rotação.

Existem quatro rotações e elas são classificadas em dois tipos:

Rotação simples à esquerda (rotação SE): Na rotação simples à esquerda, cada nó se move uma posição para a esquerda da posição atual.
Rotação simples à direita (rotação SD): Na rotação simples à direita, cada nó se move uma posição para a direita da posição atual.
Rotação dupla à direita (rotação DD): As rotações duplas à direita são uma combinação de uma única rotação para a esquerda seguida de uma rotação para a direita. Primeiro, cada nó se move uma posição para a esquerda. Depois, se move uma posição para a direita da posição atual.
Rotação dupla à esquerda (rotação DE): As rotações duplas à esquerda são uma combinação de uma única rotação para a direita seguida de uma rotação para a esquerda. Primeiro, cada nó se move uma posição para a direita. Depois, se move uma posição para a esquerda da posição atual.

Aplicação das árvores AVL: As árvores AVL são benéficas em casos de bancos de dados, onde inserções e exclusões não são frequentes, mas onde você confere as entradas com frequência.