Encontrar el tamaño de un árbol cuádruple perfecto

Question

Necesito encontrar el tamaño de un árbol cuádruple perfecto. Esto significa que tengo 1 nodo raíz que se divide en 4 nodos que se divide en 4 nodos, etc.

por lo que un árbol cuádruple de altura 1 sería de tamaño 1 altura 2= talla 5 (1 + 4) altura 3= talla 21 (1 + 4 + 16) altura 4= talla 85 (1 + 4 + 16 + 64)

etc.

Sé que el tamaño de un árbol binario perfecto se puede encontrar con: size= 2 ^ (altura + 1) -1 Así que creo que existe una ecuación similar para el árbol cuádruple.

Entonces, ¿qué es?

Answer 1

Esta es una serie geométrica .Entonces, la fórmula relevante es:

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

donde a es el primer valor, r es la proporción común, n es el número de términos y ^ denota "a-la-potencia-de".

Answer 2

Para un árbol cuádruple, el algoritmo es

((4^depth)-1)/3

Por ejemplo, con la profundidad 3 obtienes

(64-1)/3 = 21

y si cuentas tres capas obtienes

1 + 4 + 16 = 21

En mi implementación, incluso lo he dividido en dos matrices donde el tamaño de todos los nodos que no salen de los nodos es

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

y dejar nodos es

4^(depth-1)

Hago estos cálculos en tiempo de compilación con metaprogramación para pow y un argumento de plantilla para la profundidad.Así que solo asigno mis nodos en dos matrices.

Answer 3

En caso de que alguien necesite una muestra de código (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
}