samedi 30 juillet 2016

Finding size of perfect quad tree

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?

Aucun commentaire:

Enregistrer un commentaire