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. |
|
Nó 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. |
|
Nó 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. |