Prove ou dê um contraexemplo para as afirmações abaixo:
© Toda árvore estritamente binária é AVL.
© Toda árvore estritamente binária é AVL.
Passo 1
Primeiro, vamos entender o que a questão está pedindo. Queremos saber se toda árvore estritamente binária é uma árvore AVL. Para resolver isso, vamos precisar conhecer dois conceitos: árvore estritamente binária e árvore AVL.
Passo 2
Árvore Estritamente Binária é uma árvore onde cada nó tem exatamente 0 ou 2 filhos. Ou seja, nenhum nó tem apenas um filho.
Árvore AVL é um tipo especial de árvore binária de busca que está sempre balanceada. Isso significa que, para cada nó da árvore, a diferença de altura entre a subárvore esquerda e a subárvore direita é, no máximo, 1.
Passo 3
Vamos analisar se toda árvore estritamente binária satisfaz a condição de ser uma árvore AVL. Para isso, precisamos ver se é possível ter uma árvore estritamente binária que não seja AVL.
Passo 4
Vamos criar um contraexemplo. Imagine a seguinte árvore estritamente binária:
1
/ \
2 3
/ \
4 5
/ \
6 7
Passo 5
Vamos verificar se essa árvore é AVL. Olhando o nó 2:
- A subárvore esquerda (com raiz em 4) tem altura 2 (nós 4, 6, 7).
- A subárvore direita (com raiz em 5) tem altura 1.
A diferença de altura é 2 - 1 = 1, o que ainda está dentro do permitido. Vamos aprofundar mais.
Passo 6
Agora, olhemos o nó 1:
- A subárvore esquerda (com raiz em 2) tem altura 3 (nós 2, 4, 6, 7).
- A subárvore direita (com raiz em 3) tem altura 1.
A diferença de altura é 3 - 1 = 2, que é maior que 1. Portanto, essa árvore não é AVL.
Resposta
Encontramos um contraexemplo: a árvore estritamente binária mostrada acima não é uma árvore AVL, provando que nem toda árvore estritamente binária é AVL.
Exercícios relacionados
Prove ou dê um contraexemplo para as afirmações abaixo:
(a) Toda árvore cheia é completa.
(a) Toda árvore cheia é completa.
Detalhar o algoritmo de remoção de nós em árvores AVL.
Desenhe a árvore AVL formada pela inserção dos números de 1 a 12 em ordem crescente.
Implemente uma rotação dupla à esquerda sem utilizar uma rotação direita e depois uma esquerda.