Atps Informatica

ETAPA 4 – Pesquisa.

• A AVL (Adelson-Velskii e Landis – 1962) é uma árvore de alto balanceamento tanto nas inserções e exclusões, possui uma rotina onde executa balanceamento tal que as alturas das sub-árvores esquerda e sub-árvores direita tenham alturas bem próximas.
• Se o fator de balanceamento de qualquer nó ficar menor do que -1 ou maior do que 1 então a árvore tem que ser balanceada.
• Para rotação em AVL temos dos tipos: rotação dupla e rotação simples.

Exemplo de rotação simples:

[pic 1]

        Fonte: http://www.ufjf.br/jairo_souza/files/2009/12/5-Indexa%C3%A7%C3%A3o-Arvore-AVL.pdf

   Exemplo de rotação dupla: [pic 2]

• Ao trabalharmos com inserção através da AVL podemos ter 4 métodos diferentes de realizar:

1.  Rotação (LL): O novo nó X é inserido na sub-árvore da esquerda do filho esquerdo de A;

[pic 3]

1. Rotação (LR): X é inserido na sub-árvore da direita do filho esquerdo de A;

[pic 4]

1. Rotação (RR): X é inserido na sub-árvore da direita do filho direito de A;

[pic 5]

1. Rotação (RL): X é inserido na sub-árvore da esquerda do filho direito de A;

[pic 6]

• Lembrando que sempre devemos balancear uma arvore do tipo AVL:

1. Sempre que existir um fator de balanceamento superior a +1 ou inferior a -1;
2. Caso exista mais de um nó que se encaixe neste perfil deve-se sempre balancear o nó com o nível mais alto;

• Para remoção de dados em AVL:

1. As rotações simples e duplas são necessárias para balancear;
2. A falta de balanceamento pode se propagar em direção à raiz e muitas rotações podem ser necessárias;

[pic 7]

        Fonte: http://slideplayer.com.br/slide/356518/

...