如果我有 N 个节点，如何找到八叉树中的级别数？

Question

如果八叉树级别为0，那么我有8个节点。现在，如果八叉树级别为 1，那么我有 72 个节点。但是，如果我有（例如）500 个节点，我该如何计算级别？

Answer 1

要计算级别 n 的最大节点数，您需要计算：

8**1 + 8**2 + 8**3 ... 8**n

所以在第 2 级，那是 8 + 64

这可以归纳为：

((8 ** (h + 1)) - 1)/7 - 1

在javascript中你可以这样写：

function maxNodes(h){
  return ((8 ** (h + 1)) - 1)/7 - 1
}

for (let i = 1; i < 4; i++){
  console.log(maxNodes(i))
}

要求逆，您需要使用 Log base 8 和一些代数，您将得出一个公式：

floor (log(base-8)(7 * n + 1))

在某些语言中，例如 python，您可以计算 math.floor(math.log(7*n + 1, 8))，但 javascript 没有任意基数的日志，因此您需要依赖身份：

Log(base-b)(n) == Log(n)/Log(b)

并计算如下：

function height(n){
    return Math.floor(Math.log(7 * n + 1)/Math.log(8))
}

console.log(height(8))
console.log(height(72))  // last on level 2
console.log(height(73))  // first on level 3
console.log(height(584)) // last on level 3
console.log(height(585)) // first on level 4

如果我有 N 个节点，如何找到八叉树中的级别数？

How do I find the amount of levels in an Octree if I have N nodes?

algebra

octree