Remoção de Nós em Árvores AVL

Árvores AVL Prof Ricardo Porto Contato ricardoaportosouunitcombr 1 Remoção de Nós em Uma Árvore Binária A remoção de nós em uma árvore binária requer uma série de testes para determinar como os filhos dos nós serão reatados A seguir veremos as 03 situações existentes Remoção de Nós em Uma Árvore Binária 1 O nó a ser removido não tem filhos isto é ele é uma folha como é o caso do nó 35 da seguinte árvore Neste caso basta atualizar o ponteiro do pai para que ele aponte para uma subárvore vazia Remoção de Nós em Uma Árvore Binária Remoção de Nós em Uma Árvore Binária 2 O nó a ser removido tem somente um filho esquerdo ou direito como é o caso do nó 40 da seguinte figura Neste caso fazemos com que o pai aponte para o filho do nó removido Remover Nó 3 Nós iremos utilizar o seguinte algoritmo para reatar essas subárvores de modo que as propriedades da árvore binária de busca sejam mantidas Introdução As árvores binárias foram projetadas para conseguirmos um acesso rápido aos dados entretanto dependendo da ordem de chegada dos dados a árvore pode ficar degenerada Introdução Considere duas árvores Binárias de Busca obtidas de uma árvore vazia e da inserção dos números de 1 a 5 1 Primeira árvore os números foram inseridos na ordem 21435 2 Segunda foram inseridos na ordem 1 2 3 4 5 3 Como fazer para balancear esta árvore Árvores de busca AVL Por esta razão em 1962 dois matemáticos russos G M Adelson Velskii e E M Landis criaram uma estrutura de árvore binária balanceada os quais denominaram de árvores AVL Uma árvore AVL é uma árvore binária de busca onde a diferença entre as duas subárvores de cada nó é de no máximo uma unidade Árvores de busca AVL As árvores AVL têm uma representação similar às árvores binárias de busca sendo que as operações de inserção e remoção têm de monitorar constantemente as alturas das subárvores esquerda e direita do nó Para manter essa informação iremos adicionar mais um campo no nó da árvore chamado balanço Árvores de busca AVL class Node String nome Node filhoEsq Node filhoDir int Balanco Node pai Árvores de busca AVL O valor do balanço será Balanço AlturaSubárvoreesquerda AlturaSubárvoredireita Se o valor do balanço for negativo indica que o nó está mais pesado no lado direito enquanto que se seu valor for positivo o nó está mais pesado no lado esquerdo Se for zero o nó está equilibrado Árvores de busca AVL Em uma árvore AVL o balanço deverá estar sempre no intervalo de 1 a 1 Árvores de busca AVL Em uma árvore AVL o balanço deverá estar sempre no intervalo de 1 a 1 Inserção em Árvores de Busca AVL A inserção de um nó em uma árvore AVL é semelhante à inserção em uma árvore binária de busca No entanto a depender do local onde o nó será inserido a árvore resultante poderá deixar de ser balanceada Inserção em Árvores de Busca AVL Por exemplo a figura seguinte mostra a árvore resultante ao ser inserida a chave 5 Mesmo após a inserção a árvore permaneceu balançeada Inserção em Árvores de Busca AVL Observe agora o que acontece ao ser inserida a chave 60 na mesma árvore Neste caso a árvore resultante ficou desbalanceada Inserção em Árvores de Busca AVL Dicas Se no caminho onde o nó vai ser inserido todos os balanços têm o valor zero a árvore resultante vai continuar balanceada Se o caminho onde o nó vai ser inserido existir algum balanço diferente de zero a árvore resultante continuará balanceada se a inserção for feita no lado mais leve Se a inserção for feita no lado mais pesado a árvore ficará desbalanceada Inserção em Árvores de Busca AVL O ponto crítico em uma árvore AVL é a presença de balanços diferentes de zero Sendo assim iremos dar atenção especial ao nó com balanço diferente de zero mais próximo do lugar onde o novo nó será inserido Esse nó iremos denominar de pivô Inserção em Árvores de Busca AVL Se formos inserir 15 o pivô será o nó 20 ao passo que se formos inserir 48 o pivô será o nó 45 Logo Pivô será o nó com balanço diferente de zero mais próximo do local onde o novo nó será inserido Inserção em Árvores de Busca AVL Após cada inserção em uma árvore AVL temos que verificar se algum nó ficou desbalanceado Ou seja se a diferença de altura entre suas duas subárvores ficou fora do intervalo entre 1 e 1 Balanceando a árvore AVL Se a árvore ficar desbalanceada precisamos efetuar algumas transformações na árvore para que ela volte a ficar balanceada Balanceando a árvore AVL Essas transformações são denominadas rotações podendo ocorrer um dos seguintes casos Rotação simples para a direita Rotação simples para a esquerda Rotação Dupla Direita uma para a esquerda outra para a direita Rotação dupla Esquerda uma para a direita e outra para a esquerda Rotação simples para a direita Exemplo de rotação simples para a direita Rotação simples para a esquerda Exemplo de rotação simples para a esquerda Rotação dupla à Direita uma para a esquerda outra para a direita É feita uma rotação simples para a esquerda em torno do filho esquerdo do pivô seguida de uma rotação simples para a direita em torno do pivô Rotação dupla à Esquerda uma para a direita outra para a esquerda É feita uma rotação para a direita em torno do filho direito do pivô seguida de uma rotação para a esquerda em torno do pivô Observações Para descobrir se a rotação é simples ou dupla após a inclusão encontrar fator de balanceamento de um nó e verificar se é igual a 2 ou 2 Fator de Balanceamento 2 e fator de balanceamento do filho Esquerdo 1 Aplico a Rotação dupla à Direita Fator de Balanceamento 2 e fator de balanceamento do filho Direito 1 Aplico a Rotação dupla à Esquerda Remoção em Árvore AVL A remoção de um nó em uma árvore AVL pode também provocar seu desbalanceamento Para rebalancear a árvore usamos um processo semelhante ao que foi usado na inserção através do uso de rotações Exercícios Dadas as seguintes árvores AVL insira os elementos pedidos rebalanceando a árvore conforme necessário 1 Insira o elemento 5 na árvore abaixo 30 10 40 8 20 2 Insira o elemento 1 na árvore abaixo 10 5 30 3 8 20 40 2 Exercícios 3Insira o elemento 53 na árvore abaixo 40 32 46 44 50 4 Insira o elemento 43 na árvore abaixo 40 32 46 44 50 Exercícios 5 Insira o elemento 4 na árvore abaixo 10 7 30 5 8 20 40 2 6 Insira o número 27 na árvore abaixo 40 20 60 10 30 50 80 5 25 90 Exercícios 7 Insira o número 46 árvore abaixo 35 30 40 10 33 37 45 5 38 47 Exercícios Insira em uma árvore AVL itens com as chaves apresentadas nos itens a seguir na ordem em que aparecem Desenhe a árvore resultante da inserção sendo que uma nova árvore deve ser desenhada quando houver uma rotação Indique qual a rotação que foi executada a 30 40 24 58 48 26 11 13 14 b 20 15 25 10 30 24 17 12 5 3 c 40 30 50 45 55 52 d 20 15 25 12 17 24 30 10 14 13 e 20 15 25 12 17 30 26 Referências Costa Alberto Árvores Estrutura de Dados Disponível em httpalbertocnsytesnet20122ed1aulasárvoreshtm Costa Alberto Árvores Estrutura de Dados Disponível em httpalbertocnsytesnet20122ed1aulasárvoresbinariashtm COSTA Patrícia Dockhorn Estruturas de Dados Árvores Slides Vanessa Maily Árvores de Busca