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

Passo 1

A questão pede para exemplificar a inserção de um valor em uma árvore AVL que gere um desequilíbrio do tipo direita–esquerda (RL) e em seguida mostrar como fazer o rebalanceamento.

Passo 2

Começamos com uma árvore AVL simples, perfeita e balanceada, contendo os nós 10 (raiz) e 20 (filho direito):
10

20
Aqui o fator de balanceamento de 10 é 0 (altura direita 1 menos altura esquerda 0).

Passo 3

Inserimos o valor 15 como em uma BST normal, comparando com a raiz 10 e depois com 20. A árvore fica:
10

20
/
15
Agora recalculamos fatores de balanceamento:
  • No nó 20: altura direita 0, esquerda 1 ⇒ bf(20) = –1 (balanceado)
  • No nó 10: altura direita 2, esquerda 0 ⇒ bf(10) = +2 (desequilíbrio)
    Como o filho direito (20) tem bf negativo, é o caso RL.

Passo 4

Para resolver RL, aplicamos duas rotações:
  1. Rotação à direita em 20: faz de 15 o novo filho direito de 10:
    10

    15

    20
  2. Rotação à esquerda em 10: faz de 15 a nova raiz:
    15
    /
    10 20

Passo 5

A árvore agora está balanceada, com todos os fatores de balanceamento entre –1 e +1.

Resposta

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

Exercícios relacionados