Algoritmos e Estrutura de Dados III Árvore AVL. URI - DECC - Ciência da Computação Contextualização •As ABP estudadas têm uma séria desvantagem que pode

Algoritmos e Estrutura de Dados III

Árvore AVL

URI - DECC - Ciência da Computação

Contextualização

• As ABP estudadas têm uma séria desvantagem que pode afetar o tempo necessário para recuperar um item armazenado.

• A desvantagem é que o desempenho da ABP depende da

ordem em que os elementos são inseridos.

1, 2, 3, 4, 5, 6, 7 4, 6, 2, 5, 1, 7, 31

2

3

4

5

6

7

2

4

6

1 3 5 7


Árvores AVL

• Nome com origem em seus inventores:– Georgii Adelson-Velsky e Yevgeniy Landis;– Publicaram um documento chamado: "Algoritmos para

organização da informação“, em 1962;

• Uma árvore binária de pesquisa T é denominada AVL se:– Para todos nós de T, as alturas de suas duas sub-

árvores diferem no máximo de uma unidade.

• Para cada inserção ou exclusão no pior caso é de O(log n).


Como reconhecer uma árvore desbalanceada?

• Como saber se a árvore está desbalanceada ?– Verificando se existe algum nodo “desregulado”.

• Como saber se um nodo está desregulado ? – Subtraindo-se as alturas das suas sub-árvores. – Fator de Balanceamento

• Por questões de eficiência, estas diferenças são pré-calculadas e armazenadas nos nós correspondentes, sendo atualizadas durante as operações.


Fator de Balanceamento

• Fator de Balanceamento de um nó:

– dado pelo seu peso em relação a sua sub-árvore fb = altura árvore direita – altura árvore esquerda

– O fator de balanceamento de uma folha é sempre 0

– Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator;– Fatbal = -1, quando a sub-árvore da esquerda é um nível mais alto que a direita.– Fatbal = 0, quando as duas sub-árvores tem a mesma altura.– Fatbal = 1, quando a sub-árvore da direita é um nível mais alto que a esquerda.

– Um nó com fator de balanceamento -2 ou 2 é considerada um árvore não-AVL

• requer um balanceamento por rotação ou dupla-rotação.


Propriedade da AVL

• Procurar manter todas as folhas mais ou menos na mesma altura de forma a respeitar o FB < 2

• Ou seja, Para todo nó

| altura(dir) - altura(esq) | < 2


Relembrando as definições...

• Altura de uma árvore (também denominada profundidade) é a distância entre x e o seu descendente mais afastado. Mais precisamente, a altura de x é o número de passos do mais longo caminho que leva de x até uma folha somando um.– Por definição a altura de uma árvore vazia é -1

E

/ \

D I

/ / \

B G K

/ \ / \ /

A C F H J

Altura dessa árvore é 3

Altura de K é 1

Altura de J é 0

Altura de I é 2


Exemplos de cálculos de FB

1

2

3

4

5

6

7

+6

+5

+4

+3

+2

+1

0

Inserção: 1, 2, 3, 4, 5, 6 e 7

2

4

6

1 3 5 700

0

0 0

00

Inserção: 4, 2, 3, 6, 5, 1 e 7

4

1 6

3

2

5 7

-1

0

00

+2

-1

0

Inserção: 4, 1, 3, 6, 5, 2 e 7


Operação: Inserção

2

4

6

1 3 5 7

0 0

0

0 0

00

Op. de balanceamento

4

1 6

3

2

5 7

0

00

+2

-1

0

Inserção: 4, 6, 1, 7, 5, 3 e 2. -1

00

1

0

1

2

3

AlturaFb


Operação: Remoção

4

6

7

+2

0

+1Remover nó 2

4

6

70

0

0

Op. de balanceamento

4

2 6

7

+1

0

+10

Inserção: 4, 6, 2 e 7.

AlturaFb

0

10

2


Operações

– Adição e exclusão requerem que a árvore esteja balanceada, se a árvore não estiver balanceada é necessário seu balanceamento

• através da rotação ou dupla-rotação.


Rotação

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

• A rotação na árvore AVL 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.

– Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai


Tipos de Rotações

• Rotação Simples:– Rotação a Esquerda– Rotação a Direita

• Rotação Dupla:– Rotação a Esquerda– Rotação a Direita


a) Para identificar quando uma rotação é simples ou dupla deve-se observar os sinais dos FBs do nodo desbalanceado e do filho que gerou o desbalanceamento:• Sinal for igual, a rotação é simples• Sinal for diferente a rotação é dupla

b) Se Fb for positivo (+) a rotação para à esquerda

c) Se Fb for negativa (-) a rotação para à direita

Dicas


Rotação Simples à Direita

Inserção à esquerda de árvore desbalanceada à esquerda (bal = -1)

Promover o elemento do meio através de um giro no sentido horário.


Rotação Simples à Esquerda

Inserção à direita de árvore desbalanceada à direita (bal = +1)

Promover o elemento do meio através de um giro no sentido anti-horário.


Exemplo de Rotação Simples

• Suponha que nós queiramos inserir o nó 3 na árvore inicial abaixo

3

08

4 10

2 6

0

0 0

-18

4 10

2 6

3

-1 0

+1 0

-2

0

Rotação a direita (nó 8)

0

0

0 0

4

2 8

1063

+1 0

A inserção do nó 3 produziu um desbalanço no nó 8 verificado pelo FB = -2 neste nó. Neste caso, como os sinais dos FB são os mesmos (nó 8 com FB = -2 e nó 4 com FB = -1) significa que precisamos fazer apenas uma ROTAÇÃO SIMPLES.


- Inserção do elemento 20

(rotação simples à direita + rotação simples à esquerda)

Rotação Dupla à Esquerda


- Inserção do elemento 20

Rotação Dupla à Direita

(rotação simples à esquerda + rotação simples à direita)


Exemplo de Rotação Dupla (1/2)

• Suponha que queiramos inserir o nó 5 na árvore abaixo

08

4 10

2 6

0

0 0

-1

0

8

4 10

2 6

50

0

-1

+1

-2

(a)8

6 10

4

52

0

0

0

0-2

-2

Observe que o nó 8 tem FB = -2 e tem um filho com FB = +1 (sinais opostos). Neste caso, o balanceamento é alcançado com duas rotações. Primeiro: (a) rotação simples sobre o nó 4 (com FB = +1) para a esquerda.


Exemplo de Rotação Dupla (2/2)

8

6 10

4

52

0

0

0

0-2

-2

Logo após da rotação a esquerda: (b) rotaciona-se o nó 8 (FB = -2) na direção oposta (direita neste caso).

(b)

6

4 8

2 105

0

0

0

00

+1


Caso I: Rotação Simples

• Suponha que inserimos os números 50, 40 e 30 em uma árvore. Obteremos então:

• A inserção novamente produziu um desbalanceamento.

• Neste caso, como os sinais dos FB são os mesmos, significa que precisamos fazer apenas uma ROTAÇÃO SIMPLES à direita no nodo com FB -2.

• No caso simétrico (nodo com FB 2) faríamos uma rotação simples à esquerda.


Caso I: Rotação Simples

• Após a rotação simples teremos:

• A árvore está balanceada dentro das propriedades de AVL.


Exemplo:

• Considerando a árvore abaixo:

• A árvore está balanceada, como podemos observar pelos Fb de cada nodo.

• São dois os possíveis casos de desbalancemento


Caso II: Rotação Dupla

• Ao inserir o número 5 na árvore teremos a seguinte árvore:

• O nodo 8 fica com o FB -2 e tem um filho com FB +1. Neste caso para manter o balanceamento devemos aplicar duas rotações, também denominada ROTAÇÃO DUPLA.

• Primeiro rotaciona-se o nodo com FB 1 para a esquerda.



• Logo rotaciona-se o nodo que possuía FB -2 na direção oposta, nesse caso a direita.



• Os FB dos nodos voltaram a ficar dentro do esperado das árvores AVL.

• O caso simétrico ao explicado acima acontece com os sinais de FB trocados, ou seja, um nodo com FB +2 com um filho com FB -1. Também utilizariamos uma rotação dupla, mas nos sentidos contrários, ou seja, o nodo com FB -1 seria rotacionado para a direita e o nodo com FB +2 seria rotacionado para a esquerda.


• A descrição do algoritmo em pseudo-código para a construção de uma árvore AVL seria:

– Inserir o novo nodo normalmente – Iniciando com o nodo pai do nodo recém-inserido, testar se a propriedade

AVL é violada no novo nodo. Temos aqui 2 possibilidades:– A condição AVL foi violada

• Execute as operações de rotação conforme for o caso (Caso I ou Caso II).

• Volte ao passo de Inserção.– A condição AVL não foi violada.– Se o nodo recém-testado não tem pai, ou seja, é o nodo raiz da árvore,

volte para inserir novo nodo.

Documents

Algoritmos e Estrutura de Dados III Árvore AVL. URI - DECC - Ciência da Computação Contextualização •As ABP estudadas têm uma séria desvantagem que pode