Quels sont les nombres minimaux et maximaux d'éléments dans un tas de hauteur h?
-
29-09-2020 - |
Question
Je suis tombé sur la question suivante:
quels sont les nombres minimaux et maximaux d'éléments dans un tas de hauteur $ h $ ?
à qui je suis venu avec cette théorie: $$ \ sum_ {i= 0} ^ {h-1} 2 ^ i= 2 ^ h-1 $$
2 ^ h-1 $ est les nœuds internes et qui est compris en fonction du fait compris. Mais parce que nulle part, sauf CLRS mentionne les tas d'être un arbre binaire
Le nombre maximum d'éléments peut être facilement calculé: $$ \ sum_ {i= 0} ^ {h} 2 ^ i= 2 ^ {h + 1} -1 $$
Mais je ne peux pas avoir le point de calculer le nombre minimum d'éléments: Devrait-ce être: $$ 2 ^ {h} +1 $$ for $ 0 $ ou $ 2 $ propriété enfants
ou devrait-il être: $$ 2 ^ {h} $$ pour $ $ 0 $ ou $ 1 $ Propriété des enfants
Référence1: https://walkcccc.github.io/clrs/ CHAP06 / 6.1 / # 61-1
Référence2:
merci.
La solution
Un tas de hauteur $ h $ est terminé jusqu'au niveau à la profondeur $ H-1 $ et doit avoir au moins un nœud sur niveau $ h $ .
Par conséquent, le nombre total minimum de nœuds doit être au moins $ \ sum_ {i= 0} ^ ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ h. $ , et cela serré depuis un tas avec 2 ^ h $ nœuds a la hauteur $ h $ .