Finding size of perfect quad tree

Question

I need to find the size of a perfect quad tree. This means I have 1 root node that splits into 4 nodes that splits into 4 nodes etc.

so a quad tree of height 1 would be size 1 height 2 = size 5 (1 + 4) height 3 = size 21 (1 + 4 + 16) height 4 = size 85 (1 + 4 + 16 + 64)

etc..

I know that the size of a perfect binary tree can be found with: size = 2^(height+1)-1 So I believe that a similar equation exists for quad tree.

So what is it?

Answer 1

This is a geometric series. So the relevant formula is:

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

where a is the first value, r is the common ratio, n is the number of terms, and ^ denotes "to-the-power-of".

Answer 2

For a quad tree the algorithm is

((4^depth)-1)/3

For example with depth 3 you get

(64-1)/3 = 21

and if you count three layers you get

1 + 4 + 16 = 21

In my implementation I have even divided it into two arrays where the size for all nodes that arent leave nodes is

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

and leave nodes is

4^(depth-1)

I do these calculations at compile time with meta programming for pow, and a template argument for the depth. So i just allocate my nodes in two arrays.

Answer 3

Just in case anyone will need a code sample (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
}