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.
Passo 1
Beleza, vamos resolver esse exercício de árvores AVL! O enunciado pede para inserir os números 5, 7, 11, 17, 4, 6, 2, 1, 22 e 3, nessa ordem, e mostrar passo a passo como a árvore fica, indicando as rotações que acontecem. Vamos precisar entender o que é uma árvore AVL, que é um tipo de árvore binária de busca que se mantém balanceada usando rotações. Isso ajuda a garantir que as operações de busca, inserção e remoção sejam eficientes.
Passo 2
Primeiro, vamos inserir o 5 na árvore. Como a árvore está vazia, o 5 será a raiz.
5
Passo 3
Agora, inserimos o 7. Como 7 é maior que 5, ele vai para a direita de 5.
5
\
7
A árvore ainda está balanceada, então nada mais precisa ser feito.
Passo 4
Em seguida, inserimos o 11. 11 é maior que 5 e também maior que 7, então vai para a direita de 7.
5
\
7
\
11
Agora, verificamos o balanceamento. O nó 5 tem um fator de balanceamento de -2 (altura à direita 2, à esquerda 0), então precisamos fazer uma rotação à esquerda no nó 5.
Após a rotação:
7
/ \
5 11
Passo 5
Vamos inserir o 17. 17 é maior que 7 e maior que 11, então vai para a direita de 11.
7
/ \
5 11
\
17
A árvore está balanceada, sem necessidade de rotações.
Passo 6
Inserimos o 4. 4 é menor que 7 e menor que 5, então vai para a esquerda de 5.
7
/ \
5 11
/ \
4 17
Balanceamento está ok, sem rotações necessárias.
Passo 7
Agora, inserimos o 6. 6 é menor que 7, mas maior que 5, então vai para a direita de 5.
7
/ \
5 11
/ \ \
4 6 17
A árvore continua balanceada.
Passo 8
Inserindo o 2. 2 é menor que 7, menor que 5 e menor que 4, então vai para a esquerda de 4.
7
/ \
5 11
/ \ \
4 6 17
/
2
Agora, o nó 5 tem um fator de balanceamento de +2 (esquerda 2, direita 1), que ainda está dentro do limite, então não precisa de rotação.
Passo 9
Vamos inserir o 1. 1 é menor que 7, 5, 4 e 2, então vai para a esquerda de 2.
7
/ \
5 11
/ \ \
4 6 17
/
2
/
1
Agora, o nó 4 tem fator de balanceamento de +2 (esquerda 2, direita 0), o que significa que precisamos fazer uma rotação à direita no nó 4.
Após a rota��ão:
7
/ \
5 11
/ \ \
2 6 17
/ \
1 4
Passo 10
Por fim, inserimos o 22. 22 é maior que 7, 11 e 17, então vai para a direita de 17.
7
/ \
5 11
/ \ \
2 6 17
/ \ \
1 4 22
A árvore está balanceada após essa inserção, sem necessidade de rotações.
Passo 11
Vamos inserir o 3. 3 é menor que 7, menor que 5, maior que 2 e menor que 4, então vai para a direita de 2.
7
/ \
5 11
/ \ \
2 6 17
/ \ \
1 4 22
/
3
Agora, o nó 2 tem fator de balanceamento de -1 (esquerda 1, direita 1), e o nó 5 tem fator de balanceamento de -1 também. A árvore continua balanceada, então não precisamos de rotações.
Resposta
A árvore AVL final após todas as inserções fica assim:
7
/ \
5 11
/ \ \
2 6 17
/ \ \
1 4 22
/
3
Foram realizadas rotações:
- Rotação à esquerda no nó 5 após inserir o 11.
- Rotação à direita no nó 4 após inserir o 1.
Exercícios relacionados
Implemente uma rotação dupla à esquerda sem utilizar uma rotação direita e depois uma esquerda.
Desenhe a árvore AVL formada pela inserção dos números de 1 a 12 em ordem crescente.
Prove que uma rotação dupla à direita pode ser obtida com uma rotação esquerda seguida de uma rotação direita.
Descreva a estrutura de uma árvore AVL formada pela inserção dos números de 1 a n em ordem crescente. Qual é a altura dessa árvore?