Trovare le dimensioni di un albero quadruplo perfetto

Question

Devo trovare le dimensioni di un albero quadruplo perfetto. Ciò significa che ho 1 nodo radice che si divide in 4 nodi che si divide in 4 nodi ecc.

quindi un albero quadruplo di altezza 1 sarebbe di taglia 1 altezza 2= taglia 5 (1 + 4) altezza 3= taglia 21 (1 + 4 + 16) altezza 4= taglia 85 (1 + 4 + 16 + 64)

ecc ..

So che la dimensione di un albero binario perfetto può essere trovata con: size= 2 ^ (altezza + 1) -1 Quindi credo che esista un'equazione simile per il quad tree.

Allora che cos'è?

Answer 1

Questa è una serie geometrica .Quindi la formula pertinente è:

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

dove a è il primo valore, r è il rapporto comune, n è il numero di termini e ^ indica "to-the-power-of".

Answer 2

Per un albero quadruplo l'algoritmo è

((4^depth)-1)/3

Ad esempio con la profondità 3 si ottiene

(64-1)/3 = 21

e se conti tre livelli ottieni

1 + 4 + 16 = 21

Nella mia implementazione l'ho persino diviso in due array dove la dimensione per tutti i nodi che non sono nodi lasciati è

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

e lasciare i nodi è

4^(depth-1)

Faccio questi calcoli in fase di compilazione con la meta programmazione per pow e un argomento template per la profondità.Quindi alloco semplicemente i miei nodi in due array.

Answer 3

Nel caso qualcuno avesse bisogno di un esempio di codice (in 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
}