寻找完美四叉树的尺寸

Question

我需要找到一个完美四叉树的尺寸。 这意味着我有分裂成该分成4个节点等

所以高度1的四叉树将是尺寸1的节点4 1个根节点 高度2 =尺寸5（1 + 4） 高度3 =尺寸21（1 + 4 + 16） 高度4 = 85的尺寸（1 + 4 + 16 + 64）

等。

我知道一个完美的二进制树的大小可以与发现： size = 2 ^（height + 1）-1 所以我认为四叉树存在类似的方程。

那是什么？

Answer 1

这是一个geometric series。因此相关公式为：

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

其中a是第一值，r是公比，n是项数，和^表示“到最幂”。

Answer 2

对于一个四叉树的算法是

((4^depth)-1)/3 

例如与深度3你

(64-1)/3 = 21 

，如果你算上三层你

1 + 4 + 16 = 21 

我在执行我甚至将它分成两个数组 其中所有节点的大小不是l屋檐节点是

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

离开节点是

4^(depth-1) 

我做这些计算在编译时使用的元编程战俘，以及深度模板参数。所以我只分配两个数组中的节点。

Answer 3

万一有人需要一个代码示例（在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 
}