1 INE5408 Estruturas de DadosÁrvores AVL Características Rotações Algoritmos

2 Histórico Inventada em por Georgy Maximovich Adelson-Velskii (Гео́ргий Макси́мович Адельсо́н-Ве́льский) e Yevgeniy Mikhailovich Landis (Евгений Михайлович Ландис) e publicada em: "An algorithm for the organization of information. Trans. of Akademiya Nauk SSSR. Doklady, 1962, v. 146, no. 2, pp " Georgy Maximovich Adelson-Velskii (Samara, Rússia, 1922) Yevgeniy Mikhailovich Landis (Kharkov, Ucrânia, 1921)

3 Características Manter uma árvore binária de busca balanceada sob a presença de constantes inserções e deleções é ineficiente. Para contornar esse problema foi criada a árvore AVL (Adelson-Velskii e Landis). A árvore AVL é uma árvore binária com uma condição de balanço, porém não completamente balanceada. Árvores AVL permitem inserção / deleção e rebalanceamento aceitavelmente rápidos.

4 Características Critério de balanceamento:dado um nodo qualquer, uma árvore está AVL-balanceada se as alturas das duas subárvores deste nodo diferem de, no máximo, 1. Para rebalancear uma árvore após uma inserção, são utilizadas rotações de subárvores: rotações simples em muitos casos; rotações duplas em alguns.

5 Características Estrutura de um nodo na árvore AVLEstrutura nodoAVL {         info    : tipo_info;  esq     : *nodoAVL;       dir     : *nodoAVL;        alt     : inteiro; }; O campo alt deve ser atualizado recursivamente quando um nodo for inserido ou deletado.

6 Características Para o retorno da altura de uma subárvore necessitamos de uma função especial um nodo pode não ter um ou ambos os filhos embre-se que a pesquisa para garantir a condição-AVL é realizada perguntando-se a altura das duas subárvores inteiro altura( subárvore *nodoAVL) início                 se (subárvore for NULO)                         retorne -1; /* A altura de uma subárvore inexistente é definida como -1 */ senão                         retorne subárvore->alt;                 fim se         fim

7 Inclusão com rotação Exemplo de rebalanceamento:o nodo com chave 6.5 desequilibrou a árvore. Com a rotação da subárvore em torno do nodo 7, rebalanceamos. 6 6 2 2 7 8 1 4 1 4 7 6,5 8 3 6,5 3

8 Inclusão com rotação Algoritmo básico:partimos do nodo inserido e subimos a árvore; atualizamos a informação do balanceamento em cada nodo (na árvore AVL, cada nodo conhece a sua altura); se chegamos à raiz sem encontrar nada errado, terminamos; caso encontremos um nodo desbalanceado (|altesq - altdir| < 2 ferida), realizamos a rotação no primeiro nodo desbalanceado encontrado. No exemplo anterior, isto significa que, depois da inserção de 6.5, o nodo 8 ficou desbalanceado.

9 Exemplo: criação de uma árvore AVL com os números de 1 a 7O primeiro problema ocorre quando inserimos o 3. A condição-AVL foi violada. executamos uma rotação simples entre a raiz (cuja condição-AVL está violada) e seu filho da direita. 1 2 2 1 3 3

10 Exemplo: criação de uma árvore AVL com os números de 1 a 7Inserimos o elemento 4 sem problemas. Inserimos o elemento 5: violação em 3. Mesmo processo da rotação anterior será seguido. Importantíssimo: observe-se que 2 precisa ser notificado que seu filho agora é o nodo com chave 4. 2 2 1 1 4 3 4 3 5 5

11 Exemplo: criação de uma árvore AVL com os números de 1 a 7A inclusão do elemento 6 desequilibra a raiz: subárvore direita tem altura 0; subárvore esquerda tem altura 2. Rotacionamos na raiz entre 2 e 4: transformamos 2 em filho de 4; subárvore esquerda original de 4 é agora subárvore direita de 2. Condição de ordem da árvore de busca é mantida.

12 Exemplo: criação de uma árvore AVL com os números de 1 a 7A inclusão de um nodo com chave 7 causa uma rotação como já havíamos visto antes: 5 fica desequilibrado; rotacionamos em 6.

13 Inclusão com rotação simples à esquerdaCorresponde a uma rotação entre os nodos k2 e seu filho da esquerda, k1, envolvendo as subárvores A, B e C Devolvo k1 como a nova raiz desta subárvore Esta aresta é o ponto de desequilíbrio k2 A k1 B C

14 Inclusão com rotação simples à esquerdanodoAVL *simp_roda_esq(k2 *nodoAVL) variáveis locais k1 : *nodoAVL; início k1 <- k2->esq; k2->esq <- k1->dir; k1->dir <- k2; /* atualize alturas */ k2->alt <- max(altura(k2->esq), altura(k2->dir)) + 1; k1->alt <- max(altura(k1->esq), k2->alt) + 1; retorne k1; /* nova raiz da subárvore */ fim

15 Inclusão com rotação simples à direitanodoAVL *simp_roda_dir(k2 *nodoAVL) variáveis locais k1 : *nodoAVL; início k1 <- k2->dir; k2->dir <- k1->esq; k1->esq <- k2; /* atualize alturas */ k2->alt <- max(altura(k2->dir), altura(k2->esq)) + 1; k1->alt <- max(altura(k1->dir), k2->alt) + 1; retorne k1; /* nova raiz da subárvore */ fim

16 Inclusão com rotação duplaO algoritmo descrito até agora tem um problema: existem casos onde ele não basta para consertar a árvore após uma inclusão ou exclusão. Exemplo: inserimos as chaves 8 a 15, em ordem inversa, na árvore anterior. a inserção de 15 não provoca problemas, nem desbalanceia a árvore; a inserção de 14, por sua vez, faz o rebalanceamento falhar.

17 Inclusão com rotação duplaO problema que surge aqui é que tanto 7 como 14 são candidatos à subárvore esquerda de 15. Neste caso, necessitamos de uma dupla rotação.

18 Inclusão com rotação duplaO processo é semelhante à rotação simples, só que envolve 4 subárvores: A, B, C e D corresponderia a uma rotação efetuada primeiro entre k1 e k2 e depois entre k2 e k3. k3 k3 A B C D k2 k1 k1 A k2 D B C

19 Inclusão com rotação duplaP1: Rotação entre k1 e k2 k3 k1 D A k2 B C

20 Inclusão com rotação duplaP2: Rotação entre k2 e k3 Devolvo k2 como a nova raiz desta subárvore k3 A k2 k1 B C D

21 Rotação dupla à esquerdaExemplo simétrico ao anterior. k3 k1 k2 A B D C k3 A B C D k2 k1

22 Inclusão do elemento 14 com rotação duplaNo exemplo, a rotação direita-esquerda envolve o 7, o 15 e o 14: k3 é o nodo de chave 7, k1 o de chave 15 e k2 o de chave 14; primeiro rotacionamos à direita, depois 7-14 à esquerda.

23 Inclusão do elemento 13 com rotação duplaNovamente uma dupla rotação direita-esquerda: desta vez a rotação envolverá 6 (k3), 14 (k1) e 7 (k2).

24 A inclusão do elemento 12 provoca um desequilíbrio na raiz:como 12 não está entre 4 e 7, sabemos que uma rotação simples vai funcionar.

25 A inclusão do elemento 11 provoca um desequilíbrio logo embaixo:como 11 não está entre 12 e 13, sabemos que uma rotação simples vai funcionar.

26 Inclusão dos elementos 10, 9 e 8Os elementos 10 e 9 serão inseridos com rotação simples, e o elemento 8 sem rotação alguma. Tente em casa A árvore resultante será vista a seguir.

27 Caso interessante: inclusão do elemento 8.5

28 Temos uma rotação dupla que parece ser uma simples

29 Rotação Dupla à EsquerdaFunção chamada somente se k3 possuir um filho à esquerda e se o filho à esquerda de k3 possuir um filho à direita. Ela realiza a rotação e atualiza as alturas das subárvores rotacionadas. nodoAVL *dup_roda_esq(k3 : *nodoAVL) início                 /* Rotacione entre k1 e k2 */                 k3->esq <- simp_roda_dir( k3-> esq ); /* Rotacione entre k3 e k2 */                 retorne ( simp_roda_esq( k3 );         fim Da mesma forma que com a rotação simples, a rotação dupla à direita é a operação simétrica da rotação à esquerda e é facilmente implementada. 

30 Inserção em Árvore AVL A inserção em uma árvore AVL é necessariamente efetuada recursivamente, ao se retornar de cada nível (chamada recursiva), a subárvore onde ocorreu a inserção deve ser rebalanceada se necessário. algoritmo longo: será visto em página web