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实现为单一维数组？

- user1855952

---

由于KDTrees是二叉树，请参考以下链接：http://en.wikipedia.org/wiki/Binary_tree#Arrays - Eugen Constantin Dinca

你可以创建一个std::vector<KDNode> nodes; 然后使用nth_element来查找中位数等。左右指针可以直接指向向量中的子节点（如果数据集是静态的，你不希望向量调整大小）。无需自己分配任何内存。 - gvd

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。

- Justin

Answer 2

在一定的代价下，您可以使用空间填充曲线来减少维度。使用quadkey搜索最近邻。

- Micromega