Encontrando o tamanho da árvore quádrupla perfeita

Question

Preciso encontrar o tamanho de uma árvore quádrupla perfeita. Isso significa que tenho 1 nó raiz que se divide em 4 nós que se divide em 4 nós, etc.

então, uma árvore quádrupla de altura 1 teria tamanho 1 altura 2= tamanho 5 (1 + 4) altura 3= tamanho 21 (1 + 4 + 16) altura 4= tamanho 85 (1 + 4 + 16 + 64)

etc ..

Eu sei que o tamanho de uma árvore binária perfeita pode ser encontrado com: size= 2 ^ (height + 1) -1 Portanto, acredito que exista uma equação semelhante para árvore quádrupla.

Então, o que é?

Answer 1

Esta é uma série geométrica .Portanto, a fórmula relevante é:

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

onde a é o primeiro valor, r é a proporção comum, n é o número de termos e ^ denota "até o poder de".

Answer 2

Para uma árvore quádrupla, o algoritmo é

((4^depth)-1)/3

Por exemplo, com profundidade 3 você obtém

(64-1)/3 = 21

e se você contar três camadas, obterá

1 + 4 + 16 = 21

Na minha implementação, até o dividi em dois arrays onde o tamanho de todos os nós que não deixam nós é

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

e deixar nós é

4^(depth-1)

Eu faço esses cálculos em tempo de compilação com metaprogramação para pow e um argumento de modelo para a profundidade.Então, eu apenas aloco meus nós em dois arrays.

Answer 3

Caso alguém precise de uma amostra de código (em 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
}