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
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
Agora altura de 30: altura(esquerda)=0, altura(direita)=2.
Calculamos o fator de balanceamento de 30: BF(30)=0-2=-2 indicando desbalanceamento. E no filho 40 temos BF(40)=0-1=-1, caracterizando o caso direita–direita (RR).

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
Com fatores de balanceamento:
BF(40)=0, BF(30)=0 e BF(50)=0, retornando assim a propriedade AVL.

Exercícios relacionados