Prove ou dê um contraexemplo para as afirmações abaixo:
© 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.
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.