Qual o número máximo de folhas em uma arvore estritamente binária com altura h? Justifique sua resposta.
Passo 1
O enunciado pede o máximo de folhas que uma árvore estritamente binária pode ter, em função da sua altura
. Aqui “árvore estritamente binária” significa que todo nó interno tem exatamente dois filhos, e a altura
é o número máximo de arestas num caminho da raiz até alguma folha. Vamos usar raciocínio por indução (ou o fato de que cada nível duplica o número de nós) para obter o resultado.
Passo 2
Para
a árvore consiste apenas da raiz, que é também folha. Logo o número máximo de folhas é
o que confere com as possibilidades de uma árvore sem arestas.
Passo 3
Suponha que em toda árvore estritamente binária de altura
o máximo de folhas seja
. Considere agora uma árvore de altura
. A raiz tem dois subárvores, cada uma de altura no máximo
. Pelo passo de indução, cada subárvore pode ter no máximo
folhas, e como são disjuntas, o total de folhas é
Resposta
O número máximo de folhas em uma árvore estritamente binária de altura
é