Dê um pequeno exemplo de como adicionar um número a uma árvore AVL causando uma árvore desbalanceada do tipo direita direita. Rebalancear a árvore.

Passo 1

O enunciado pede um exemplo de inserção em árvore AVL que gere desequilíbrio do tipo direita–direita e depois seja consertado via rotação. O conteúdo envolve árvores AVL, fator de balanceamento e rotação à esquerda.

Passo 2

Começamos com a árvore contendo apenas o nó 10. Estrutura: raiz = 10, sem filhos. A altura é 0 e ela está perfeitamente balanceada.

Passo 3

Inserimos o valor 20. Como 20 > 10, ele se torna filho direito de 10. A árvore agora é:
10

20
Calculamos o fator de balanceamento de 10:
BF(10)=h(direita)-h(esquerda)=1-0=1
Como |BF(10)|<=1, continua balanceada.

Passo 4

Inserimos o valor 30. Ele vai para a direita de 10 e depois à direita de 20. A árvore fica:
10

20

30
Aqui temos
BF(20)=1-0=1
mas
BF(10)=h(direita)-h(esquerda)=2-0=2
Como BF(10)=2 e o caminho de inserção foi direita–direita, configuramos um caso DD.

Passo 5

Para rebalancear no caso direita–direita, aplicamos rotação simples à esquerda no nó 10. O 20 sobe para raiz, o 10 vira filho esquerdo de 20 e o 30 permanece como filho direito de 20. Resultado:
20
/
10 30
Agora todos os fatores de balanceamento voltam a ser 0, e a árvore está balanceada novamente.

Resposta

Árvore rebalanceada: raiz 20, com filho esquerdo 10 e filho direito 30.

Exercícios relacionados