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

Question

我正在尝试实现一个通用的n维树，它将保存n维数据。对于n维数据，我指的是在我的例子中有6-7坐标的数据点。以下是Tree (一种复合数据类型)和Tree类：

#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的原因。如果我们在超立方体中只有一个数据点，那么我们停止，我们有一个叶节点。如果我们有多个，我们会进一步分裂。只有在超立方体的坐标所定义的边界内，数据点才会被放置在超立方体中。

例如，假设您有一个二维坐标平面(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树.

编辑:我想我应该发布我当前的拆分函数：

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+tree，R*树，X树)对于范围查询和最近邻查询都很好.但是，原始的R-树对于以后修改、添加/删除数据非常不利。

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

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

更多的细节可以找到这里和这里。缺点是当前的开放源码版本仅在Java中(不是python)，而且非常复杂。我有一个大大改进的版本(简单得多的代码)，但我可能需要一段时间才能发布它。

Answer 2

下面是我为在超级立方体空间中运行cppn查询而开发的类似实现。在回顾四叉树的算法时，我还注意到细分应该是yeild 2^n坐标，并且利用这个坐标是由维长之和的置换来表示的，并且(+或-)值/2。由于它的值随着我们的变化而变化只能处于两种状态，所以我在这里找到了一个非常优雅的解决方案来查找二进制字符串的排列：https://codereview.stackexchange.com/questions/24690/print-all-binary-strings-of-length-n使用这个循环可以创建一个新的点，并使用该索引处的位串置换来确定该维值和中的第二个数字的符号(1 =正和0=负值)。

下面我首先介绍了java实现，因为我认为它的可读性更强，位字符串排列更优雅，下面是python实现，但不使用int->位字符串来生成排列。这两种方法都会将任意维数n分解为2^n个子树。

public class FractalTree {
    public double[] coord;
    public double width;
    public double weight;
    public double lvl;
    public String[] signs;
    public FractalTree[] children;
    public FractalTree(double[] c, double width, int lvl) {
        this.coord = c;
        this.width = width;
        this.lvl = lvl;
        this.children = new FractalTree[(int)Math.pow(2.0, (double)c.length)];
        this.permute_signs(this.coord.length);
    }
    public void subdivide_into_children() {
        for(int idx = 0; idx < this.children.length; idx++) {
            String sign_pattern = this.signs[idx];
            double[]  new_coord = new double[this.coord.length];
            for(int idx_2 = 0; idx_2 < this.coord.length; idx_2++) {
                char sign = sign_pattern.charAt(idx_2);
                if(sign == '1') {
                    new_coord[idx_2] = coord[idx_2] + this.width/2.0;
                } else {
                    new_coord[idx_2] = coord[idx_2] - this.width/2.0;
                }
            }
        }
    }

    public void permute_signs(int coord_len) {
        String str_len = "%" + Integer.toString(coord_len) + "s";
        for(long ix = 0; ix < this.children.length; ix++) {
            this.signs[(int)ix] = String.format(str_len, Long.toBinaryString(ix)).replace(' ', '0');
        }
    }

}

class nDimensionTree:

    def __init__(self, in_coord, width, level):
        self.w = 0.0
        self.coord = in_coord
        self.width = width
        self.lvl = level
        self.num_children = 2**len(self.coord)
        self.cs = [None] * self.num_children
        self.signs = self.set_signs()
        print(self.signs)
    def set_signs(self):
        return list(itertools.product([1,-1], repeat=len(self.coord)))

    def divide_childrens(self):
        for x in range(self.num_children):
            new_coord = []
            for y in range(len(self.coord)):
                new_coord.append(self.coord[y] + (self.width/(2*self.signs[x])))
            newby = nDimensionTree(new_coord, self.width/2, self.lvl+1)
        self.cs.append(newby)