KDTree实现为单个阵列/没有节点

Question

所以对于一个项目,我实现了一个平衡的KD树和k近邻搜索算法,它作为标准树的"传统"方式 - 即我有如下节点结构

struct KDNode{
    int level; //used for x,y,z axis splitting
    Point pos;
    KDNode *left, *right; //Child nodes
}

...然后将树存储在内存中作为实际的树数据结构.但是,我最近听说可以将KD-Tree作为大型数组存储在内存中而无需创建任何节点对象,并且这种构造方法在内存方面和时间性能方面更加高效.

但是,我完全不确定这样的结构是如何工作的,并且无法在网上找到任何关于如何以这种方式实现KD-Tree的详细信息.

所以我的问题是,如何在不使用节点的情况下将KD树实现为单维数组？

Answer 1

好吧,我可以看到它是如何在单个数组中实现的.但它需要一个相当密集且均衡的kd树.如果你的树是稀疏的,它可以用数组来实现,但是在空间方面会相当浪费.

您可以使用他们用于在数组中实现堆的相同技术.有一个公式可以使用项目当前索引查找项目的子项,更多信息在此处和此处.对于左孩子,公式是2*index + 1,对于右孩子,公式是2*index + 2.

这个"作为数组的堆"可以应用于任何二叉树数据结构,但它特别适用于堆,因为您知道该数组将被密集填充.

在节点中具有索引值的完整二叉树:

               [0]
      [1]                [2]
  [3]     [4]       [5]       [6]  
[7] [8] [9] [10] [11] [12] [13] [14]

数组中的相同表示:[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]

如果你在[4]并想找到它的孩子; 它的左孩子是(2*4 + 1)9,它的右孩子是(2*4 + 2)10.