c++ - 预测 kD 树中所需的预分配节点数

Question

我正在以广度优先的方式在数组表示中实现动态kD-Tree(将节点存储在 std::vector 中)。每个i -th 非叶节点在 (i<<1)+1 处有一个左子节点和一个合适的 child 在(i<<1)+2 .它将支持点的增量插入和点的集合。但是，我在确定增量预分配空间所需的可能节点数时遇到了问题。

我找到了 formula on the web ，这似乎是错误的:

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

where m is the smallest power of 2 greater than or equal to n, the number of points.

我对公式的实现如下:

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

函数 nextPowerOf2 返回最大或等于 n 的 2 的幂

如有任何帮助，我们将不胜感激。

Answer 1

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

1)如果你在空间的中点划分它们(也就是说，如果空间是从x1到x2，你用x3=(x1+x2)/2线划分空间)，那么:i) 每个点将被分配到它自己的节点，并且ii) 每个中间节点都是空的。

在这种情况下，节点的数量将取决于点的坐标有多大。如果坐标以 |X| 为界，则 kd-tree 中的节点总数应略小于 log |X| * n(更准确地说，大约 log |X| * n - n log n + 2n)在最坏的情况下。要看到这一点，请考虑以下添加点的方式:添加多个集合，每个集合有两个随机分布的非常接近的点。对于每一对点，树将需要连续划分空间日志 |X|次，如果记录 |X|明显大于 log n，创建 log |X|过程中的中间节点。

2) 如果用一个点作为分界线来划分它们，那么每个节点(包括中间节点)都会包含一个点。因此，节点总数就是 n。但是，请注意，如果点不是以随机顺序给出(例如，如果点按 X 的升序给出，则树的深度将为O(n)。为了比较，(1)中树的深度至多为O(log |X|))。