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

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(self.node.data) 是否不等于 1 的原因。如果我们只包含 1 个数据点超立方体，然后我们停下来，我们有一个叶节点。如果我们有多个，我们会进一步 split 。仅当数据点位于超立方体坐标定义的边界内时，才会将其放置在超立方体中。

例如，假设您有一个 2D 坐标平面 [(0,1),(0,1)] - 我们的根节点。我们想要用数据点 [(0.5, 0.1),(0.2,0.3)] 填充它。由于我们有两个数据点，因此我们将平面分割为 2^n 个新的超立方体(在本例中为正方形)，其中 n 是维数 - 在本例中为 2。从 1x1 的根平方我们得到 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 树。

编辑:我想我应该发布我当前的split函数:

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 树非常简单并且适合插入/删除。 R 树(R+树、R*树、X 树)非常适合范围查询和最近邻居查询。然而，原始的 R-Tree 对于稍后修改添加/删除数据来说非常糟糕。

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

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

更多详细信息请参见 here和here 。缺点是当前的open-source version仅在 Java 中(不是 Python)并且相当复杂。我正在开发一个相当改进的版本(更简单的代码)，但可能需要一段时间才能发布它。