Arvore AVL

Mais uma vez meus leitores vamos falar sobre estrutura de dados, dessa vez vamos observar arvore AVL, primeiramente uma arvore AVL é uma arvore binaria de busca, ou seja possui limitações no modo de inserir e  no grau da arvore, bom mais uma vez vale lembrar sem ED não existe bons sistemas, nem tudo pode ser feito de maneira intuitiva, bom então essa é mais uma base para o uso efetivo de Big data em suas aplicações, segue o material :

Árvores Balanceadas AVL

---

Definição: Uma árvore é considerada AVL quando a altura de suas subárvores direita e esquerda diferem no máximo 1 unidade, isto é, a árvore permanece sempre balanceada. AVL vem da abreviatura dos nomes de seus criadores G.M. Adelson-Velskii e  E.M. Landis, em 1962.

Definição de uma árvore AVLtype
   TDirecao = (NoEsquerdo, NoDireito);
   PNo = ^No;
   No = record
           Dado : Tipo_do_Dado;
           Links : array[NoEsquerdo..NoDireito] of PNo;
           Balanco : -1..1;
   end;
   ArvoreAVL = PNo;

Exemplo: Observe os balanços de cada nó da árvore AVL abaixo


Exemplo: Efetuando uma inserção em uma árvore AVL

Após a inserção de B no exemplo acima, a árvore passou a ficar desbalanceada. Para corrigir tal situação, aplicamos rotações para tornar a árvore balanceada novamente.

Rotações

---

Rotação Simples para Direita: Quando pivô e filho esquerdo têm mais elementos no lado esquerdo.

Após a inserção do valor 3, a árvore AVL ficou desbalanceada. O pivô (nó que contém 8) tem balanço 2 e seu filho esquerdo (nó que contém 4) tem balanço 1. Ao aplicar a rotação simples para direita, a árvore volta a ficar balanceada.

procedure RotacaoParaDireita(var Pivo : PNo);
var Temp, FilhoEsq : PNo;
begin
   FilhoEsq := Pivo^.Links[NoEsquerdo];
   Temp := FilhoEsq^.Links[NoDireito];
   FilhoEsq^.Links[NoDireito] := Pivo;
   Pivo^.Links[NoEsquerdo] := Temp;
end;

Rotação Simples para Esquerda: Quando pivô e filho direito têm mais elementos no lado direito.

Após a inserção do valor 13, a árvore AVL ficou desbalanceada. O pivô (nó que contém 10) tem balanço -2 e seu filho esquerdo (nó que contém 12) tem balanço -1. Ao aplicar a rotação simples para esquerda, a árvore volta a ficar balanceada.

procedure RotacaoParaEsquerda(var Pivo : PNo);
var Temp, FilhoDir : PNo;
begin
   FilhoDir := Pivo^.Links[NoDireito];
   Temp := FilhoDir^.Links[NoEsquerdo];
   FilhoDir^.Links[NoEsquerdo] := Pivo;
   Pivo^.Links[NoDireito] := Temp;
end;

Rotação Dupla uma para Esquerda outra para Direita: Quando pivô tem mais elementos do lado esquerdo e filho tem mais elementos do lado direito.

Após a inserção do valor 7, a árvore fica desbalanceada. Como o pivô (nó com valor 8) tem mais elementos do lado esquerdo, mas seu filho esquerdo (nó com valor 4) possui mais elementos do lado direito, é preciso primeiro fazer uma rotação à esquerda em torno do filho esquerdo para depois efetuar a rotação para a direita sobre o pivô.

Rotação Dupla uma para Direita outra para Esquerda: Quando pivô tem mais elementos do lado direito e filho tem mais elementos do lado esquerdo.

Após a inserção do valor 11, a árvore fica desbalanceada. Como o pivô (nó com valor 10) tem mais elementos do lado direito, mas seu filho direito (nó com valor 12) possui mais elementos do lado esquerdo, é preciso primeiro fazer uma rotação à direita em torno do filho direito para depois efetuar a rotação para a esquerda sobre o pivô (nó com valor 10).

De forma geral, teríamos o quadro abaixo:

Fonte:http://200.17.141.213/~alberto/2012-2/ed1/aulas/arvores_avl.htm