8 arvore avl

Prévia do material em texto

Estrutura de Dados
Árvore AVL
Manoel Vilela
<2017-10-19 Thu 23:37>
Sumário
1 Descrição 1
2 Origem e Motivação 1
3 Fator de Balanceamento 1
4 Regras 2
4.1 Rebalanceamento . . . . . . . . . . . . . . . . . . . . . . . . . 2
4.2 Inserção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4.3 Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Descrição
Esta nota se refere aos procedimentos necessário para balanceamento que
são envolvidos numa árvore do tipo AVL.
2 Origem e Motivação
A árvore AVL foi criada pelos matemáticos russos Adelson Velsky e Lan-
dis na antiga união soviética em 1962 para que fosse possível inserir e buscar
um elemento em tempo de log(n) operações. Onde n é o número de nós.
Sua complexidade é então de fatoO(log(n) para ambas operações e possuí
espaço de O(n), considerando ambos pior e médio caso.
Para controlar o desbalanceamento da árvore com remoções e inserção,
ambos algoritmos que fazem essas operações consideram o fator de balan-
ceamento.
1
3 Fator de Balanceamento
O fator de balanceamento é o critério adotado nas operações de inserção
e remoção para mexer parar realizar uma operação de balanceamento ou não
na árvore. Isto é, ele que caracteriza se a árvore está ou não balanceada, ou
necessariamente, se uma subárvore está desbalanceada.
O critério é definido da seguinte maneira:
Se a árvore é balanceada, todo nó terá fator de balanceamento 1, 0 ou
-1.
O fator de balanceamento é definido pela equação:
FB(T ) = H(left(T ))−H(right(T ))
Onde T é uma árvore, left e right selecionam os filhos e H é a função que
calcula a altura.
4 Regras
A principal regra definida para esse tipo de estrutura de dados está no
procedimento de rebalanceamento que é executado após as operações de in-
serção e remoção. Os critérios usados para balanceamento envolve as alturas
dos nós através do Fator de Balanceamento (FB) que pode ter no máximo
valor de módulo 1. As operações para rebalanceamento envolve rotações em
torno de um nó específico.
4.1 Rebalanceamento
Há dois casos para um nó qualquer:
1. Quando para um nó |FB| = 2 e seu filho |FB| = 1 mas ambos tem
sinais trocados
2. Quando para um nó |FB| = 2 e seu filho |FB| = 1 mas ambos tem
sinais iguais.
Para (1) efetua-se uma dupla rotação em torno do nó com |FB| = 2.
Primeiro o filho, depois o pai. A direção da rotação é inversa ao sinal, isto é,
se é negativo, é para direita se é positivo é para esquerda. A segunda rotação
feita no nó filho e a direção é inversa a primeira. Para (2) efetua-se apenas
uma simples rotação de acordo com o sinal de FB.
2
1 # Rotação Simples a Esquerda
2 # p aponta para o nó desbalanceado
3 q = right(p)
4 hold = left(q)
5 left(q) = p
6 right(p) = hold
7 p = q
Código 1: Pseudo-código para rotação simples a esquerda
1 # Rotação Simples a Direita
2 # p aponta para o nó desbalanceado
3 q = left(p)
4 hold = right(q)
5 right(q) = p
6 left(p) = hold
7 p = q
Código 2: Pseudo código para rotação simples a direita.
4.2 Inserção
A Árvore AVL é também uma Árvore Binária de Busca, portanto, os
critérios de onde inserir um novo nó permanece o mesmo. Insere-se a direita
se o nó a ser inserido é maior que o nó atual, insere-se a esquerda se é menor
que o nó atual.
De tal maneira, ao percorrer de maneira infixa (ou simétrica) você terá
um vetor ordenado de forma crescente.
Ao final da inserção, é necessário verificar se houve desbalanceamento da
árvore através dos critérios que envolve o cálculo do Fator de Balanceamento.
As regras usadas estão definidas no tópico anterior.
4.3 Remoção
As regras de remoção são no geral idênticas as descritas acima para in-
serção, com a adição das propriedades usada em Árvore Binária de Busca
para remoção também.
3
	Descrição
	Origem e Motivação
	Fator de Balanceamento
	Regras
	Rebalanceamento
	Inserção
	Remoção