TrabalhoEstrutura De Dados

CENTRO UNIVERSITÁRIO GERALDO DI BIASE
FUNDAÇÃO EDUCACIONAL ROSEMAR PIMENTEL

INSTITUTO DE CIÊNCIAS SOCIAIS E HUMANAS
CURSO SISTEMAS DE INFORMAÇÃO

-ÁRVORE AVL -ÁRVORE RED-BLACK

Marcelle Moreira

Volta Redonda,2014
Árvore AVL
Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó diferem no máximo em uma unidade. As operações de busca, inserção e remoção de elementos possuem complexidade O( log2 n ) (no qual é 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 referência encontra-se no documento "Algoritmos para organização da informação" de 1962.

Uma árvore não-AVL

Características
Balanceamento
Uma árvore AVL é dita balanceada quando, para cada nó da á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. Para definir o balanceamento é utilizado um fator específico para nós.
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
Inserção
Inserção em uma árvore AVL deve ser dada pela inserção do nodo 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.
Remoção
A remoção deve ser dada por uma rotação em torno do nó a ser removido, a fim de torná-lo folha para que então possa