Obtenha a equação que relaciona a altura de uma árvore binária completa com o seu número de vértices.

Passo 1

A questão pede para relacionar a altura de uma árvore binária completa com o número de vértices. Isso cai em Estruturas de Dados/Teoria dos Grafos, e vamos usar a definição de árvore binária completa e a soma de uma série geométrica para resolver.

Passo 2

Numa árvore binária completa, cada nível i (começando em 0 na raiz) tem exatamente 2^i vértices. Se a altura da árvore é h, existem níveis de 0 até h.
O número total de vértices N é a soma dos vértices de todos os níveis. Usamos a soma de série geométrica:
N = sumi=0^h 2^i

Passo 3

Aplicando a fórmula da soma de série geométrica, temos:
N = 2^h+1 - 1

Passo 4

Agora isolamos h. Primeiro somamos 1 em ambos os lados:
N + 1 = 2^h+1
Em seguida, aplicamos logaritmo na base 2:
log2(N + 1) = h + 1
Finalmente, resolvemos para h:
h = log2(N + 1) - 1

Resposta

h = log2(N + 1) - 1

Exercícios relacionados