n-D树 - 计算超立方体的坐标

Question

我想实现一个通用的n维树，它将保存n维数据。对于n维数据，我是指具有6-7坐标的数据点。这里是树节点（复合数据类型）和树类：

#data = data points (i.e. [x,y,z,k,m,n]) 
#hypercube = set of tuples; coordinates [(x0,x1),(y0,y1)...] 
class _Node: 
    def __init__(self, data, hypercube): 
     self.data = data 
     self.hypercube = hypercube 

class _nTree: 
    def __init__(self, hypercube, depth = 0): 
     self.node = [] 
     self.children = [] 
     self.depth = depth 
     self.hypercube = hypercube 

    def __insert__(self, data): 
     if not self.node: 
      self.node = _Node(data, self.hypercube) 
      if (len(self.node.data) != 1): 
       self.__split__() 

对我来说，每一个孩子将包含被包含在其父节点中的数据 - 这就是后面检查，如果LEN的原因（自我.node.data）不等于1.如果我们只有一个数据点包含在超立方体中，那么我们停止并且有一个叶节点。如果我们有多个，我们会进一步分裂。只有当数据点位于由超立方体的坐标定义的边界内时，数据点才会放置在超立方体中。

例如，假设您有一个坐标为[（0,1），（0,1）]的二维平面 - 我们的根节点。我们想用数据点[（0.5,0.1），（0.2,0.3）]填充它。由于我们有两个数据点，因此我们将该平面划分为2^n个新的超立方体（在这种情况下为正方形），其中n是维数 - 在这种情况下为2。从1×1的根部平方得到4个较小的坐标[[（0,0.5），（0,0.5）]，[（0.5,1），（0.5,1）]，[（0.5,1）， 0,0.5）]，[（0,0.5），（0.5,1）] - 这基本上是根节点的孩子。这是一个可以在这里可视化的四叉树的例子：https://en.wikipedia.org/wiki/Quadtree

我想要做同样的事情，但有多个维度。现在

，我试图解释什么，我试图做的，我的问题是：

超立方体变量包含当前节点的坐标。我怎样才能实现我的拆分功能，它会正确地生成坐标？例如，如果我有6个维度，则必须为每个节点生成64个坐标（2^n; n =维度数）。作为一个头，它不是一棵K-D树。

编辑：我想我应该张贴我目前的分裂功能：

def __split__(self): 
    n_of_children = 2**(len(self.node.hypercube[0])) 
    vector = self.__get_vector__() #returns the coordinates of all 64 hypercubes/trees 
    self.children = [_nTree(vector, self.depth+1) for i in range(n_of_children)[ 
    self.__insert_children__(self.data) 

我宣布每一个孩子作为一个树状结构，然后我打电话insert_children决定进入哪个孩子每个数据点进入。如果一个孩子有一个以上的数据点，我们重复整个分裂和插入的过程。

Answer 1

我曾经写过Java中的K维四叉树，这里是代码：

NodeKD(double[] min, double[] max, int maxDepth, NodeKD parent) { 
    this.min = min; 
    this.max = max; 
    this.center = new double[min.length]; 
    for (int i = 0; i < min.length; i++) { 
     this.center[i] = (max[i]+min[i])/2; 
    } 
    this.maxDepth = maxDepth == -1 ? 4 : maxDepth; 
    this.children = new ArrayList<>(); 
    qA = new NodeKD[1 << min.length]; 
    this.parent = parent; 
} 

private void subdivide() { 
    int dim = min.length; 
    double[] min = new double[dim]; 
    double[] max = new double[dim]; 
    for (int i = 0; i < qA.length; i++) { 
     long mask = 1L; 
     for (int j = 0; j < dim; j++) { 
      if ((j & mask) == 0) { 
       min[j] = this.min[j]; 
       max[j] = this.center[j]; 
      } else { 
       min[j] = this.center[j]; 
       max[j] = this.max[j]; 
      } 
      mask <<= 1; 
     } 
     qA[i] = new NodeKD(min, max, maxDepth-1, this); 
    } 
} 

然而，据我所知，四叉树（2D）和八叉树（3D）是不是很有效更高的尺寸。取决于你想做什么（范围查询，最近邻居查询，简单的查找，大量的插入......），我会选择一个不同的结构。 KD-Trees非常简单，可以插入/删除。 R-Trees（R +树，R *树，X-tree）对于范围查询和最近邻居查询非常有用。然而，原来的R-Tree对于稍后修改添加/删除数据是相当不利的。

我个人最喜欢的是我自己的PH-Tree。它类似于一个k维四叉树，但有一些区别：

• 它实质上是一个'trie'，或者是critbit树。这意味着只要一个值为'0'而另一个值为'1'，它就会查看分割值的位表示。由于我在比特级上进行操作，因此节点内的导航和寻址非常有效，因为我可以简单地使用k比特字符串（对于k维）来遍历本地孩子，并检查它们对查询的适用性。这避免了具有高维度的可伸缩性带来的许多问题。
• 它使用前缀共享来减少内存要求（每个节点仅存储本地值彼此不同的位）。
• 由于静态性质（根据比特分割），不会有任何修改影响两个以上的节点，因此永远不会需要重新平衡。
• 虽然没有重新平衡，但树的深度限制为64（假设为64位值），因此它不会严重退化。

一些更多的细节可以发现here和here。缺点是当前的open-source version仅在Java（不是python）中，而且非常复杂。我有一个相当大的改进版本（更简单的代码），但可能需要一段时间才能发布。