¿Cuáles son los números mínimos y máximos de elementos en un montón de altura H?

Question

Me encontré con la pregunta:

¿Cuáles son los números mínimos y máximos de elementos en un montón de altura $ H $ ?

a la que me fui con esta teoría: $$ \ sum_ {i= 0} ^ {h-1} 2 ^ i= 2 ^ h-1 $$

$ 2 ^ h-1 $ son los nodos internos y que se entiende de acuerdo con el hecho comprendido. Pero debido a que en ninguna parte, excepto CLRS, menciona un montón de ser un árbol binario en todas partes, se menciona como un árbol binario completo.

El número máximo de elementos se puede calcular fácilmente: $$ \ sum_ {i= 0} ^ {h} 2 ^ i= 2 ^ {H + 1} -1 $$

Pero no puedo obtener el punto de calcular el número mínimo de elementos: Deberia ser: $$ 2 ^ {H} +1 $$ para $ 0 $ o $ 2 $ propiedad de niños

o debería ser: $$ 2 ^ {h} $$ para $ 0 $ o $ 1 $ propiedad de los niños

Referencia1: https://walkccc.github.io/clrs/ Chap06 / 6.1 / # 61-1

Referencia2: HEOPSORT

gracias.

Answer 1

Un montón de altura $ H $ se completa con el nivel en profundidad $ h-1 $ y necesita tener al menos un nodo en el nivel $ H $ .

Por lo tanto, el número total mínimo de nodos debe ser al menos $ \ sum_ {i= 0} ^ {h-1} 2 ^ i + 1= 2 ^ {H} -1 + 1= 2 ^ h. $ , y esta apretada desde un montón con $ 2 ^ h $ nodos tiene altura $ h $ .