Prove ou dê um contraexemplo para as afirmações abaixo:
(a) Toda árvore cheia é completa.
(a) Toda árvore cheia é completa.
Passo 1
Beleza, vamos lá! O enunciado pede para a gente provar ou dar um contraexemplo para a afirmação: “Toda árvore cheia é completa.” Aqui, estamos lidando com conceitos de árvores binárias na teoria dos grafos. Para resolver isso, vamos precisar entender as definições de árvore cheia e árvore completa e ver se sempre que uma árvore é cheia, ela também é completa.
Passo 2
Primeiro, vamos relembrar o que é uma árvore cheia. Uma árvore cheia é uma árvore binária onde cada nó tem exatamente 0 ou 2 filhos. Não pode haver nós com apenas um filho.
Passo 3
Agora, vamos ver o que é uma árvore completa. Uma árvore completa é uma árvore binária onde todos os níveis, exceto o último, estão completamente preenchidos, e todos os nós no último nível estão o mais à esquerda possível. Isso garante que não haja “lacunas” entre os nós do último nível.
Passo 4
Agora, vamos verificar se toda árvore cheia é necessariamente completa. Para isso, vamos tentar encontrar um contraexemplo, ou seja, uma árvore que seja cheia, mas não seja completa.
Passo 5
Imagine a seguinte árvore cheia:
A
/ \
B C
/ \
D E
Essa árvore é cheia porque cada nó tem 0 ou 2 filhos. Porém, o nó C não tem filhos, enquanto os nós D e E estão no nível abaixo. Agora, se adicionarmos outro nível onde C tem dois filhos, a árvore continua cheia e completa. Mas se omitirmos os filhos de C, a árvore deixa de ser completa porque o último nível não está completamente preenchido à esquerda.
Passo 6
Portanto, esse exemplo mostra que é possível ter uma árvore cheia que não é completa, já que há uma “lacuna” no último nível.
Resposta
A afirmação “Toda árvore cheia é completa” é falsa. Existe uma árvore cheia que não é completa, conforme o contraexemplo apresentado.
Exercícios relacionados
Detalhar o algoritmo de remoção de nós em árvores AVL.
Qual o melhor e o pior caso de altura de uma árvore binária de busca e uma árvore AVL para um mesmo número
de elementos?
Prove ou dê um contraexemplo para as afirmações abaixo:
© Toda árvore estritamente binária é AVL.
© Toda árvore estritamente binária é AVL.
Desenhe a árvore AVL formada pela inserção dos números de 1 a 12 em ordem crescente.