Estrutura de dados e algoritmos - Árvores AVL

E se a entrada para a árvore de pesquisa binária vier de maneira classificada (crescente ou decrescente)? Ficará assim -

Observa-se que o desempenho de pior caso do BST é o mais próximo dos algoritmos de busca linear, ou seja, Ο (n). Em dados em tempo real, não podemos prever o padrão de dados e suas frequências. Assim, surge a necessidade de equilibrar o BST existente.

Nomeado após seu inventor Adelson, Velski E Landis, AVL treessão árvore de pesquisa binária de equilíbrio de altura. A árvore AVL verifica a altura das subárvores esquerda e direita e garante que a diferença não seja maior do que 1. Esta diferença é chamada deBalance Factor.

Aqui, vemos que a primeira árvore está equilibrada e as duas próximas árvores não estão equilibradas -

Na segunda árvore, a subárvore esquerda de C tem altura 2 e a subárvore direita tem altura 0, então a diferença é 2. Na terceira árvore, a subárvore direita de Atem altura 2 e falta a esquerda, então é 0 e a diferença é 2 novamente. A árvore AVL permite que a diferença (fator de equilíbrio) seja apenas 1.

BalanceFactor = height(left-sutree) − height(right-sutree)

Se a diferença na altura das subárvores esquerda e direita for maior que 1, a árvore é balanceada usando algumas técnicas de rotação.

Rotações AVL

Para se equilibrar, uma árvore AVL pode realizar os seguintes quatro tipos de rotações -

  • Rotação à esquerda
  • Rotação direita
  • Rotação esquerda-direita
  • Rotação direita-esquerda

As duas primeiras rotações são rotações simples e as duas rotações seguintes são rotações duplas. Para ter uma árvore desequilibrada, precisamos pelo menos de uma árvore de altura 2. Com esta árvore simples, vamos entendê-los um por um.

Rotação Esquerda

Se uma árvore se torna desequilibrada, quando um nó é inserido na subárvore direita da subárvore direita, então realizamos uma única rotação à esquerda -

Em nosso exemplo, nó Atornou-se desequilibrado porque um nó é inserido na subárvore direita da subárvore direita de A. Executamos a rotação para a esquerda, tornandoA a subárvore esquerda de B.

Rotação à Direita

A árvore AVL pode ficar desequilibrada, se um nó for inserido na subárvore esquerda da subárvore esquerda. A árvore então precisa de uma rotação correta.

Conforme representado, o nó desequilibrado se torna o filho direito de seu filho esquerdo executando uma rotação para a direita.

Rotação Esquerda-Direita

Rotações duplas são versões ligeiramente complexas de versões já explicadas de rotações. Para melhor entendê-los, devemos anotar cada ação realizada durante a rotação. Vamos primeiro verificar como realizar a rotação esquerda-direita. Uma rotação esquerda-direita é uma combinação de rotação esquerda seguida por rotação direita.

Estado Açao
Um nó foi inserido na subárvore direita da subárvore esquerda. Isto fazCum nó desequilibrado. Esses cenários fazem com que a árvore AVL execute a rotação da esquerda para a direita.
Primeiro executamos a rotação à esquerda na subárvore esquerda de C. Isto fazA, a subárvore esquerda de B.
C ainda está desequilibrado, porém agora, é por causa da subárvore esquerda da subárvore esquerda.
Devemos agora girar a árvore para a direita, fazendo B o novo nó raiz desta subárvore. C agora se torna a subárvore direita de sua própria subárvore esquerda.
A árvore agora está equilibrada.

Rotação direita-esquerda

O segundo tipo de rotação dupla é a rotação direita-esquerda. É uma combinação de rotação para a direita seguida de rotação para a esquerda.

Estado Açao
Um nó foi inserido na subárvore esquerda da subárvore direita. Isto fazA, um nó desequilibrado com fator de equilíbrio 2.
Primeiro, fazemos a rotação correta ao longo C nó, fazendo C a subárvore direita de sua própria subárvore esquerda B. Agora,B torna-se a subárvore certa de A.
A ainda está desequilibrado por causa da subárvore direita de sua subárvore direita e requer uma rotação para a esquerda.
Uma rotação para a esquerda é realizada fazendo B o novo nó raiz da subárvore. A torna-se a subárvore esquerda de sua subárvore direita B.
A árvore agora está equilibrada.