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

发布时间：2020-12-16 07:12:59 所属栏目：百科来源：网络整理

导读：我正在以广度优先的方式实现数组表示中的动态kD-Tree(以std :: vector存储节点).每个第i个非叶节点在(i 1)1处具有左子节点并且在(i 1)2处具有右子节点.它将支持点的增量插入和点的集合. 但是,我正面临着确定增量预分配空间所需的可能节点数的问题. 我发现了

我正在以广度优先的方式实现数组表示中的动态kD-Tree(以std :: vector存储节点).每个第i个非叶节点在(i <1)1处具有左子节点并且在(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);
}

function nextPowerOf2返回2的最大值或等于n的幂

任何帮助,将不胜感激.

解决方法

kd树的每个节点将空间划分为两个空格.因此,kd树中的节点数取决于您执行此划分的方式：

1)如果你在空间的中点划分它们(也就是说,如果空间是从x1到x2,你用x3 =(x1 x2)/ 2行划分空间),然后：
i)每个点都将分配自己的节点,和
ii)每个中间节点都是空的.

在这种情况下,节点的数量将取决于点的坐标有多大.如果坐标以| X |为界,则kd-tree中的节点总数应略小于log | X |.在最坏的情况下,* n(更确切地说,在log | X | * n – n log n 2n附近).要看到这一点,请考虑以下添加点的方法：添加多个集合,每个集合有两个非常接近的点.对于每对点,树将需要连续划分空间log | X |次,如果是log | X |显着大于log n,创建log | X |过程中的中间节点.

2)如果使用点作为分界线来划分它们,则每个节点(包括中间节点)将包含一个点.因此,节点的总数简单地为n.但是,请注意,如果不以随机顺序给出点,则使用点来划分空间可能会产生非常糟糕的性能(例如,如果点以X的升序给出,则树的深度会为O(n).为了比较,(1)中树的深度最多为O(log | X |)).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!