Árvore AVL
# Árvore AVL

Árvore AVL é uma árvore binária de busca balanceada, ou seja, uma árvore balanceada (árvore completa) são as árvores que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências idênticas. Contudo, para garantir essa propriedade em aplicações dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada operação sobre seus nós (inclusão ou exclusão), para ser alcançado um custo de algoritmo com o tempo de pesquisa tendendo a $O(\log n)$.
As operações de busca, inserção e remoção de elementos possuem complexidade $O(\log n)$(no qual $n$ é o número de elementos da árvore), que são aplicados a árvore de busca binária.
O nome AVL vem de seus criadores soviéticos Adelson Velsky e Landis, e sua primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962.
Nessa estrutura de dados cada elemento é chamado de nó. Cada nó armazena uma chave e dois ponteiros, uma para a subárvore esquerda e outro para a subárvore direita.
No presente artigo serão apresentados: os conceitos básicos, incluindo uma proposta de estrutura; apresentação das operações busca, inserção e remoção, todas com complexidade $O(\log n)$.

## História

Esta estrutura foi criada em 1962 pelos soviéticos Adelson Velsky e Landis que a criaram para que fosse possível inserir e buscar um elemento em tempo c.log (n) operações, onde n é o número de elementos contido na árvore. Tal estrutura foi a primeira árvore binária balanceada criada.

## Conceitos básicos
### Definição

Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.
Pela definição fica estabelecido que todos os nós de uma árvore AVL devem respeitar a seguinte propriedade:
|h$_d$(u) - h$_e$(u)| ≤ 1, onde h$_d$(u) é a altura da subárvore direita do nó u e h$_e$(u) é a altura da subárvore esquerda do nó u.
O valor h$_d$(u) - h$_e$(u) é denominado fator de balanço do nó. Quando um nó possui fator de balanço com valor -1, 0 ou 1 então o mesmo é um nó regulado. Todos os nós de uma árvore AVL são regulados, caso contrário a árvore não é AVL.

### Estrutura

Proposta de estrutura dos nós de uma árvore AVL básica, com chave do tipo inteiro:
O campo chave armazena o valor da chave. Os campos esq e dir são ponteiros para as subárvores esquerda e direita, respectivamente. O campo fb armazena o fator de balanço.
Definição da estrutura da árvore:

### Balanceamento

Toda árvore AVL é balanceada, isto é, sua altura é O(log n).
A vantagem do balanceamento é possibilitar que a busca seja de complexidade O(log n). Entretanto, as operações de inserção e remoção devem possuir custo similar. No caso da árvore AVL, a inserção e remoção têm custo O(log n).
Por definição, todos os nós da AVL devem ter fb = -1, 0 ou 1.
Para garantir essa propriedade, a cada inserção ou remoção o fator de balanço deve ser atualizado a partir do pai do nó inserido até a raiz da árvore. Na inserção basta encontrar o primeiro nó desregulado (fb= -2 ou fb= 2), aplicar o operação de rotação necessária, não havendo necessidade de verificar os demais nós. Na remoção a verificação deverá prosseguir até a raiz, podendo requerer mais de uma rotação.
Uma árvore AVL sempre terá um tamanho menor que:
$\log _{\varphi }({\sqrt {5}}(n+2))-2={\frac {\log _{2}({\sqrt {5}}(n+2))}{\log _{2}(\varphi )}}-2=\log _{\varphi }(2)\cdot \log _{2}({\sqrt {5}}(n+2))-2\approx 1.44\log _{2}(n+2)-0.328$
Onde n é o número de elementos da árvore e $\varphi$ é a proporção áurea.

### Complexidade

A árvore AVL tem complexidade $O(\log n)$ para todas operações e ocupa espaço n, onde n é o número de nós da árvore.
Complexidade da árvore AVL em notação O :
| | Média | Pior caso |
| Espaço | $O(n)$ | $O(n)$ |
| Busca | $O(\log n)$ | $O(\log n)$ |
| Inserção | $O(\log n)$ | $O(\log n)$ |
| Deleção | $O(\log n)$ | $O(\log n)$ |

## Operações
### Busca

A busca é a mesma utilizada em árvore binária de busca.
A busca pela chave de valor K inicia sempre pelo nó raiz da árvore.
Seja pt_u um ponteiro para o nó u sendo verificado. Caso o pt_u seja nulo então a busca não foi bem sucedida (K não está na árvore ou árvore vazia). Verificar se a chave K igual pt_u->chave (valor chave armazenado no nó u), então a busca foi bem sucedida. Caso contrário, se K < pt_u->chave então a busca segue pela subárvore esquerda; caso contrário, a busca segue pela subárvore direita.

#### Algoritmo de busca

Exemplo de algoritmo de busca em Java.

### Inserção

Para inserir um novo nó de valor K em uma árvore AVL é necessária uma busca por K nesta mesma árvore. Após a busca o local correto para a inserção do nó K será em uma subárvore vazia de uma folha da árvore. Depois de inserido o nó, a altura do nó pai e de todos os nós acima deve ser atualizada. Em seguida o algoritmo de rotação simples ou dupla deve ser acionado para o primeiro nó pai desregulado.

#### Algoritmo recursivo

Os parâmetros p e mudou_h são passados por referência. O ponteiro p aponta para o nó atual. O parâmetro mudou_h é do tipo lógico e informa ao chamador se a subárvore apontada por p mudou sua altura.

#### Como identificar mudança de altura?

Considerar que o nó p é raiz da subárvore T$_p$ e houve inserção em uma de suas subárvores.
Caso a subárvore T$_p$ tenha mudado de altura, decrementar fb (inserção na subárvore esquerda) ou incrementar fb (inserção na subárvore direita).
Caso 1: Ao inserir um nó folha, a subárvore T$_p$ passa de altura 0 para altura 1, então T$_p$ mudou de altura.
Caso 2: fb=0 antes da inserção foi alterado para 1 ou -1, então a subárvore T$_p$ mudou de altura.
Caso 3: fb=1 ou -1 antes da inserção, passou a ter valor 0, então a subárvore T$_p$ não mudou de altura.
Caso 4: O fb passou a ter valor -2 ou 2 após a inserção, então há necessidade de aplicação de alguma operação de rotação. Após a rotação, a subárvore T$_p$ terá a mesma altura anterior à inserção.
Exemplo de algoritmo de inserção em Java
Algoritmos de complemento à inserção e/ou algoritmos para identificar desbalanceamento em Java
Rotação para Direita e para Esquerda em Java

### Remoção

O primeiro passo para remover uma chave K consiste em realizar uma busca binária a partir do nó raiz. Caso a busca encerre em uma subárvore vazia, então a chave não está na árvore e a remoção não pode ser realizada. Caso a busca encerre em um nó u o nó que contenha a chave então a remoção poderá ser realizada da seguinte forma:
Caso 1: O nó u é uma folha da árvore, apenas exclui-lo.
Caso 2: O nó u tem apenas uma subárvore, necessariamente composta de um nó folha, basta apontar o nó pai de u para a única subárvore e excluir o nó u.
Caso 3: O nó u tem duas subárvores: localizar o nó v predecessor ou sucessor de K, que sempre será um nó folha ou possuirá apenas uma subárvore; copiar a chave de v para o nó u; excluir o nó v a partir da respectiva subárvore de u.
O último passo consiste em verificar a desregulagem de todos nós a partir do pai do nó excluído até o nó raiz da árvore. Aplicar rotação simples ou dupla em cada nó desregulado.

#### Algoritmo recursivo

Exemplo de algoritmo de remoção em Java
Algoritmos auxilares na remoção

#### Como identificar mudança de altura na remoção ?

Considerar que o nó p é raiz da subárvore T$_p$ e houve remoção em uma de suas subárvores.
Caso a subárvore T$_p$ tenha mudado de altura, incrementar fb (remoção na subárvore esquerda) ou decrementar fb (remoção na subárvore direita).
Caso 1: Ao remover um nó folha, a subárvore T$_p$ passa de altura 1 para altura 0, então T$_p$ mudou de altura.
Caso 2: fb=0 antes da remoção foi alterado para 1 (remoção à esquerda) ou -1 (remoção à direita), então a subárvore T$_p$ não mudou de altura.
Caso 3: fb=1 ou -1 antes da remoção à direita e à esquerda, respectivamente, passando a ter valor 0, então a subárvore T$_p$ mudou de altura.
Caso 4: fb passou a ter valor -2 ou 2 após a remoção, então houve necessidade de aplicação de rotação. Após a rotação dupla T$_p$ muda de altura, exceto quando u=0 (antes da remoção- caso não relatado na literatura).

### Rotação

A operação básica em uma árvore AVL geralmente envolve os mesmos algoritmos de uma árvore de busca binária desbalanceada. A rotação na árvore AVL ocorre devido ao seu desbalanceamento, uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho".
Para garantirmos as propriedades da árvore AVL rotações devem ser feitas conforme necessário após operações de remoção ou inserção. Seja P o nó pai, FE o filho da esquerda de P e FD o filho da direita de P podemos definir 4 tipos diferentes de rotação:

#### Rotação simples à direita

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a 2 e a diferença das alturas h dos filhos de FE é igual a 1. O nó FE deve tornar o novo pai e o nó P deve se tornar o filho da direita de FE. Segue pseudocódigo:
* Seja Y o filho à esquerda de X
* Torne o filho à direita de Y o filho à esquerda de X.
* Torne X o filho à direita de Y

#### Rotação à esquerda

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a -2 e a diferença das alturas h dos filhos de FD é igual a -1. O nó FD deve tornar o novo pai e o nó P deve se tornar o filho da esquerda de FD. Segue pseudocódigo:
* Seja Y o filho à direita de X
* Torne o filho à esquerda de Y o filho à direita de X.
* Torne X filho à esquerda de Y
** Rotação simples a esquerda

#### Rotação dupla à direita

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a 2 e a diferença das alturas h dos filhos de FE é igual a -1. Nesse caso devemos aplicar uma rotação à esquerda no nó FE e, em seguida, uma rotação à direita no nó P.
Deve ser observado que as 3 possíveis combinações de alturas da subárvores T$_2$ e T$_3$ constam da figura (h, h-1; h, h; e h-1, h), implicando em nos respectivos balanços do nó u (0/0/-1) e do nó p (1/0/0).

#### Rotação dupla à esquerda

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a -2 e a diferença das alturas h dos filhos de FD é igual a 1. Nesse caso devemos aplicar uma rotação à direita no nó FD e, em seguida, uma rotação à esquerda no nó P.
* Rotação dupla à esquerda

##### Algoritmo de rotação à direita

Cabe ressaltar, apesar de não estar relatado na literatura, que na remoção poderá ocorre a situação na qual u^.fb=0. Neste caso deverá ser aplicada rotação simples e o fator de balanço dos nós u e p serão respectivamente 1 e -1.

#### Rotação à esquerda

Caso o fator de balanço do nó p tenha valor +2, então haverá necessidade de aplicar rotação simples ou dupla à esquerda.
Para identificar se qual rotação aplicar, bastará analisar o fator de balanço do nó u, raiz da subárvore direita do nó p.

##### Rotação simples à esquerda

Caso o fator de balanço do nó u seja +1, então deverá ser aplicada uma rotação simples à esquerda. A figura a seguir mostra a configuração da árvore antes e depois da rotação.

##### Rotação dupla à esquerda

Caso o fator de balanço do nó u seja -1, então deverá ser aplicada uma rotação dupla à esquerda. A figura a seguir mostra a configuração da árvore antes e depois da rotação.

## Aplicações

A árvore AVL é muito útil, pois executa as operações de inserção, busca e remoção em tempo O(log n). Comparado-a com a árvore rubro-negra, a AVL é mais rápido nas aplicações que fazem uma quantidade excessiva de buscas, porém esta estrutura é um pouco mais lenta para inserção e remoção. Isso se deve ao fato de as árvores AVL serem mais rigidamente balanceadas.

### Dicionários

Árvore AVL pode ser usada para formar um dicionário de uma linguagem ou de programas, como os opcodes de um assembler ou um interpretador.

### Geometria Computacional

Árvore AVL pode ser usada também na geometria computacional por ser uma estrutura muito rápida. Sem uma estrutura com complexidade O(log n) alguns algoritmos da geometria computacional poderiam demorar dias para serem executados.

### Conjuntos

Árvore AVL podem ser empregadas na implementação de conjuntos, principalmente aqueles cujas chave não são números inteiros.
A complexidade das principais operações de conjuntos usando árvore AVL:
* Inserir - O(log n);
* Remover - O(log n);
* Pertence - O(log n);
* União - O(n.log n);
* Interseção - O(n.log n).