Desenhe a árvore AVL formada pela inserção dos números de 1 a 12 em ordem crescente.
Passo 1
Beleza, vamos resolver esse exercício juntos! A questão pede para desenhar uma árvore AVL resultante da inserção dos números de 1 a 12 em ordem crescente. Uma árvore AVL é um tipo de árvore binária de busca que mantém-se balanceada automaticamente após cada inserção ou remoção, garantindo que a altura das subárvores esquerda e direita de qualquer nó difira no máximo por 1.
Para resolver isso, vamos precisar entender como funciona a inserção em árvores binárias de busca e como a própria árvore AVL verifica e ajusta o balanceamento usando rotações. Vamos passo a passo inserir cada número de 1 a 12 e fazer os ajustes necessários para manter a árvore balanceada.
Passo 2
Vamos começar inserindo o número 1. Como a árvore está vazia, esse será o nó raiz.
1
Passo 3
Agora, inserimos o número 2. Como 2 é maior que 1, ele vai para a direita do nó 1.
1
\
2
A árvore ainda está balanceada, pois a diferença de altura entre as subárvores esquerda e direita do nó 1 é 1, que está dentro do limite permitido.
Passo 4
Inserimos o número 3. Comparando com 1 e depois com 2, 3 é maior que ambos, então vai para a direita do 2.
1
\
2
\
3
Agora, a árvore está desbalanceada. O nó 1 tem uma subárvore direita de altura 2 e nenhuma subárvore à esquerda, o que gera uma diferença de altura de 2. Para corrigir isso, realizamos uma rotação à esquerda no nó 1.
Após a rotação, a árvore fica assim:
2
/ \
1 3
Agora, a árvore está balanceada novamente.
Passo 5
Vamos inserir o número 4. Começando no nó 2, 4 é maior, vai para a direita do 2, depois maior que 3, vai para a direita do 3.
2
/ \
1 3
\
4
A diferença de altura no nó 2 é 2 (subárvore direita com altura 2 e esquerda com altura 1), então precisamos rebalancear. Fazemos uma rotação à esquerda no nó 2.
3
/ \
2 4
/
1
Agora, a árvore está balanceada.
Passo 6
Inserindo o número 5. Comparando com 3, depois com 4, e depois maior, vai para a direita de 4.
3
/ \
2 4
/ \
1 5
A árvore ainda está balanceada, já que a diferença de altura entre as subárvores de cada nó é no máximo 1.
Passo 7
Inserimos o número 6. Seguimos para a direita de 3, de 4, de 5, e insere à direita de 5.
3
/ \
2 4
/ \
1 5
\
6
Agora, o nó 4 tem uma subárvore direita com altura 2 e nenhuma à esquerda, diferença de altura 2. Realizamos uma rotação à esquerda no nó 4.
3
/ \
2 5
/ / \
1 4 6
A árvore está balanceada novamente.
Passo 8
Vamos inserir o número 7. Vai para a direita de 3, de 5, de 6, e insere à direita de 6.
3
/ \
2 5
/ / \
1 4 6
\
7
O nó 5 agora tem uma subárvore direita com altura 2 e a esquerda com altura 1, diferença de altura 1. A árvore continua balanceada.
Passo 9
Inserindo o número 8. Segue para a direita de 3, de 5, de 6, de 7, e insere à direita de 7.
3
/ \
2 5
/ / \
1 4 6
\
7
\
8
O nó 6 fica desbalanceado com diferença de altura 2. Realizamos uma rotação à esquerda no nó 6.
3
/ \
2 5
/ / \
1 4 7
/ \
6 8
A árvore está balanceada novamente.
Passo 10
Agora, inserimos o número 9. Vai para a direita de 3, de 5, de 7, de 8, e insere à direita de 8.
3
/ \
2 5
/ / \
1 4 7
/ \
6 8
\
9
O nó 7 tem uma subárvore direita com altura 2 e a esquerda com altura 1, diferença de altura 1. A árvore permanece balanceada.
Passo 11
Inserimos o número 10. Segue para a direita de 3, de 5, de 7, de 8, de 9, e insere à direita de 9.
3
/ \
2 5
/ / \
1 4 7
/ \
6 8
\
9
\
10
O nó 8 fica desbalanceado. Fazemos uma rotação à esquerda no nó 8.
3
/ \
2 5
/ / \
1 4 7
/ \
6 9
/ \
8 10
A árvore está balanceada novamente.
Passo 12
Finalmente, inserimos o número 12. Vai para a direita de 3, de 5, de 7, de 9, de 10, e insere à direita de 10.
3
/ \
2 5
/ / \
1 4 7
/ \
6 9
/ \
8 10
\
12
O nó 10 está desbalanceado. Realizamos uma rotação à esquerda no nó 10.
3
/ \
2 5
/ / \
1 4 7
/ \
6 9
/ \
8 12
/
10
Agora, a árvore está completamente balanceada.
Resposta
A árvore AVL resultante após inserir os números de 1 a 12 em ordem crescente é:
3
/ \
2 5
/ / \
1 4 7
/ \
6 9
/ \
8 12
/
10
Exercícios relacionados
Prove ou dê um contraexemplo para as afirmações abaixo:
© Toda árvore estritamente binária é AVL.
© Toda árvore estritamente binária é AVL.
Prove ou dê um contraexemplo para as afirmações abaixo:
(a) Toda árvore cheia é completa.
(a) Toda árvore cheia é completa.
Implemente uma rotação dupla à esquerda sem utilizar uma rotação direita e depois uma esquerda.
Desenhe passo a passo a ávore AVL resultante da inserção dos elementos 5, 7, 11,
e 3, nesta ordem, indicando as rotações que foram executadas.