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).
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:
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:
- Rotação à direita em 20: faz de 15 o novo filho direito de 10:
10
15
20 - 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.