Dê um pequeno exemplo de remoção de um número de um árvore AVL causando uma árvore desbalanceada do tipo direita-direita. Rebalancear a árvore.
Passo 1
O enunciado pede um exemplo de remoção de um nó em uma árvore AVL que provoque um desbalanceamento do tipo direita–direita e, em seguida, o rebalanceamento usando rotação simples à esquerda. O conteúdo envolve definição de fator de balanceamento, detecção de caso RR e aplicação da rotação.
Passo 2
Vamos criar uma árvore AVL pequena com os nós 30, 20, 40 e 50, de modo que ela fique balanceada antes da remoção. A estrutura é:
30
/
20 40
50
/
20 40
50
Calculando alturas (altura de nó nulo = 0, de folha = 1): altura(20)=1, altura(50)=1, altura(40)=2, altura(30)=3. Os fatores de balanceamento são todos em {–1,0,1}, logo está balanceada.
Passo 3
Removemos o nó 20. A árvore passa a ser:
30
40
50
40
50
Agora altura de 30: altura(esquerda)=0, altura(direita)=2.
Calculamos o fator de balanceamento de 30: indicando desbalanceamento. E no filho 40 temos
, caracterizando o caso direita–direita (RR).
Calculamos o fator de balanceamento de 30:
Passo 4
Para corrigir o desequilíbrio RR, aplicamos uma rotação simples à esquerda em 30. Nessa rotação, 40 sobe para a raiz, 30 vira filho esquerdo de 40 e 50 permanece filho direito de 40.
Resposta
Árvore resultante após a rotação à esquerda em 30:
40
/
30 50
30 50
Com fatores de balanceamento: