la taille de l'arbre Trouver quad parfait

Question

Je dois trouver la taille d'un arbre quad parfait. Cela signifie que j'ai 1 nœud racine qui se divise en 4 nœuds qui se divise en quatre noeuds etc.

un arbre quad de taille 1 serait la taille 1 hauteur 2 = taille 5 (1 + 4) hauteur 3 = Taille 21 (1 + 4 + 16) hauteur = 4 taille 85 (1 + 4 + 16 + 64)

etc ..

Je sais que la taille d'un arbre binaire parfait peut être trouvé avec: size = 2 ^ (hauteur + 1) -1 Je crois donc qu'une équation similaire existe pour arbre quad.

Alors, quel est-il?

Answer 1

Ceci est un . Ainsi, la formule pertinente est:

S = a * (1 - r^n) / (1 - r)

où a est la première valeur, r est le rapport commun, n est le nombre de termes, et ^ « désigne à la mise sous tension de ».

Answer 2

Pour un arbre quad l'algorithme est

((4^depth)-1)/3

Par exemple avec la profondeur 3 vous obtenez

(64-1)/3 = 21

et si vous comptez trois couches que vous obtenez

1 + 4 + 16 = 21

Dans ma mise en œuvre, je l'ai même divisé en deux tableaux où la taille pour tous les nœuds qui ne coûtent pas les noeuds de congé est

((4^(depth-1))-1)/3

et le congé noeuds est

4^(depth-1)

Je fais ces calculs au moment de la compilation avec la programmation méta pour pow, et un argument de modèle pour la profondeur. Donc, je viens répartisse mes noeuds dans deux tableaux.

Answer 3

Juste au cas où quelqu'un aura besoin d'un exemple de code (en swift3)

public func tileCount(forLevelRange levelRange: Range<UInt>) -> UInt64 {

   var tileCount: UInt64 = 0
   for level in levelRange.lowerBound ..< levelRange.upperBound {
       tileCount += UInt64(pow(Double(1 << level), 2) )
   }

   return tileCount
}