Prsistemas E Tecnologia

TRABALHO CLASSIFICAÇÃO E PESQUISA

ARVORE AVL

PROF. ADALBERTO

SISTEMAS DE INFORMAÇÃO – 6º SEMESTRE – NOTURNO

SÃO PAULO

2013 

CONCEITUAÇÃO

Árvore AVL em Ciência da Computação é uma árvore de busca binária auto balanceada.

Por definição, as alturas das duas subárvores a partir de cada nó difere no máximo em uma unidade, positiva ou negativa.

As operações de busca, inserção e remoção de elementos possuem complexidade O(log2 n) no qual n é o número de elementos da árvore.

Inserções e remoções podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.

O nome AVL vem de seus criadores Adelson Velsky e Landis, e sua primeira referencia encontra-se no documento “Algoritimos para organização da informação” de 1962, que propuseram manter uma árvore binária balanceada dinamicamente, ou seja, na medida em que os nós fossem sendo inseridos

BALANCEAMENTO

Uma árvore AVL é dita balanceada quando, para cada nó de árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) não é maior do que um.

Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de inserção e remoção de elementos.

O fator de balanceamento de um nó é dado pelo seu peso em relação a sua subárvore, um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não AVL e requer um balanceamento por rotação ou dupla rotação.

OPERAÇÕES: ROTAÇÃO, INSERÇÃO, ORDENAÇÃO e BUSCA

Rotação

A operação básica em uma árvore AVL geralmente envolve os mesmos algoritimos de uma árvore de busca binária desbalanceada.

A rotação 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 nodo estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um “joelho”.

Rotação a esquerda

Em uma árvore binaria, basta empurrar o nodo N para baixo e para a esquerda, o filho à direita de N o substitui, e o filho à esquerda do filho à direita vem a ser o novo filho à direita de N.

Rotação à direita

Numa árvore binaria basta empurrar o nodo N para baixo e para direita, o filho à esquerda de N o substitui e o filho à direita do filho à esquerda vem a ser o novo filho à esquerda de N.

Inserção

Inserção em uma árvore AVL deve ser dada pela inserção do nó seguida de uma verificação na propriedade do fator de balanceamento, caso não obedeça a essa propriedade, deve-se fazer uma rotação conveniente.