Á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
editarA 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
editarNas á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.