Encontre a altura de uma árvore ternária

Question

heap ternário é como uma árvore binária, apenas cada nó pode ter até $ 3 $ filhos e não $ 2 $ < / span>.

Eu tento vincular o número de nós no heap, $ n $ , usando a altura da heap $ h $ .

As soluções chega a:

$$ 3 ^ h

No entanto, eu chego:

$$ \ frac {3 ^ h} {2}

Em suma, o que eu faço é:

$$ \ sum_ {i= 0} ^ {h - 1} 3 ^ i=frac {3 ^ h-1} {2} $$

Para todos os nós em todos os níveis, exceto pelo último nível, porque todos os níveis estão cheios.

Se o último nível estiver cheio:

$$ \ frac {3 ^ h - 1} {2} + 3 ^ h $$

Se o último nível tiver apenas $ 1 $ nó, obtemos:

$$ \ frac {3 ^ h - 1} {2} + 1 $$

A partir daqui eu concluo o que mostrei no começo.

Por que as soluções chegam a outra coisa?

Answer 1

A solução esperada está errada.

Escolha $ h= 0 $ .A única heap ternária com altura $ 0 $ tem apenas um nó.No entanto, a solução esperada diz que precisa ter pelo menos $ 3 ^ 0 + 1= 2 $ nós.

Caso você quisesse escrever $ 3 ^ h \ le n \ le 3 ^ {h + 1} $ em vez de $ 3 ^ h , a solução esperada ainda está errada. Considere um heap ternário com $ n= 2 $ nós.Este heap tem altura $ 1 $ mas de acordo com a solução esperada deve ter pelo menos $ 3 ^ h= 3 $ nós