ÁRVORE AVL (ESTRUTURAS DE DADOS)

A árvore AVL foi inventada por GM Adelson - Velsky e EM Landis em 1962. A árvore é chamada de AVL em homenagem a seus inventores.

A árvore AVL pode ser definida como uma árvore de pesquisa binária com altura balanceada em que cada nó está associado a um fator de equilíbrio que é calculado subtraindo a altura de sua subárvore direita daquela de sua subárvore esquerda.

Diz-se que a árvore está balanceada se o fator de equilíbrio de cada nó estiver entre -1 e 1, caso contrário, a árvore ficará desequilibrada e precisará ser balanceada.

Fator de equilíbrio (k) = altura (esquerda (k)) - altura (direita (k))

Se o fator de equilíbrio de qualquer nó for 1, significa que a subárvore esquerda está um nível acima da subárvore direita.

Se o fator de equilíbrio de qualquer nó for 0, significa que a subárvore esquerda e a subárvore direita contêm altura igual.

Se o fator de equilíbrio de qualquer nó for -1, significa que a subárvore esquerda está um nível abaixo da subárvore direita.

Uma árvore AVL é fornecida na figura a seguir. Podemos ver que o fator de equilíbrio associado a cada nó está entre -1 e +1. portanto, é um exemplo de árvore AVL.

Complexidade

Algoritmo	Caso médio	Pior caso
Espaço	sobre)	sobre)
Procurar	o(log n)	o(log n)
Inserir	o(log n)	o(log n)
Excluir	o(log n)	o(log n)

Operações na árvore AVL

Devido ao fato de que a árvore AVL também é uma árvore de busca binária, todas as operações são realizadas da mesma forma que em uma árvore de busca binária. A busca e o deslocamento não levam à violação da propriedade da árvore AVL. Porém, inserção e exclusão são as operações que podem violar esta propriedade e, portanto, precisam ser revisitadas.

SN	Operação	Descrição
1	Inserção	A inserção na árvore AVL é realizada da mesma forma que em uma árvore binária de busca. No entanto, isso pode levar à violação da propriedade da árvore AVL e, portanto, a árvore pode precisar de balanceamento. A árvore pode ser equilibrada aplicando rotações.
2	Eliminação	A exclusão também pode ser realizada da mesma maneira que em uma árvore de pesquisa binária. A exclusão também pode perturbar o equilíbrio da árvore, portanto, vários tipos de rotações são usados para reequilibrar a árvore.

Por que árvore AVL?

A árvore AVL controla a altura da árvore de pesquisa binária, não permitindo que ela seja distorcida. O tempo necessário para todas as operações em uma árvore de busca binária de altura h é Oh) . No entanto, pode ser estendido para Sobre) se o BST ficar distorcido (ou seja, no pior caso). Ao limitar esta altura ao log n, a árvore AVL impõe um limite superior em cada operação a ser O (log n) onde n é o número de nós.

Rotações AVL

Realizamos rotação na árvore AVL apenas caso o Fator de Equilíbrio seja diferente -1, 0 e 1 . Existem basicamente quatro tipos de rotações que são as seguintes:

Rotação L L: o nó inserido está na subárvore esquerda da subárvore esquerda de A
Rotação R R: o nó inserido está na subárvore direita da subárvore direita de A
Rotação L R: o nó inserido está na subárvore direita da subárvore esquerda de A
Rotação R L: o nó inserido está na subárvore esquerda da subárvore direita de A

Onde o nó A é o nó cujo fator de equilíbrio é diferente de -1, 0, 1.

As duas primeiras rotações LL e RR são rotações simples e as próximas duas rotações LR e RL são rotações duplas. Para uma árvore ficar desequilibrada a altura mínima deve ser no mínimo 2, Vamos entender cada rotação

1. Rotação RR

Quando o BST fica desequilibrado, devido a um nó ser inserido na subárvore direita da subárvore direita de A, então realizamos a rotação RR, a rotação RR é uma rotação anti-horária, que é aplicada na aresta abaixo de um nó com fator de equilíbrio -2

No exemplo acima, o nó A tem fator de equilíbrio -2 porque um nó C é inserido na subárvore direita de A subárvore direita. Realizamos a rotação RR na aresta abaixo de A.

2. Rotação LL

Quando o BST fica desequilibrado, devido a um nó ser inserido na subárvore esquerda da subárvore esquerda de C, então realizamos a rotação LL, a rotação LL é a rotação no sentido horário, que é aplicada na aresta abaixo de um nó com fator de equilíbrio 2.

No exemplo acima, o nó C tem fator de equilíbrio 2 porque um nó A é inserido na subárvore esquerda da subárvore esquerda C. Realizamos a rotação LL na aresta abaixo de A.

3. Rotação LR

As rotações duplas são um pouco mais difíceis do que a rotação única, que já foi explicada acima. Rotação LR = rotação RR + rotação LL, ou seja, a primeira rotação RR é realizada na subárvore e depois a rotação LL é realizada na árvore completa, por árvore completa entendemos o primeiro nó do caminho do nó inserido cujo fator de equilíbrio é diferente de -1 , 0 ou 1.

Vamos entender cada etapa com muita clareza:

Estado	Ação
	Um nó B foi inserido na subárvore direita de A, a subárvore esquerda de C, por causa do qual C se tornou um nó desequilibrado com fator de equilíbrio 2. Este caso é a rotação L R onde: O nó inserido está na subárvore direita da subárvore esquerda de C
	Como rotação LR = rotação RR + rotação LL, portanto, RR (sentido anti-horário) na subárvore com raiz em A é executado primeiro. Ao fazer rotação RR, nó A , tornou-se a subárvore esquerda de B .
	Após realizar a rotação RR, o nó C ainda está desequilibrado, ou seja, possui fator de equilíbrio 2, pois o nó A inserido está à esquerda da esquerda C
	Agora realizamos rotação LL no sentido horário na árvore completa, ou seja, no nó C. nó C agora se tornou a subárvore direita do nó B, A é a subárvore esquerda de B
	O fator de equilíbrio de cada nó agora é -1, 0 ou 1, ou seja, o BST está balanceado agora.

4. Rotação RL

Como já discutido, as rotações duplas são um pouco mais difíceis do que a rotação única, que já foi explicada acima. Rotação R L = rotação LL + rotação RR, ou seja, a primeira rotação LL é realizada na subárvore e depois a rotação RR é realizada na árvore completa, por árvore completa entendemos o primeiro nó do caminho do nó inserido cujo fator de equilíbrio é diferente de -1 , 0 ou 1.

Estado	Ação
	Um nó B foi inserido na subárvore esquerda de C a subárvore direita de A , por causa do qual A se tornou um nó desequilibrado com fator de equilíbrio - 2. Este caso é a rotação RL onde: O nó inserido está na subárvore esquerda da subárvore direita de A
	Como rotação RL = rotação LL + rotação RR, portanto, LL (sentido horário) na subárvore com raiz em C é executado primeiro. Ao fazer rotação RR, nó C tornou-se a subárvore certa de B .
	Depois de realizar a rotação LL, o nó A ainda está desequilibrado, ou seja, tendo fator de equilíbrio -2, que é devido à subárvore direita do nó A da subárvore direita.
	Agora realizamos rotação RR (rotação anti-horária) na árvore completa, ou seja, no nó A. nó C agora se tornou a subárvore direita do nó B e o nó A se tornou a subárvore esquerda de B.
	O fator de equilíbrio de cada nó agora é -1, 0 ou 1, ou seja, o BST está balanceado agora.

P: Construa uma árvore AVL com os seguintes elementos

H, I, J, B, A, E, C, F, D, G, K, L

1. Insira H, I, J

Ao inserir os elementos acima, principalmente no caso de H, o BST fica desequilibrado pois o Fator de Equilíbrio de H é -2. Como o BST está inclinado para a direita, realizaremos a rotação RR no nó H.

A árvore de equilíbrio resultante é:

2. Insira B, A

Ao inserir os elementos acima, especialmente no caso de A, o BST fica desequilibrado porque o fator de equilíbrio de H e I é 2, consideramos o primeiro nó do último nó inserido, ou seja, H. Como o BST de H é inclinado para a esquerda, realizaremos a rotação LL no nó H.

A árvore de equilíbrio resultante é:

3. Insira E

Ao inserir E, o BST fica desequilibrado pois o Fator de Equilíbrio de I é 2, pois se viajarmos de E para I descobrimos que ele está inserido na subárvore esquerda da subárvore direita de I, realizaremos Rotação LR no nó I. LR = rotação RR + LL

3 a) Primeiro realizamos rotação RR no nó B

A árvore resultante após rotação RR é:

3b) Primeiro realizamos rotação LL no nó I

A árvore balanceada resultante após rotação LL é:

4. Insira C, F, D

exemplo de árvore de pesquisa binária

Ao inserir C, F, D, BST fica desequilibrado pois o Fator de Equilíbrio de B e H é -2, pois se viajarmos de D para B descobrimos que ele está inserido na subárvore direita da subárvore esquerda de B, iremos realizar Rotação RL no nó I. RL = rotação LL + RR.

4a) Primeiro realizamos rotação LL no nó E

A árvore resultante após a rotação LL é:

4b) Em seguida, realizamos rotação RR no nó B

A árvore balanceada resultante após rotação RR é:

5. Insira G

Ao inserir G, o BST fica desequilibrado pois o Fator de Equilíbrio de H é 2, pois se viajarmos de G para H, descobrimos que ele está inserido na subárvore esquerda da subárvore direita de H, realizaremos a Rotação LR no nó I. LR = rotação RR + LL.

5 a) Primeiro realizamos rotação RR no nó C

A árvore resultante após rotação RR é:

5 b) Em seguida, realizamos rotação LL no nó H

A árvore balanceada resultante após rotação LL é:

6. Insira K

Ao inserir K, o BST fica desequilibrado, pois o fator de equilíbrio de I é -2. Como o BST está inclinado para a direita de I para K, realizaremos a rotação RR no nó I.