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:
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:
Passo 3
Aplicando a fórmula da soma de série geométrica, temos:
Passo 4
Agora isolamos h. Primeiro somamos 1 em ambos os lados:
Em seguida, aplicamos logaritmo na base 2:
Finalmente, resolvemos para h: