Finden der Größe des perfekten Quad-Baums

Question

Ich muss die Größe eines perfekten Quad-Baums finden. Dies bedeutet, dass ich 1 Wurzelknoten habe, der sich in 4 Knoten aufteilt, der sich in 4 Knoten usw. aufteilt.

Ein Quad-Baum der Höhe 1 wäre also Größe 1 Höhe 2= Größe 5 (1 + 4) Höhe 3= Größe 21 (1 + 4 + 16) Höhe 4= Größe 85 (1 + 4 + 16 + 64)

etc ..

Ich weiß, dass die Größe eines perfekten Binärbaums gefunden werden kann mit: size= 2 ^ (height + 1) -1 Daher glaube ich, dass eine ähnliche Gleichung für den Quad-Baum existiert.

Also was ist das?

Answer 1

Dies ist eine geometrische Serie .Die relevante Formel lautet also:

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

wobei a der erste Wert ist, r das gemeinsame Verhältnis ist, n die Anzahl der Begriffe ist und ^ "nach der Potenz von" bezeichnet.

Answer 2

Für einen Quad-Baum lautet der Algorithmus

((4^depth)-1)/3

Zum Beispiel mit Tiefe 3 erhalten Sie

(64-1)/3 = 21

und wenn Sie drei Ebenen zählen, erhalten Sie

1 + 4 + 16 = 21

In meiner Implementierung habe ich es sogar in zwei Arrays aufgeteilt Dabei beträgt die Größe für alle Knoten, die keine Knoten verlassen,

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

und Knoten verlassen ist

4^(depth-1)

Ich führe diese Berechnungen zur Kompilierungszeit mit Metaprogrammierung für pow und einem Vorlagenargument für die Tiefe durch.Also ordne ich meine Knoten einfach in zwei Arrays zu.

Answer 3

Nur für den Fall, dass jemand ein Codebeispiel (in swift3) benötigt

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
}