arrays - KDTree 实现为单个数组/无节点

Question

因此，对于一个项目，我已经为它实现了一个平衡的 KD-Tree 和 k-最近邻搜索算法，作为标准树的“传统”方式 - 即我有如下节点结构

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

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

但是，我完全不确定这样的构造将如何工作，也无法在网上找到任何详细说明我将如何以这种方式实现 KD-Tree 的内容。

所以我的问题是，如何在不使用节点的情况下将 KD-Tree 实现为一维数组？

score 5 · Accepted Answer

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

您可以使用他们用来在数组中实现堆的相同技术。有一个公式可以使用项目当前索引查找项目的子项，更多信息在这里和这里。左孩子的公式是 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。

score 1 · Accepted Answer

您可以通过空间填充曲线来减少尺寸，但需要付出一些代价。使用四键搜索最近邻。

2 回答 2