预测在kD树中需要预分配的节点数量。

Question

我正在实现一个动态的 数组表示的 kD-树（将节点存储在 std::vector 中），以广度优先的方式进行。每个非叶节点的左子节点为 (i<<1)+1，右子节点为 (i<<1)+2。它将支持点的增量插入和点的收集。 然而，我面临着确定递增地预分配空间所需的可能节点数量的问题。

我在网上找到了一个 公式，但似乎是错误的:

N = min(m − 1, 2n − ½m − 1),

其中 m 是大于或等于点数 n 的最小的 2 的幂。

我的公式实现如下:

size_t required(size_t n)
{
    size_t m = nextPowerOf2(n);
    return min(m - 1, (n<<1) - (m>>1) - 1);
}

函数nextPowerOf2返回一个大于或等于n的2的幂次方

任何帮助将不胜感激。

- plasmacel

---

你应该首先尝试与博客作者分享你的想法。 - Lior Kogan

你尝试过用少量的点来查看错误吗？错误是什么，是没有预先分配足够的对象吗？您介意提供实际值吗？例如：我尝试了X个点...计算出的m值为Y，并且required返回值为Z...但最终我需要W个节点。 - wendelbsilva

由于问题涉及所需节点数量，是的，错误就在于没有足够的预分配节点，这导致了段错误。我使用实际值测试了算法，它是有效的，但是存储空间不足。 - plasmacel

Answer 1

每个kd树节点将空间分成两个空间。因此，kd树中的节点数取决于如何执行此划分：

1）如果在空间的中点处进行划分（即，如果空间从x1到x2，则使用x3 =（x1 + x2）/ 2线划分空间），则： i）每个点将被分配其自己的节点，并且 ii）每个中间节点将为空。

在这种情况下，节点数将取决于点的坐标有多大。如果坐标受|X|限制，则kd树中的总节点数应该略小于log |X| * n（更准确地说，在最坏的情况下约为log |X| * n-n log n + 2n）。要了解这一点，请考虑以下添加点的方法：您添加多个集合，每个集合都有两个极端相邻的点随机放置。对于每对点，树将需要连续将空间划分log |X|次，如果log |X|显着大于log n，则在此过程中创建log |X|个中间节点。

2）如果您使用点作为分割线进行划分，则每个节点（包括中间节点）都将包含一个点。因此，节点的总数就是n。但是，请注意，如果点没有按随机顺序给出（例如，如果点按X的升序给出），则使用点来划分空间可能会导致非常糟糕的性能。（与之相比，在（1）中树的深度最多为O（log |X|）。）

- Irvan

---

在您的情况2中，您假设kd树通过轮流使用轴交替规则来划分点集，这可能会导致效率低下，正如您所述。然而，这种行为只是交替规则的影响，而不是“使用一个点作为分割线来划分它们”的技术。我使用最长边切割规则（通过它们轴对齐边界框的最大维度来划分点集）进行划分，这种方法不受此行为的影响。 - plasmacel

此外，实际节点数确实等于点数。但请注意，kD-Tree以广度优先的方式在数组中表示。每个第i个节点在(i<<1)+1处有一个左子节点，在(i<<1)+2处有一个右子节点。因此，节点不需要显式存储其左/右子节点。这种表示方法对缓存非常友好，不像链表表示法。在这种特殊情况下，您需要预先分配比实际需要更多的空间，因为理论上每个节点都可能在i+1和i+2处有一个左和/或右子节点，这是无法预测的。 - plasmacel

@plasmacel 是的，我忘了这点。在这种情况下，你很可能无法使用方案1，因为所需的内存现在将是O（|X|）。顺便说一下，如果你使用最长边规则，我假设你是通过它们的中点划分空间的？在这种情况下，我对方案1所说的内容仍然适用。如果你仍然使用方案2（使用一个点来划分它们最长的轴线上的空间），那么方案2中的点仍然有效，即如果在最坏情况下插入这些点，则树的深度为O（N），需要2^N的内存。 - Irvan