Aula8 Trees AVL Splay

1

Árvores Balanceadas (AVL)

2

Roteiro

Contextualização

Árvores Balanceadas (AVL)

Operações de Balanceamento

3

Roteiro

Contextualização

Árvores Balanceadas (AVL)

Operações de Balanceamento

4

Contextualização

As ABP estudadas têm uma séria desvantagem que podeafetar o tempo necessário para recuperar um itemarmazenado.

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, 3

1

2

3

4

5

6

7

2

4

6

1 3 5 7

5

Contextualização

Idealmente, deseja-se que a árvore estejabalanceada, para qualquer nó p da árvore.

Como saber se a árvore está balanceada ?

Para cada nó p da árvore a altura da sua sae éaproximadamente igual à altura da sua sad.

6

Roteiro

Contextualização

Árvores Balanceadas (AVL)

Operações de Balanceamento

7

Árvores Balanceadas (AVL)

O nome AVL vem de seus criadores Adelson Velsky e Landis(1962).

Uma árvore binária de pesquisa T é denominada AVL se:

Para todos nós de T, as alturas de suas duas sub-árvoresdiferem no máximo de uma unidade.

Operações de consulta, inserção e remoção de nós tem custoO(log2n).

130

100 150

120 20080

110

120

100

11080

130

200

150

8

Como reconhecer uma árvore desbalanceada? (1/2)

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.

Por questões de eficiência, estas diferenças sãopré-calculadas e armazenadas nos nóscorrespondentes, sendo atualizadas durante asoperações.

9

Como reconhecer uma árvore desbalanceada? (2/2)

Possíveis valores de diferença para cada nó em umaárvore balanceada: -1, 0, 1.

Fator de Balanceamento (FB) de cada nó da árvore

FB(p) = h(sad(p)) – h(sae(p))

10

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 7

0 0

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

11

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

12

Operação: Remoção

4

6

7

+2

0

+1Remover nó 2

4

6

7

0

0

0

Op. de balanceamento4

2 6

7

+1

0

+10

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

13

Roteiro

Contextualização

Árvores Balanceadas (AVL)

Operações de Balanceamento

14

Operações de Inserção e Remoção

A inserção ou remoção de um nó em uma árvore AVLpode ou não provocar seu desbalanceamento.

Se a árvore AVL ficar desbalanceada, a restauraçãodo seu balanceamento é realizado através deROTAÇÕES.

15

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

Dicas:

a) Para identificar quando uma rotação é simplesou dupla deve-se observar os sinais do Fb:

• 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

Rotação:

17

Exemplos 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.

18

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

5

0

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.

19

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

20

Pseudo-Código: Rotações Simples

Rotação Simples a Esquerdap aponta para o nó desbalanceado

q = right(p);

hold = left(q);

left(q) = p;

right(p) = hold;

p = q;

Rotação Simples a Direitap aponta para o nó desbalanceado

q = left(p);

hold = right(q);

right(q) = p;

left(p) = hold;p = q;

10

12

157

30

21

+2

0

+10

+10

10 15 12 7 21 30

2

10

1

154

7

0

0

0

-1

-1

-210 15 4 2 1 7

21

Conclusões

Balanceamento de árvores busca minimizar onúmero médio de comparações necessárias paralocalizar qualquer dado.

Operações de inserção e remoção de nós tendema tornar as árvores desbalanceadas.

Há um custo extra de processamento.

Compensado quando os dados armazenadosprecisam ser recuperados muitas vezes.

22

AVL Tree Applet

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

Créditos

23

Prof. Alexandre Parra Carneiro da Silva

parrasilva@gmail.com

Árvore Splay

É uma árvore binária de pesquisa (BST)

É uma árvore auto-equilibrada.

Em qualquer operação (pesquisa, inserção, remoção) a árvore faz SPLAY.

Basicamente fazer SPLAY, é trazer um elemento x para a raiz da árvore (BTT- Bring To Top), utilizando sucessivas rotações e tantas quanto necessárias, chamadas ZIG, ZIGZIG e ZIGZAG.

Árvore Splay

Lema: “Tornar mais acessível o que é mais usado”

Ajusta a estrutura da árvore à freqüência de acesso aos dados

Junto à raiz estão os elementos

mais usados

mais recentes

Os mais inativos ficam mais “longe” da raiz

Cada vez que um elemento é pesquisado o nó respectivo é puxado para a raiz usando rotações duplas AVL

Exemplo de Uso

Consultas bancárias

Ao fazer uma consulta, o registro de um cliente será levado para o topo da árvore, diminuindo o tempo de acesso para as próximas consultas. Assim, clientes que fazem consultas freqüentemente terão acesso mais rápido. Os registros de clientes que não utilizam estes serviços, por sua vez, ficarão nos níveis mais inferiores da árvore.

Árvore Splay: zig e zag

Árvore Splay: zig-zig

Árvore Splay: zig-zag

Algoritmo de Pesquisa(x, A)

Início

Faz percurso BST até encontrar.

Se existe o elemento x na árvore A

Faz SPLAY do elemento x

Senão

Faz SPLAY do sucessor esquerdo mais próximo de x

FimExemplo de pesquisa(9, A):

1) Pesquisa tipo BST até encontrar, existe então, faz SPLAY do x (neste caso 9).Caso não existisse faria SPLAY do 8, que é o elemento menor mais próximo de 9.2) Neste caso para fazer SPLAY é utilizado o ZIGZAG(x).3) Árvore final com o x na raiz.

Algoritmo de Inserção(A, x)

Início

Faz SPLAY do elemento x .

Como não existe, o elemento menor mais próximo de x fica na raiz

Agora é só inserir x, que passa a ser a raiz da árvore

FimExemplo de inserção(8, A):

1) SPLAY(8)

2) 7 vai para a raiz

3) Inserir 8, 7 é o seu filho esquerdo,e 10 o seu filho direito.

Algoritmo de Remoção(A, x)

InícioSe existe o elemento x na árvore A.

Faz SPLAY do elemento x.Faz SPLAY do elemento x, na sua subárvore esquerda.Traz o elemento menor mais próximo de x para a raiz.Remove o x.

SenãoFaz SPLAY do elemento menor mais próximo de x.

Fim

Exemplo de remoção(12, A):

1) Pesquisa tipo BST

2) SPLAY (12,A)

3) SPLAY (12,A') onde A' é a subárvore esquerda do 12, assim temos a certeza que o 12 não vai ter filho esquerdo.

4) Elemento menor mais próximo de 12 na raiz e sem filho esquerdo podemos então remover.

5) Elimina-se o 12 e liga-se o pai de x (12) com seu filho direito (15)

Conclusão

Árvores Splay podem ficar desequilibradas mas garantem uma complexidade O(log n) ao longo do

tempo de utilização (complexidade amortizada)

Ajusta a árvore à freqüência de acesso aos dados Junto à raiz estão os elementos

mais usados mais recentes os mais inativos ficam mais longe da raiz

Referências

Bibliografia:Drozdek, Adam. Estrutura de Dados e Algoritmos em C++ (Árvores Auto-

Ajustadas)

Sites:http://www.cs.nyu.edu/algvis/java/SplayTree.htmlhttp://w3.ualg.pt/~hshah/ped/Aula%2011/A11/aula11.htmlhttp://inf.unisinos.br/~ari/estrut/splay.pdfhttp://dct.ual.pt/historial/2004_05/aed2/teoricas/Semana6.pdf

Demonstrações:http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20app

let.htm

http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/SplayTree-Example.html