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:
10
20
Calculamos o fator de balanceamento de 10:
Como
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
10
20
30
Aqui temos
mas
Como
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.
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.