Árvores balanceadas - AVL

1. Árvores Balanceadas
AVL
Prof: Sergio Souza Costa

2. Sobre mim
Sérgio Souza Costa
Professor - UFMA
Doutor em Computação Aplicada (INPE)


[email protected]
https://sites.google.com/site/profsergiocosta/home
https://twitter.com/profsergiocosta
http://gplus.to/sergiosouzacosta
http://www.slideshare.net/skosta/presentations?order=popular

3. Introdução
●As árvores binárias de busca permitem a
organização da informação com o objetivo a
otimizar as buscas.

4. Introdução
●As árvores binárias de busca permitem a
organização da informação com o objetivo a
otimizar as buscas.
●Ela permite o acesso mais rapido aos
elementos dado que os elementos estão
organizados na árvore, obedecendo uma
certa propriedade.
■Esquerda são os menores que a raiz
■Direita são os maiores que a raiz

5. Introdução
●As Árvores binárias de busca (ABB)
estudadas têm uma séria desvantagem
que pode afetar o tempo necessário para
recuperar um item armazenado.

6. Introdução
Insiram os seguintes valores em uma árvore
binária de busca (ABB):
1, 2, 3, 4, 5, 6, 7 4, 6, 2, 5, 1, 7, 3

O que vocês concluem com isso ?

7. Introdução
A desvantagem é que o desempenho da ABB depende
da ordem em que os elementos são inseridos.

8. Introdução
A desvantagem é que o desempenho da ABB depende
da ordem em que os elementos são inseridos.

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

9. Introdução
A desvantagem é que o desempenho da ABB depende
da ordem em que os elementos são inseridos.

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

Como saber se a árvore está balanceada ?

10. Introdução
A desvantagem é que o desempenho da ABB depende
da ordem em que os elementos são inseridos.

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

Como saber se a árvore está balanceada ?







A altura dos nós
é um importante
dado.

11. 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-árvores
diferem no máximo de uma unidade.

20
30
10
40
35
20
30
10
4035
Qual é AVL ? Que nó
esta desbalanceado ?
a) b)

12. AVL
●Como saber se a árvore está
desbalanceada?

13. AVL
●Como saber se a árvore está
desbalanceada?
○Verificando se existe algum nodo “desregulado”.

14. AVL
●Como saber se a árvore está
desbalanceada?
○Verificando se existe algum nodo “desbalanceado”.

●Como saber se um nodo está
desbalanceado ?

15. AVL
●Como saber se a árvore está
desbalanceada?
○Verificando se existe algum nodo “desbalanceado”.

●Como saber se um nodo está
desbalanceado ?
○Subtraindo-se as alturas das suas sub-árvores.

16. Fator de balanceamento
●O fator de balanceamento é dado por:
○altura (SAE) – altura(SAD)
●Ou,
○altura (SAD) – altura(SAE)

17. Fator de balanceamento
●O fator de balanceamento é dado por:
○altura (SAE) – altura(SAD)
●Ou,
○altura (SAD) – altura(SAE)
●O fator de balanceamento de um nodo é dado pelo seu
peso em relação a sua sub-árvore.
○Um nodo pode ter um fator balanceado de 1, 0, ou -1.
○Um nodo com fator de balanceamento -2 ou 2 (diferença de
2 elementos) é considerado desbalanceado e requer um
balanceamento.

18. AVL - Calculando o fator
20
30
10
40
35


Coloque as alturas de cada nó

19. AVL - Calculando o fator
20
30
10
40
35
0
1


Coloque as alturas de cada nó
2
3
0
-1
-1
-1
-1
-1
-1

20. AVL - Calculando o fator
20
30
10
40
35
0
1

Coloque as alturas de cada nó

Calcule o fator de balanceamento

altura (SAE) - altura (SAD)
2
3
0
-1
-1
-1
-1
-1
-1

21. AVL - Calculando o fator
20
30
10
40
35
0
1


altura (SAE) - altura (SAD)
2
3
0
-1
-1
-1
-1
-1
-1
0 - 2 = -2

22. AVL - Calculando o fator
20
30
10
40
35
0
1


altura (SAE) - altura (SAD)
2
3 (-2)
0
-1
-1
-1
-1
-1
-1
0 - 2 = -2

23. AVL - Calculando o fator
20
30
10
40
35
0
1


altura (SAE) - altura (SAD)
2
3 (-2)
0
-1
-1
-1
-1
-1
-1
-1 - 1 = -2

24. AVL - Calculando o fator
20
30
10
40
35
0
1


altura (SAE) - altura (SAD)
2 (-2)
3 (-2)
0
-1
-1
-1
-1
-1
-1
-1 - 1 = -2

25. AVL - Calculando o fator
20
30
10
40
35
0 (0)
1 (1)


altura (SAE) - altura (SAD)
2 (-2)
3 (-2)
0 (0)
-1
-1
-1
-1
-1
-1

26. AVL - Calculando o fator
20
30
10
40
35
0 (0)
1 (1)


altura (SAE) - altura (SAD)
2 (-2)
3 (-2)
0 (0)
-1
-1
-1
-1
-1
-1
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.

27. AVL - Calculando o fator
20
30
10
40
35
0 (0)
1 (1)


altura (SAE) - altura (SAD)
2 (-2)
3 (-2)
0 (0)
-1
-1
-1
-1
-1
-1
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.

28. Atividades
Insira os seguintes valores em uma árvore
binária, coloque os fatores de balanceamento e
diga se é ou não uma AVL e qual nó esta
desbalanceado:

a) [30,15, 50, 5,10, 20]
b) [ 80, 40, 100, 120, 90, 30]
c) [10, 50, 4, 90, 20, 8]

29. Como balancear ?

30. Como balancear ?
Através de operações de
rotações!!!!

31. Rotações
Existem quatro operações de rotações:

Rotação simples à Esquerda
Rotação simples à Direita
Rotação Dupla à Esquerda
Rotação Dupla à Direita

32. Rotações
Existem quatro operações de rotações:

Rotação simples à Esquerda
Rotação simples à Direita
Rotação Dupla à Esquerda
Rotação Dupla à Direita

As duplas são
derivadas das
simples

33. Rotações
●Quando usar as Rotações ?
○Na inserção de um elemento
○e na remoção de um elemento

●É provado que no máximo uma rotação é
suficiente para realizar o balanceamento de
uma árvore quando é inserido ou removido
um elemento

34. Rotações e balanceamento
Vamos ver primeiro as operações de rotação e
depois usa-las para balanceamento.

35. Rotações
Rotação a direita
Rotação a direita


Rotação a esquerda

36. Rotação a direita

37. Rotação a direita
30
20
10
Imagine a seguinte
árvore....

38. Rotação a direita
30
20
10
30
20
10
Imagine a seguinte
árvore....

39. Rotação a direita
30
20
10
30
20
10
Imagine a seguinte
árvore....

40. Rotação a direita
Atividades
Insiram os seguintes valores e depois rotacione
para a direita a partir da raiz:

a) [40,30, 20]
b) [40, 30, 20, 35]
c) [40, 50, 30, 20, 35]

41. Rotação a esquerda

42. Rotação a esquerda
Atividades
Insiram os seguintes valores e depois rotacione
para a esquerda a partir da raiz:

a)[40, 50, 60]
b) [40, 50, 10, 60]
c) [40, 20, 10, 50, 60, 70]

43. Rotação dupla a esquerda

44. Rotação dupla a esquerda
Atividades
Insiram os seguintes valores e depois rotacione
dupla a esquerda a partir da raiz:

a)[20, 40, 30]
b) [20, 40, 30, 50]
c) [20, 10, 40, 30, 50, 12]

45. Rotação dupla a direita

46. Rotação dupla a direita
Atividades
Insiram os seguintes valores e depois rotacione
dupla a direita a partir da raiz:

a) [40, 20, 30]
b) [40, 20, 30, 50]
c) [40, 20, 30, 10,50, 80]

47. Como usar as rotações para
manter uma árvore balanceada, ou
seja, uma AVL ?

48. Balanceamento
Ao inserir um novo elemento em uma árvore,
pode ser que um dos seus nós ascendentes se
torne desbalanceado, avô, bisavô ...

49. Balanceamento
Algoritmo:

A cada inserção, checa-se os nós ascedentes.

50. Balanceamento
Algoritmo:

●Aplica-se, o mesmo algoritmo de inserção
da árvore binária de busca.
●A cada inserção, checa-se os nós
ascedentes.
●Caso o nó esteja desbalanceado, existem
quatro diferentes configurações, como
veremos a seguir.
○Para cada configração, existe uma rotação indicada.

52. Exemplo
10
altura (SAE) - altura (SAD)
[10, 20, 30]

53. Exemplo
10
20
FB: -1 - 0 = -1 OK
altura (SAE) - altura (SAD)
[10, 20, 30]

54. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30]
30

55. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30]
30
FB: -1 - 0 = -1 OK

56. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30]
30
FB: -1 - 1 = -2 Perigo: desbalanceado

57. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30]
30
FB: -1 - 1 = -2 Perigo: desbalanceado
Qual a rotação indicada
neste caso ?

58. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30]
30
FB: -1 - 1 = -2 Perigo: desbalanceado
Qual a rotação indicada
neste caso ?

Rotação simples a
esquerda.

59. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30]
30

60. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40]
30
40

61. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40, 35]
30
40
35

62. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40, 35]
30
40
35
FB: -1 - 1 = -2 Perigo: desbalanceado

63. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40, 35]
30
40
35
FB: -1 - 1 = -2 Perigo: desbalanceado
Qual a rotação indicada
neste caso ?

64. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40, 35]
30
40
35
FB: -1 - 1 = -2 Perigo: desbalanceado
Qual a rotação indicada
neste caso ?

Rotação dupla a
esquerda.

65. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40, 35]
30
40
35
rotação
direita

66. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40, 35]
30
35
40

67. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40, 35]
30
35
40
rotação
esquerda

68. Exemplo
10
20
altura (SAE) - altura (SAD)
[10, 20, 30, 40, 35]
35
30
40
FB: 0 - 1 = -1 OK
continua a checagem com o no
ascendente.

69. Atividades
A partir de uma árvore AVL, insiram os
seguintes valores:

a) [10, 20,15,45,67,81,91,10]
b) [1, 5,80,20,67,91,8,10]
c) [10,20,30, 50, 5, 15, 30]

70. Codificação
Transformando uma árvore binária de
busca em AVL ...

71. Codificação
Transformando uma árvore binária de
busca em AVL ...
baixem o seguinte código:

https://sites.google.com/site/skosta/teaching/2011-2/sif-
120/arquivos/arvore_binaria.c?attredirects=0&d=1

72. Rotações
Os algoritmos de rotação serão os primeiros a
serem codificados:

●rotação a esquerda
●rotação a diretia

73. Rotação a esquerda

74. BTNode* leftRotation (BTNode* r) {
BTNode* aux = getRight(r);
setRight(r, getLeft(aux));
setLeft(aux, r);
return aux;
}


Rotação a esquerda

75. BTNode* leftRotation (BTNode* r) {
BTNode* aux = getRight(r);
setRight(r, getLeft(aux));
setLeft(aux, r);
return aux;
}


Rotação a esquerda
r
10
20
30
5
40
15

76. BTNode* leftRotation (BTNode* r) {
BTNode* aux = getRight(r);
setRight(r, getLeft(aux));
setLeft(aux, r);
return aux;
}


Rotação a esquerda
r
10
20
30
5
40
15

77. BTNode* leftRotation (BTNode* r) {
BTNode* aux = getRight(r);
setRight(r, getLeft(aux));
setLeft(aux, r);
return aux;
}


Rotação a esquerda
r
10
20
30
5
40
15
aux

78. BTNode* leftRotation (BTNode* r) {
BTNode* aux = getRight(r);
setRight(r, getLeft(aux));
setLeft(aux, r);
return aux;
}


Rotação a esquerda
r
10
20
30
5
40
15
aux

79. BTNode* leftRotation (BTNode* r) {
BTNode* aux = getRight(r);
setRight(r, getLeft(aux));
setLeft(aux, r);
return aux;
}


Rotação a esquerda
r
10
20
30
5
40
15
aux

80. BTNode* leftRotation (BTNode* r) {
BTNode* aux = getRight(r);
setRight(r, getLeft(aux));
setLeft(aux, r);
return aux;
}


Rotação a esquerda
r
10
20
30
5
40
15
aux

81. BTNode* leftRotation (BTNode* r) {
BTNode* aux = getRight(r);
setRight(r, getLeft(aux));
setLeft(aux, r);
return aux;
}


Rotação a esquerda
r
10
20
30
5
40
15
aux

82. BTNode* rightRotation (BTNode* r) {
BTNode* aux = getLeft(r);
setLeft(r, getRight(aux));
setRight(aux, r);
return aux;
}



Rotação a esquerda

83. Rotações duplas
// rotação dupla a direita
BTNode* rightDoubleRotation (BTNode* r) {
setLeft(r, leftRotation(getLeft(r)));
return rightRotation (r);
}

// rotação dupla a esquerda
BTNode* leftDoubleRotation (BTNode* r) {
setRight(r, rightRotation(getRight
(r)));
return leftRotation (r);
}

84. BTNode* balance (BTNode* r) {
int fb;
if (r == NULL) return NULL;
fb = height (getLeft(r)) - height (getRight(r));
if (fb < -1) {
if (height( getRight (getRight(r))) > height( getLeft (getRight(r))))
return leftRotation (r);
else
return leftDoubleRotation (r);
}else if (fb > 1) {
if (height( getLeft (getLeft(r))) > height( getRight (getLeft(r))))
return rightRotation (r);
else
return rightDoubleRotation (r); }
return r;
}

85. Como usar o algoritmo de
balanceamento ?

86. Nas operações de inserção e
remoção
// inserção
BTNode *BSTinsert (BTNode *r, int x) {
if (r == NULL)
r = Node (x, NULL, NULL);
else if (x < getElement(r) )
setLeft( r, BSTinsert(getLeft(r), x ) );
else
setRight( r, BSTinsert(getRight(r), x ) );
return balance(r);
}

87. Qual o problema SÉRIO com
este nosso algoritmo ?

88. Qual o problema SÉRIO com
este nosso algoritmo ?
A operação que calcula a altura
da árvore não está eficiente.

Sua complexidade é linear,
como torná-la constante ?

89. Uma verdadeira AVL
A codificação de uma AVL necessita que o
cálculo da altura seja constante, caso contrário
ela será eficiente na busca porém MUITO
ineficiente nas inserções e remoções.

90. AVL
typedef struct AVL {
int e;
int height;
struct AVL *l;
struct AVL *r;
} AVL;

int height (AVL* r) {
if ( r == NULL ) return -1;
else return r->height;
}

adiciona mais uma
variavel a estrutura
a função altura agora tem
complexidade constante

91. AVL
Contudo, teremos atualizar a altura para cada:

●inserção
●remoção
●rotações

92. Atividades
Acessem