Finding the perfect ATV size

Question

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

so a square tree of height 1 will 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 an ideal binary tree can be found with: size = 2 ^ (height + 1) -1 Therefore, I believe that a similar equation exists for a quad tree.

So what is it?

Answer 1

This is a geometric series . The corresponding formula:

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

where a is the first value, r is the general relation, n is the number of members, and ^ means "to-the-power-of".

Answer 2

For quad tree algorithm

 ((4^depth)-1)/3 

For example, with a depth of 3 you get

 (64-1)/3 = 21 

and if you count three layers, you will get

 1 + 4 + 16 = 21 

In my implementation, I even divided it into two arrays where the size for all nodes left without attacks is

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

and leave the nodes

 4^(depth-1) 

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

Answer 3

Just in case, someone 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 }