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

Question

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

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

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

但是，我完全不确定这样的构造将如何工作，并且无法在网上找到任何详细说明我将如何以这种方式实现 KD 树的详细信息。

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

Answer 1

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

您可以使用他们用于在数组中实现堆的相同技术。有一个公式可以使用项目当前索引查找项目的子项，更多信息 here和 here .左 child 公式为2*index+1，右 child 公式为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] 并且想找到它的 child ；它的左 child 是 (2*4+1) 9，它的右 child 是 (2*4+2) 10。