Arvore AVL - Slides da Aula sobre Arvores Balanceadas

Árvore AVL Profa Rachel Reis rachelreisufvbr Árvore Binária de Pesquisa Desvantagem desempenho da Árvore Binária de Pesquisa depende da ordem em que os elementos são inseridos Exemplo 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Quantas comparações para encontrar o elemento 7 4 6 2 5 1 7 3 1 2 3 4 6 5 7 Árvore AVL Também conhecida como Árvore Binária Balanceada Característica Uma árvore é denominada AVL se todos os seus nós estiverem balanceados Fator de balanceamento de um nó deve ser 1 0 ou 1 Como calcular o fator de balanceamento de um nó Altura de sua subárvore esquerda menos a altura de sua subárvore direita Fator de Balanceamento Exemplo 1 1 2 4 6 7 Hesq do nó 1 0 Hdir do nó 1 0 FB Hesq Hdir 0 0 0 0 Fator de Balanceamento Hesq do nó 7 0 Hdir do nó 7 0 FB Hesq Hdir 0 0 0 0 Exemplo 1 1 2 4 6 7 Hesq do nó 2 1 Hdir do nó 2 0 FB Hesq Hdir 1 0 1 1 Fator de Balanceamento Hesq do nó 6 0 Hdir do nó 6 1 FB Hesq Hdir 0 1 1 1 Exemplo 1 0 Fator de Balanceamento 1 2 4 6 7 Hesq do nó 4 2 Hdir do nó 4 2 FB Hesq Hdir 2 2 0 Exemplo 1 0 Fator de Balanceamento 1 1 0 0 1 2 4 6 7 Árvore Balanceada Exemplo 2 Fator de Balanceamento 4 6 7 1 0 FB 6 1 FB7 0 FB Hesq Hdir 0 2 2 Exemplo 2 Fator de Balanceamento 4 6 7 2 Hesq do nó 4 0 Hdir do nó 4 2 Exemplo 2 Fator de Balanceamento 4 6 7 2 Árvore NÃO balanceada 1 0 Rotação A inserção ou remoção de um nó em uma árvore AVL pode ou não provocar seu desbalanceamento Se a árvore AVL ficar desbalanceada a restauração do seu balanceamento é realizado por meio de rotações simples ou dupla Rotação Simples à Direita 5 1 2 5 6 7 7 5 Duas situações 1 O nóraiz da árvore ou de uma de suas subárvores tem FB2 e tem um filho com FB1 rotação à direita 5 6 7 0 0 0 Rotação Simples à Esquerda 5 6 7 2 1 Duas situações 2 O nóraiz da árvore ou de uma de suas subárvores tem FB2 e tem um filho com FB1 rotação à esquerda 0 0 0 5 6 7 Rotação Simples Exemplo 1 0 1 0 4 8 10 9 15 12 1 0 2 Calcular o FB de cada nó Rotação Simples Exemplo 1 4 8 10 9 15 12 2 Nó 8 desbalanceado Rotação Simples Exemplo 1 1 4 8 10 9 15 12 2 Rotação à esquerda 0 Rotação Simples à Esquerda Exemplo 1 1 4 8 10 9 15 12 2 8 10 15 12 4 9 0 0 0 0 0 1 Rotação Simples Exemplo 2 4 8 10 2 6 3 0 1 2 0 0 1 Nó 8 desbalanceado Rotação Simples Exemplo 2 4 8 10 2 6 3 1 2 Rotação à direita 0 Rotação Simples à Direita Exemplo 2 4 8 10 2 6 3 1 2 2 4 8 6 3 10 0 1 0 0 0 0 Rotação Dupla esquerdadireita 5 5 6 7 1 6 7 7 5 Duas situações 1 O nóraiz da árvore ou de uma de suas subárvores tem FB2 e tem um filho com FB1 rotação esquerdadireita 2 0 0 0 5 6 7 Rotação Dupla direitaesquerda Duas situações 2 O nóraiz de uma árvore ou subárvore tem FB2 e tem um filho com FB1 rotação direitaesquerda 7 5 5 9 7 8 1 7 8 9 2 7 8 9 0 0 0 Rotação Dupla Exemplo 3 Calcular o FB de cada nó 0 0 1 1 0 2 4 8 10 2 6 5 0 Rotação Dupla Exemplo 3 Nó 8 desbalanceado 0 0 1 1 0 2 4 8 10 2 6 5 0 Rotação Dupla Exemplo 3 1 4 8 10 2 6 5 Rotação esquerdadireita 4 8 10 2 6 5 2 4 8 10 2 6 5 0 0 0 0 0 1 Rotação Resumo Rotação simples Rotacionar uma única vez o nó de FB 2 ou FB 2 Se for negativo rotacionar à esquerda Se for positivo rotacionar à direita Rotação Resumo Rotação dupla Rotação ESQUERDADIREITA 1 FB 1 rotacionar à esquerda 2 FB 2 rotacionar à direita Rotação DIREITAESQUERDA 1 FB 1 rotacionar à direita 2 FB 2 rotacionar à esquerda Exercício 1 Calcule o fator de balanceamento nas árvores AVL abaixo e realize a rotação simples ou dupla quando necessário B K P M D C R B K P M D N a b Implementação Dinâmica Rotação esquerdadireita Rotação à esquerda Rotação à direita Definir AVL Árvore AVL Rotação direitaesquerda Definição typedef struct sNo TIPO info int fb struct sNo esq struct sNo dir NO fb info dir esq ptRaiz typedef struct sAVL NO ptRaiz AVL Implementação Dinâmica Rotação esquerdadireita Rotação à esquerda Rotação à direita Definir AVL Rotação direitaesquerda Árvore AVL void avlRotDirNO raiz NO temp temp raizesq raizesq tempdir tempdir raiz raizfb 0 raiz temp raiz ptrRaiz 2 7 1 5 0 2 7 5 5 5 7 7 2 2 1 0 void avlRotDirNO raiz NO aux temp raizesq raizesq tempdir tempdir raiz raizfb 0 raiz temp raiz ptrRaiz aux 2 7 1 5 0 2 7 5 5 5 7 7 2 2 1 0 void avlRotDirNO raiz NO aux aux raizesq raizesq tempdir tempdir raiz raizfb 0 raiz temp raiz ptrRaiz aux 2 7 1 5 0 2 7 5 5 5 7 7 2 2 1 0 void avlRotDirNO raiz NO aux aux raizesq raizesq auxdir tempdir raiz raizfb 0 raiz temp raiz ptrRaiz 2 7 1 5 0 2 7 5 5 5 7 7 2 2 0 NULL NULL 1 aux void avlRotDirNO raiz NO aux aux raizesq raizesq auxdir auxdir raiz raizfb 0 raiz temp raiz ptrRaiz 2 7 1 5 0 2 7 5 5 5 7 7 2 2 1 0 aux void avlRotDirNO raiz NO aux aux raizesq raizesq auxdir auxdir raiz raizfb 0 raiz temp 1 5 aux 2 7 0 2 raiz ptrRaiz 2 5 7 1 0 2 void avlRotDirNO raiz NO aux aux raizesq raizesq auxdir auxdir raiz raizfb 0 raiz temp 1 5 aux 0 7 0 2 raiz ptrRaiz 2 5 7 1 0 0 void avlRotDirNO raiz NO aux aux raizesq raizesq auxdir auxdir raiz raizfb 0 raiz aux 1 5 aux 0 7 0 2 raiz ptrRaiz 2 5 7 1 0 0 1 5 0 7 0 2 raiz ptrRaiz FB do nóraiz será corrigido pela função que chamar avlRotDir Rotação à direita 2 5 7 1 0 0 Rotação à direita void avlRotDirNO raiz NO aux aux raizesq raizesq auxdir auxdir raiz raizfb 0 raiz aux Rotação à direita Implementação Dinâmica Rotação esquerdadireita Rotação à esquerda Definir AVL Rotação direitaesquerda Árvore AVL Exercício 2 Implementar a função da árvore AVL de rotação simples à esquerda Rotação à direita Implementação Dinâmica Rotação esquerdadireita Rotação à esquerda Definir AVL Rotação direitaesquerda Árvore AVL void avlRotEsqDirNO raiz NO fE NO ffd fE raizesq ffD fEdir fEdir ffDesq ffDesq fE raiz ptrRaiz 2 7 1 5 0 6 2 7 5 5 6 7 1 0 void avlRotEsqDirNO raiz NO fE NO ffD fE raizesq ffD fEdir fEdir ffDesq ffDesq fE raiz ptrRaiz 2 7 1 5 0 6 7 5 5 6 7 1 Criar os ponteiros e os colocar em posição 0 2 void avlRotEsqDirNO raiz NO fE NO ffD fE raizesq ffD fEdir fEdir ffDesq ffDesq fE ptrRaiz 2 7 1 5 0 6 7 5 5 6 7 1 raiz fE 0 2 void avlRotEsqDirNO raiz NO fE NO ffD fE raizesq ffD fEdir fEdir ffDesq ffDesq fE ptrRaiz 2 7 1 5 0 6 7 5 5 6 7 1 0 raiz fE ffD 2 void avlRotEsqDirNO raiz NO fE NO ffD fE raizesq ffD fEdir fEdir ffDesq ffDesq fE ptrRaiz 2 7 1 5 0 6 7 5 5 6 7 1 raiz fE ffD Primeira rotação para a esquerda 0 2 void avlRotEsqDirNO raiz NO fE NO ffD fE raizesq ffD fEdir fEdir ffDesq ffDesq fE ptrRaiz 2 7 1 5 0 6 7 5 5 6 7 1 raiz fE ffD Primeira rotação para a esquerda 0 2 NULL NULL void avlRotEsqDirNO raiz NO fE NO ffD fE raizesq ffD fEdir fEdir ffDesq ffDesq fE ptrRaiz 2 7 1 5 0 6 raiz fE ffD Primeira rotação para a esquerda 7 5 5 6 7 1 0 2 void avlRotEsqDirNO raiz NO fE NO ffD fE raizesq ffD fEdir fEdir ffDesq ffDesq fE ptrRaiz 2 7 1 5 0 6 2 5 6 7 1 0 raiz fE ffD Primeira rotação para a esquerda void avlRotEsqDirNO raiz raizesq ffDdir ffDdir raiz ifffDfb 1 raizfb 1 else raizfb 1 Segunda rotação para a direita ptrRaiz 2 7 1 5 0 6 2 5 6 7 1 0 raiz fE ffD void avlRotEsqDirNO raiz raizesq ffDdir ffDdir raiz ifffDfb 1 raizfb 1 else raizfb 1 Segunda rotação para a direita ptrRaiz 2 7 1 5 0 6 2 5 6 7 1 0 raiz fE ffD NULL NULL void avlRotEsqDirNO raiz raizesq ffDdir ffDdir raiz ifffDfb 1 raizfb 1 else raizfb 1 Segunda rotação para a direita ptrRaiz 2 7 1 5 0 6 2 5 6 7 1 0 raiz fE ffD 2 void avlRotEsqDirNO raiz raizesq ffDdir ffDdir raiz ifffDfb 1 raizfb 1 else raizfb 0 Acertar o FB do nó apontado pelo ponteiro raiz ptrRaiz 2 7 1 5 0 6 5 6 7 1 0 raiz fE ffD void avlRotEsqDirNO raiz raizesq ffDdir ffDdir raiz ifffDfb 1 raizfb 1 else raizfb 0 ptrRaiz 2 7 1 5 0 6 2 5 6 7 1 0 raiz fE ffD void avlRotEsqDirNO raiz raizesq ffDdir ffDdir raiz ifffDfb 1 raizfb 1 else raizfb 0 ptrRaiz 2 7 1 5 0 6 5 6 7 1 0 raiz fE ffD False 2 void avlRotEsqDirNO raiz raizesq ffDdir ffDdir raiz ifffDfb 1 raizfb 1 else raizfb 0 ptrRaiz 0 7 1 5 0 6 0 5 6 7 1 0 raiz fE ffD void avlRotEsqDirNO raiz ifffDfb 1 fEfb 1 else fEfb 0 raiz ffD 0 5 6 7 1 0 ptrRaiz 0 7 1 5 0 6 raiz fE ffD Acertar o FB do nó apontado pelo ponteiro fE void avlRotEsqDirNO raiz ifffDfb 1 fEfb 1 else fEfb 0 raiz ffD 0 5 6 7 1 0 ptrRaiz 0 7 1 5 0 6 raiz fE ffD False void avlRotEsqDirNO raiz ifffDfb 1 fEfb 1 else fEfb 0 raiz ffD 0 5 6 7 0 0 ptrRaiz 0 7 0 5 0 6 raiz fE ffD void avlRotEsqDirNO raiz ifffDfb 1 fEfb 1 else fEfb 0 raiz ffD 0 5 6 7 0 0 ptrRaiz 0 7 0 5 0 6 raiz fE ffD void avlRotEsqDirNO raiz NO fE NO ffD fE raizesq ffD fEdir fEdir ffDesq ffDesq fE raizesq ffDdir ffDdir raiz ifffDfb 1 raizfb 1 else raizfb 0 ifffDfb 1 fEfb 1 else fEfb 0 raiz ffD Acertar o FB do nó apontado por fE Acertar o FB do nó apontado por raiz Segunda rotação para a direita Primeira rotação para a esquerda Ponteiros colocados em posição Fator de balanceamento Existem três situações para atualizar o fator de balanceamento na rotação esquerdadireita Situação 3 Fator de balanceamento fE 1 ffD 1 raiz 2 4 8 10 2 6 5 fE 1 ffD 1 raiz 2 4 8 10 2 6 7 fE 1 ffD 0 raiz 2 4 8 10 2 6 5 7 Situação 1 Situação 2 Fator de balanceamento Situação 1 0 ffD 1 4 8 10 2 6 5 4 8 10 2 6 5 Árvore balanceada fE 1 raiz 2 Fator de balanceamento Situação 1 0 ffD 1 4 8 10 2 6 5 4 8 10 2 6 5 raiz 1 raiz 2 ifffDfb 1 raizfb 1 else raizfb 0 Fator de balanceamento Situação 1 0 fE 1 ffD 1 4 8 10 2 6 5 4 8 10 2 6 5 fE 0 ifffDfb 1 fEfb 1 else fEfb 0 Fator de balanceamento Situação 2 0 fE 1 ffD 1 raiz 2 4 8 10 2 6 7 4 8 10 2 6 7 Árvore balanceada Fator de balanceamento Situação 2 0 ffD 1 raiz 2 4 8 10 2 6 7 4 8 10 2 6 7 raiz 0 ifffDfb 1 raizfb 1 else raizfb 0 Fator de balanceamento Situação 2 0 fE 1 ffD 1 4 8 10 2 6 7 4 8 10 2 6 7 fE 1 ifffDfb 1 fEfb 1 else fEfb 0 Fator de balanceamento Situação 3 0 fE 1 ffD 0 raiz 2 4 8 10 2 6 7 5 4 8 10 2 6 7 Árvore balanceada 5 Fator de balanceamento Situação 3 0 ffD 0 raiz 2 4 8 10 2 6 7 5 4 8 10 2 6 7 5 raiz 0 ifffDfb 1 raizfb 1 else raizfb 0 Fator de balanceamento Situação 3 0 fE 1 ffD 0 4 8 10 2 6 7 5 4 8 10 2 6 7 5 fE 0 ifffDfb 1 fEfb 1 else fEfb 0 Rotação esquerdadireita Rotação à direita Implementação Dinâmica Rotação à esquerda Definir AVL Rotação direitaesquerda Árvore AVL Exercício 3 Implementar a função da árvore AVL de rotação dupla direitaesquerda Inserir um elemento Implementação Dinâmica Remover um elemento Árvore AVL Etapas da inserção 1 Buscar o elemento x na árvore AVL Se x existir na árvore Nada precisa ser feito Caso contrário Encontrar a posição de inserção Inserir o novo elemento na árvore Etapas da inserção 2 Verificar se a inserção desbalanceou algum nó Em caso negativo A inserção termina Em caso positivo Realizar o rebalanceamento da árvore a partir das operações de rotação simples dupla Funções auxiliares Inserção Para auxiliar na operação de inserção foram criadas duas funções auxiliares avlAux1 avlAux2 Função auxiliar 1 Inserção Para auxiliar na operação de inserção foram criadas duas funções auxiliares avlAux1 avlAux2 Função auxiliar 1 Inserção Elemento foi inserido à esquerda de raiz e causou o desbalanceamento FBraiz 2 novo elemento novo elemento Rotação simples à direita Função auxiliar 1 Inserção Caso 1 7 5 5 7 3 2 raiz fE 1 Caso 2 7 5 5 7 6 2 raiz fE 1 Rotação dupla esquerdadireita void avlAux1NO raiz NO fE fE raizesq iffEfb 1 Sinais iguais e positivo avlRotDirraiz else Sinais diferentes avlRotEsqDirraiz raiz fb 0 Função auxiliar 1 Inserção Função auxiliar 2 Inserção Para auxiliar na operação de inserção foram criadas duas funções auxiliares avlAux1 avlAux2 Função auxiliar 2 Inserção Elemento foi inserido à direita de raiz e causou o desbalanceamento FBraiz 2 Dois casos novo elemento Função auxiliar 2 Inserção novo elemento Rotação simples à esquerda Caso 1 7 5 7 4 3 raiz fD 9 2 1 Caso 2 Rotação dupla direitaesquerda 7 7 4 3 raiz fD 5 2 1 void avlAux2NO raiz NO fD fD raizdir iffDfb 1 Sinais iguais e negativo avlRotEsqraiz else Sinais diferentes avlRotDirEsqraiz raiz fb 0 Função auxiliar 2 Inserção int avlinserirNO raiz int elem int ok ifraiz NULL raiz alocarNo ifraiz NULL return 0 raizesq NULL raizdir NULL raizinfo elem raizfb 0 return 1 Ávore AVL inserção ifelem raizinfo recursividade à esquerda ok avlinserirraizesq elem ifok switchraizfb case 1 raizfb 0 ok 0 break case 0 raizfb1 break case 1 avlAux1raiz ok 0 break verificar FB de raiz era mais alto à direita fica com FB0 interrompe propagação de balanceamento ficou com esquerda maior e propaga FB FB 2 interrompe a propagação do balanceamento else ifelem raizinfo recursividade à direita ok avlinserirraizdir elem ifok switchraizfb case 1 raizfb 0 ok 0 break case 0 raizfb 1 break case 1 avlAux2raiz ok 0 break verificar FB de raiz era mais alto à direita fica com FB0 interrompe propagação de balanceamento ficou com direita maior e propaga FB FB 2 interrompe a propagação do balanceamento else ok 0 return ok Inserir um elemento Implementação Dinâmica Remover um elemento Árvore AVL Árvore AVL Remoção Aplicar o algoritmo de remoção de um nó em uma Árvore Binária de Pesquisa Três casos são considerados Caso 1 o nó é folha Caso 2 o nó possui uma subárvore esq ou dir Caso 3 o nó possui as duas subárvores esq e dir Substituir pelo maior valor da subárvore esquerda Substituir pelo menor valor da subárvore direita Árvore AVL Remoção Após a remoção de um nó atualizar os fatores de balanceamento do ascendente do nó removido até a raiz Para cada nó nesse caminho cujo fator de balanceamento se torne 2 ou 2 efetuar rotações simples ou dupla O rebalanceamento NÃO pára quando o primeiro nó com fator de balanceamento 2 ou 2 é encontrado como na inserção Árvore balanceada Árvore AVL Remoção Exemplo 1 10 20 30 1 5 1 0 0 Árvore AVL Remoção Exemplo 1 10 20 30 5 10 20 30 2 1 0 1 1 0 0 Raciocínio Que nó inserido teria causado o desequilíbrio 10 20 30 Rotação simples à esquerda Árvore balanceada Árvore AVL Remoção Exemplo 2 10 12 8 1 5 0 0 1 Árvore AVL Remoção Exemplo 2 10 12 8 5 1 0 0 1 10 8 2 5 0 1 Raciocínio Que nó inserido teria causado o desequilíbrio Rotação dupla esquerdadireita 5 8 10 Árvore balanceada Árvore AVL Remoção Exemplo 3 6 10 12 1 2 0 0 0 8 0 Árvore AVL Remoção Exemplo 3 6 10 12 2 8 1 0 0 0 0 6 10 12 8 2 0 0 0 Raciocínio Que nó inserido teria causado o desequilíbrio Árvore AVL Remoção Exemplo 3 6 10 12 8 2 0 Solução escolhese arbitrariamente um desses dois nós desprezase o outro e simulase a sua inserção 0 0 Árvore AVL Remoção Exemplo 3 6 10 12 2 1 0 8 0 Por exemplo Escolhese o nó 12 e deprezase o nó 8 Árvore AVL Remoção Exemplo 3 6 10 12 8 2 0 0 0 6 10 12 Rotação simples à esquerda Árvore AVL Remoção Exemplo 3 8 6 10 12 1 1 0 0 Recolocar o nó 8 na árvore Exercício 4 Como ficaria a árvore se escolhêssemos o nó 8 e desprezássemos o nó 12 6 10 12 8 2 0 0 0 Árvore AVL Remoção Existem situação mais complexas O processo de balanceamento após a retirada de um nó pode provocar um novo desequílibrio na árvore Solução Reaplicar as rotações quantas vezes forem necessárias Referências Bibliográficas Ascencio A F G Araújo G S de 2010 Estruturas de Dados algoritmos análise da complexidade e implementações em JAVA e C São Paulo Pearson Prentice Hall Forbellone A L V Eberspacher H F 2005 Lógica de Programação A construção de algoritmos e estruturas de dados 3ª edição São Paulo Pearson Prentice Hall