Implemente uma versão da AVL em que a condição de balanceamento seja:
Passo 1
Então, galera! A gente tem um exercício que pede pra gente implementar uma árvore AVL, mas com uma condição de balanceamento um pouquinho diferente. Normalmente, numa árvore AVL padrão, a diferença de altura entre a subárvore direita e a esquerda de qualquer nó não pode ser maior que 1. Mas aqui, a condição é que essa diferença seja no máximo 2. Para resolver isso, vamos precisar entender o que é uma árvore AVL, como funciona o balanceamento dela, e como ajustar as rotações para manter essa nova condição de balanceamento.
Passo 2
Primeiro, vamos lembrar o que é uma árvore AVL. É uma árvore binária de busca que mantém-se balanceada automaticamente, garantindo que as operações de busca, inserção e remoção sejam eficientes. O balanceamento é mantido pela condição que a diferença de altura entre as subárvores esquerda e direita de qualquer nó seja no máximo 1.
Passo 3
Agora, como nossa condição mudou para permitir uma diferença de até 2, precisamos adaptar os métodos de balanceamento. Isso significa que, após cada inserção ou remoção, vamos verificar se a diferença de altura entre as subárvores de algum nó ultrapassou 2. Se sim, vamos precisar realizar rotações para balancear a árvore.
Passo 4
Vamos falar sobre as rotações. Em uma árvore AVL padrão, temos rotações simples e duplas para corrigir o balanceamento quando a diferença de altura é maior que 1. Como agora a diferença permitida é maior, podemos precisar de rotações mais específicas para corrigir quando a diferença for exatamente 2.
Passo 5
Para implementar isso, vamos precisar modificar as funções de inserção e remoção. Após cada operação, vamos calcular a altura das subárvores esquerda e direita de cada nó e verificar se a diferença absoluta é maior que 2. Se for, aplicamos as rotações necessárias para reequilibrar a árvore.
Passo 6
Vamos também precisar ajustar a função que calcula a altura de cada nó. Isso porque, com a nova condição, a maneira como atualizamos e verificamos a altura pode ser um pouco diferente. Vamos garantir que a altura esteja sempre correta após cada inserção ou remoção.
Passo 7
Por fim, vamos testar nossa implementação com alguns casos de inserção e remoção para ver se a árvore mantém o balanceamento conforme a nova condição estabelecida. Isso ajuda a garantir que tudo está funcionando direitinho.
Resposta
Implementando as modificações mencionadas, conseguimos uma versão da árvore AVL onde a diferença de altura entre as subárvores direita e esquerda de qualquer nó é no máximo 2, mantendo a árvore balanceada conforme a nova condição estabelecida.
Exercícios relacionados
Dê exemplo de uma família de árvores AVL cuja exclusão de nós implica a realização de
operações de rotação para o rebalanceamento.
Descreva a estrutura de uma árvore AVL formada pela inserção dos números de 1 a n em ordem crescente. Qual é a altura dessa árvore?
Qual o número mínimo e máximo de nós em uma árvore AVL de altura
? Justifique sua resposta.
Mostre uma árvore AVL
que possua um nó
cuja remoção resulta em uma árvore não-AVL
, tal que
não possa ser balanceada por meio de uma única rotação (simples ou dupla). Desenhe a árvore
, especifique o nó a a ser removido, e explique por quê a árvore resultante
não pode ser balanceada com uma única rotação.